The Envy Cost of Strategy-proof and Ex-post Efficient Assignment
Zhangchi Ding
Source abstract
How much envy is unavoidable under strategy-proofness and ex-post efficiency? For every market size, we determine the minimum worstcase envy over all mechanisms satisfying these axioms on the full strictpreference domain. Envy is the largest positive cumulative-probability gap, equivalently the supremum of normalized expected-utility envy consistent with an agent's ranking. With n ≥ 3 agents and n distinct objects, the minimax value is ⌊(n-1) 2 /4⌋/[n(n-1)], attained by random serial dictatorship. The lower bound requires no anonymity or neutrality. Its proof combines incentive equalities, efficiency, and capacity balance on a four-report domain, without characterizing admissible mechanisms. The optimal loss converges to 1/4. With multiple copies of object types, exact envy-freeness is feasible under the same axioms precisely when the two smallest capacities sum to at least the number of agents.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.