Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Bhaskar, Umang
Fleischer, Lisa
Hoy, Darrell
Huang, Chien-Chung

dblp
dblp
dblp
dblp

Not MPG Author(s):

Bhaskar, Umang
Fleischer, Lisa
Hoy, Darrell

Editor(s):

Mathieu, Claire

dblp

Not MPII Editor(s):

Mathieu, Claire

BibTeX cite key*:

Huang2008

Title, Booktitle

Title*:

Equilibria of Atomic Flow Games are not Unique


soda_submission2.pdf (226.25 KB)

Booktitle*:

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)

Event, URLs

URL of the conference:

http://www.siam.org/proceedings/soda/2009/soda09.php

URL for downloading the paper:

http://www.siam.org/proceedings/soda/2009/soda09.php

Event Address*:

New York, U.S.A.

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

4 January 2009

Event End Date:

6 January 2009

Publisher

Name*:

ACM

URL:

http://www.siam.org/

Address*:

New York, NY

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:

January

Pages:

748-757

Year*:

2009

VG Wort Pages:


ISBN/ISSN:


Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

In STOC 2006, Hayrapetyan, Tardos and Wexler introduced the problem
of studying collusion in network routing games. In this
work, we show that collusion adds significant
complexity to the structure of equilibria in nonatomic routing games,
answering an open question posed by
Cominetti, Correa, and Stier-Moses (ICALP 2006):

Without collusion, it follows from well-known convexity arguments
that equilibria exist and are unique (up to induced delays, and under
weak assumptions on delay functions). The question
is, does this uniqueness continue to hold in the presence of collusion?

We answer no: we show that if collusion is allowed in nonatomic routing games,
there may be multiple equilibria.
We demonstrate the multiplicity via two specific examples.
In addition, we show our examples are topologically minimal
by giving a complete characterization of the class of
network topologies for which unique equilibria exist. Our
proofs and examples are based on a novel characterization of
these topologies in terms of sets of circulations.

Keywords:

Game Theory



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Huang2008,
AUTHOR = {Bhaskar, Umang and Fleischer, Lisa and Hoy, Darrell and Huang, Chien-Chung},
EDITOR = {Mathieu, Claire},
TITLE = {Equilibria of Atomic Flow Games are not Unique},
BOOKTITLE = {Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)},
PUBLISHER = {ACM},
YEAR = {2009},
PAGES = {748--757},
ADDRESS = {New York, U.S.A.},
MONTH = {January},
}


Entry last modified by Anja Becker, 03/04/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
02/13/2009 05:18:09 PM
Revisions
2.
1.
0.

Editor(s)
Anja Becker
Chien-Chung Huang
Chien-Chung Huang

Edit Dates
01.03.2010 13:42:46
03/24/2009 03:59:24 PM
02/13/2009 05:18:09 PM

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
soda_submission2.pdf