Nothing Special   »   [go: up one dir, main page]

skip to main content
10.5555/3398761.3398802acmconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article

Testing Axioms Against Human Reward Divisions in Cooperative Games

Published: 13 May 2020 Publication History

Abstract

Axiomatic approaches are an appealing method for designing fair algorithms, as they provide formal structure for reasoning about and rationalizing individual decisions. However, to make these algorithms useful in practice, their axioms must appropriately capture social norms. We explore this tension between fairness axioms and socially acceptable decisions in the context of cooperative game theory. We use two crowdsourced experiments to study people's impartial reward divisions in cooperative games, focusing on games that systematically vary the values of the single-player coalitions. Our results show that people select rewards that are remarkably consistent, but place much more emphasis on the single-player coalitions than the Shapley value does. Further, their reward divisions violate both the null player and additivity axioms, but support weaker axioms. We argue for a more general methodology of testing axioms against experimental data, retaining some of the conceptual simplicity of the axiomatic approach while still using people's opinions to drive the design of fair algorithms.

References

[1]
Victor H. Aguiar, Roland Pongou, and Jean-Baptiste Tondji. 2018. A non-parametric approach to testing the axioms of the Shapley value with limited data. Games and Economic Behavior111 (Sep. 2018), 41--63.
[2]
Yoram Bachrach and Jeffrey Rosenschein. 2008. Coalitional skill games. In Pro-ceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems. 1023--1030.
[3]
Sylvain Béal, Eric Rémila, and Philippe Solal. 2015. A decomposition of the spaceof TU-games using addition and transfer invariance. Discrete Applied Mathematics 184 (Mar. 2015), 1--13.
[4]
Gary E. Bolton, Kalyan Chatterjee, and Kathleen L. McGinn. 2003. How commu-nication links influence coalition bargaining: A laboratory investigation. Management Science 49, 5 (May 2003), 583--598.
[5]
Colin Camerer. 2003.Behavioural game theory: Experiments in strategic interaction. Princeton Unversity Press.
[6]
André Casajus and Frank Huettner. 2013. Null players, solidarity, and the egali-tarian Shapley values. Journal of Mathematical Economics 49, 1 (jan 2013), 58--61.
[7]
Georgios Chalkiadakis, Edith Elkind, and Michael Wooldridge. 2011. Computational aspects of cooperative game theory. Synthesis Lectures on Artificial Intelligence and Machine Learning5, 6 (2011), 1--168.
[8]
Geoffroy De Clippel and Kareen Rozen. 2013. Fairness through the lens of cooperative game theory: An experimental approach. (2013). http://cowles.econ.yale.edu/
[9]
Greg d'Eon, Joslin Goh, Kate Larson, and Edith Law. 2019. Paying Crowd Workers for Collaborative Work.Proc. ACM Hum.-Comput. Interact. 3, CSCW, Article 125(Nov. 2019), 24 pages.
[10]
Rachel Freedman, Jana Schaich Borg, Walter Sinnott-Armstrong, John P Dickerson, and Vincent Conitzer. 2018. Adapting a kidney exchange algorithm to align with human values. In Thirty-Second AAAI Conference on Artificial Intelligence.
[11]
Ya'akov (Kobi) Gal, Moshe Mash, Ariel D. Procaccia, and Yair Zick. 2016. Which is the fairest (rent division) of them all?. In Proceedings of the 2016 ACM Conference on Economics and Computation - EC '16. ACM Press, New York, New York, USA, 67--84.
[12]
Ben Green and Yiling Chen. 2019. The Principles and Limits of Algorithm-in-the-Loop Decision Making. Proc. ACM Hum.-Comput. Interact. 3, CSCW, Article 50 (Nov. 2019), 24 pages.
[13]
Yoram Halevy. 2007. Ellsberg Revisited: An Experimental Study. Econometrica 75, 2 (2007), 503--536. xarXiv: https://onlinelibrary.wiley.com/doi/pdf/10.1111/j.1468-0262.2006.00755.x
[14]
Jason S Hartford, James R Wright, and Kevin Leyton-Brown. 2016. Deep Learning for Predicting Human Strategic Behavior. In Advances in Neural Information Processing Systems 29, D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett (Eds.). Curran Associates, Inc., 2424--2432. http://papers.nips.cc/paper/6509-deep-learning-for-predicting-human-strategic-behavior.pdf
[15]
Dorothea K. Herreiner and Clemens Puppe. 2010. Inequality aversion and efficiency with ordinal and cardinal social preferences-An experimental study. Journal of Economic Behavior & Organization 76, 2 (2010), 238--253.
[16]
Dorothea K. Herreiner and Clemens D Puppe. 2009. Envy freeness in experimental fair division problems. Theory and decision 67, 1 (2009), 65--100.
[17]
Samuel Ieong and Yoav Shoham. 2005. Marginal contribution nets: A compact representation scheme for coalitional games. In Proceedings of the 6th ACM Conference on Electronic Commerce. ACM, 193--202.
[18]
Reinoud Joosten. 1996. Dynamics, equilibria, and values. Ph.D. Dissertation. Maastricht University.
[19]
James P. Kahan and Amnon Rapoport. 1977. When you don't need to join: The effects of guaranteed payoffs on bargaining in three-person cooperative games. Theory and Decision 8, 2 (1977), 97--127.
[20]
James P. Kahan and Amnon Rapoport. 1984. Theories of coalition formation. Psychology Press.
[21]
Anson Kahng, Min Kyung Lee, Ritesh Noothigattu, Ariel Procaccia, and Christos-Alexandros Psomas. 2019. Statistical Foundations of Virtual Democracy. In Proceedings of the 36th International Conference on Machine Learning (Proceedings of Machine Learning Research), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.), Vol. 97. PMLR, Long Beach, California, USA, 3173--3182. http://proceedings.mlr.press/v97/kahng19a.html
[22]
Gerhard K. Kalisch, John W. Milnor, John F. Nash, and Evan D. Nering. 1954. Some experimental n-person games. In Decision Processes, Robert M. Thrall, Clyde H. Coombs, and Robert L. Davis (Eds.). 301--327.
[23]
Min Kyung Lee and Su Baykal. 2017. Algorithmic Mediation in Group Decisions: Fairness Perceptions of Algorithmically Mediated vs. Discussion-Based Social Division. In Proceedings of the 2017 ACM Conference on Computer Supported Cooperative Work and Social Computing (CSCW '17). ACM, New York, NY, USA,1035--1048.
[24]
Min Kyung Lee, Anuraag Jain, Hea Jin Cha, Shashank Ojha, and Daniel Kusbit. 2019. Procedural Justice in Algorithmic Fairness: Leveraging Transparency and Outcome Control for Fair Algorithmic Mediation. Proc. ACM Hum.-Comput. Interact. 3, CSCW, Article 182 (Nov. 2019), 26 pages.
[25]
Min Kyung Lee, Anuraag Jain, Hea Jin Cha, Shashank Ojha, and Daniel Kusbit. 2019. Procedural Justice in Algorithmic Fairness: Leveraging Transparency and Outcome Control for Fair Algorithmic Mediation. Proc. ACM Hum.-Comput. Interact. 3, CSCW, Article Article 182 (Nov. 2019), 26 pages.
[26]
Min Kyung Lee, Daniel Kusbit, Anson Kahng, Ji Tae Kim, Xinran Yuan, Allissa Chan, Daniel See, Ritesh Noothigattu, Siheon Lee, Alexandros Psomas, and Ariel D. Procaccia. 2019. WeBuildAI: Participatory Framework for Algorithmic Governance. Proc. ACM Hum.-Comput. Interact. 3, CSCW, Article 181 (Nov. 2019), 35 pages.
[27]
Joshua Lewis, Margareta Ackerman, and Virginia de Sa. 2012. Human cluster evaluation and formal quality measures: A comparative study. In Proceedings of the Annual Meeting of the Cognitive Science Society, Vol. 34.
[28]
Marcin Malawski. 2013. Procedural values for cooperative games. International Journal of Game Theory 42, 1 (Feb. 2013), 305--324.
[29]
Michael Maschler. 1992. The bargaining set, kernel, and nucleolus. In Handbook of game theory with economic applications, Robert J. Aumann and Sergiu Hart(Eds.). Vol. 1. Elsevier, 591--667.
[30]
John F. Nash, Rosemarie Nagel, Axel Ockenfels, and Reinhard Selten. 2012. Theagencies method for coalition formation in experimental games. Proceedings of the National Academy of Sciences 109, 50 (2012), 20358--20363.
[31]
Ritesh Noothigattu, Snehalkumar S Gaikwad, Edmond Awad, Sohan Dsouza, Iyad Rahwan, Pradeep Ravikumar, and Ariel D Procaccia. 2018. A voting-based system for ethical decision making. In Thirty-Second AAAI Conference on Artificial Intelligence.
[32]
Andrzej S. Nowak and Tadeusz Radzik. 1994. A solidarity value for n-person transferable utility games. International Journal of Game Theory 23, 1 (Mar 1994),43--48 DOI http://dx.doi.org/10.1007/BF01242845
[33]
Andrzej S Nowak and Tadeusz Radzik. 1996. On convex combinations of two values. Applicationes Mathematicae 24, 1 (1996), 47--56.
[34]
Ariel Procaccia. 2020. Axioms Should Explain Solutions. In Future of Economic Design, Jean-François Laslier, Hervé Moulin, M. Remzi Sanver, and William S. Zwicker (Eds.). Springer, Forthcoming.
[35]
Tadeusz Radzik and Theo Driessen. 2013. On a family of values for TU-games generalizing the Shapley value. Mathematical Social Sciences 65, 2 (mar 2013), 105--111.
[36]
Lloyd S. Shapley. 1953. A value for n-person games. In Contributions to the Theory of Games(2nd ed.), H. Kuhn and A. W. Tucker (Eds.). Princeton Unversity Press, Princeton, 307--317. https://pdfs.semanticscholar.org/ba28/dafc77ec548d1f7d7af09c9470ae7b6752dd.pdf
[37]
René van den Brink, Yukihiko Funaki, and Yuan Ju. 2013. Reconciling marginalism with egalitarianism: consistency, monotoni city, and implementation of egalitarian Shapley values. Social Choice and Welfare 40, 3 (2013), 693--714.
[38]
Michael A. Williams. 1988. An Empirical Test of Cooperative Game Solution Concepts. Behavioral science 33, 3 (Jul 01 1988), 224. http://ezproxy.library.ubc.ca/login?url=https://search.proquest.com/docview/1301274414?accountid=14656Last updated - 2013-02-24.
[39]
James R. Wright and Kevin Leyton-Brown. 2010. Beyond equilibrium: Predicting human behavior in normal-form games. Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI-10)(2010), 901--907.
[40]
H. P. Young. 1985. Monotonic solutions of cooperative games. International Journal of Game Theory 14, 2 (Jun 1985), 65--72.
[41]
Yair Zick, Kobi Gal, Yoram Bachrach, and Moshe Mash. 2017. How to form winning coalitions in mixed human-computer settings. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 465--471.

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
AAMAS '20: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems
May 2020
2289 pages
ISBN:9781450375184

Sponsors

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 13 May 2020

Check for updates

Author Tags

  1. cooperative games
  2. human behaviour
  3. shapley value

Qualifiers

  • Research-article

Funding Sources

  • Ontario Student Assistance Program
  • NSERC

Conference

AAMAS '19
Sponsor:

Acceptance Rates

Overall Acceptance Rate 132 of 651 submissions, 20%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 34
    Total Downloads
  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 16 Nov 2024

Other Metrics

Citations

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media