Computer Science – Computer Science and Game Theory
Scientific paper
2010-03-27
Computer Science
Computer Science and Game Theory
Scientific paper
We study auctions with additive valuations where agents have a limit on the number of goods they may receive. We refer to such valuations as {\em capacitated} and seek mechanisms that maximize social welfare and are simultaneously incentive compatible, envy-free, individually rational, and have no positive transfers. If capacities are infinite, then sequentially repeating the 2nd price Vickrey auction meets these requirements. In 1983, Leonard showed that for unit capacities, VCG with Clarke Pivot payments is also envy free. For capacities that are all unit or all infinite, the mechanism produces a Walrasian pricing (subject to capacity constraints). Here, we consider general capacities. For homogeneous capacities (all capacities equal) we show that VCG with Clarke Pivot payments is envy free (VCG with Clarke Pivot payments is always incentive compatible, individually rational, and has no positive transfers). Contrariwise, there is no incentive compatible Walrasian pricing. For heterogeneous capacities, we show that there is no mechanism with all 4 properties, but at least in some cases, one can achieve both incentive compatibility and envy freeness.
Cohen Edith
Feldman Michal
Fiat Amos
Kaplan Haim
Olonetsky Svetlana
No associations
LandOfFree
Truth and Envy in Capacitated Allocation Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Truth and Envy in Capacitated Allocation Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Truth and Envy in Capacitated Allocation Games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-127498