Incompatibility of efficiency and strategyproofness in the random assignment setting with indifferences
From MaRDI portal
Publication:1786741
Abstract: A fundamental resource allocation setting is the random assignment problem in which agents express preferences over objects that are then randomly allocated to the agents. In 2001, Bogomolnaia and Moulin presented the probabilistic serial (PS) mechanism that is an anonymous, neutral, Pareto optimal, and weak strategyproof mechanism when the preferences are considered with respect to stochastic dominance. The result holds when agents have strict preferences over individual objects. It has been an open problem whether there exists a mechanism that satisfies the same properties when agents may have indifference among the objects. We show that for this more general domain, there exists no extension of PS that is ex post efficient and weak strategyproof. The result is surprising because it does not even require additional symmetry or fairness conditions such as anonymity, neutrality, or equal treatment of equals. Our result further demonstrates that the lack of weak SD-strategyproofness of the extended PS mechanism of Katta and Sethuraman (2006) is not a design flaw of extended PS but is due to an inherent incompatibility of efficiency and strategyproofness of PS in the full preference domain.
Recommendations
Cites work
- A new solution to the random assignment problem.
- A solution to the random assignment problem on the full preference domain
- Algorithms and Computation
- Assignment Problem Based on Ordinal Preferences
- Fair division under ordinal preferences: computing envy-free allocations of indivisible goods
- Fairness and efficiency in strategy-proof object allocation mechanisms
- House allocation with existing tenants
- Incentive properties for ordinal mechanisms
- Queue allocation of indivisible goods
- Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
- Straightforwardness of Game Forms with Lotteries as Outcomes
- Strategy-proof allocation of indivisible goods
- The impossibility of extending random dictatorship to weak preferences
Cited in
(10)- Random assignments with uniform preferences: an impossibility result
- Inefficiency of the Nash equilibrium for selfish machine covering on two hierarchical uniform machines
- An incompatibility between recursive unanimity and strategy-proofness in two-sided matching problems
- Why do popular mechanisms lack efficiency in random environments?
- A solution to the random assignment problem on the full preference domain
- The incompatibility of Pareto optimality and dominant-strategy incentive compatibility in sufficiently-anonymous budget-constrained quasilinear settings
- A new impossibility result for random assignments
- Partial strategyproofness: relaxing strategyproofness for the random assignment problem
- Extended random assignment mechanisms on a family of good sets
- The impossibility of strategy-proof, Pareto efficient, and individually rational rules for fractional matching
This page was built for publication: Incompatibility of efficiency and strategyproofness in the random assignment setting with indifferences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1786741)
