IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0041900.html
   My bibliography  Save this article

Human Matching Behavior in Social Networks: An Algorithmic Perspective

Author

Listed:
  • Lorenzo Coviello
  • Massimo Franceschetti
  • Mathew D McCubbins
  • Ramamohan Paturi
  • Andrea Vattani

Abstract

We argue that algorithmic modeling is a powerful approach to understanding the collective dynamics of human behavior. We consider the task of pairing up individuals connected over a network, according to the following model: each individual is able to propose to match with and accept a proposal from a neighbor in the network; if a matched individual proposes to another neighbor or accepts another proposal, the current match will be broken; individuals can only observe whether their neighbors are currently matched but have no knowledge of the network topology or the status of other individuals; and all individuals have the common goal of maximizing the total number of matches. By examining the experimental data, we identify a behavioral principle called prudence, develop an algorithmic model, analyze its properties mathematically and by simulations, and validate the model with human subject experiments for various network sizes and topologies. Our results include i) a -approximate maximum matching is obtained in logarithmic time in the network size for bounded degree networks; ii) for any constant , a -approximate maximum matching is obtained in polynomial time, while obtaining a maximum matching can require an exponential time; and iii) convergence to a maximum matching is slower on preferential attachment networks than on small-world networks. These results allow us to predict that while humans can find a “good quality” matching quickly, they may be unable to find a maximum matching in feasible time. We show that the human subjects largely abide by prudence, and their collective behavior is closely tracked by the above predictions.

Suggested Citation

  • Lorenzo Coviello & Massimo Franceschetti & Mathew D McCubbins & Ramamohan Paturi & Andrea Vattani, 2012. "Human Matching Behavior in Social Networks: An Algorithmic Perspective," PLOS ONE, Public Library of Science, vol. 7(8), pages 1-9, August.
  • Handle: RePEc:plo:pone00:0041900
    DOI: 10.1371/journal.pone.0041900
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0041900
    Download Restriction: no

    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0041900&type=printable
    Download Restriction: no

    File URL: https://libkey.io/10.1371/journal.pone.0041900?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. John William Hatfield & Scott Duke Kominers, 2012. "Matching in Networks with Bilateral Contracts," American Economic Journal: Microeconomics, American Economic Association, vol. 4(1), pages 176-208, February.
    2. Daniel Kahneman & Amos Tversky, 2013. "Prospect Theory: An Analysis of Decision Under Risk," World Scientific Book Chapters, in: Leonard C MacLean & William T Ziemba (ed.), HANDBOOK OF THE FUNDAMENTALS OF FINANCIAL DECISION MAKING Part I, chapter 6, pages 99-127, World Scientific Publishing Co. Pte. Ltd..
    3. Siddharth Suri & Duncan J Watts, 2011. "Cooperation and Contagion in Web-Based, Networked Public Goods Experiments," PLOS ONE, Public Library of Science, vol. 6(3), pages 1-18, March.
    4. Unknown, 1986. "Letters," Choices: The Magazine of Food, Farm, and Resource Issues, Agricultural and Applied Economics Association, vol. 1(4), pages 1-9.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Mao, Fubing & Ma, Lijia & He, Qiang & Xiao, Gaoxi, 2020. "Match making in complex social networks," Applied Mathematics and Computation, Elsevier, vol. 371(C).
    2. Tao Jia & Robert F Spivey & Boleslaw Szymanski & Gyorgy Korniss, 2015. "An Analysis of the Matching Hypothesis in Networks," PLOS ONE, Public Library of Science, vol. 10(6), pages 1-12, June.
    3. Vanessa Cedeno-Mieles & Zhihao Hu & Yihui Ren & Xinwei Deng & Noshir Contractor & Saliya Ekanayake & Joshua M Epstein & Brian J Goode & Gizem Korkmaz & Chris J Kuhlman & Dustin Machi & Michael Macy & , 2020. "Data analysis and modeling pipelines for controlled networked social science experiments," PLOS ONE, Public Library of Science, vol. 15(11), pages 1-58, November.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Attema, Arthur E. & Brouwer, Werner B.F., 2012. "A test of independence of discounting from quality of life," Journal of Health Economics, Elsevier, vol. 31(1), pages 22-34.
    2. Christoph Bühren & Thorben C. Kundt, 2013. "Worker or Shirker – Who Evades More Taxes? A Real Effort Experiment," MAGKS Papers on Economics 201326, Philipps-Universität Marburg, Faculty of Business Administration and Economics, Department of Economics (Volkswirtschaftliche Abteilung).
    3. Vadym Lepetyuk & Christian A. Stoltenberg, 2012. "Reconciling consumption inequality with income inequality," Working Papers. Serie AD 2012-19, Instituto Valenciano de Investigaciones Económicas, S.A. (Ivie).
    4. Fortin, Bernard & Lacroix, Guy & Villeval, Marie-Claire, 2007. "Tax evasion and social interactions," Journal of Public Economics, Elsevier, vol. 91(11-12), pages 2089-2112, December.
    5. Amedeo Piolatto & Matthew D. Rablen, 2017. "Prospect theory and tax evasion: a reconsideration of the Yitzhaki puzzle," Theory and Decision, Springer, vol. 82(4), pages 543-565, April.
    6. James Alm & Antoine Malézieux, 2021. "40 years of tax evasion games: a meta-analysis," Experimental Economics, Springer;Economic Science Association, vol. 24(3), pages 699-750, September.
    7. Garbarino, Ellen & Slonim, Robert & Villeval, Marie Claire, 2019. "Loss aversion and lying behavior," Journal of Economic Behavior & Organization, Elsevier, vol. 158(C), pages 379-393.
    8. Cropper, Maureen L & Oates, Wallace E, 1992. "Environmental Economics: A Survey," Journal of Economic Literature, American Economic Association, vol. 30(2), pages 675-740, June.
    9. Gold, Natalie, 2020. "How should we reconcile self-regarding and pro-social motivations? A renaissance of “Das Adam Smith Problem”," LSE Research Online Documents on Economics 109218, London School of Economics and Political Science, LSE Library.
    10. Ola Andersson & Jim Ingebretsen Carlson & Erik Wengström, 2021. "Differences Attract: An Experimental Study of Focusing in Economic Choice," The Economic Journal, Royal Economic Society, vol. 131(639), pages 2671-2692.
    11. Luigi Mittone, 2002. "Individual styles of tax evasion: an experimental study," CEEL Working Papers 0202, Cognitive and Experimental Economics Laboratory, Department of Economics, University of Trento, Italia.
    12. Nigar Hashimzade & Gareth Myles, 2017. "Risk-based Audits in a Behavioral Model," Public Finance Review, , vol. 45(1), pages 140-165, January.
    13. Natalie Gold, 2019. "The limits of commodification arguments: Framing, motivation crowding, and shared valuations," Politics, Philosophy & Economics, , vol. 18(2), pages 165-192, May.
    14. Klaus Abbink & Heike Hennig-Schmidt, 2006. "Neutral versus loaded instructions in a bribery experiment," Experimental Economics, Springer;Economic Science Association, vol. 9(2), pages 103-121, June.
    15. Bradley Jones, 2015. "Asset Bubbles: Re-thinking Policy for the Age of Asset Management," IMF Working Papers 2015/027, International Monetary Fund.
    16. Piergiorgio Alessandri, 2004. "Aggregate Consumption and the Stock Market: Should We Worry about Non-linear Wealth Effects?," Birkbeck Working Papers in Economics and Finance 0410, Birkbeck, Department of Economics, Mathematics & Statistics.
    17. Ellen Garbarino & Robert Slonim & Marie Claire Villeval, 2016. "Loss Aversion and lying behavior: Theory, estimation and empirical evidence," Working Papers halshs-01404333, HAL.
    18. Matthew D. Rablen, 2010. "Tax Evasion and Exchange Equity: A Reference-Dependent Approach," Public Finance Review, , vol. 38(3), pages 282-305, May.
    19. Pántya, József & Kovács, Judit & Kogler, Christoph & Kirchler, Erich, 2016. "Work performance and tax compliance in flat and progressive tax systems," Journal of Economic Psychology, Elsevier, vol. 56(C), pages 262-273.
    20. Marc Willinger, 1990. "La rénovation des fondements de l'utilité et du risque," Revue Économique, Programme National Persée, vol. 41(1), pages 5-48.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pone00:0041900. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.