English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Contention Resolution under Selfishness

MPS-Authors
/persons/resource/persons44250

Christodoulou,  Giorgos
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44922

Ligett,  Katrina
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45230

Pyrga,  Evangelia
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Christodoulou, G., Ligett, K., & Pyrga, E. (2010). Contention Resolution under Selfishness. In S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, & P. Spirakis (Eds.), Automata, Languages and Programming (pp. 430-441). Berlin: Springer. doi:10.1007/978-3-642-14162-1_36.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-1631-D
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.