A Caltech Library Service

Contention Resolution under Selfishness

Christodoulou, George and Ligett, Katrina and Pyrga, Evangelia (2014) Contention Resolution under Selfishness. Algorithmica, 70 (4). pp. 675-693. ISSN 0178-4617. doi:10.1007/s00453-013-9773-4.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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. (in SODA ’07, pp. 179–188, SIAM, Philadelphia 2007) 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 Θ(n+clogn) and is in o(1)-equilibrium, where n is the number of users.

Item Type:Article
Related URLs:
URLURL TypeDescription
Ligett, Katrina0000-0003-2780-6656
Additional Information:© 2013 Springer Science+Business Media New York. Received: 20 December 2010; Accepted: 22 March 2013; Published online: 11 April 2013. The first author was partially supported by DFG grant Kr 2332/1-3 within Emmy Noether Program and by EPSRC grant EP/F069502/1. The second author was supported in part by an NSF Graduate Research Fellowship, NSF grant 0937060 to the Computing Research Association for the CIFellows Project, and NSF grant 1004416.
Funding AgencyGrant Number
Deutsche Forschungsgemeinschaft (DFG)Kr 2332/1-3
Engineering and Physical Sciences Research Council (EPSRC)EP/F069502/1
NSF Graduate Research FellowshipUNSPECIFIED
Subject Keywords:Algorithmic game theory; Contention resolution
Issue or Number:4
Record Number:CaltechAUTHORS:20141208-082730675
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:52450
Deposited By: Tony Diaz
Deposited On:09 Dec 2014 22:30
Last Modified:10 Nov 2021 19:41

Repository Staff Only: item control page