research-article

Behavioral experiments on a network formation game

Authors:

Michael Kearns,

Yevgeniy VorobeychikAuthors Info & Claims

EC '12: Proceedings of the 13th ACM Conference on Electronic Commerce

Pages 690 - 704

https://doi.org/10.1145/2229012.2229066

Published: 04 June 2012 Publication History

Abstract

We report on an extensive series of behavioral experiments in which 36 human subjects collectively build a communication network over which they must solve a competitive coordination task for monetary compensation. There is a cost for creating network links, thus creating a tension between link expenditures and collective and individual incentives. Our most striking finding is the poor performance of the subjects, especially compared to our long series of prior experiments. We demonstrate that the subjects built difficult networks for the coordination task, and compare the structural properties of the built networks to standard generative models of social networks. We also provide extensive analysis of the individual and collective behavior of the subjects, including free riding and factors influencing edge purchasing decisions.

References

[1]

Albers, S., Eilts, S., Even-Dar, E., Mansour, Y., and Roddity, L. 2006. On Nash equilibria for a network creation game. In Symposium on Discrete Algorithms (SODA).

Digital Library

[2]

Barabasi, L. and Albert, R. 1999. Emergence of scaling in random networks. Science 286, 509--512.

[3]

Bollabas, B. 2001. Random Graphs. Cambridge University Press.

[4]

Borgs, C., Chayes, J., Ding, J., and Lucier, B. 2011. The hitchhiker's guide to affiliation networks: A game-theoretic approach. In Innovations in Theoretical Computer Science (ITCS).

[5]

Brautbar, M. and Kearns, M. 2011. A clustering coefficient network formation game. In Symposium on Algorithmic Game Theory (SAGT).

Digital Library

[6]

Burns, T. and Stalker, G. 1994. The Management of Innovation. Oxford University Press.

[7]

Chakraborty, T., Judd, J. S., Kearns, M., and Tan, J. 2010. A behavioral study of bargaining in social networks. In ACM Conference on Electronic Commerce. 243--252.

Digital Library

[8]

Even-Dar, E. and Kearns, M. 2006. A small world threshold for economic network formation. In Neural Information Processing Systems (NIPS).

[9]

Even-Dar, E., Kearns, M., and Suri, S. 2007. A network formation game for bipartite exchange economies. In Symposium on Discrete Algorithms (SODA).

Digital Library

[10]

Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C., and Shenker, S. 2003. On a network creation game. In Principles of Distributed Computing (PODC).

Digital Library

[11]

Jackson, M. O. 2005. A survey of models of network formation: stability and efficiency. In Group Formation in Economics: Networks, Clubs and Coalitions. Cambridge University Press.

[12]

Jackson, M. O. 2010. Social and Economic Networks. Princeton University Press.

Digital Library

[13]

Judd, S., Kearns, M., and Vorobeychik, Y. 2010. Behavioral dynamics and influence in networked coloring and consensus. Proceedings of the National Academy of Sciences 107, 34, 14978--14982.

[14]

Kearns, M. and Judd, J. S. 2008. Behavioral experiments in networked trade. In ACM Conference on Electronic Commerce. 150--159.

Digital Library

[15]

Kearns, M., Judd, S., Tan, J., and Wortman, J. 2009. Behavioral experiments in biased voting in networks. Proceedings of the National Academy of Sciences 106, 5, 1347--1352.

[16]

Kearns, M., Judd, S., and Vorobeychik, Y. 2011. Behavioral conflict and fairness in social networks. In Workshop on Internet and Network Economics.

Digital Library

[17]

Kearns, M., Suri, S., and Montfort, N. 2006. An experimental study of the coloring problem on human subject networks. Science 313, 824--827.

[18]

Kleinberg, J. 2000. Navigation in a small world. Nature 406, 845.

[19]

Nishiguchi, T. and Beaudet, A. 2000. Fractal design: Self-organizing links in supply chain management. In Knowledge Creation: A Source of Value, G. von Krogh et. al., Ed. St. Martin's Press, 199--230.

[20]

Tardos, E. and Wexler, T. 2007. Network formation games and the potential function method. In Algorithmic Game Theory. Cambridge University Press, 487--513.

[21]

Watts, D. and Strogatz, S. 1998. Collective dynamics of small-world networks. Nature 393, 409--410.

Cited By

Arya PSrivastava N(2025)Characterizing the roles of preference homophily and network structure on outcomes of consensus gamesComputational and Mathematical Organization Theory10.1007/s10588-025-09396-3Online publication date: 23-Jan-2025
https://doi.org/10.1007/s10588-025-09396-3
Liu XHu ZDeng XKuhlman C(2023)A Calibration Model For Bot-Like Behaviors In Agent-Based Anagram Game Simulation2023 Winter Simulation Conference (WSC)10.1109/WSC60868.2023.10408394(221-232)Online publication date: 10-Dec-2023
https://doi.org/10.1109/WSC60868.2023.10408394
Arya PSrivastava N(2023)Understanding Clique Formation in Social Networks - An Agent-Based Model of Social Preferences in Fixed and Dynamic NetworksSocial, Cultural, and Behavioral Modeling10.1007/978-3-031-43129-6_23(231-240)Online publication date: 16-Sep-2023
https://doi.org/10.1007/978-3-031-43129-6_23
Show More Cited By

Index Terms

Behavioral experiments on a network formation game
1. Applied computing
  1. Law, social and behavioral sciences

Recommendations

Prisoner's Dilemma Game on Network
Multi-Agent Systems for Society

We study on the Prisoner's Dilemma game on network to clarify the influence of the network structures on agent strategies, and vice versa. A model is proposed to treat an interaction between the agent strategies and the network formation process. In ...
Game theoretic models for social network analysis
WWW '11: Proceedings of the 20th international conference companion on World wide web

The existing methods and techniques for social network analysis are inadequate to capture both the behavior (such as rationality and intelligence) of individuals and the strategic interactions that occur among these individuals. Game theory is a natural ...
Strategic complementarities, network games and endogenous network formation
Abstract
This paper investigates the role of strategic complementarities in the context of network games and network formation models. In the general model of static games on networks, we characterize conditions on the utility function that ensure the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '12: Proceedings of the 13th ACM Conference on Electronic Commerce

June 2012

1016 pages

ISBN:9781450314152

DOI:10.1145/2229012

General Chair:
Boi Faltings
École Polytechnique Fédérale de Lausanne (EPFL)
,
Program Chairs:
Kevin Leyton-Brown
University of British Columbia
,
Panos Ipeirotis
New York University

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 June 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EC '12

Sponsor:

SIGecom

EC '12: ACM Conference on Electronic Commerce

June 4 - 8, 2012

Valencia, Spain

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25

Sponsor:
sigecom

The 25th ACM Conference on Economics and Computation

July 7 - 11, 2025

Stanford , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
291
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)2

Reflects downloads up to 22 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Arya PSrivastava N(2025)Characterizing the roles of preference homophily and network structure on outcomes of consensus gamesComputational and Mathematical Organization Theory10.1007/s10588-025-09396-3Online publication date: 23-Jan-2025
https://doi.org/10.1007/s10588-025-09396-3
Liu XHu ZDeng XKuhlman C(2023)A Calibration Model For Bot-Like Behaviors In Agent-Based Anagram Game Simulation2023 Winter Simulation Conference (WSC)10.1109/WSC60868.2023.10408394(221-232)Online publication date: 10-Dec-2023
https://doi.org/10.1109/WSC60868.2023.10408394
Arya PSrivastava N(2023)Understanding Clique Formation in Social Networks - An Agent-Based Model of Social Preferences in Fixed and Dynamic NetworksSocial, Cultural, and Behavioral Modeling10.1007/978-3-031-43129-6_23(231-240)Online publication date: 16-Sep-2023
https://doi.org/10.1007/978-3-031-43129-6_23
Grigoryan GEtemadidavan SCollins A(2022)Computerized agents versus human agents in finding core coalition in glove gamesSIMULATION10.1177/00375497221093652(003754972210936)Online publication date: 8-May-2022
https://doi.org/10.1177/00375497221093652
Takko TBhattacharya KMonsivais DKaski K(2021)Human-agent coordination in a group formation gameScientific Reports10.1038/s41598-021-90123-811:1Online publication date: 24-May-2021
https://doi.org/10.1038/s41598-021-90123-8
Riedl ARohde IStrobel M(2021)Free neighborhood choice boosts socially optimal outcomes in stag-hunt coordination problemScientific Reports10.1038/s41598-021-87019-y11:1Online publication date: 8-Apr-2021
https://doi.org/10.1038/s41598-021-87019-y
Cedeno-Mieles VHu ZRen YDeng XContractor NEkanayake SEpstein JGoode BKorkmaz GKuhlman CMachi DMacy MMarathe MRamakrishnan NSaraf PSelf N(2020)Data analysis and modeling pipelines for controlled networked social science experimentsPLOS ONE10.1371/journal.pone.024245315:11(e0242453)Online publication date: 24-Nov-2020
https://doi.org/10.1371/journal.pone.0242453
Almaatouq ANoriega-Campero AAlotaibi AKrafft PMoussaid MPentland A(2020)Adaptive social networks promote the wisdom of crowdsProceedings of the National Academy of Sciences10.1073/pnas.1917687117117:21(11379-11386)Online publication date: 11-May-2020
https://doi.org/10.1073/pnas.1917687117
Cedeno-Mieles VHu ZRen YDeng XAdiga ABarrett CContractor NEkanayake SEpstein JGoode BKorkmaz GKuhlman CMachi DMacy MMarathe MRamakrishnan NRavi SSaraf PSelf N(2020)Networked experiments and modeling for producing collective identity in a group of human subjects using an iterative abduction frameworkSocial Network Analysis and Mining10.1007/s13278-019-0620-810:1Online publication date: 7-Jan-2020
https://doi.org/10.1007/s13278-019-0620-8
Goyal SHernández PMartínez-Cánovas GMoisan FMuñoz-Herrera MSánchez A(2020)Integration and diversityExperimental Economics10.1007/s10683-020-09676-6Online publication date: 10-Sep-2020
https://doi.org/10.1007/s10683-020-09676-6
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten