Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/10976Full metadata record
| DC Field | Value | Language |
|---|---|---|
| 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.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.identifier.primary | Doi 10.1145/1383369.1383383 | - |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.publicationDate | 2008 | - |
| 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.journalName | Acm Transactions on Algorithms | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά) | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Fotakis-2008-Atomic Congestion Ga.pdf | 395.16 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
