Atomic Congestion Games among Coalitions
| dc.contributor.author | Fotakis, D. | en |
| dc.contributor.author | Kontogiannis, S. | en |
| dc.contributor.author | Spirakis, P. | en |
| dc.date.accessioned | 2015-11-24T17:01:46Z | |
| dc.date.available | 2015-11-24T17:01:46Z | |
| dc.identifier.issn | 1549-6325 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/10976 | |
| dc.rights | Default Licence | - |
| dc.subject | algorithmic game theory | en |
| dc.subject | congestion games | en |
| dc.subject | convergence to equilibria | en |
| dc.subject | price of anarchy | en |
| dc.subject | selfish routing game | en |
| dc.subject | equilibria | en |
| dc.title | Atomic Congestion Games among Coalitions | en |
| heal.abstract | We consider algorithmic questions concerning the existence, tractability, and quality of Nash equilibria, in atomic congestion games among users participating in selfish coalitions. We introduce a coalitional congestion model among atomic players and demonstrate many interesting similarities with the noncooperative case. For example, there exists a potential function proving the existence of pure Nash equilibria (PNE) in the unrelated parallel links setting; in the network setting, the finite improvement property collapses as soon as we depart from linear delays, but there is an exact potential (and thus PNE) for linear delays. The price of anarchy on identical parallel links demonstrates a quite surprising threshold behavior: It persists on being asymptotically equal to that in the case of the noncooperative KP-model, unless the number of coalitions is sublogarithmic. We also show crucial differences, mainly concerning the hardness of algorithmic problems that are solved efficiently in the noncooperative case. Although we demonstrate convergence to robust PNE, we also prove the hardness of computing them. On the other hand, we propose a generalized fully mixed Nash equilibrium that can be efficiently constructed in most cases. Finally, we propose a natural improvement policy and prove its convergence in pseudopolynomial time to PNE which are robust against (even dynamically forming) coalitions of small size. | en |
| heal.access | campus | - |
| heal.fullTextAvailability | TRUE | - |
| heal.identifier.primary | Doi 10.1145/1383369.1383383 | - |
| heal.journalName | Acm Transactions on Algorithms | en |
| heal.journalType | peer reviewed | - |
| heal.language | en | - |
| heal.publicationDate | 2008 | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.type | journalArticle | - |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.type.en | Journal article | en |
Files
License bundle
1 - 1 of 1
Loading...
- Name:
- license.txt
- Size:
- 1.74 KB
- Format:
- Item-specific license agreed upon to submission
- Description: