On the Approximate Core and Nucleon of Flow Games with Public Arcs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908341349908480 |
|---|---|
| author | Liu, Pengfei Xiao, Han Lu, Tianhang Fang, Qizhi |
| author_facet | Liu, Pengfei Xiao, Han Lu, Tianhang Fang, Qizhi |
| contents | We investigate flow games featuring both private arcs owned by individual players and public arcs accessible cost-free to all coalitions. We explore two solution concepts within this framework: the approximate core and the nucleon. The approximate core relaxes core requirements by permitting a bounded relative payoff deviation for every coalition, and the nucleon is a multiplicative analogue of Schmeidler's nucleolus which lexicographically maximizes the vector consisting of relative payoff deviations for every coalition arranged in a non-decreasing order. By leveraging a decomposition property for paths and cycles in a flow network, we derive complete characterizations for the approximate core and demonstrate that the nucleon can be computed in polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_13535 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Approximate Core and Nucleon of Flow Games with Public Arcs Liu, Pengfei Xiao, Han Lu, Tianhang Fang, Qizhi Computer Science and Game Theory 05C57, 91A12, 91A43, 91A46 We investigate flow games featuring both private arcs owned by individual players and public arcs accessible cost-free to all coalitions. We explore two solution concepts within this framework: the approximate core and the nucleon. The approximate core relaxes core requirements by permitting a bounded relative payoff deviation for every coalition, and the nucleon is a multiplicative analogue of Schmeidler's nucleolus which lexicographically maximizes the vector consisting of relative payoff deviations for every coalition arranged in a non-decreasing order. By leveraging a decomposition property for paths and cycles in a flow network, we derive complete characterizations for the approximate core and demonstrate that the nucleon can be computed in polynomial time. |
| title | On the Approximate Core and Nucleon of Flow Games with Public Arcs |
| topic | Computer Science and Game Theory 05C57, 91A12, 91A43, 91A46 |
| url | https://arxiv.org/abs/2401.13535 |