Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-09T01:19:42.654Z Has data issue: false hasContentIssue false
  • English
  • Français

A distributed voting scheme to maximize preferences

Published online by Cambridge University Press:  20 July 2006

Peter Auer  and
Nicolò Cesa-Bianchi
Peter Auer
Affiliation:
Dept. of Mathematics and Information Technologies, University of Leoben, Austria.
Nicolò Cesa-Bianchi
Affiliation:
Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano, Italy; [email protected]
Get access

Abstract

We study the problem of designing a distributed voting scheme for electing a candidate that maximizes the preferences of a set of agents. We assume the preference of agent i for candidate j is a real number xi,j, and we do not make any assumptions on the mechanism generating these preferences. We show simple randomized voting schemes guaranteeing the election of a candidate whose expected total preference is nearly the highest among all candidates. The algorithms we consider are designed so that each agent has to disclose only a few bits of information from his preference table. Finally, in the important special case in which each agent is forced to vote for at most one candidate we show that our voting scheme is essentially optimal.

Keywords

Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 40 , Issue 2: Alberto Bertoni: Climbing summits , April 2006 , pp. 389 - 403
Copyright
© EDP Sciences, 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

P. Auer, P. Caianiello and N. Cesa-Bianchi, Tight bounds on the cumulative profit of distributed voters, in Proceedings of the 15th ACM Symposium on Principles of Distributed Computing. ACM Press (1996) 312.
P. Caianiello, P. Crescenzi and A. Marchetti-Spaccamela, Distributed voting and maximum satisfiability. Unpublished manuscript (1993).
Chang, H.S., Multi-policy iteration with a distributed voting. Math. Methods Oper. Res. 60 (2004) 299–310. CrossRef
Chang, H.S., On the probability of correct selection by distributed voting in stochastic optimization. J. Optim. Theory Appl. 125 (2005) 231–240. CrossRef
Y.S. Chow and H. Teicher, Probability Theory. Springer (1988).
X. Deng and C.H. Papadimitriou, Distributed decision-making with incomplete information, in Proceedings of the 12ft IFIP Congress. Madrid (1992).
C. Dwork, R. Kumar, M. Naor and D. Sivakumar, Rank aggregation revisited, in Proceedings of the 10th International World Wide Web Conference (2001) 96–104.
E. Ephrati and J.S. Rosenschein, Reaching agreement through partial revelation of preferences, in Proceedings of the 10th European Conference on Artificial Intelligence (1992) 229–233.
C.H. Papadimitriou and M. Yannakakis, On the value of information in distributed decision making, in Proceedings of the 10th ACM Symposium on Principles of Distributed Computing. ACM Press (1991) 61–64.
C.H. Papadimitriou and M. Yannakakis, Linear programming without the matrix, in Proceedings of the 25th ACM Symposium on the Theory of Computing. ACM Press (1993) 121–129.
D. Pollard, Convergence of Stochastic Processes. Springer (1984).