M-DPOP: Faithful distributed implementation of efficient social choice problems

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.

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

Boi Faltings, Adrian Petcu, Wei Xue

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.

2007

Recent Advances in Dynamic, Distributed Constraint Optimization

Adrian Petcu

Constraint satisfaction/optimization is a powerful paradigm for solving numerous tasks in distributed AI, including planning, scheduling and resource allocation. However, up to now, distributed algorithms for constraint reasoning (especially optimization) have not been applied to large-scale systems due to their prohibitive complexity in terms of number of messages being exchanged. We have recently developed a series of new techniques for distributed constraint optimization, based on \textit{dynamic programming}. Unlike the methods that existed before, our techniques require a very small number of messages (\textit{linear in the size of the problem}). The maximal message size depends on a parameter of the problem graph, called the \textit{induced width}. Thus, these methods are likely to work very well on large but loose problems. We have proposed a whole range of techniques that deal with the most common problems in multiagent environments: efficiency, dynamics of the environment, privacy and the self interest of the agents involved. We believe that these methods are a particularly interesting foundation for distributed problem solving in dynamic, distributed environments.

2006

Coordination and Sampling in Distributed Constraint Optimization

Brammert Ottens

The Distributed Constraint Optimization (DCOP) framework can be used to model a wide range of optimization problems that are inherently distributed. A distributed optimization problem can be viewed as a problem distributed over a set of agents, where agents are responsible for finding a solution for their part of the problem. In the DCOP framework, the decisions the agents need to take are modeled using decision variables, and both the local problems and the inter-dependencies are modeled using constraints. In this thesis, we attack two problems related to the DCOP framework. In the first part of this thesis, we look at coordination problems with complex, non- trivial preferences. In the DCOP literature, the notion of complex is used for problems where agents need to take multiple-decisions and thus own multiple decision variables. To express the fact that agents preferences are hard to obtain, we introduce the notion of a non-trivial local problem. The present DCOP literature has largely ignored the origin of preferences, i.e. algorithms assume that the constraints are known a-priori. In coordination problems with complex, non-trivial preferences this assumption no longer holds. In order to investigate the behavior of existing DCOP algorithms on such coordination problems, we first introduce a new DCOP model for such coordination problems, where we make an explicit distinction between the coordination part of the problem, and the local preferences of the agents. We then introduce two new benchmarks with complex, non-trivial local subproblems, and perform an evaluation of several complete and non-complete DCOP algorithms. Our results show that the O-DPOP algorithm, which elicits preferences from agents in a best-first order, outper- forms both other complete approaches as also local search approaches. We show that, despite the fact that a best first order cannot always be guaranteed when dealing with non-trivial local problems, O-DPOP still finds solutions that are either better, or on par with, local search algorithms. In the second part of this thesis, we introduce a new sampling based approach to solving DCOPs. Existing DCOP algorithms are either complete, but do not scale well, or scale well but are not guaranteed to find a solution. Our approach, inspired by the application of the UCB algorithm for the multi-armed bandit problem on trees, aims to provide method that scales well. Furthermore, given certain assumptions on the problem structure, our method is guaranteed to find good solutions. We introduce the Distributed UCT (DUCT) algorithm, that uses bounds similar to those used in the UCT algorithm, which is an adaptation of the UCB approach on trees. We introduce and evaluate four different variations of the DUCT algorithm, DUCT-A, DUCT-B, DUCT-C and DUCT-D, that differ in the bounds that they use. To evaluate our algorithms, we compare them with existing DCOP approaches on three different types of problems, both with and without hard constraints. Our results show that, compared with other DCOP algorithms, the DUCT-D variant consistently performs well on the problems used, with respect to both solution quality and runtime. Furthermore, it consistently sends less information than the state-of-the-art DCOP algorithms, and is thus shown to be a suitable and practical algorithm for solving DCOPs.