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):

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

URL of the conference:

http://icalp10.inria.fr/

URL for downloading the paper:

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
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
01/21/2011 01:24:17 PM
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

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