Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-15T02:54:26.563Z 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; cesa-bianchi@dsi.unimi.it
Get access

Abstract

We study the problem of designing a distributed voting schemefor electing a candidate that maximizes the preferences of a setof agents. We assume the preference of agent i for candidatej is a real number xi,j , and we do not makeany assumptions on the mechanism generating these preferences.We show simple randomized voting schemes guaranteeing theelection of a candidate whose expected total preference isnearly the highest among all candidates. The algorithmswe consider are designed so that each agent has to discloseonly a few bits of information from his preference table.Finally, in the important special case in which each agent isforced to vote for at most one candidate we show that ourvoting scheme is essentially optimal.

Keywords

Information

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.)

Article purchase

Temporarily unavailable

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).