## 1 Introduction and Motivation

In the last fifteen years a great number of works in the Electrical and Electronics Engineering community has been devoted to designing medium access control (MAC) protocols that achieve high throughput. Their main approach is to consider, instead of the initial single-channel scheme, multi-channel schemes (multi-channel MAC protocols) which resolve contention caused by packet collisions (e.g. [19, 6, 25, 24, 28, 23]). Apart from high throughput, an additional benefit of introducing more channels in such a system is robustness, meaning no great dependence on a single node’s functionality. However, to the authors’ knowledge, strategic behaviour in multi-channel systems is limited to the Aloha protocol ([18]), contrary to the case of single-channel systems (e.g. [2, 9, 11, 7, 8]). In this paper, we examine the problem of strategic contention resolution in multi-channel systems, where obedience to a suggested protocol is not required. We seek only anonymous, equilibrium protocols, that is, protocols which do not use player IDs. If a player’s protocol depended on her ID, then equilibria are simple, but can be unfair as well; scheduling each player’s transmission through a priority queue according to her ID is an equilibrium.

We provide two types of equilibrium protocols. The first type, called FIN-EQ, describes an anonymous, equilibrium protocol that yields finite expected time of successful transmission (latency) to a player. Similarly, the second type, called IN-EQ, describes an anonymous, equilibrium protocol which yields infinite expected latency to a player but is also efficient, i.e, all players transmit successfully within time with high probability. We study equilibria for two classes of feedback protocols: (a) acknowledgement-based protocols, where the user gets just the information of whether she had a successful transmission or not, only when she tries to transmit her packet, and (b) protocols with ternary feedback, where the user is informed about the number of pending players in each time-step regardless of whether she attempted transmission or not. Previous results on these classes of protocols have been produced only for the case of a single transmission channel ([7, 11]). Here we investigate the multiple-channels case.

In the last part of the paper we seek efficient protocols for both feedback classes. Due to an impossibility result that we show (Theorem 5.1), the technique used in [11] by Fiat et al. for the single-channel setting in order to provide a FIN-EQ that is also efficient, cannot be applied when there are more than one channels. This fact discourages us from searching for efficient FIN-EQ protocols and, instead, points to the search for efficient IN-EQ protocols, which indeed we find. One could argue that an anonymous protocol with infinite expected time until successful transmission, such as the IN-EQ protocols we provide, does not incentivize a player to participate in such a communication system. To this we reply that exponential waiting-time for a large amount of players (see protocol in Subsection 4.2) is equally bad for a player, since waiting for e.g. msec is like waiting forever in Real-Time-Communications.

### 1.1 Our results

The main contributions of this work are the characterizations of FIN-EQ and IN-EQ protocols in the two aforementioned feedback classes. Note that in the current bibliography regarding the single-channel setting, there are no characterizations of equilibrium in acknowledgement-based protocols. Also, in the single-channel setting the existence of a symmetric equilibrium with finite expected latency in the class of acknowledgement-based protocols remains an open problem, even for three players. However, for the settings with 2 and 3 transmission channels, we present simple anonymous FIN-EQ protocols for up to 4 and 5 players respectively which appeared in [10]. Furthermore, these protocols are memoryless, while the only known FIN-EQ protocol in the single-channel setting ([7]) is not.

The paper is organized in three main parts. Section 3 deals with FIN-EQ protocols in the acknowledgement-based feedback setting. In that section we give two characterizations of equilibrium and also provide FIN-EQ protocols for specific numbers of players and channels. Section 4 deals with FIN-EQ protocols in the ternary feedback setting and extends the corresponding results for the single-channel setting by Fiat et al. [11]. Finally, in Section 5, IN-EQ protocols with deadline are provided with the property that the time until all players transmit successfully is with high probability, when there are channels. The latter result makes clear the advantage (with respect to time efficiency) that multiple channels bring to a system with strategic users, which is that the time until all players transmit successfully with high probability is inversely proportional to the number of available channels.

### 1.2 Related work

Contention in telecommunications is a major problem that results to poor throughput due to packet collisions. Motivated mainly by this problem, many works studying conflict-resolution protocols emerged in the late 70’s ([22, 5, 4, 14, 27]). Their approach is to resolve a collision when it occurs, and only then allow further transmissions on the channel. In those works the user’s packets are assumed either to be generated by some stochastic process, or to appear at the same time in a worst-case scenario. Here, we consider the latter setting, i.e. a worst-case model of slotted time, where at any time-step all users have a packet ready to be transmitted (for an example of a similar bursty-input case, see [3]). As stated in [12], even though real implementations of multiple-access channels do not fit precisely within the slotted-time model, it can be shown (e.g. [16, 13]) that results obtained in this model do apply to realistic multiple-access channels.

Also, many works have examined multiple-channel communication protocols. In the data link layer, a Medium Access Control (MAC) protocol is responsible for the flow of data through a multiple-access medium. Our multiple-channels model is motivated by theoretical and experimental results which have shown that higher throughput and lower delay is achieved by using “multi-channel” MAC protocols (see [20, 24, 19, 25]). In [25],the multi-channel hidden terminal problem is raised which, additionally to increased packet collisions, results to incapability of the users to “sense” more than one channels at a time (possibly none); therefore a user might not know whether another user transmitted successfully or not (see also [26] for the classical “hidden terminal problem”). This motivates us for the consideration of feedback protocols with minimum feedback, i.e. “acknowledgement-based” protocols (see par.2, Section 1). Also, settings with stronger feedback have been studied (e.g. the Aloha protocol in [18]) in which a user is informed about the number of users that have not transmitted successfully yet. This is why we consider “ternary feedback” protocols (see par.2, Section 1).

Apart from the latter, all of the aforementioned works assume that the users blindly follow the given protocol, i.e. the users are not strategic. Contention resolution with strategic users has been studied only in single-channel settings or in the special case of the multiple-channel Aloha protocol. Some interesting cooperative and noncooperative models of slotted Aloha have been analysed in [1, 17, 18]. Aiming to understand the properties of contention resolution under selfishness, apart from various feedback settings, many cost functions have also been studied. One of the most meaningful cost functions is the one that models non-zero transmission costs as in [9] (and also [2, 18]).

The theoretical works that relate the most to the current paper are the seminal paper by Fiat, Mansour and Nadav [11] and two by Christodoulou et al. [7, 8] which study protocols for strategic contention resolution with zero transmission costs. These works examine the case of a single transmission channel only. In [11] the feedback is ternary. In that work, a characterization of symmetric equilibrium is provided, along with an efficient FIN-EQ protocol that puts an extremely costly equilibrium after a deadline in order to force users to be obedient. The feedback model of [7] and [8] is the acknowledgement-based. Among other results, [7] provides the unique FIN-EQ protocol for the case of two players and a deadline IN-EQ protocol for at least three players.

## 2 The Model and Definitions

#### Game structure.

We define a contention game as follows. Let be the set of players, also denoted by , and the set of channels. Each player has a single packet that she wants to send through a channel in , without caring about the identity of the channel. All players know and . We assume synchronous communications with discretized time, i.e. time slots . The players that have not yet successfully transmitted their packet are called pending and initially all players are pending. At any given time slot , a pending player has a set of pure strategies: a pure strategy is the action of choosing channel to transmit her packet on, or no transmission (). At time , a (mixed) strategy of a player

is a probability distribution over

that potentially depends on information that has gained from the process based on previous transmission attempts. If exactly one player transmits on a channel in a given slot , then her transmission is successful, the successful player exits the game (i.e. she is no longer pending), and the game continues with the rest of the players. On the other hand, whenever two or more players try to access the same channel (i.e. transmit) at the same time slot, a collision occurs and their transmissions fail, in which case the players remain in the game. The game continues until all players have successfully transmitted their packets.#### Transmission protocols.

Let be the channel-indicator variable that keeps track of the identity of the channel where player attempted transmission at time ; value indicates no transmission attempt. For any , we denote by

the transmission vector at time

, i.e. .An acknowledgement-based protocol uses very limited channel feedback. After each time step , only players that attempted a transmission receive feedback, and the rest get no information. In fact, the information received by a player who transmitted during is whether her transmission was successful (in which case she gets an acknowledgement and exits the game) or whether there was a collision.

In a protocol with ternary feedback every pending player in every round is informed about the number of remaining players . This information is given to the players regardless of their transmission history.

Let be the vector of the personal transmission history of player up to time , i.e. . We also denote by the transmission history of all players up to time , i.e. . A decision rule for a pending player at time , is a function that maps to a strategy , with elements Pr for all . When the transmission probability on some is not stated in a decision rule it is because it can be deduced from the stated ones.

For a player , a (transmission) protocol is a sequence of decision rules . Given a protocol for player , when her decision rules depend on the number of pending players and the personal history of , then we describe them by the player’s probability distribution on the action set . In this case, we denote by the probability of player choosing action at time given her personal history when players are pending right before . When the context is clear enough we will drop some of the indices accordingly.

When we state that the players use an anonymous protocol , we will mean that they follow a common protocol () whose decision rules do not depend on any ID of the player (in our setting players do not have IDs), i.e. the decision rule assigns the same strategy to all players with the same personal history. In particular, for any two players and any , if , it holds that . In this case, we drop the subscript in the notation and write instead of .

A protocol for player is a deadline protocol with deadline if and only if there exists a finite such that a particular channel is assigned (deterministically or stochastically) to player at some time and Pr for every time slot and any history .

#### Efficiency.

Assume that all players follow an anonymous protocol . We will call efficient if and only if all players will have successfully transmitted by time with high probability (i.e. with probability tending to 1, as ).

#### Individual utility.

By protocol profile we will call the n-tuple of the players’ protocols. For a given transmission sequence , which is consistent with , define the latency of agent as . That is, is the time at which successfully transmits. Also, define the finishing time of as , i.e., the least time at which all players have successfully transmitted. Given a transmission history , the -tuple of protocols induces a probability distribution over sequences of further transmissions. In that case, we write for the expected latency of a pending agent given that her current history is and from on she follows . For anonymous protocols, i.e. when , we will simply write instead. Abusing notation slightly, we will also write for the unconditional expected latency of player induced by . We also define the expected future latency and again, whenever clear from the context, we omit redundant indices or vectors from the notation.

#### Equilibria.

The objective of every player is to minimize her expected latency. We call a protocol a best response of player to the partial protocol profile if for any transmission history , player cannot decrease her expected latency by unilaterally deviating from after . That is, for all time slots , and for all protocols for player , we have

where (respectively, ) denotes the protocol profile where every player uses protocol and player uses protocol (respectively ). For an anonymous protocol , we denote by the profile where player uses protocol and player uses protocol .

We say that is an equilibrium if for any transmission history the players cannot decrease their expected latency by unilaterally deviating after ; that is, for every player , is a best response to .

#### FIN-EQ and IN-EQ protocols.

We call an anonymous protocol FIN-EQ if it is an equilibrium protocol and yields finite expected latency to a player. Similarly, we call an anonymous protocol IN-EQ if it is an equilibrium protocol, yields infinite expected latency to a player, and is also efficient.

## 3 Equilibrium for Acknowledgement-based Protocols

### 3.1 Nash equilibrium characterizations

The following equilibrium characterizations for the class of acknowledgement-based protocols help us check whether the protocols we subsequently guess are equilibrium protocols. The characterizations are for symmetric and asymmetric equilibria, arbitrary number of channels and number of players .

In an acknowledgement-based protocol, the actions of player at time depend only (a) on her personal history and (b) on whether she is pending or not at . Let be a tuple of acknowledgement-based protocols (not necessarily anonymous) for the players. For a (finite) positive integer , and a given history , define for player the protocol

(1) |

A personal history is consistent with the protocol profile if and only if there is a non-zero probability that will occur for player under . Protocol is consistent with if and only if is consistent with , and when clear from the context we write instead. We denote the set of all ’s, that is, all ’s for all , which are consistent with , by . If (i.e. is anonymous), then instead of and we write and respectively.

###### Lemma 1 (Equilibrium characterization 1).

Consider a profile

of acknowledgement-based protocols and a protocol

for some . The following statements are equivalent:

(i) is an equilibrium.

(ii) For every player ,

if then .

###### Proof.

To show that being an equilibrium is a sufficient condition, we use the same argument as in Lemma 4 of [7]. In particular, for a player , due to the Tower Property we have,

(2) |

For short, we will denote by , thus we denote by . Then, suppose that is an equilibrium and assume for the sake of contradiction that there is a transmission history for player such that . Obviously, if this would mean that protocol is better than , thus is not an equilibrium. If, on the other hand, , then from (3.1) there must exist another transmission history such that . Therefore, we conclude that which also equals by definition of the equilibrium, for every transmission history that is consistent with .

To show that being an equilibrium is also a necessary condition, assume that implies . Then, equality (3.1) becomes

and thus is by definition an equilibrium. ∎

###### Corollary 1 (Best response).

Consider a profile of acknowledgement-based protocols. For a fixed protocol of player and some consistent with , define the following protocol.

(3) |

If for player there exists a finite such that for every , then .

###### Proof.

###### Lemma 2 (Equilibrium characterization 2).

Consider a profile

of acknowledgement-based protocols. The following statements are equivalent:

(i) is an equilibrium.

(ii) For every player

###### Proof.

Sufficiency of being an equilibrium for condition (ii-a) comes directly from Lemma 1; for condition (ii-b), for the sake of contradiction suppose is an equilibrium and that there exist some protocols and such that . This means that is a better protocol than , thus is not an equilibrium, which is a contradiction.

To prove necessity of being an equilibrium under conditions (ii-a) and (ii-b), for the sake of contradiction, suppose (ii-a) and (ii-b) hold and is not an equilibrium. Then there must exist some protocol such that . Using (3.1) the latter inequality can be written as

where is consistent with and is consistent with . Given the conditions (ii-a) and (ii-b) the latter inequality is a contradiction. ∎

### 3.2 Acknowledgment-based FIN-EQ protocols

Regarding the search for FIN-EQ protocols, there is no straight-forward way for our equilibrium characterizations (previous subsection) to be used in order to find an equilibrium protocol. However, they allow us to check whether the protocols discussed in this subsection are equilibrium protocols. In this subsection we give FIN-EQ protocols for and .

We define the following anonymous, memoryless protocol for channels.

[ams gather]
Protocol : For player , every and any history ,

f_i,t^k = (Pr{X_i,t = 0 } = 0, Pr{X_i,t = a } = 1k, ∀a ∈K ).

#### n players - 2 transmission channels.

Here, we first give an example of a method for checking equilibria (Theorem 3.1). Then, with a better approach, by employing our characterizations of the previous subsection, we prove that is an equilibrium protocol for players and channels (Theorem 3.3).

###### Lemma 3.

When all players use protocol the expected latency of any player is .

###### Proof.

The process from the perspective of an arbitrary player

can be modelled as the following Markov chain; the states are named after the number of remaining players including

, and state is the state where finds herself after successful transmission.We write to denote the transition probability to go from state to state . We have

(4) |

(5) |

The expected absorption time from state to state is found from the following set of equations:

and |

where denotes the expected hitting time from state to state . By solving this system of linear equations we get

∎

In the next theorem we will give an example of a method for checking whether a given protocol profile is an equilibrium, which however could be inconclusive in some cases. Suppose you we want to check whether an arbitrary protocol profile is an equilibrium. By definition of the equilibrium, we can fix all protocols except player ’s, i.e. and check if is a best response to them, and repeat this for every player . By fixing we create a stochastic environment for player who can be considered to be free to take sequential decisions through time. These decisions correspond to decision rules of . Since, due to the feedback limitations,

has no information about the number of pending players, this situation from her point of view is modeled as an infinite state Partially Observable Markov Decision Process (POMDP).

is a best response to if and only if is an optimal policy of the POMDP, that is, a set of decisions through time that minimize her expected latency.However for this kind of POMDPs there are no known techniques to find an optimal policy. In order to circumvent this problem, we can assume that player is an advantageous player that always knows how many players are pending. This turns the infinite state POMDP into a finite state Markov Decision Process (MDP), whose optimal policy we can find through known techniques (e.g. [21]). One can see that the optimal policy in the MDP of the advantageous player yields at most the expected latency of the optimal policy in the POMDP of the initial player . Thus, if the best policy in the MDP yields the same expected latency as what gives to , then we know that is a best response; however, if the best policy of the MDP yields smaller expected latency, then we get no information about whether is a best response in the POMDP or not. The proof of the next theorem demonstrates the method and shows that protocol of (3.2) is an equilibrium protocol for 3 players.

###### Theorem 3.1.

For 3 players and 2 channels, is an equilibrium protocol with expected latency .

###### Proof.

Consider the Markov Decision Process (MDP) , where is the state space for time ; is the set of possible actions that can be taken after observing state at time ; defines the transition probability to state at time , and only depends on the state and chosen action at time ; is the cost function that determines the immediate cost for the agent’s choice of action while in state . When the state cannot be observed with certainty at time , the agent only knows a probability distribution, called belief state, over . The process then is called Partially Observable Markov Decision Process (POMDP). An optimal policy is a function that rules, for each state or belief state, which action to perform, with an objective to minimize the expected cost.

For the proof of the above theorem we will use the following property of POMDPs. This property comes directly from the fact that an agent optimizing over all policies that every time consider her exact state gets a better policy than an agent that knows a probability distribution on the state space (belief states).

###### Proposition 1.

An optimal policy of an agent in a POMDP yields as expected cost at least the expected cost of the optimal policy of the corresponding MDP, in which at any time the agent observes her exact state.

To prove Theorem 3.1 we think as follows. Let us fix protocol as defined in (3.2) for two players, and let the remaining player have an arbitrary protocol . Then let us find the optimal policy for . If and only if the optimal policy yields expected cost strictly lower than what protocol would yield for player (due to Lemma 3, that is ), then is not an equilibrium protocol. The game stated at Theorem 3.1, from player ’s perspective, is modelled by a POMDP where each state is determined by the number of pending players, with an additional absorbing state - where goes after successfully transmitting - and ’s transmission history for every . Player ’s belief state at any time is determined by her belief state at time , the action she chose at time , and her observation (e.g. her transmission history up to ). This is a POMDP with infinite states, for which, to the best of our knowledge, currently there are no methods in the literature for finding an optimal policy.

However, we will find the best policy and the expected cost of the corresponding MDP, where player knows in what state she finds herself after an action and observation. This expected cost is a lower bound on the expected cost of the optimal policy of the original POMDP (see Proposition 1). In the MDP we create, player knows at any time how many players are pending and her transmission history up to time .

Let indicate the number of pending players. Observe that the time steps at which the process has a given are consecutive; without loss of generality assume that for some , the process is in the discrete time interval , where we set . Consider now the set of all states of the MDP, where the number of pending players is fixed, whereas the transmission history for can vary. Because of the protocol being memoryless, the same action (probability distribution over action space ) of chosen at any state in produces the same transition probabilities. Therefore, choosing the optimal policy makes the set of states collapse to a single state , where . The resulting MDP is a finite MDP with states and , where the latter is an absorption state to which player goes after a successful transmission. Denote the expected cost of the MDP’s optimal policy given that the initial state is by . In our problem the immediate cost for any combination of state and action is 1, since we count the number of rounds in which is pending. Using Lemma 5.4.2 and Theorem 5.4.3 of [21] we can find by solving the following system of linear equations

(6) |

Then, by minimizing each over policies we get the optimal expected costs , . As a byproduct of the minimization we find the best policy .

In our problem, a policy is a tuple (), where , determines the probability that player will attempt a transmission, and , determines the probability that she will attempt the transmission on channel . To give a small example, for a given state , . By solving system (6), we get that

which implies that a policy does not depend on any of the ’s. Now, by minimizing the above expected costs we get and for and . Note that the optimal policy allows and to be arbitrary probabilities. being even 0 is not a contradiction since in our MDP the player is always aware of the pending players (state); in the case where , when the player is in state , she waits one round until the other player transmits successfully and then realizes that she is alone pending in ; in the next round she transmits with probability 1.

We subsequently exploit the lack of memory and the anonymity of our protocol defined in equation (3.2) and show more general results on equilibria (Theorem 3.3), using the characterizations from Subsection 3.1.

###### Theorem 3.2.

In a contention game with channels, consider an anonymous, memoryless protocol of player with the property: Pr, for every . For more than 4 players any such protocol is not an equilibrium protocol.

###### Proof.

Assume that an anonymous protocol as stated in the theorem is an equilibrium protocol for players. We will show that condition (ii-b) of Lemma 2 does not hold. That is, if players use a protocol with the property that in each time its decision rule assigns zero probability to “no transmission”, then there exists a best response that yields strictly better expected latency for an arbitrary player.

Suppose is an equilibrium protocol. consists of a decision rule for each time slot , i.e. a probability distribution on the available channels (with probability 0 of “no transmission” as the theorem’s statement requires). Since all players use this protocol, in an arbitrary time all players have the same distribution on the channels. For the sake of contradiction, suppose there is some for which the decision rule is other than . Without loss of generality, we have . Thus, an arbitrary player , at time , can unilaterally change her distribution to and increase her probability of transmitting successfully in the specific round. As a consequence her expected latency would strictly decrease, hence a protocol with a decision rule with different probabilities on each channel cannot be in a symmetric equilibrium. Therefore, the anonymous, equilibrium protocol , with the property Pr for every , prescribes for every . The expected latency of a player using such a protocol, when there are pending players, is found in Lemma 3 to be .

We will show that, when the number of pending players at is , protocol

is a better response for an arbitrary player , that is, .

Suppose player uses protocol when there are pending players at . At time she is not aware of the number of players that remain pending. However, there are two cases, either players are pending in case none of the other players in transmitted successfully, or players remain in case only one of the other players transmitted successfully in . Note that there is no way that two players cannot simultaneously transmit successfully in round due to the given protocol and the number of pending players. The probability for each of the two aforementioned events is,

where is the number of players that transmit successfully, , and for . To see how this formula is produced, please refer to the proof of Lemma 7 (Section 5), up to equation (5.2). Here, equation (5.2) is used for and .

In order to capture the dependence of the expected future cost (after history ) on the number of pending players , when player uses and the rest of the players use , we denote it by . Similarly, we denote the expected latency by . We have,

(7) |

Since protocol belongs to the class of protocols defined in the statement of Theorem 3.2, the following corollary is immediate.

###### Corollary 2.

For players and channels, is not an equilibrium protocol. In fact, a better response for any player is to not transmit in and then follow .

Now we prove two lemmata that, combined with our second characterization of equilibria (Lemma 2), result to one of this section’s main theorems (Theorem 3.3) that determines equilibrium protocols for players and channels. In particular, we will show that for number of players , and , when players use , if some deviator unilaterally chooses any possible protocol as defined in (1) that is consistent with , she will suffer the same expected latency, namely . Then, we will show that if the deviator unilaterally chooses any possible protocol as defined in (1) that is not consistent with , she will suffer expected latency at least . These two facts, by Lemma 2, show that is an equilibrium protocol for .

###### Lemma 4.

For players and channels, any player that follows a protocol in the profile , where is defined in (3.2), has expected latency .

###### Proof.

Consider the contention game with fixed number of players and 2 channels. players use protocol and a player uses some protocol as defined in (1), for some . To make easier our reference to the expected future latency of a player in the special case where (almost) all players follow protocol of (3.2), and to capture the number of players in the notation, we will denote by

Comments

There are no comments yet.