Cooperative games with bounded dependency degree
Cooperative games provide a framework to study cooperation among self-interested agents. They offer a number of solution concepts describing how the outcome of the cooperation should be shared among the players. Unfortunately, computational problems associated with many of these solution concepts te...
| मुख्य लेखकों: | , , |
|---|---|
| स्वरूप: | Conference item |
| प्रकाशित: |
Association for the Advancement of Artificial Intelligence Publications
2018
|
| _version_ | 1826273938078957568 |
|---|---|
| author | Igarashi, A Izsak, R Elkind, E |
| author_facet | Igarashi, A Izsak, R Elkind, E |
| author_sort | Igarashi, A |
| collection | OXFORD |
| description | Cooperative games provide a framework to study cooperation among self-interested agents. They offer a number of solution concepts describing how the outcome of the cooperation should be shared among the players. Unfortunately, computational problems associated with many of these solution concepts tend to be intractable---NP-hard or worse. In this paper, we incorporate complexity measures recently proposed by Feige and Izsak (2013), called dependency degree and supermodular degree, into the complexity analysis of coopera- tive games. We show that many computational problems for cooperative games become tractable for games whose dependency degree or supermodular degree are bounded. In particular, we prove that simple games admit efficient algorithms for various solution concepts when the supermodular degree is small; further, we show that computing the Shapley value is always in FPT with respect to the dependency degree. Finally, we observe that, while determining the dependency among players is computationally hard, there are efficient algorithms for special classes of games. |
| first_indexed | 2024-03-06T22:35:50Z |
| format | Conference item |
| id | oxford-uuid:59ddaabf-4c42-4b8f-b6ed-0bcd1b8b52e8 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T22:35:50Z |
| publishDate | 2018 |
| publisher | Association for the Advancement of Artificial Intelligence Publications |
| record_format | dspace |
| spelling | oxford-uuid:59ddaabf-4c42-4b8f-b6ed-0bcd1b8b52e82022-03-26T17:12:20ZCooperative games with bounded dependency degreeConference itemhttp://purl.org/coar/resource_type/c_5794uuid:59ddaabf-4c42-4b8f-b6ed-0bcd1b8b52e8Symplectic Elements at OxfordAssociation for the Advancement of Artificial Intelligence Publications2018Igarashi, AIzsak, RElkind, ECooperative games provide a framework to study cooperation among self-interested agents. They offer a number of solution concepts describing how the outcome of the cooperation should be shared among the players. Unfortunately, computational problems associated with many of these solution concepts tend to be intractable---NP-hard or worse. In this paper, we incorporate complexity measures recently proposed by Feige and Izsak (2013), called dependency degree and supermodular degree, into the complexity analysis of coopera- tive games. We show that many computational problems for cooperative games become tractable for games whose dependency degree or supermodular degree are bounded. In particular, we prove that simple games admit efficient algorithms for various solution concepts when the supermodular degree is small; further, we show that computing the Shapley value is always in FPT with respect to the dependency degree. Finally, we observe that, while determining the dependency among players is computationally hard, there are efficient algorithms for special classes of games. |
| spellingShingle | Igarashi, A Izsak, R Elkind, E Cooperative games with bounded dependency degree |
| title | Cooperative games with bounded dependency degree |
| title_full | Cooperative games with bounded dependency degree |
| title_fullStr | Cooperative games with bounded dependency degree |
| title_full_unstemmed | Cooperative games with bounded dependency degree |
| title_short | Cooperative games with bounded dependency degree |
| title_sort | cooperative games with bounded dependency degree |
| work_keys_str_mv | AT igarashia cooperativegameswithboundeddependencydegree AT izsakr cooperativegameswithboundeddependencydegree AT elkinde cooperativegameswithboundeddependencydegree |