In this paper, we study contention resolution protocols from a game-theoretic perspective. In a recent work, we considered 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. One of the main results of ESA2016 was that no acknowledgment-based protocol can be in equilibrium. In fact, it seems that many natural acknowledgment-based protocols fail to prevent users from unilaterally switching to persistent protocols that always transmit with probability 1. It is therefore natural to ask how powerful a protocol must be so that it can beat persistent deviators. In this paper we consider age-based protocols, which can be described by a sequence of probabilities of transmitting in each time step. Those probabilities are given beforehand and do not change based on the transmission history. We present a 3-player age-based protocol that can prevent users from unilaterally deviating to a persistent protocol in order to decrease their expected transmission time. It is worth noting that the answer to this question does not follow from the results and proof ideas of ESA2016. Our protocol is non-trivial, in the sense that, when all players use it, finite expected transmission time is guaranteed. In fact, we show that this protocol is preferable to any deadline protocol in which, after some fixed time, attempt transmission with probability 1 in every subsequent step. An advantage of our protocol is that it is very simple to describe, and users only need a counter to keep track of time. Whether there exist @math -player age-based protocols that do not use counters and can prevent persistence is left as an open problem for future research.
@cite_14: This paper studies distributed choice of retransmission probabilities in slotted ALOHA. Both the cooperative team problem as well as the noncooperative game problem are considered. Unlike some previous work, we assume that mobiles do not know the number of backlogged packets at other nodes. A Markov chain analysis is used to obtain optimal and equilibrium retransmission probabilities and throughput. We then investigate the impact of adding retransmission costs (which may represent the disutility for power consumption) on the equilibrium and show how this pricing can be used to make the equilibrium throughput coincide with the optimal team throughput.
@cite_4: We consider distributed opportunistic scheduling (DOS) in wireless ad-hoc networks, where many links contend for the same channel using random access. In such networks, distributed opportunistic scheduling involves a process of joint channel probing and distributed scheduling. Due to channel fading, the link condition corresponding to a successful channel probing could be either good or poor. In the latter case, further channel probing, although at the cost of additional delay, may lead to better channel conditions and hence higher transmission rates. The desired tradeoff boils down to judiciously choosing the optimal stopping strategy for channel probing and the rate threshold. In this paper, we pursue a rigorous characterization of the optimal strategies from two perspectives, namely, a network-centric perspective and a user-centric perspective. We first consider DOS from a network-centric point of view, where links cooperate to maximize the overall network throughput. Using optimal stopping theory, we show that the optimal strategy turns out to be a pure threshold policy, where the rate threshold can be obtained by solving a fixed point equation. We further devise an iterative algorithm for computing the threshold. Next, we explore DOS from a user-centric perspective, where each links seeks to maximize its own throughput. We treat the problem of rate threshold selections for different links as a non-cooperative game. We explore the existence and uniqueness of the Nash equilibrium, and show that the Nash equilibrium can be approached by the best response strategy. We then develop an online stochastic iterative algorithm using local observations only, and establish its convergence. Finally, we observe that there is an efficiency loss in terms of the throughput at the Nash equilibrium, and introduce apricing-based mechanism to mitigate the loss.
@cite_1: 
@cite_0: 
@cite_19: Aloha [1] and its slotted variant [2] are commonly deployed Medium Access Control (MAC) protocols in environments where multiple transmitting devices compete for a medium, yet may have difficulty sensing each others presence. This paper models and evaluates the throughput that can be achieved in a system where nodes compete for bandwidth using a generalized version of slotted- Aloha protocols. We evaluate the channel utilization and fairness of these types of protocols for a variety of node objectives, including maximizing aggregate throughput of the channel, each node greedily maximizing its own throughput, and attacker nodes that attempt to jam the channel. If all nodes are selfish and greedily attempt to maximize their own throughputs, a situation similar to the traditional Prisoners Dilemma[3] arises. Our results reveal that under heavy loads, greedy strategies reduce the utilization, and that attackers cannot do much better than attacking during randomly selected slots.
@cite_16: We consider a wireless collision channel, shared by a finite number of users who transmit to a common base station. Users are self-optimizing, and each wishes to minimize its average transmission rate (or power investment), subject to minimum- throughput demand. The channel quality between each user and the base station is time-varying, and partially observed by the user in the form of channel state information (CSI) signals. We assume that each user can transmit at a fixed power level and that its transmission decision at each time slot is stationary in the sense that it can depend only on the current CSI. We are interested in properties of the Nash equilibrium of the resulting game between users. We define the feasible region of user's throughput demands, and show that when the demands are within this region, there exist exactly two Nash equilibrium points, with one strictly better than the other (in terms of invested power) for all users. We further provide some lower bounds on the channel capacity that can be obtained, both in the symmetric and non-symmetric case. Finally, we show that a simple greedy mechanism converges to the best equilibrium point without requiring any coordination between the users.
@cite_10: We study distributed choice of retransmission probabilities in slotted Aloha under power differentiation. We consider random transmission powers and further study the role of priorities (through power control) given either to new arriving packets or to backlogged ones. We study both the cooperative team problem in which a common objective is jointly optimized as well as the noncooperative game problem. We show that the new proposed schemes not only improve the average performances considerably but are also able in some cases to eliminate the bi-stable nature of the slotted Aloha.
@cite_25: We present a game-theoretic approach to the study of scheduling communications in wireless networks and introduce and study a class of games that we call Interference Games . In our setting, a player can successfully transmit if it "shouts strongly enough "; that is, if her transmission power is sufficiently higher than all other (simultaneous) transmissions plus the environmental noise. This physical phenomenon is commonly known as the Signal-to-Interference-plus-Noise-Ratio (SINR).
There are various game theoretic models of slotted ALOHA that have been studied in the literature, apart from the ones mentioned in the introduction; see for example @cite_14 @cite_19 @cite_10 . However, in most of these models only transmission protocols that always transmit with the same probability are considered. There has been also research on pricing schemes @cite_1 as well as on cases in which the channel quality changes dynamically with time and players must choose their transmission levels accordingly @cite_16 @cite_4 @cite_25 . An interesting game-theoretic model that lies between the contention and congestion model was studied in @cite_0 ; where decisions of when to submit is part of the action space of the players.