Document Open Access Logo

Online Coalition Formation Under Random Arrival or Coalition Dissolution

Authors Martin Bullinger , René Romen

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.27.pdf
  • Filesize: 0.74 MB
  • 18 pages

Document Identifiers

Author Details

Martin Bullinger
  • Technical University of Munich, Germany
René Romen
  • Technical University of Munich, Germany

Funding

Deutsche Forschungsgemeinschaft, grants BR 2312/11-2, BR 2312/12-1.

Acknowledgements

We would like to thank Thorben Tröbst and Viktoriia Lapshyna for valuable discussions.

Cite AsGet BibTex

Martin Bullinger and René Romen. Online Coalition Formation Under Random Arrival or Coalition Dissolution. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.27

Abstract

Coalition formation considers the question of how to partition a set of n agents into disjoint coalitions according to their preferences. We consider a cardinal utility model with additively separable aggregation of preferences and study the online variant of coalition formation, where the agents arrive in sequence and whenever an agent arrives, they have to be assigned to a coalition immediately. The goal is to maximize social welfare. In a purely deterministic model, the greedy algorithm, where an agent is assigned to the coalition with the largest gain, is known to achieve an optimal competitive ratio, which heavily relies on the range of utilities. We complement this result by considering two related models. First, we study a model where agents arrive in a random order. We find that the competitive ratio of the greedy algorithm is Θ(1/(n²)), whereas an alternative algorithm, which is based on alternating between waiting and greedy phases, can achieve a competitive ratio of Θ(1/n). Second, we relax the irrevocability of decisions by allowing to dissolve coalitions into singleton coalitions, presenting a matching-based algorithm that once again achieves a competitive ratio of Θ(1/n). Hence, compared to the base model, we present two ways to achieve a competitive ratio that precisely gets rid of utility dependencies. Our results also give novel insights in weighted online matching.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
  • Theory of computation → Algorithmic game theory
Keywords
  • Online Algorithms
  • Coalition Formation
  • Online Matching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. H. Aziz, F. Brandl, F. Brandt, P. Harrenstein, M. Olsen, and D. Peters. Fractional hedonic games. ACM Transactions on Economics and Computation, 7(2):1-29, 2019. Google Scholar
  2. H. Aziz, F. Brandt, and H. G. Seedig. Computing desirable partitions in additively separable hedonic games. Artificial Intelligence, 195:316-334, 2013. Google Scholar
  3. S. Banerjee, H. Konishi, and T. Sönmez. Core in a simple coalition formation game. Social Choice and Welfare, 18:135-153, 2001. Google Scholar
  4. V. Bilò, A. Fanelli, M. Flammini, G. Monaco, and L. Moscardelli. Nash stable outcomes in fractional hedonic games: Existence, efficiency and computation. Journal of Artificial Intelligence Research, 62:315-371, 2018. Google Scholar
  5. V. Bilò, G. Monaco, and L. Moscardelli. Hedonic games with fixed-size coalitions. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pages 9287-9295, 2022. Google Scholar
  6. N. Boehmer, M. Bullinger, and A. M. Kerkmann. Causes of stability in dynamic coalition formation. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pages 5499-5506, 2023. Google Scholar
  7. A. Bogomolnaia and M. O. Jackson. The stability of hedonic coalition structures. Games and Economic Behavior, 38(2):201-230, 2002. Google Scholar
  8. F. Brandt and M. Bullinger. Finding and recognizing popular coalition structures. Journal of Artificial Intelligence Research, 74:569-626, 2022. Google Scholar
  9. F. Brandt, M. Bullinger, and L. Tappe. Single-agent dynamics in additively separable hedonic games. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pages 4867-4874, 2022. Google Scholar
  10. F. Brandt, M. Bullinger, and A. Wilczynski. Reaching individually stable coalition structures. ACM Transactions on Economics and Computation, 11(1-2):4:1-65, 2023. Google Scholar
  11. F. T. Bruss. Sum the odds to one and stop. The Annals of Probability, 28(3):1384-1391, 2000. Google Scholar
  12. M. Bullinger. Pareto-optimality in cardinal hedonic games. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 213-221, 2020. Google Scholar
  13. M. Bullinger. Boundaries to single-agent stability in additively separable hedonic games. In Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 26:1-26:15, 2022. Google Scholar
  14. M. Bullinger and W. Suksompong. Topological distance games. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pages 5549-5556, 2023. Google Scholar
  15. R. Carosi, G. Monaco, and L. Moscardelli. Local core stability in simple symmetric fractional hedonic games. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 574-582, 2019. Google Scholar
  16. K. Cechlárová and A. Romero-Medina. Stability in coalition formation games. International Journal of Game Theory, 29:487-494, 2001. Google Scholar
  17. D. Dimitrov, P. Borm, R. Hendrickx, and S. C. Sung. Simple priorities and core stability in hedonic games. Social Choice and Welfare, 26(2):421-433, 2006. Google Scholar
  18. J. H. Drèze and J. Greenberg. Hedonic coalitions: Optimality and stability. Econometrica, 48(4):987-1003, 1980. Google Scholar
  19. E. Elkind, A. Fanelli, and M. Flammini. Price of pareto optimality in hedonic games. Artificial Intelligence, 288:103357, 2020. Google Scholar
  20. J. Feldman, N. Korula, V. Mirrokni, S. Muthukrishnan, and M. Pál. Online ad assignment with free disposal. In Proceedings of the 5th International Conference on Web and Internet Economics (WINE), pages 374-385, 2009. Google Scholar
  21. M. Flammini, B. Kodric, G. Monaco, and Q. Zhang. Strategyproof mechanisms for additively separable and fractional hedonic games. Journal of Artificial Intelligence Research, 70:1253-1279, 2021. Google Scholar
  22. M. Flammini, G. Monaco, L. Moscardelli, M. Shalom, and S. Zaks. On the online coalition structure generation problem. Journal of Artificial Intelligence Research, 72:1215-1250, 2021. Google Scholar
  23. M. Gairing and R. Savani. Computing stable outcomes in symmetric additively separable hedonic games. Mathematics of Operations Research, 44(3):1101-1121, 2019. Google Scholar
  24. Z. Huang, N. Kang, Z. G. Tang, X. Wu, Y. Zhang, and X. Zhu. How to match when all vertices arrive online. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC), pages 17-29, 2018. Google Scholar
  25. Z. Huang and T. Tröbst. Online matching. In F. Echenique, N. Immorlica, and V. V. Vazirani, editors, Online and Matching-Based Market Design. Cambridge University Press, 2023. Google Scholar
  26. C. Karande, A. Mehta, and P. Tripathi. Online bipartite matching with unknown distributions. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pages 587-596, 2011. Google Scholar
  27. R. M. Karp, U. V. Vazirani, and V. V. Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pages 352-358, 1990. Google Scholar
  28. M. Mahdian and Q. Yan. Online bipartite matching with random arrivals: An approach based on strongly factor-revealing lps. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pages 597-605, 2011. Google Scholar
  29. M. Olsen. Nash stability in additively separable hedonic games and community structures. Theory of Computing Systems, 45:917-925, 2009. Google Scholar
  30. S. C. Sung and D. Dimitrov. Computational complexity in additive hedonic games. European Journal of Operational Research, 203(3):635-639, 2010. Google Scholar
  31. Y. Wang and S. C. Wong. Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 1070-1081, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact