In this paper, we study contention resolution protocols from a game-theoretic perspective. We focus on acknowledgment-based protocols, where a user gets feedback from the channel only when she attempts transmission. In this case she will learn whether her transmission was successful or not. Users that do not transmit will not receive any feedback. We are interested in equilibrium protocols, where no player has an incentive to deviate. The limited feedback makes the design of equilibrium protocols a hard task as best response policies usually have to be modeled as Partially Observable Markov Decision Processes, which are hard to analyze. Nevertheless, we show how to circumvent this for the case of two players and present an equilibrium protocol. For many players, we give impossibility results for a large class of acknowledgment-based protocols, namely age-based and backoff protocols with finite expected finishing time. Finally, we provide an age-based equilibrium protocol, which has infinite expected finishing time, but every player finishes in linear time with high probability. Keywords and phrases contention resolution, acknowledgment-based protocols, game theory Contention resolution in multiple access channels is one of the most fundamental problems in networking. In a multiple access channel (or broadcast channel) multiple users want to communicate with each other by sending messages into the channel. The channel is not centrally controlled, so two or more users can transmit their messages at the same time. If this happens then the messages collide and the transmission is unsuccessful. Contention resolution protocols specify how to resolve such conflicts, while simultaneously optimizing some performance measure, like channel utilization or average throughput. In this paper we follow the standard assumption that time is divided into discrete time slots, messages are broken up into fixed sized packets, and one packet fits exactly into one time slot. Moreover, we consider one of the simplest possible scenarios where there are n users, each of them having a single packet that needs to be transmitted through the channel. When exactly one user attempts transmission in a given slot, the transmission is successful. However, if more than one users attempt transmission in the same slot, a collision occurs, their transmission fails and they need to retransmit their packages in later time slots. Under centralized control of the users, avoiding collisions would be simple: exactly one user would transmit at each time step, alternating in a round-robin fashion. The complexity of the problem stems from the fact that there is no centralized control and therefore channel access has to be managed by a distributed protocol. There is a large body of literature that
Among other results, REF provides the unique FIN-EQ protocol for the case of two players and a deadline IN-EQ protocol for at least three players.
Strategic Contention Resolution with Limited Feedback
ArXiv
ArXiv
Computer Science Mathematics