IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v350y2025i3d10.1007_s10479-016-2198-0.html
   My bibliography  Save this article

Evolutionary coalitional games for random access control

Author

Listed:
  • Xin Luo

    (Hong Kong University of Science and Technology)

  • Hamidou Tembine

    (New York University Abu Dhabi)

Abstract

This paper considers a random access system with several users and one shared medium. Each user has its own queue (of packets) which can be empty or not. We propose an evolving coalitional game between the users and analyze the system outcomes. Unlike classical coalitional approaches that assume that coalitional structures are fixed and formed cost-free, we explain how coalitions can be formed in a fully distributed manner using evolutionary dynamics and coalitional combined fully distributed payoff and strategy (CODIPAS) learning. We introduce the concept of evolutionarily stable coalitional structure (ESCS), which, when it is formed, is resilient to small perturbation of strategies. We show that (1) the formation and the stability of coalitions depend mainly on the cost of making a coalition compared to the benefit of cooperation, (2) the grand coalition can be unstable and a localized coalitional structure is formed as an evolutionarily stable coalitional structure. When the core is empty, the coalitional CODIPAS scheme selects one element of the stable set. Finally, we discuss the convergence and complexity of the proposed coalitional learning in access control with different users’ activities. Some extensions to cognitive medium access control with queue management are provided.

Suggested Citation

  • Xin Luo & Hamidou Tembine, 2025. "Evolutionary coalitional games for random access control," Annals of Operations Research, Springer, vol. 350(3), pages 1075-1108, July.
    • Handle: RePEc:spr:annopr:v:350:y:2025:i:3:d:10.1007_s10479-016-2198-0
    DOI: 10.1007/s10479-016-2198-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-016-2198-0
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-016-2198-0?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
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Roth, Alvin E. & Erev, Ido, 1995. "Learning in extensive-form games: Experimental data and simple dynamic models in the intermediate term," Games and Economic Behavior, Elsevier, vol. 8(1), pages 164-212.
    2. AUMANN, Robert J. & DREZE, Jacques H., 1974. "Cooperative games with coalition structures," LIDAM Reprints CORE 217, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. J. Drechsel & A. Kimms, 2010. "The subcoalition-perfect core of cooperative games," Annals of Operations Research, Springer, vol. 181(1), pages 591-601, December.
    Full references (including those not matched with items on IDEAS)

    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. Terry E. Daniel & Eyran J. Gisches & Amnon Rapoport, 2009. "Departure Times in Y-Shaped Traffic Networks with Multiple Bottlenecks," American Economic Review, American Economic Association, vol. 99(5), pages 2149-2176, December.
    2. Ianni, A., 2002. "Reinforcement learning and the power law of practice: some analytical results," Discussion Paper Series In Economics And Econometrics 203, Economics Division, School of Social Sciences, University of Southampton.
    3. Antonio Magaña & Francesc Carreras, 2018. "Coalition Formation and Stability," Group Decision and Negotiation, Springer, vol. 27(3), pages 467-502, June.
    4. Grabisch, Michel & Sudhölter, Peter, 2018. "On a class of vertices of the core," Games and Economic Behavior, Elsevier, vol. 108(C), pages 541-557.
    5. repec:osf:osfxxx:9vm5t_v1 is not listed on IDEAS
    6. Colin F. Camerer, 1997. "Progress in Behavioral Game Theory," Journal of Economic Perspectives, American Economic Association, vol. 11(4), pages 167-188, Fall.
    7. Sun, Ning & Trockel, Walter & Yang, Zaifu, 2008. "Competitive outcomes and endogenous coalition formation in an n-person game," Journal of Mathematical Economics, Elsevier, vol. 44(7-8), pages 853-860, July.
    8. Thorsten Chmura & Thomas Pitz, 2007. "An Extended Reinforcement Algorithm for Estimation of Human Behaviour in Experimental Congestion Games," Journal of Artificial Societies and Social Simulation, Journal of Artificial Societies and Social Simulation, vol. 10(2), pages 1-1.
    9. Sylvain Béal & Mostapha Diss & Rodrigue Tido Takeng, 2025. "New axiomatizations of the Diversity Owen and Shapley values," International Journal of Game Theory, Springer;Game Theory Society, vol. 54(1), pages 1-16, June.
    10. Anthony Ziegelmeyer & Frédéric Koessler & Kene Boun My & Laurent Denant-Boèmont, 2008. "Road Traffic Congestion and Public Information: An Experimental Investigation," Journal of Transport Economics and Policy, University of Bath, vol. 42(1), pages 43-82, January.
    11. Martin Kocher & Matthias Sutter, 2007. "Individual versus group behavior and the role of the decision making procedure in gift-exchange experiments," Empirica, Springer;Austrian Institute for Economic Research;Austrian Economic Association, vol. 34(1), pages 63-88, March.
    12. DeJong, D.V. & Blume, A. & Neumann, G., 1998. "Learning in Sender-Receiver Games," Other publications TiSEM 4a8b4f46-f30b-4ad2-bb0c-1, Tilburg University, School of Economics and Management.
    13. Sergiu Hart & Andreu Mas-Colell, 2013. "A Simple Adaptive Procedure Leading To Correlated Equilibrium," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 2, pages 17-46, World Scientific Publishing Co. Pte. Ltd..
    14. Marco LiCalzi & Roland Mühlenbernd, 2022. "Feature-weighted categorized play across symmetric games," Experimental Economics, Springer;Economic Science Association, vol. 25(3), pages 1052-1078, June.
    15. Enrico Zaninotto & Alessandro Rossi & Loris Gaio, 1999. "Stochastic learning in coordination games: a simulation approach," Quaderni DISA 015, Department of Computer and Management Sciences, University of Trento, Italy, revised 29 Jun 2003.
    16. Rami Zwick & Amnon Rapoport, 2002. "Tacit Coordination in a Decentralized Market Entry Game with Fixed Capacity," Experimental Economics, Springer;Economic Science Association, vol. 5(3), pages 253-272, December.
    17. Montero, M.P., 2002. "Two-Stage Bargaining with Reversible Coalitions : The Case of Apex Games," Other publications TiSEM 7dba0283-bc13-4f2c-8f5e-5, Tilburg University, School of Economics and Management.
    18. Gary E. Bolton & Jordi Brandts & Elena Katok & Axel Ockenfels & Rami Zwick, "undated". "Testing Theories of Other-regarding Behavior," Papers on Strategic Interaction 2002-43, Max Planck Institute of Economics, Strategic Interaction Group.
    19. Antonio Cabrales & Giovanni Ponti, 2000. "Implementation, Elimination of Weakly Dominated Strategies and Evolutionary Dynamics," Review of Economic Dynamics, Elsevier for the Society for Economic Dynamics, vol. 3(2), pages 247-282, April.
    20. Boosey, Luke & Brookins, Philip & Ryvkin, Dmitry, 2017. "Contests with group size uncertainty: Experimental evidence," Games and Economic Behavior, Elsevier, vol. 105(C), pages 212-229.
    21. Karl Schlag & Andriy Zapechelnyuk, 2009. "Decision Making in Uncertain and Changing Environments," Discussion Papers 19, Kyiv School of Economics.

    More about this item

    Keywords

    ;
    ;
    ;

    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:annopr:v:350:y:2025:i:3:d:10.1007_s10479-016-2198-0. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.