Haris Aziz
Anna Bogomolnaia
Skip Abstract Section
Abstract
We consider a setting in which agents vote to choose a fair mixture of public outcomes. The agents have dichotomous preferences: Each outcome is liked or disliked by an agent. We discuss three outstanding voting rules. The Conditional Utilitarian rule, a variant of the random dictator, is strategyproof and guarantees to any group of like-minded agents an influence proportional to its size. It is easier to compute and more efficient than the familiar Random Priority rule. We show, both formally and by numerical experiments, that its inefficiency is low when the number of agents is low. The efficient Egalitarian rule protects individual agents but not coalitions. It is excludable strategyproof: An agent does not want to lie if she cannot consume outcomes she claims to dislike. The efficient Max Nash Product rule offers the strongest welfare guarantees to coalitions, which can force any outcome with a probability proportional to their size. But it even fails the excludable form of strategyproofness.
- A. Abdulkadiroğlu and T. Sönmez. 1998. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66, 3 (1998), 689--701.Google Scholar
Cross Ref
- S. Airiau, H. Aziz, I. Caragiannis, J. Kruger, J. Lang, and D. Peters. 2019. Portioning using ordinal preferences: Fairness and efficiency. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI’19).Google Scholar
- H. Aziz. 2013. Maximal recursive rule: A new social decision scheme. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence. AAAI Press, 34--40.Google Scholar
- H. Aziz. 2019. A probabilistic approach to voting, allocation, matching, and coalition formation. In The Future of Economic Design, J.-F. Laslier, H. Moulin, R. Sanver, and W. S. Zwicker (Eds.). Springer.Google Scholar
- H. Aziz, F. Brandl, F. Brandt, and M. Brill. 2018. On the tradeoff between efficiency and strategyproofness. Games Econ. Behav. 110 (2018), 1--18.Google ScholarCross Ref
- H. Aziz, F. Brandt, and M. Brill. 2013. The computational complexity of random serial dictatorship. Econ. Lett. 121, 3 (2013), 341--345.Google ScholarCross Ref
- H. Aziz, M. Brill, V. Conitzer, E. Elkind, R. Freeman, and T. Walsh. 2017. Justified representation in approval-based committee voting. Soc. Choice Welf. 48, 2 (2017), 461--485.Google ScholarCross Ref
- H. Aziz, E. Elkind, S. Huang, M. Lackner, L. Sánchez-Fernández, and P. Skowron. 2018. On the complexity of extended and proportional justified representation. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI’18). AAAI Press, 902--909.Google Scholar
- H. Aziz and P. Stursberg. 2014. A generalization of probabilistic serial to randomized social choice. In Proceedings of the 28th AAAI Conference on Artificial Intelligence. AAAI Press, 559--565.Google Scholar
- G. Benade, S. Nath, A. D. Procaccia, and N. Shah. 2017. Preference elicitation for participatory budgeting. In Proceedings of the 31st AAAI Conference on Artificial Intelligence. AAAI Press, 376--382.Google Scholar
- A. Bogomolnaia. 2018. The most ordinally egalitarian of random voting rules. J. Pub. Econ. Theor. 20, 2 (2018), 271--276.Google ScholarCross Ref
- A. Bogomolnaia and H. Moulin. 2001. A new solution to the random assignment problem. J. Econ. Theor. 100, 2 (2001), 295--328.Google ScholarCross Ref
- A. Bogomolnaia and H. Moulin. 2004. Random matching under dichotomous preferences. Econometrica 72, 1 (2004), 257--279.Google ScholarCross Ref
- A. Bogomolnaia, H. Moulin, F. Sandomirskyi, and E. Yanovskaya. 2017. Competitive division of a mixed manna. Econometrica 85, 6 (2017), 1847--1871.Google ScholarCross Ref
- A. Bogomolnaia, H. Moulin, and R. Stong. 2002. Collective choice under dichotomous preferences. Mimeo, University of Glasgow, 2002.Google Scholar
- A. Bogomolnaia, H. Moulin, and R. Stong. 2005. Collective choice under dichotomous preferences. J. Econ. Theor. 122, 2 (2005), 165--184.Google ScholarCross Ref
- F. Brandl, F. Brandt, and J. Hofbauer. 2015. Incentives for participation and abstention in probabilistic social choice. In Proceedings of the 14th International Conference on Autonomous Agents and Multi-Agent Systems. IFAAMAS, 1411--1419.Google Scholar
- F. Brandl, F. Brandt, and H. G. Seedig. 2016. Consistent probabilistic social choice. Econometrica 84, 5 (2016), 1839--1880.Google ScholarCross Ref
- F. Brandt. 2017. Rolling the dice: Recent results in probabilistic social choice. In Trends in Computational Social Choice, U. Endriss (Ed.). AI Access, Chapter 1, 3--26.Google Scholar
- Y. Cabannes. 2004. Participatory budgeting: A significant contribution to participatory democracy. Environ. Urbaniz. 16, 1 (2004), 27--46.Google ScholarCross Ref
- I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang. 2016. The unreasonable fairness of maximum Nash welfare. In Proceedings of the 17th ACM Conference on Economics and Computation (EC’16). 305--322.Google Scholar
- T. Driessen. 1988. Cooperative Games, Solutions and Applications. Kluwer.Google Scholar
- C. Duddy. 2015. Fair sharing under dichotomous preferences. Math. Soc. Sci. 73 (2015), 1--5.Google ScholarCross Ref
- B. Fain, A. Goel, and K. Munagala. 2016. The core of the participatory budgeting problem. In Proceedings of the 12th International Conference on Web and Internet Economics (WINE’16). 384--399.Google Scholar
- P. Faliszewski, P. Skowron, A. Slinko, and N. Talmon. 2017. Multiwinner voting: A new challenge for social choice theory. In Trends in Computational Social Choice, U. Endriss (Ed.). Chapter 2.Google Scholar
- P. C. Fishburn. 1984. Probabilistic social choice based on simple voting comparisons. Rev. Econ. Stud. 51, 4 (1984), 683--692.Google ScholarCross Ref
- P. C. Fishburn and S. J. Brams. 1983. Paradoxes of preferential voting. Math. Mag. 56, 4 (1983), 207--214.Google ScholarCross Ref
- T. FluschnikP. Skowron, M. Triphaus and K. Wilker. 2019. Fair knapsack. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence. AAAI, 1941--1948.Google Scholar
- A. Gibbard. 1977. Manipulation of schemes that mix voting with chance. Econometrica 45, 3 (1977), 665--681.Google ScholarCross Ref
- J. Gordon. 1994. Institutions as relational investors: A new look at cumulative voting. Colum. Law Rev. 94, 1 (1994), 124--192.Google ScholarCross Ref
- U. Grandi. 2017. Agent-mediated social choice. In The Future of Economic Design, J. F. Laslier, H. Moulin, R. Sanver, and W. Zwicker (Eds.). Springer.Google Scholar
- J. Hughes and G. Sasse. 2003. Monitoring the monitors: EU enlargement conditionality and minority protection in the CEECs. J. Ethnopol. Minor. Iss. Eur. 1 (2003), 35.Google Scholar
- G. Laffond, J.-F. Laslier, and M. Le Breton. 1993. The bipartisan set of a tournament game. Games Econ. Behav. 5, 1 (1993), 182--201.Google ScholarCross Ref
- M. Michorzewski, D. Peters, and P. Skowron. 2020. Price of fairness in budget division and probabilistic social choice. In Proceedings of the 34rd AAAI Conference on Artificial Intelligence. AAAI.Google Scholar
- H. Moulin. 1981. The proportional veto principle. Rev. Econ. Stud. 48, 3 (1981).Google ScholarCross Ref
- H. Moulin. 1982. Voting with proportional veto power. Econometrica 50, 1 (1982), 145--162.Google ScholarCross Ref
- H. Moulin. 1988. Axioms of Cooperative Decision Making. Cambridge University Press, UK.Google Scholar
- H. Moulin. 2003. Fair Division and Collective Welfare. The MIT Press, Cambridge, MA.Google Scholar
- H. Moulin. 2019. Fair division in the Internet age. Ann. Rev. Econ. 11 (2019), 1--37.Google ScholarCross Ref
- J. F. Nash. 1950. The bargaining problem. Econometrica 18, 2 (1950), 155--162.Google ScholarCross Ref
- R. La Porta, F. Lopez de Silanes, A. Schleifer, and R. Vishny. 2000. Investor protection and corporate governance. J. Finan. Econ. 58, 1--2 (2000), 3--27.Google ScholarCross Ref
- J. Sawyer and D. MacRae. 1962. Game theory and cumulative voting in illinois: 1902--1954. Amer. Polit. Sci. Rev. 56, 4 (1962), 936--946.Google ScholarCross Ref
- H. Steinhaus. 1948. The problem of fair division. Econometrica 16 (1948), 101--104.Google Scholar
- W. Thomson. 2016. Introduction to the theory of fair allocation. In Handbook of Computational Social Choice, F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia (Eds.). Cambridge University Press, Chapter 11.Google Scholar
- H. R. Varian. 1974. Equity, envy, and efficiency. J. Econ. Theor. 9 (1974), 63--91.Google ScholarCross Ref
- V. V. Vazirani. 2012. Rational convex programs and efficient algorithms for 2-player Nash and nonsymmetric bargaining games. SIAM J. Disc. Math. 26, 3 (2012), 896--918.Google ScholarCross Ref
- G. Young. 1950. The case for cumulative voting. Wisc. Law Rev. 49--56 (1950).Google Scholar
Index Terms
- Fair Mixing: The Case of Dichotomous Preferences
Recommendations
Fair Mixing: the Case of Dichotomous Preferences
EC '19: Proceedings of the 2019 ACM Conference on Economics and ComputationWe consider a setting in which agents vote to choose a fair mixture of public outcomes. The agents have dichotomous preferences: each outcome is liked or disliked by an agent. We discuss three outstanding voting rules. The Conditional Utilitarian rule, ...
An options-based solution to the sequential auction problem
The sequential auction problem is commonplace in open, electronic marketplaces such as eBay. This is the problem where a buyer has no dominant strategy in bidding across multiple auctions when the buyer would have a simple, truth-revealing strategy if ...
How Bad is Selfish Doodle Voting?
AAMAS '18: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent SystemsDoodle polls allow people to schedule meetings or events based on the time preferences of participants. Each participant indicates on a web-based poll form which time slots they find acceptable and a time slot with the most votes is chosen. This is a ...
Comments