Title: Partial Strategyproofness: An Axiomatic Approach to Relaxing Strategyproofness for Random Assignment Mechanisms
Abstract: In this paper, we present a new relaxed notion of strategyproofness to study the incentive properties of non-strategyproof random assignment mechanisms. To this end, we first show that fully strategyproof mechanisms are characterized by three intuitive axioms: swap monotonicity, upper invariance, and lower invariance. By dropping the lower invariance axiom, we obtain an interesting new relaxation of strategyproofness, which we call partial strategyproofness. We then show that this new concept is useful in a number of ways: (1) It has an axiomatic motivation and yields an appealing economic intuition. (2) It relies on a maximal domain restriction, which induces a meaningful, parametric measure for the incentive properties of non-strategyproof mechanisms, and this measure is consistent with the comparison of mechanisms by their vulnerability to manipulation. (3) It allows an alternative definition via a dominance relation that is independent of cardinal utilities. This leads to algorithms for verifying partial strategyproofness and computation the degree of strategyproofness of any given mechanism. (4) It is an intermediate concept between full strategyproofness and other concepts, such as weak, convex, and approximate strategyproofness, as well as strategyproofness in the large, and it parametrizes the whole
space between fully strategyproof and lexicographic-strategyproof mechanisms. (5) It yields an interesting version of local sufficiency that unifies prior local sufficiency results. Finally, we demonstrate that our new partial strategyproofness concept enables us to compare the incentive properties of important non-strategyproof mechanisms such as the Probabilistic Serial mechanism, two variants of the Boston mechanism, and new hybrid mechanisms.