IDEAS home Printed from https://ideas.repec.org/a/spr/jogath/v44y2015i4p903-932.html
   My bibliography  Save this article

Evolutionary dynamics and equitable core selection in assignment games

Author

Listed:
  • Heinrich Nax

    ()

  • Bary Pradelski

    ()

Abstract

We study evolutionary dynamics in assignment games where many agents interact anonymously at virtually no cost. The process is decentralized, very little information is available and trade takes place at many different prices simultaneously. We propose a completely uncoupled learning process that selects a subset of the core of the game with a natural equity interpretation. This happens even though agents have no knowledge of other agents’ strategies, payoffs, or the structure of the game, and there is no central authority with such knowledge either. In our model, agents randomly encounter other agents, make bids and offers for potential partnerships and match if the partnerships are profitable. Equity is favored by our dynamics because it is more stable, not because of any ex ante fairness criterion. Copyright Springer-Verlag Berlin Heidelberg 2015

Suggested Citation

  • Heinrich Nax & Bary Pradelski, 2015. "Evolutionary dynamics and equitable core selection in assignment games," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(4), pages 903-932, November.
  • Handle: RePEc:spr:jogath:v:44:y:2015:i:4:p:903-932
    DOI: 10.1007/s00182-014-0459-1
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s00182-014-0459-1
    Download Restriction: Access to full text is restricted to subscribers.

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Klaus, Bettina & Klijn, Flip & Walzl, Markus, 2010. "Stochastic stability for roommate markets," Journal of Economic Theory, Elsevier, vol. 145(6), pages 2218-2240, November.
    2. Chung, Kim-Sau, 2000. "On the Existence of Stable Roommate Matchings," Games and Economic Behavior, Elsevier, vol. 33(2), pages 206-230, November.
    3. Newton, Jonathan & Sawa, Ryoji, 2015. "A one-shot deviation principle for stability in matching problems," Journal of Economic Theory, Elsevier, vol. 157(C), pages 1-27.
    4. E. Inarra & C. Larrea & E. Molis, 2008. "Random paths to P-stability in the roommate problem," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 461-471, March.
    5. Klaus, Bettina & Klijn, Flip, 2007. "Paths to stability for matching markets with couples," Games and Economic Behavior, Elsevier, vol. 58(1), pages 154-171, January.
    6. Agastya, Murali, 1999. "Perturbed Adaptive Dynamics in Coalition Form Games," Journal of Economic Theory, Elsevier, vol. 89(2), pages 207-233, December.
    7. Crawford, Vincent P & Knoer, Elsie Marie, 1981. "Job Matching with Heterogeneous Firms and Workers," Econometrica, Econometric Society, vol. 49(2), pages 437-450, March.
    8. Demange, Gabrielle & Gale, David, 1985. "The Strategy Structure of Two-sided Matching Markets," Econometrica, Econometric Society, vol. 53(4), pages 873-888, July.
    9. Sawa, Ryoji, 2014. "Coalitional stochastic stability in games, networks and markets," Games and Economic Behavior, Elsevier, vol. 88(C), pages 90-111.
    10. M. L. Balinski, 1965. "Integer Programming: Methods, Uses, Computations," Management Science, INFORMS, vol. 12(3), pages 253-313, November.
    11. Nash, John, 1950. "The Bargaining Problem," Econometrica, Econometric Society, vol. 18(2), pages 155-162, April.
    12. Young, H Peyton, 1993. "The Evolution of Conventions," Econometrica, Econometric Society, vol. 61(1), pages 57-84, January.
    13. Rochford, Sharon C., 1984. "Symmetrically pairwise-bargained allocations in an assignment market," Journal of Economic Theory, Elsevier, vol. 34(2), pages 262-281, December.
    14. Iñarra, E. & Larrea, C. & Molis, E., 2013. "Absorbing sets in roommate problems," Games and Economic Behavior, Elsevier, vol. 81(C), pages 165-178.
    15. Selten, Reinhard & Stoecker, Rolf, 1986. "End behavior in sequences of finite Prisoner's Dilemma supergames A learning theory approach," Journal of Economic Behavior & Organization, Elsevier, vol. 7(1), pages 47-70, March.
    16. Diamantoudi, Effrosyni & Miyagawa, Eiichi & Xue, Licun, 2004. "Random paths to stability in the roommate problem," Games and Economic Behavior, Elsevier, vol. 48(1), pages 18-28, July.
    17. Foster, Dean P. & Young, H. Peyton, 2006. "Regret testing: learning to play Nash equilibrium without knowing you have an opponent," Theoretical Economics, Econometric Society, vol. 1(3), pages 341-367, September.
    18. Francesc Llerena & Marina Nunez, 2011. "A geometric characterization of the nucleolus of the assignment game," Economics Bulletin, AccessEcon, vol. 31(4), pages 3275-3285.
    19. Kandori, Michihiro & Mailath, George J & Rob, Rafael, 1993. "Learning, Mutation, and Long Run Equilibria in Games," Econometrica, Econometric Society, vol. 61(1), pages 29-56, January.
    20. Pradelski, Bary S.R. & Young, H. Peyton, 2012. "Learning efficient Nash equilibria in distributed systems," Games and Economic Behavior, Elsevier, vol. 75(2), pages 882-897.
    21. Bo Chen & Satoru Fujishige & Zaifu Yang, 2010. "Decentralized Market Processes to Stable Job Matchings with Competitive Salaries," KIER Working Papers 749, Kyoto University, Institute of Economic Research.
    22. Germano, Fabrizio & Lugosi, Gabor, 2007. "Global Nash convergence of Foster and Young's regret testing," Games and Economic Behavior, Elsevier, vol. 60(1), pages 135-154, July.
    23. Murali Agastya, 1997. "Adaptive Play in Multiplayer Bargaining Situations," Review of Economic Studies, Oxford University Press, vol. 64(3), pages 411-426.
    24. Rozen, Kareen, 2013. "Conflict leads to cooperation in demand bargaining," Journal of Economic Behavior & Organization, Elsevier, vol. 87(C), pages 35-42.
    25. Demange, Gabrielle & Gale, David & Sotomayor, Marilda, 1986. "Multi-Item Auctions," Journal of Political Economy, University of Chicago Press, vol. 94(4), pages 863-872, August.
    26. Solymosi, Tamas & Raghavan, Tirukkannamangai E S, 1994. "An Algorithm for Finding the Nucleolus of Asignment Games," International Journal of Game Theory, Springer;Game Theory Society, vol. 23(2), pages 119-143.
    27. Roth, Alvin E & Vande Vate, John H, 1990. "Random Paths to Stability in Two-Sided Matching," Econometrica, Econometric Society, vol. 58(6), pages 1475-1480, November.
    28. Sotomayor, Marilda, 2003. "Some further remark on the core structure of the assignment game," Mathematical Social Sciences, Elsevier, vol. 46(3), pages 261-265, December.
    29. Bettina Klaus & Frédéric Payot, 2013. "Paths to Stability in the Assignment Problem," Cahiers de Recherches Economiques du Département d'Econométrie et d'Economie politique (DEEP) 13.14, Université de Lausanne, Faculté des HEC, DEEP.
    30. Kelso, Alexander S, Jr & Crawford, Vincent P, 1982. "Job Matching, Coalition Formation, and Gross Substitutes," Econometrica, Econometric Society, vol. 50(6), pages 1483-1504, November.
    31. Arnold, Tone & Schwalbe, Ulrich, 2002. "Dynamic coalition formation and the core," Journal of Economic Behavior & Organization, Elsevier, vol. 49(3), pages 363-380, November.
    32. Newton, Jonathan, 2012. "Recontracting and stochastic stability in cooperative games," Journal of Economic Theory, Elsevier, vol. 147(1), pages 364-381.
    33. Young, H. Peyton, 2009. "Learning by trial and error," Games and Economic Behavior, Elsevier, vol. 65(2), pages 626-643, March.
    34. Fuhito Kojima & M. Ünver, 2008. "Random paths to pairwise stability in many-to-many matching problems: a study on market equilibration," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 473-488, March.
    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. Nax, Heinrich H., 2015. "Equity dynamics in bargaining without information exchange," LSE Research Online Documents on Economics 65426, London School of Economics and Political Science, LSE Library.
    2. repec:jmi:articl:jmi-v2i1a1 is not listed on IDEAS
    3. Klaus, Bettina & Newton, Jonathan, 2016. "Stochastic stability in assignment problems," Journal of Mathematical Economics, Elsevier, vol. 62(C), pages 62-74.
    4. Alós-Ferrer, Carlos & Buckenmaier, Johannes, 2017. "Trader matching and the selection of market institutions," Journal of Mathematical Economics, Elsevier, vol. 69(C), pages 118-127.
    5. repec:gam:jgames:v:7:y:2016:i:2:p:10:d:66888 is not listed on IDEAS
    6. Bolle Friedel & Otto Philipp E., 2016. "Matching as a Stochastic Process," Journal of Economics and Statistics (Jahrbuecher fuer Nationaloekonomie und Statistik), De Gruyter, vol. 236(3), pages 323-348, May.
    7. Heinrich H. Nax & Bary S. R. Pradelski, 2016. "Core Stability and Core Selection in a Decentralized Labor Matching Market," Games, MDPI, Open Access Journal, vol. 7(2), pages 1-16, March.
    8. Heinrich Nax, 2015. "Equity dynamics in bargaining without information exchange," Journal of Evolutionary Economics, Springer, vol. 25(5), pages 1011-1026, November.

    More about this item

    Keywords

    Assignment games; Cooperative games; Core; Equity; Evolutionary game theory; Learning; Matching markets; Stochastic stability; C71; C73; C78; D83;

    JEL classification:

    • C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games
    • C73 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Stochastic and Dynamic Games; Evolutionary Games
    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
    • D83 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Search; Learning; Information and Knowledge; Communication; Belief; Unawareness

    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:spr:jogath:v:44:y:2015:i:4:p:903-932. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Sonal Shukla) or (Rebekah McClure). General contact details of provider: http://www.springer.com .

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.