hide
Free keywords:
-
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.
