[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Preference elicitation and robust winner determination for single- and multi-winner social choice

Published: 01 February 2020 Publication History

Abstract

The use of voting schemes based on rankings of alternatives to solve social choice problems can often impose significant burden on voters, both in terms of communication and cognitive requirements. In this paper, we develop techniques for preference elicitation in voting settings (i.e., vote elicitation) that can alleviate this burden by minimizing the amount of preference information needed to find (approximately or exactly) optimal outcomes. We first describe robust optimization techniques for determining winning alternatives given partial preference information (i.e., partial rankings) using the notion of minimax regret. We show that the corresponding computational problem is tractable for some important voting rules, and intractable for others. We then use the solution to the minimax-regret optimization as the basis for vote elicitation schemes that determine appropriate preference queries for voters to quickly reduce potential regret. We apply these techniques to multi-winner social choice problems as well, in which a slate of alternatives must be selected, developing both exact and greedy robust optimization procedures. Empirical results on several data sets validate the effectiveness of our techniques.

References

[1]
Hassene Aissi, Cristina Bazgan, Daniel Vanderpooten, Min-max and min-max regret versions of combinatorial optimization problems: a survey, Eur. J. Oper. Res. 197 (2) (2009) 427–438.
[2]
Fuad Aleskerov, Vyacheslav V. Chistyakov, Valery Kalyagin, The threshold aggregation, Econ. Lett. 107 (2) (2010) 261–262.
[3]
Kenneth J. Arrow, A difficulty in the concept of social welfare, J. Polit. Econ. 58 (August 1950) 328–346.
[4]
Igor Averbakh, Minmax regret solutions for minimax optimization problems with uncertainty, Oper. Res. Lett. 27 (2000) 57–65.
[5]
Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, Toby Walsh, Justified representation in approval-based committee voting, Soc. Choice Welf. 48 (2) (2017) 461–485.
[6]
Haris Aziz, Piotr Faliszewski, Bernard Grofman, Arkadii Slinko, Nimrod Talmon, Egalitarian committee scoring rules, in: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-18, Stockholm, 2018, pp. 56–62.
[7]
Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Simon Mackenzie, Nicholas Mattei, Toby Walsh, Computational aspects of multi-winner approval voting, in: Proceedings of the Fourteenth International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS-15, Istanbul, 2015, pp. 107–115.
[8]
Yoram Bachrach, Nadja Betzler, Piotr Faliszewski, Probabilistic possible winner determination, in: Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI-10, Atlanta, GA, 2010, pp. 697–702.
[9]
Dorothea Baumeister, Piotr Faliszewski, Jérôme Lang, Jörg Rothe, Campaigns for lazy voters: truncated ballots, in: Proceedings of the Eleventh International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS-12, Valencia, Spain, 2012, pp. 577–584.
[10]
Dorothea Baumeister, Jörg Rothe, Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules, in: Proceedings of the Nineteenth European Conference on Artificial Intelligence, ECAI-10, Lisbon, 2010, pp. 1019–1020.
[11]
Nawal Benabbou, Serena Di Sabatino Di Diodoro, Patrice Perny, Paolo Viappiani, Incremental preference elicitation in multi-attribute domains for choice and ranking with the Borda count, in: International Conference on Scalable Uncertainty Management, Nice, France, Springer, 2016, pp. 81–95.
[12]
Nadja Betzler, Britta Dorn, Towards a dichotomy for the possible winner problem in elections based on scoring rules, J. Comput. Syst. Sci. 76 (8) (2010) 812–836.
[13]
Nadja Betzler, Arkadii Slinko, Johannes Uhlmann, On the computation of fully proportional representation, J. Artif. Intell. Res. 47 (2013) 475–519.
[14]
Craig Boutilier, Computational decision support: regret-based models for optimization and preference elicitation, in: P.H. Crowley, T.R. Zentall (Eds.), Comparative Decision Making: Analysis and Support Across Disciplines and Applications, Oxford University Press, Oxford, 2013, pp. 423–453.
[15]
Craig Boutilier, Fahiem Bacchus, Ronen I. Brafman UCP-Networks, A directed graphical representation of conditional utilities, in: Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence, UAI-01, Seattle, 2001, pp. 56–64.
[16]
Craig Boutilier, Relu Patrascu, Pascal Poupart, Dale Schuurmans, Constraint-based optimization and utility elicitation using the minimax decision criterion, Artif. Intell. 170 (8–9) (2006) 686–713.
[17]
Craig Boutilier, Kevin Regan, Paolo Viappiani, Online feature elicitation in interactive optimization, in: Proceedings of the Twenty-Sixth International Conference on Machine Learning, ICML-09, Montreal, 2009, pp. 73–80.
[18]
Craig Boutilier, Jeffrey Rosenschein, Incomplete information and communication in voting (Chapter 10), in: F. Brandt, V. Conitzer, U. Endriss, J. Lang, A.D. Procaccia (Eds.), Handbook of Computational Social Choice, Cambridge University Press, 2015.
[19]
Craig Boutilier, Tuomas Sandholm, Rob Shields, Eliciting bid taker non-price preferences in (combinatorial) auctions, in: Proceedings of the Nineteenth National Conference on Artificial Intelligence, AAAI-04, San Jose, CA, 2004, pp. 204–211.
[20]
Steven Brams, Peter Fishburn, Approval voting, Am. Polit. Sci. Rev. 72 (3) (1978) 831–847.
[21]
Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel Procaccia (Eds.), Handbook of Computational Social Choice, Cambridge University Press, Cambridge, 2016.
[22]
Darius Braziunas, Craig Boutilier, Minimax regret-based elicitation of generalized additive utilities, in: Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence, UAI-07, Vancouver, 2007, pp. 25–32.
[23]
Darius Braziunas, Craig Boutilier, Assessing regret-based preference elicitation with the UTPREF recommendation system, in: Proceedings of the Eleventh ACM Conference on Electronic Commerce, EC'10, Cambridge, MA, 2010, pp. 219–228.
[24]
Ioannis Caragiannis, Dimitris Kalaitzis, Evangelos Markakis, Approximation algorithms and mechanism design for minimax approval voting, in: Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI-10, Atlanta, 2010, pp. 737–742.
[25]
Ioannis Caragiannis, Ariel D. Procaccia, Nisarg Shah, When do noisy votes reveal the truth?, in: Proceedings of the Fourteenth ACM Conference on Electronic Commerce, EC'13, Philadelphia, 2013, pp. 143–160.
[26]
John R. Chamberlin, Paul N. Courant, Representative deliberations and representative decisions: proportional representation and the Borda rule, Am. Polit. Sci. Rev. 77 (3) (1983) 718–733.
[27]
Yann Chevaleyre, Ulle Endriss, Jérôme Lang, Nicolas Maudet, A short introduction to computational social choice, in: Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM-07, Harrachov, Czech Republic, 2007, pp. 51–69.
[28]
Yann Chevaleyre, Ulle Endriss, Jérôme Lang, Nicolas Maudet, Preference handling in combinatorial domains: from AI to social choice, AIM Mag. 29 (4) (2008) 37.
[29]
Reuven Cohen, Liran Katzir, The generalized maximum coverage problem, Inf. Process. Lett. 108 (1) (2008) 15–22.
[30]
Ronan Congar, Vincent Merlin, A characterization of the maximin rule in the context of voting, Theory Decis. 72 (1) (January 2012) 131–147.
[31]
Vincent Conitzer, Eliciting single-peaked preferences using comparison queries, J. Artif. Intell. Res. 35 (2009) 161–191.
[32]
Vincent Conitzer, Making decisions based on the preferences of multiple agents, Commun. ACM 53 (3) (2010) 84–94.
[33]
Vincent Conitzer, Tuomas Sandholm, Vote elicitation: complexity and strategy-proofness, in: Proceedings of the Eighteenth National Conference on Artificial Intelligence, AAAI-02, Edmonton, 2002, pp. 392–397.
[34]
Vincent Conitzer, Tuomas Sandholm, Communication complexity of common voting rules, in: Proceedings of the Sixth ACM Conference on Electronic Commerce, EC'05, Vancouver, 2005, pp. 78–87.
[35]
Lihi Naamani Dery, Meir Kalech, Lior Rokach, Bracha Shapira, Reaching a joint decision with minimal elicitation of voter preferences, Inf. Sci. 278 (2014) 466–487.
[36]
Palash Dey, Arnab Bhattacharyya, Sample complexity for winner prediction in elections, in: Proceedings of the Fourteenth International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS-15, Istanbul, 2015, pp. 1421–1430.
[37]
Palash Dey, Neeldhara Misra, Elicitation for preferences single peaked on trees, in: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16, New York, 2016, pp. 215–221.
[38]
Palash Dey, Neeldhara Misra, Preference elicitation for single crossing domain, in: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16, New York, 2016, pp. 222–228.
[39]
Ning Ding, Fangzhen Lin, Voting with partial information: what questions to ask?, in: Proceedings of the Twelfth International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS-13, St. Paul, MN, 2013, pp. 1237–1238.
[40]
John A. Doucette, Kate Larson, Robin Cohen, Conventional machine learning for social choice, in: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI-15, Austin, TX, 2015, pp. 858–864.
[41]
Joanna Drummond, Craig Boutilier, Elicitation and approximately stable matching with partial preferences, in: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13, Beijing, 2013, pp. 97–105.
[42]
Cynthia Dwork, Ravi Kumar, Moni Naor, D. Sivakumar, Rank aggregation methods for the web, in: Proceedings of the Tenth International World Wide Web Conference, WWW-01, Hong Kong, ACM, 2001, pp. 613–622.
[43]
Edith Elkind, Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Properties of multiwinner voting rules, Soc. Choice Welf. 48 (3) (2017) 599–632.
[44]
Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Nimrod Talmon, Multiwinner voting: a new challenge for social choice theory (Chapter 2), in: Endriss Ulle (Ed.), Trends in Computational Social Choice, AI Access, 2017, pp. 27–47.
[45]
Yuval Filmus, Joel Oren, Efficient voting via the top-k elicitation scheme: a probabilistic approach, in: Proceedings of the Fifteenth ACM Conference on Electronic Commerce, EC'14, Palo Alto, 2014, pp. 295–312.
[46]
Wulf Gaertner, A Primer in Social Choice Theory. LSE Perspectives in Economic Analysis, Oxford University Press, August 2006.
[47]
Pranava R. Goundan, Andreas S. Schulz, Revisiting the greedy approach to submodular set function maximization, Optim. Online (2007).
[48]
Mohammad Taghi Hajiaghayi, Mohammad Mahdian, Vahab S. Mirrokni, The facility location problem with general cost functions, Networks 42 (1) (2003) 42–47.
[49]
Noam Hazon, Yonatan Aumann, Sarit Kraus, Michael Wooldridge, On the evaluation of election outcomes under uncertainty, Artif. Intell. 189 (2012) 1–18.
[50]
Nathanaël Hyafil, Craig Boutilier, Regret-based incremental partial revelation mechanisms, in: Proceedings of the Twenty-First National Conference on Artificial Intelligence, AAAI-06, Boston, 2006, pp. 672–678.
[51]
Nathanaël Hyafil, Craig Boutilier, Mechanism design with partial revelation, in: Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07, Hyderabad, India, 2007, pp. 1333–1340.
[52]
Nathanaël Hyafil, Craig Boutilier, Partial revelation automated mechanism design, in: Proceedings of the Twenty-Second National Conference on Artificial Intelligence, AAAI-07, Vancouver, 2007, pp. 72–78.
[53]
Meir Kalech, Sarit Kraus, Gal A. Kaminka, Claudia V. Goldman, Practical voting rules with partial information, J. Auton. Agents Multi-Agent Syst. 22 (1) (2011) 151–182.
[54]
Toshihiro Kamishima, Hideto Kazawa, Shotaro Akaho, Supervised ordering: an empirical survey, in: IEEE International Conference on Data Mining, ICDM-05, Houston, TX, 2005, pp. 673–676.
[55]
Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan, Segmentation problems, J. ACM 51 (2004) 263–280.
[56]
Kathrin Konczak, Jérôme Lang, Voting procedures with incomplete preferences, in: IJCAI-05 Workshop on Advances in Preference Handling, Edinburgh, 2005, pp. 124–129.
[57]
Kouvelis Panos, Gang Yu, Robust Discrete Optimization and Its Applications, Kluwer, Dordrecht, 1997.
[58]
Jérôme Lang, Maria Silvia Pini, Francesca Rossi, Domenico Salvagnin, Kristen Brent Venable, Toby Walsh, Winner determination in voting trees with incomplete preferences and weighted votes, Auton. Agents Multi-Agent Syst. 25 (1) (2012) 130–157.
[59]
David Timothy Lee, Efficient, private, and ε-strategyproof elicitation of tournament voting rules, in: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15, Buenos Aires, 2015, pp. 2016–2032.
[60]
David Timothy Lee, Ashish Goel, Tanja Aitamurto, Helene Landemore, Crowdsourcing for participatory democracies: efficient elicitation of social choice functions, in: Second AAAI Conference on Human Computation and Crowdsourcing, Pittsburgh, PA, 2014, pp. 133–142.
[61]
Lev Omer, Jeffrey S. Rosenschein, Convergence of iterative voting, in: Proceedings of the Eleventh International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS-12, Valencia, Spain, 2012, pp. 611–618.
[62]
Tyler Lu, Craig Boutilier, Budgeted social choice: from consensus to personalized decision making, in: Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11, Barcelona, 2011, pp. 280–286.
[63]
Tyler Lu, Craig Boutilier, Robust approximation and incremental elicitation in voting protocols, in: Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11, Barcelona, 2011, pp. 287–293.
[64]
Tyler Lu, Craig Boutilier, Vote elicitation with probabilistic preference models: empirical estimation and cost tradeoffs, in: Proceedings of the Second International Conference on Algorithmic Decision Theory, ADT-11, Piscataway, NJ, 2011, pp. 135–149.
[65]
Tyler Lu, Craig Boutilier, Multi-winner social choice with incomplete preferences, in: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13, Beijing, 2013, pp. 263–270.
[66]
R. Duncan Luce, Individual Choice Behavior: A Theoretical Analysis, Wiley, 1959.
[67]
Brendan Lucier, Joel Oren, Online (budgeted) social choice, in: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, AAAI-14, Québec City, 2014, pp. 1456–1462.
[68]
Colin L. Mallows, Non-null ranking models, Biometrika 44 (1957) 114–130.
[69]
Nicholas Mattei, Toby Walsh Preflib, A library for preferences, in: Proceedings of the Third International Conference on Algorithmic Decision Theory (ADT-13), Bruxelles, Belgium, 2013, pp. 259–270. see http://www.preflib.org.
[70]
Reshef Meir, Maria Polukarov, Jeffrey S. Rosenschein, Nicholas R. Jennings, Convergence to equilibria in plurality voting, in: Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI-10, Atlanta, GA, 2010, pp. 823–828.
[71]
Reshef Meir, Ariel D. Procaccia, Jeffrey S. Rosenschein, Aviv Zohar, Complexity of strategic behavior in multi-winner elections, J. Artif. Intell. Res. 33 (2008) 149–178.
[72]
Burt L. Monroe, Fully proportional representation, Am. Polit. Sci. Rev. 89 (4) (1995) 925–940.
[73]
Hannu Nurmi, Voting Procedures Under Uncertainty, Springer-Verlag, Berlin, 2002.
[74]
Joel Oren, Yuval Filmus, Craig Boutilier, Efficient vote elicitation under candidate uncertainty, in: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13, Beijing, 2013, pp. 309–316.
[75]
Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, Toby Walsh, Aggregating partially ordered preferences, J. Log. Comput. 19 (2009) 475–502.
[76]
R.L. Plackett, The analysis of permutations, Appl. Stat. 24 (1975) 193–202.
[77]
Richard F. Potthoff, Steven J. Brams, Proportional representation: broadening the options, J. Theor. Polit. 10 (2) (1998) 147–178.
[78]
Ariel D. Procaccia, Jeffrey S. Rosenschein, Aviv Zohar, On the complexity of achieving proportional representation, Soc. Choice Welf. 30 (2008) 353–362.
[79]
Kevin Regan, Craig Boutilier, Regret-based reward elicitation for Markov decision processes, in: Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI-09, Montreal, 2009, pp. 451–454.
[80]
Kevin Regan, Craig Boutilier, Eliciting additive reward functions for Markov decision processes, in: Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11, Barcelona, 2011, pp. 2159–2164.
[81]
Michel Regenwetter, Bernard Grofman, A.A.J. Marley, Ilia Tsetlin, Behavioral Social Choice: Probabilistic Models, Statistical Inference, and Applications, Cambridge University Press, Cambridge, 2006.
[82]
Reyhaneh Reyhani, Mark Wilson, Best-reply dynamics for scoring rules, in: 20th European Conference on Artificial Intelligence, ECAI-12, Montpellier, France, 2012, pp. 672–677.
[83]
Magnus Roos, Jörg Rothe, Complexity of social welfare optimization in multiagent resource allocation, in: Proceedings of the Ninth International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS-10, Toronto, 2010, pp. 641–648.
[84]
Ahti Salo, Raimo P. Hämäläinen, Preference ratios in multiattribute evaluation (PRIME)—elicitation and decision procedures under incomplete information, IEEE Trans. Syst. Man Cybern. 31 (6) (2001) 533–545.
[85]
Piotr Skowron, Piotr Faliszewski, Chamberlin-Courant rule with approval ballots: approximating the MaxCover problem with bounded frequencies in FPT time, J. Artif. Intell. Res. 60 (1) (2017) 687–716. 9.
[86]
Piotr Skowron, Piotr Faliszewski, Jérôme Lang, Finding a collective set of items: from proportional multirepresentation to group recommendation, Artif. Intell. 241 (2016) 191–216.
[87]
Piotr Skowron, Piotr Faliszewski, Arkadii Slinko, Achieving proportional representation is easy in practice, in: Proceedings of the Twelfth International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS-13, St. Paul, MN, 2013, pp. 399–406.
[88]
Piotr Krzysztof Skowron, Piotr Faliszewski, Arkadii Slinko, Fully proportional representation as resource allocation: Approximability results, in: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13, Beijing, 2013, pp. 353–359.
[90]
Hossein Azari Soufiani, David C. Parkes, Lirong Xia, Preference elicitation for general random utility models, in: Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence, UAI-13, Bellevue, WA, 2013, pp. 596–605.
[91]
Olivier Toubia, John R. Hauser, Duncan I. Simester, Polyhedral methods for adaptive choice-based conjoint analysis, J. Mark. Res. 41 (1) (2004) 116–131.
[92]
Paolo Viappiani, Craig Boutilier, Regret-based optimal recommendation sets in conversational recommender systems, in: Proceedings of the 3rd ACM Conference on Recommender Systems, RecSys09, New York, 2009, pp. 101–108.
[93]
Toby Walsh, Uncertainty in preference elicitation and aggregation, in: Proceedings of the Twenty-Second National Conference on Artificial Intelligence, AAAI-07, Vancouver, 2007, pp. 672–678.
[94]
Toby Walsh, Complexity of terminating preference elicitation, in: Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS-08, Estoril, Portugal, 2008, pp. 967–974.
[95]
Tianhan Wang, Craig Boutilier, Incremental utility elicitation with the minimax regret decision criterion, in: Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03, Acapulco, 2003, pp. 309–316.
[96]
Lirong Xia, Vincent Conitzer, Determining possible and necessary winners under common voting rules given partial orders, J. Artif. Intell. Res. 41 (2011) 25–67.
[97]
Zhao, Zhibing; Li, Haoming; Wang, Junming; Kephart, Jeffrey; Mattei, Nicholas; Su, Hui; Xia, Lirong (2018): A cost-effective framework for preference elicitation and aggregation. preprint arXiv:1805.05287.

Index Terms

  1. Preference elicitation and robust winner determination for single- and multi-winner social choice
          Index terms have been assigned to the content through auto-classification.

          Recommendations

          Comments

          Please enable JavaScript to view thecomments powered by Disqus.

          Information & Contributors

          Information

          Published In

          cover image Artificial Intelligence
          Artificial Intelligence  Volume 279, Issue C
          Feb 2020
          223 pages

          Publisher

          Elsevier Science Publishers Ltd.

          United Kingdom

          Publication History

          Published: 01 February 2020

          Author Tags

          1. Social choice
          2. Voting
          3. Preference elicitation
          4. Robust optimization
          5. Partial preferences
          6. Minimax regret
          7. Decision theory

          Qualifiers

          • Research-article

          Contributors

          Other Metrics

          Bibliometrics & Citations

          Bibliometrics

          Article Metrics

          • 0
            Total Citations
          • 0
            Total Downloads
          • Downloads (Last 12 months)0
          • Downloads (Last 6 weeks)0
          Reflects downloads up to 22 Dec 2024

          Other Metrics

          Citations

          View Options

          View options

          Media

          Figures

          Other

          Tables

          Share

          Share

          Share this Publication link

          Share on social media