BB-M-DPOP: Structural Techniques for Budget-Balance in Distributed Implementations of Efficient Social Choice

We model social choice problems in which self interested agents with private utility functions have to agree on values for a set of variables subject to side constraints. The goal is to implement the efficient solution, maximizing the total utility across all agents. Existing techniques for this problem fall into two groups. Distributed constraint optimization algorithms can find the solution without any central authority but are vulnerable to manipulation. Incentive compatible mechanisms can ensure that agents report truthful information about their utilities and prevent manipulation of the outcome but require centralized computation. Following the agenda of {\em distributed implementation}~\cite{parkes04}, we integrate these methods and introduce {\em M-DPOP}, the first distributed optimization protocol that {\em faithfully} implements the Vickrey-Clarke-Groves (VCG) mechanism for this problem of efficient social choice. 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. The only central authority required is a bank that can extract payments from agents. We exploit structure in the problem to develop a faithful method to redistribute some of the VCG payments back to agents. Although this method is not guaranteed to achieve complete budget-balance, experimental results show that it performs significantly better than the basic VCG scheme. For problems with more than 10 agents, we always observe redistribution above 80%, and sometimes even up to 100% redistribution of the VCG taxes. % We extend the redistribution scheme to provide complete budget balance. The new scheme works by renouncing optimality: each agent's influence is forcibly limited to a restricted area, which allows us to effectively redistribute all VCG payments in a faithful way.