Optimal Decision-Making With Minimal Waste:Strategyproof Redistribution of VCG PaymentsRuggiero CavalloDEAS, Harvard University33 Oxford St.Cambridge, MA [email protected] for coordinating group decision-making amongself-interested agents often employ a trusted center, capableof enforcing the prescribed outcome. Typically such mech-anisms, including the ubiquitous Vickrey Clarke Groves(VCG), require significant transfer payments from agentsto the center. While this is sought after in some settings, itis often an unwanted cost of implementation. We proposea modification of the VCG framework that—by using do-main information regarding agent valuation spaces—is oftenable to achieve redistribution of much of the required trans-fer payments back among the agents, thus coming closer tobudget-balance. The proposed mechanism is strategyproof,ex post individual rational, no-deficit, and leads to an ef-ficient outcome; we prove that among all mechanisms withthese qualities and an anonymity property it is optimally bal-anced, in that no mechanism ever yields greater payoff to th eagents. We provide a general characterization of when strat-egyproof redistribution is possible, and demonstrate specif-ically that substantial redistribution can be achieved in al-location problems.Categories and Subject DescriptorsI.2.11 [Artificial Intelligence]: Distributed ArtificialIntelligence—Multiagent systems; J.4 [Social and Behav-ioral Sci ences]: EconomicsGeneral TermsAlgorithms, Economics, TheoryKeywordsSocial choice, Mechanism design, VCGPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.AAMAS’06 May 8–12 2006, Hakodate, Hokkaido, Japan.Copyright 2006 ACM 1-59593-303-4/06/0005 ...$5.00.1. INTRODUCTIONThis paper is concerned with decision-making problemsthat involve a group of self-interested parties, when eachparty may be in competition with other members of thegroup. Instances of this problem abound in everyday life.Consider, to name just a few examples: a group of house-mates that jointly own a car and must decide who shouldget to use it on a Friday night; a set of city neighborhoodscompeting for a grant to build a new playground; a groupof astronomers competing for the rights to use a p ublicly-owned space telescope; or companies competing for govern-ment allocation of wireless spectrum.How would one formulate a general framework fordecision-making in domains such as these? One natural ob-jective is that the decision process lead to the choice thatmaximizes the total value that is realized. Moreover, and tothat end, it is highly desirable that the mechanism not en-courage manipulation by dishonest agents—we want truth-fulness to be in each agent’s best-interest; this will allow usto reasonably predict the actual effects of whatever outcomeis selected, and will simplify the task of the agents by tak-ing strategic behavior out of the equation that maximizesexpected reward.The well-known Groves family of social choice mecha-nisms, by requiring specific p ayments to each agent, reachesoutcomes with the desirable properties described above.However, implementing t he payments specified in the mostbasic Groves mechanism requires a large external budget,making it infeasible in typical decision-making scenarioswhere th ere is no outside funding.The Vickrey Clarke Groves (VCG) mechanism counter-acts this potential budget imbalance by imposing “charges”on the agents, to be delivered to a “center” capable of en-forcing the specified outcome. For typical decision-makingproblems,1VCG results in net transfers being delivered onlyin th e direction of agents to the center. While there aresome scenarios in which revenue to a center is sought af-ter (e.g., some auctions), often it is preferable to maintainas much wealth as possible within the group of agents, andthe transfer payment can be viewed as an undesirable “costof implementation.” In other words, budget-balance is fre-quently a sought after mechanism property, and though itdoesn’t ru n a deficit, the VCG mechanism fails in this re-gard by producing a surplus of agent charges (hence calledthe “VCG surplus”).1Specifically, when there are no positive externalities.The ideal social choice mechanism would have the desir-able properties of VCG (truthfulness; social welfare maxi-mization; non-negative payoff guarantee), and at the sametime run neither a budget surplus nor deficit. As we will see,this exact bud get-balance is usually not attainable. How-ever, while it has often been stated that no improvementover VCG is possible, we demonstrate that this is not thecase in a broad class of domains (e.g., allocation problems)where valuations have some basic structure.We propose a modification of the VCG framework thatincorporates redistribution of as much of the VCG sur-plus as possible back among the agents. We prove that—among all truthful, social welfare maximizing, and no-deficitmechanisms that meet basic anonymity and participationconstraints—this “redistribution mechanism” is optimall ybalanced, in that no mechanism ever comes closer to budget-balance. We describe why in the case of completely un -constrained valuation functions no redistribution is possible,and characterize the domains in which it is.We start by focusing our analysis on the special setting of“all-or-nothing” (AON) domains, those in which each out-come yields non-zero reward for just a single agent (everyagent gets either all the reward or none). Here the redis-tribution mechanism has a particularly simple and elegantform, and the most redistribution is possible. In fact, inAON domains th e mechanism is completely budget-balanced(i.e., redistributes all surplus) in the limit as the number ofagents goes to infinity, for arbitrary valuations in an AONcontext. We demonstrate the applicability of the mecha-nism to general allocation problems, and describe empiricalresults that indicate the extent to which redistribution ispossible for different degrees of dependency between agentvaluations. Finally, we discuss implementation of the mech-anism in the absence of a central
View Full Document
Unlocking...