Incompatibility of efficiency and strategyproofness in the random assignment setting with indifferences

DOI10.1016/J.ECONLET.2017.08.010zbMATH Open1396.91320arXiv1604.07540OpenAlexW2964053380MaRDI QIDQ1786741FDOQ1786741

Authors: Haris Aziz, Pang Luo, Christine Rizkallah 

Publication date: 25 September 2018

Published in: Economics Letters (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1604.07540

Recommendations

• A solution to the random assignment problem on the full preference domain
• Strategy-proof and envy-free random assignment
• A new solution to the random assignment problem.
• An equilibrium analysis of the probabilistic serial mechanism
• Random assignment of multiple indivisible objects

zbMATH Keywords

stochastic dominancesocial choice theorystrategyproofnessprobabilistic serialrandom assignment problem

Mathematics Subject Classification ID

Social choice (91B14) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cites Work

• House allocation with existing tenants
• Strategy-proof allocation of indivisible goods
• Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
• A new solution to the random assignment problem.
• A solution to the random assignment problem on the full preference domain
• Queue allocation of indivisible goods
• Fairness and efficiency in strategy-proof object allocation mechanisms
• Straightforwardness of Game Forms with Lotteries as Outcomes
• Fair division under ordinal preferences: computing envy-free allocations of indivisible goods
• The computational complexity of random serial dictatorship
• Incentive properties for ordinal mechanisms
• Assignment Problem Based on Ordinal Preferences
• Algorithms and Computation
• The impossibility of extending random dictatorship to weak preferences

Cited In (10)

• The incompatibility of Pareto optimality and dominant-strategy incentive compatibility in sufficiently-anonymous budget-constrained quasilinear settings
• Extended random assignment mechanisms on a family of good sets
• Inefficiency of the Nash equilibrium for selfish machine covering on two hierarchical uniform machines
• A solution to the random assignment problem on the full preference domain
• Random assignments with uniform preferences: an impossibility result
• Partial strategyproofness: relaxing strategyproofness for the random assignment problem
• Why do popular mechanisms lack efficiency in random environments?
• The impossibility of strategy-proof, Pareto efficient, and individually rational rules for fractional matching
• An incompatibility between recursive unanimity and strategy-proofness in two-sided matching problems
• A new impossibility result for random assignments

Uses Software

• SDS_Impossibility

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)