The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes.
[PDF]
Abstract
Most of what is known about the problem of combinatorial assignment -- e.g., assigning schedules of courses to students -- are impossibility theorems which indicate that there is no perfect mechanism. This paper proposes a new mechanism, Approximate Competitive Equilibrium from Equal Incomes (A-CEEI), and shows that it satisfies attractive second-best criteria of efficiency, fairness, and incentives. First, I prove existence of a novel approximation to CEEI: any strictly positive amount of budget inequality is sufficient to guarantee existence of item prices which approximately clear the market. Second, I propose two new criteria of outcome fairness, maximin share and envy bounded by a single good, which weaken Steinhaus's (1948) fair share and Foley's (1967) envy freeness to accommodate indivisibilities and complementarities in a realistic way. Third, I show that A-CEEI satisfies the fairness criteria. Last, I show that A-CEEI is strategyproof in the large. I examine A-CEEI's performance on real data and compare the proposed mechanism to alternatives from theory and practice: all other known mechanisms are either unfair ex-post or manipulable even in the large, and most are both manipulable and unfair
https://ericbudish.org/wp-content/uploads/2018/09/clear.png00Academic Web Pageshttps://ericbudish.org/wp-content/uploads/2018/09/clear.pngAcademic Web Pages2010-08-06 00:00:002022-05-02 16:14:492010 Working Paper Version