Abstract
Social choice is a normative study of designing protocols for collective decision making. However, in instances where the underlying decision space is too large or complex for ordinal voting, standard voting methods may be impractical. How then can we design a protocol - preferably decentralized, simple, scalable, and not requiring any special knowledge of the decision space - to reach consensus? We propose sequential deliberation as a natural solution to this problem. In this iterative method, successive pairs of agents bargain over the decision space using the previous decision as a disagreement alternative. We show that sequential deliberation finds a 1.208-approximation to the optimal social cost when the space of preferences define a median graph, coming very close to this value with only a small constant number of agents sampled from the population. We also give lower bounds on simpler classes of mechanisms to justify our design choices. We further show that sequential deliberation is ex-post Pareto efficient and has truthful reporting as an equilibrium of the induced extensive form game. Finally, we prove that for general metric spaces, the first and second moment of the distribution of social cost of the outcomes produced by sequential deliberation are also bounded by constants.
B. Fain—Supported by NSF grants CCF-1637397 and IIS-1447554.
A. Goel—Supported by the Army Research Office Grant No. 116388, the Office of Naval Research Grant No. 11904718, by NSF grant CCF-1637418, and by the Stanford Cyber Initiative.
K. Munagala—Supported by NSF grants CCF-1408784, CCF-1637397, and IIS-1447554.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
See also recent work by [38] that considers minimizing the variance of randomized truthful mechanisms.
- 2.
The motivation for considering Squared-Distortion instead of the standard deviation is that the latter might prefer a more deterministic mechanism with a worse social cost, a problem that the Squared-Distortion avoids.
References
Airiau, S., Endriss, U.: Iterated majority voting. In: Rossi, F., Tsoukias, A. (eds.) ADT 2009. LNCS, vol. 5783, pp. 38–49. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04428-1_4
Anshelevich, E., Bhardwaj, O., Postl, J.: Approximating optimal social choice under metric preferences. In: AAAI, vol. 15, pp. 777–783 (2015)
Anshelevich, E., Postl, J.: Randomized social choice functions under metric preferences. In: 25th International Joint Conference on Artificial Intelligence (2016)
Bandelt, H.J., Barthelemy, J.P.: Medians in median graphs. Discret. Appl. Math. 8(2), 131–142 (1984)
Barbera, S., Gul, F., Stacchetti, E.: Generalized median voter schemes and committees. J. Econ. Theor. 61(2), 262–289 (1993)
Bennett, E., Houba, H.: Odd man out: bargaining among three players. Working Papers 662, UCLA Department of Economics, May 1992. http://www.econ.ucla.edu/workingpapers/wp662.pdf
Binmore, K., Shaked, A., Sutton, J.: Testing noncooperative bargaining theory: a preliminary study. Am. Econ. Rev. 75(5), 1178–1180 (1985)
Binmore, K., Rubinstein, A., Wolinsky, A.: The nash bargaining solution in economic modelling. Rand J. Econ. 17(2), 176–188 (1986)
Boutilier, C., Caragiannis, I., Haber, S., Lu, T., Procaccia, A.D., Sheffet, O.: Optimal social choice functions: a utilitarian view. Artif. Intell. 227, 190–213 (2015)
Cheng, Y., Dughmi, S., Kempe, D.: Of the people: voting is more effective with representative candidates. In: EC (2017)
Clearwater, A., Puppe, C., Slinko, A.: Generalizing the single-crossing property on lines and trees to intermediate preferences on median graphs. In: Proceedings of the 24th International Conference on Artificial Intelligence, IJCAI 2015, pp. 32–38 (2015)
Fain, B., Goel, A., Munagala, K., Shaksuwong, S.: Sequential deliberation for social choice (2017). https://arxiv.org/abs/1710.00771
Feldman, M., Fiat, A., Golomb, I.: On voting and facility location. In: Proceedings of the 2016 ACM Conference on Economics and Computation, EC 2016, pp. 269–286. ACM, New York (2016)
Fishkin, J., Luskin, R.: Experimenting with a democratic ideal: deliberative polling and public opinion. Acta Polit. 40(3), 284–298 (2005)
Garg, N., Kamble, V., Goel, A., Marn, D., Munagala, K.: Collaborative optimization for collective decision-making in continuous spaces. In: Proceedings of the World Wide Web (WWW) Conference (2017)
Goel, A., Lee, J.: Towards large-scale deliberative decision-making: small groups and the importance of triads. In: ACM EC (2016)
Goel, A., Krishnaswamy, A.K., Munagala, K.: Metric distortion of social choice rules. In: EC (2017)
Gross, S., Anshelevich, E., Xia, L.: Vote until two of you agree: mechanisms with small distortion and sample complexity. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 4–9 February 2017, San Francisco, California, USA, pp. 544–550 (2017)
Harsanyi, J.C.: A simplified bargaining model for the n-person cooperative game. Int. Econ. Rev. 4(2), 194–220 (1963)
Hylland, A., Zenkhauser, R.: A mechanism for selecting public goods when preferences must be elicited. Working Paper (1980)
Kalai, E.: Proportional solutions to bargaining situations: interpersonal utility comparisons. Econometrica 45(7), 1623–1630 (1977)
Kalai, E., Smorodinsky, M.: Other solutions to nash’s bargaining problem. Econometrica 43(3), 513–518 (1975)
Knuth, D.E.: The Art of Computer Programming: Combinatorial Algorithms, Part 1, 1st edn. Addison-Wesley Professional, Boston (2011)
Krishna, V., Serrano, R.: Multilateral bargaining. Rev. Econ. Stud. 63(1), 61–80 (1996)
Lang, J., Xia, L.: Voting in combinatorial domains. In: Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D. (eds.) Handbook of Computational Social Choice. Cambridge University Press, Cambridge (2016)
Lev, O., Rosenschein, J.S.: Convergence of iterative voting. In: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, vol. 2, pp. 611–618. International Foundation for Autonomous Agents and Multiagent Systems (2012)
Meir, R., Polukarov, M., Rosenschein, J.S., Jennings, N.R.: Convergence to equilibria in plurality voting. In: Proceedings of the 24th Conference on Artificial Intelligence (AAAI 2010), pp. 823–828 (2010)
Myerson, R.B.: Two-person bargaining problems and comparable utility. Econometrica 45(7), 1631–1637 (1977)
Nash, J.F.: The bargaining problem. Econometrica 18(2), 155–162 (1950). http://www.jstor.org/stable/1907266
Neelin, J., Sonnenschein, H., Spiegel, M.: An experimental test of Rubinstein’s theory of bargaining. Working Papers 587, Princeton University, Department of Economics, Industrial Relations Section, May 1986
Nehring, K., Puppe, C.: The structure of strategy-proof social choice. Part I: general characterization and possibility results on median spaces. J. Econ. Theor. 135(1), 269–305 (2007)
Rabinovich, Z., Obraztsova, S., Lev, O., Markakis, E., Rosenschein, J.S.: Analysis of equilibria in iterative voting schemes. In: AAAI, vol. 15, pp. 1007–1013. Citeseer (2015)
Roth, A.E.: Bargaining phenomena and bargaining theory. In: Roth, A.E. (ed.) Laboratory Experiments in Economics: Six Points of View, pp. 14–41. Cambridge University Press, Cambridge (1987)
Rubinstein, A.: Perfect equilibrium in a bargaining model. Econometrica 50(1), 97–109 (1982). http://www.jstor.org/stable/1912531
Saban, D., Stier-Moses, N.: The competitive facility location problem in a duopoly: connections to the 1-median problem. In: Goldberg, P.W. (ed.) WINE 2012. LNCS, vol. 7695, pp. 539–545. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-35311-6_44
Schummer, J., Vohra, R.V.: Strategy-proof location on a network. J. Econ. Theor. 104(2), 405–428 (2002)
Thompson, D.F.: Deliberative democratic theory and empirical political science. Annu. Rev. Polit. Sci. 11(1), 497–520 (2008)
Wajc, D., Procaccia, A., Zhang, H.: Approximation-variance tradeoffs in mechanism design, January 2017
Wendell, R.E., McKelvey, R.D.: New perspectives in competitive location theory. Eur. J. Oper. Res. 6(2), 174–182 (1981)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Fain, B., Goel, A., Munagala, K., Sakshuwong, S. (2017). Sequential Deliberation for Social Choice. In: R. Devanur, N., Lu, P. (eds) Web and Internet Economics. WINE 2017. Lecture Notes in Computer Science(), vol 10660. Springer, Cham. https://doi.org/10.1007/978-3-319-71924-5_13
Download citation
DOI: https://doi.org/10.1007/978-3-319-71924-5_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-71923-8
Online ISBN: 978-3-319-71924-5
eBook Packages: Computer ScienceComputer Science (R0)