A new perspective on implementation by voting trees

ABSTRACT

Voting trees provide an abstract model of decision-making among a group of individuals in terms of an iterative procedure for selecting a single vertex from a tournament. A family of voting trees is said to implement a given voting rule if for every tournament it chooses according to the rule. While partial results concerning implementable rules and necessary conditions for implementability have been obtained, a complete characterization of voting rules implementable by trees has proven surprisingly hard to find. A prominent rule that cannot be implemented by trees is the Copeland rule, which singles out vertices with maximum degree. In this paper, we suggest a new angle of attack and re-examine the implementability of the Copeland solution using paradigms and techniques at the core of theoretical computer science. We study the extent to which voting trees can approximate the maximum degree, and give upper and lower bounds on the worst-case ratio between the degree of the vertex chosen by a tree and the maximum degree, both for the deterministic model concerned with a single fixed tree, and for randomizations over arbitrary sets of trees. Our main positive result is a randomization over surjective trees of polynomial size that provides an approximation ratio of at least 1/2. The proof is based on a connection between a randomization over caterpillar trees and a rapidly mixing Markov chain.

REFERENCES

• 1: J.S. Banks. Sophisticated voting outcomes and agenda control. Social Choice and Welfare, 1:295--306, 1985.
• 2: J. Bartholdi, C.A. Tovey, and M.A. Trick. The computational difficulty of manipulating an election. Social Choice and Welfare, 6:227--241, 1989.
• 3: Felix Brandt , Felix Fischer , Paul Harrenstein, The computational complexity of choice sets, Proceedings of the 11th conference on Theoretical aspects of rationality and knowledge, June 25-27, 2007, Brussels, Belgium [doi>10.1145/1324249.1324263]
• 4: R. Chen and F.K. Hwang. Stronger players win more balanced knockout tournaments. Graphs and Combinatorics, 4(1):95--99, 1988.
• 5: Vincent Conitzer , Tuomas Sandholm , Jérôme Lang, When are elections with few candidates hard to manipulate?, Journal of the ACM (JACM), v.54 n.3, p.14-es, June 2007 [doi>10.1145/1236457.1236461]
• 6: P.J. Coughlan and M.L. Breton. A social choice function implementable via backward induction with values in the ultimate uncovered set. Review of Economic Design, 4:153--160, 1999.
• 7: M. de Condorcet. Essai sur l'application de l'analyse à la probabilité de décisions rendues à la pluralité de voix. Imprimerie Royal, 1785. Facsimile published in 1972 by Chelsea Publishing Company, New York.
• 8: B. Dutta and A. Sen. Implementing generalized Condorcet social choice functions via backward induction. Social Choice and Welfare, 10:149--160, 1993.
• 9: R. Farquharson. Theory of Voting. Yale University Press, 1969.
• 10: J.A. Fill. Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process. The Annals of Applied Probablity, 1(1):62--87, 1991.
• 11: P.C. Fishburn. Even-chance lotteries in social choice theory. Theory and Decision, 3(1):18--40, 1972.
• 12: Ehud Friedgut , Gil Kalai , Noam Nisan, Elections Can be Manipulated Often, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.243-249, October 25-28, 2008 [doi>10.1109/FOCS.2008.87]
• 13: A. Gibbard. Manipulation of voting schemes. Econometrica, 41:587--602, 1973.
• 14: A. Gibbard. Manipulation of schemes that mix voting with chance. Econometrica, 45(3):665--681, 1977.
• 15: M. Herrero and S. Srivastava. Implementation via backward induction. Journal of Economic Theory, 56:70--88, 1992.
• 16: M.D. Intriligator. A probabilistic model of social choice. Review of Economic Studies, 40(4):553--560, 1973.
• 17: J. Kahn, M. Saks, and D. Sturtevant. A topological approach to evasiveness. Combinatorica, 4:297--306, 1984.
• 18: G. Laffond , J. F. Laslier , M. Le Breton, The Copeland measure of Condorcet choice functions, Discrete Applied Mathematics, v.55 n.3, p.273-279, Dec. 13, 1994 [doi>10.1016/0166-218X(94)90013-2]
• 19: J. Lang, M.-S. Pini, F. Rossi, K.B. Venable, and T. Walsh. Winner determination in sequential majority voting. In Proc. of 20th IJCAI, pages 1372--1377, 2007.
• 20: J.-F. Laslier. Tournament Solutions and Majority Voting. Springer, 1997.
• 21: K. May. A set of independent, necessary and sufficient conditions for simple majority decisions. Econometrica, 20:680--684, 1952.
• 22: D.C. McGarvey. A theorem on the construction of voting paradoxes. Econometrica, 21(4):608--610, 1953.
• 23: R.D. McKelvey and R.G. Niemi. A multistage game representation of sophisticated voting for binary procedures. Journal of Economic Theory, 18:1--22, 1978.
• 24: N. Miller. A new solution set for tournaments and majority voting: Further graph theoretical approaches to the theory of voting. Americal Journal of Political Science, 24:68--96, 1980.
• 25: J.W. Moon. Topics on Tournaments. Holt, Reinhart and Winston, 1968.
• 26: H. Moulin. Choosing from a tournament. Social Choice and Welfare, 3:271--291, 1986.
• 27: A.D. Procaccia, A. Zohar, Y. Peleg, and J.S. Rosenschein. Learning voting trees. In Proc. of 22nd AAAI Conference, pages 110--115, 2007.
• 28: M. Satterthwaite. Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10:187--217, 1975.
• 29: K.A. Shepsle and B.R. Weingast. Uncovered sets and sophisticated outcomes with implications for agenda institutions. American Journal of Political Science, 28(1):49--74, 1984.
• 30: Alistair Sinclair , Mark Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, v.82 n.1, p.93-133, July 1989 [doi>10.1016/0890-5401(89)90067-9]
• 31: S. Srivastava and M.A. Trick. Sophisticated voting rules: The case of two tournaments. Social Choice and Welfare, 13:275--289, 1996.
• 32: Andrew Chi-Chin Yao, Probabilistic computations: Toward a unified measure of complexity, Proceedings of the 18th Annual Symposium on Foundations of Computer Science, p.222-227, September 30-October 31, 1977
• 33: R. Zeckhauser. Majority rule with lotteries on alternatives. Quarterly Journal of Economics, 83(4):696--703, 1969.
• 34: Michael Zuckerman , Ariel D. Procaccia , Jeffrey S. Rosenschein, Algorithms for the coalitional manipulation problem, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.277-286, January 20-22, 2008, San Francisco, California

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Economics, Theory

Keywords:
approximation, computational social choice, copeland rule, voting trees