On Optimal Linear Redistribution of VCG Payments in Assignment of Heterogeneous Objects

Simple item page
dc.creatorGujar, Sujit
dc.creatorNarahari, Yadati
dc.date2008-12-28
dc.date.accessioned2026-07-07T12:22:56Z
dc.date.available2026-07-07T12:22:56Z
dc.descriptionThere are p heterogeneous objects to be assigned to n competing agents (n > p) each with unit demand. It is required to design a Groves mechanism for this assignment problem satisfying weak budget balance, individual rationality, and minimizing the budget imbalance. This calls for designing an appropriate rebate function. Our main result is an impossibility theorem which rules out linear rebate functions with non-zero efficiency in heterogeneous object assignment. Motivated by this theorem, we explore two approaches to get around this impossibility. In the first approach, we show that linear rebate functions with non-zero are possible when the valuations for the objects are correlated. In the second approach, we show that rebate functions with non-zero efficiency are possible if linearity is relaxed.
dc.description12 pages
dc.identifierhttps://arxiv.org/abs/0812.4792
dc.identifierhttp://arxiv.org/abs/0812.4792
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/213822
dc.subjectComputer Science and Game Theory
dc.subjectJ.4; I.2.11
dc.titleOn Optimal Linear Redistribution of VCG Payments in Assignment of Heterogeneous Objects
dc.typetext

Files

Collections

arXiv