MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Christodoulou, Giorgos
Ligett, Katrina
Pyrga, Evangelia		dblp
dblp
dblp
Not MPG Author(s):
Christodoulou, Giorgos
Ligett, Katrina
Editor(s):
Abramsky, Samson
Gavoille, Cyril
Kirchner, Claude
Meyer auf der Heide, Friedhelm
Spirakis, Paul		dblp
dblp
dblp
dblp
dblp
Not MPII Editor(s):
Abramsky, Samson
Gavoille, Cyril
Kirchner, Claude
Meyer auf der Heide, Friedhelm
Spirakis, Paul
BibTeX cite key*:
CPL2010
Title, Booktitle
Title*:
Contention Resolution under Selfishness
Booktitle*:
Automata, Languages and Programming : 37th International Colloquium, ICALP 2010. - Pt. II
Event, URLs
Conference URL::
http://icalp10.inria.fr/
Downloading URL:
http://dx.doi.org/10.1007/978-3-642-14162-1_36
Event Address*:
Bordeaux, France
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
6 July 2010
Event End Date:
10 July 2010
Publisher
Name*:
Springer
URL:
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
6199
Number:
Month:
Pages:
430-441
Year*:
2010
VG Wort Pages:
ISBN/ISSN:
978-3-642-14161-4
Sequence Number:
DOI:
10.1007/978-3-642-14162-1_36
Note, Abstract, ©
(LaTeX) Abstract:
In many communications settings, such as wired and wireless local-area
networks, when multiple users attempt to access a communication channel at the
same time, a conflict results and none of the communications are
successful. Contention resolution is the study of distributed transmission and
retransmission protocols designed to maximize notions of utility such as
channel utilization in the face of blocking communications.

An additional issue to be considered in the design of such protocols
is that selfish users may have incentive to deviate from the
prescribed behavior, if another transmission strategy increases their
utility. The work of Fiat et al.~\cite{Fiat07} addresses this issue by
constructing an asymptotically optimal incentive-compatible
protocol. However, their protocol assumes the cost of any single
transmission is zero, and the protocol completely collapses under non-zero
transmission costs.

In this paper, we treat the case of non-zero transmission cost $c$.
We present asymptotically optimal contention resolution protocols that
are robust to selfish users, in two different channel feedback
models. Our main result is in the Collision Multiplicity Feedback
model, where after each time slot, the number of attempted
transmissions is returned as feedback to the users. In this setting,
we give a protocol that has expected cost $2n+c\log n$ and is in
$o(1)$-equilibrium, where $n$ is the number of users.
Keywords:
Algorithmic Game Theory, Contention Resolution
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{CPL2010,
AUTHOR = {Christodoulou, Giorgos and Ligett, Katrina and Pyrga, Evangelia},
 EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul},
 TITLE = {Contention Resolution under Selfishness},
 BOOKTITLE = {Automata, Languages and Programming : 37th International Colloquium, ICALP 2010. - Pt. II},
 PUBLISHER = {Springer},
 YEAR = {2010},
 VOLUME = {6199},
 PAGES = {430--441},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Bordeaux, France},
 ISBN = {978-3-642-14161-4},
 DOI = {10.1007/978-3-642-14162-1_36},
}

Entry last modified by Anja Becker, 02/14/2011
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
01/21/2011 13:24:17
Revisions
2.
1.
0.

Editor(s)
Anja Becker
Evangelia Pyrga
Evangelia Pyrga

Edit Dates
14.02.2011 13:34:13
01/21/2011 03:42:44 PM
01/21/2011 01:24:17 PM