Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Cooperative games with overlapping coalitions: charting the tractability frontier

Zick Yair, Chalkiadakis Georgios, Elkind, Edith, 1976-, Markakis, Evangelos

Full record


URI: http://purl.tuc.gr/dl/dias/3BAB89F1-ED11-4489-A5EE-77A85A269438
Year 2019
Type of Item Peer-Reviewed Journal Publication
License
Details
Bibliographic Citation Y. Zick, G. Chalkiadakis, E. Elkind and E. Markakis, "Cooperative games with overlapping coalitions: charting the tractability frontier," Artif. Intell., vol. 271, pp. 74-97, Jun. 2019. doi: 10.1016/j.artint.2018.11.006 https://doi.org/10.1016/j.artint.2018.11.006
Appears in Collections

Summary

The framework of cooperative games with overlapping coalitions (OCF games), which was proposed by Chalkiadakis et al. [1], generalizes classic cooperative games to settings where agents may belong to more than one coalition. OCF games can be used to model scenarios where agents distribute resources, such as time or energy, among several tasks, and then divide the payoffs generated by these tasks in a fair and/or stable manner. As the framework of OCF games is very expressive, identifying settings that admit efficient algorithms for computing ‘good’ outcomes of OCF games is a challenging task. In this work, we put forward two approaches that lead to tractability results for OCF games. First, we propose a discretized model of overlapping coalition formation, where each agent i has a weight W i ∈ℕ and may allocate an integer amount of weight to any task. Within this framework, we focus on the computation of outcomes that are socially optimal and/or stable. We discover that the algorithmic complexity of this task crucially depends on the amount of resources that each agent possesses, the maximum coalition size, and the pattern of communication among the agents. We identify several constraints that lead to tractable subclasses of discrete OCF games, and supplement our tractability results by hardness proofs, which clarify the role of our constraints. Second, we introduce and analyze a natural class of (continuous) OCF games—the Linear Bottleneck Games. We show that such games always admit a stable outcome, even assuming a large space of feasible deviations, and provide an efficient algorithm for computing such outcomes.

Services

Statistics