2010 Working Paper Version

The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. [PDF]

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