M-DPOP: Faithful Distributed Implementations of Efficient Social Choice Problems

DSpace/Manakin Repository

M-DPOP: Faithful Distributed Implementations of Efficient Social Choice Problems

Show simple item record

dc.contributor.author Parkes, David
dc.contributor.author Faltings, Boi
dc.contributor.author Petcu, Adrian
dc.date.accessioned 2009-06-26T13:21:14Z
dc.date.issued 2008
dc.identifier.citation Petcu, Adrian., Boi Faltings, and David C. Parkes. 2008. M-DPOP: faithful distributed implementations of efficient social choice problems. Journal of Artificial Intelligence Research, no. 32: 705-755. en
dc.identifier.uri http://nrs.harvard.edu/urn-3:HUL.InstRepos:3122491
dc.description.abstract In the efficient social choice problem, the goal is to assign values, subject to side constraints, to a set of variables to maximize the total utility across a population of agents, where each agent has private information about its utility function. In this paper we model the social choice problem as a distributed constraint optimization problem (DCOP), in which each agent can communicate with other agents that share an interest in one or more variables. Whereas existing DCOP algorithms can be easily manipulated by an agent, either by misreporting private information or deviating from the algorithm, we introduce M-DPOP, the first DCOP algorithm that provides a faithful distributed implementation for efficient social choice. This provides a concrete example of how the methods of mechanism design can be unified with those of distributed optimization. Faithfulness ensures that no agent can benefit by unilaterally deviating from any aspect of the protocol, neither information revelation, computation, nor communication, and whatever the private information of other agents. We allow for payments by agents to a central bank, which is the only central authority that we require. To achieve faithfulness, we carefully integrate the Vickrey-Clarke-Groves (VCG) mechanism with the DPOP algorithm, such that each agent is only asked to perform computation, report information, and send messages that is in its own best interest. Determining agent i’s payment requires solving the social choice problem without agent i. Here, we present a method to reuse computation performed in solving the main problem in a way that is robust against manipulation by the excluded agent. Experimental results on structured problems show that as much as 87% of the computation required for solving the marginal problems can be avoided by re-use, providing very good scalability in the number of agents. On unstructured problems, we observe a sensitivity of M-DPOP to the density of the problem, and we show that reusability decreases from almost 100% for very sparse problems to around 20% for highly connected problems. We close with a discussion of the features of DCOP that enable faithful implementations in this problem, the challenge of reusing computation from the main problem to marginal problems in other algorithms such as ADOPT and OptAPO, and the prospect of methods to avoid the welfare loss that can occur because of the transfer of payments to the bank. en
dc.description.sponsorship Engineering and Applied Sciences en
dc.language.iso en_US en
dc.publisher AAAI Press en
dc.relation.isversionof http://dx.doi.org/10.1613/jair.2500 en
dash.license LAA
dc.title M-DPOP: Faithful Distributed Implementations of Efficient Social Choice Problems en
dc.relation.journal The Journal of Artificial Intelligence Research en
dash.depositing.author Parkes, David

Files in this item

Files Size Format View xmlui.dri2xhtml.METS-1.0.item-files-description
parkes_m-dpop.pdf 1000.Kb PDF View/Open

This item appears in the following Collection(s)

  • FAS Scholarly Articles [7218]
    Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University

Show simple item record

 
 

Search DASH


Advanced Search
 
 

Submitters