# A Game Theoretic Approach to Irregular Repetition
## Slotted Aloha

Iman Hmedoush, Cedric Adjih, Kinda Khawam, Paul Mühlethaler

► To cite this version:

Iman Hmedoush, Cedric Adjih, Kinda Khawam, Paul Mühlethaler. A Game Theoretic Approach to Irregular Repetition Slotted Aloha. IEEE Access, 2022, 10, pp.4600-4614. 10.1109/ACCESS.2022.3140495. hal-03533559

HAL Id: hal-03533559

https://inria.hal.science/hal-03533559

Submitted on 18 Jan 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Received November 30, 2021, accepted December 21, 2021, date of publication January 5, 2022, date of current version January 13, 2022.

Digital Object Identifier 10.1109/ACCESS.2022.3140495

# A Game Theoretic Approach to Irregular Repetition Slotted Aloha

IMAN HMEDOUSH<sup>1,2</sup>, CÉDRIC ADJIH<sup>1,2</sup>, KINDA KHAWAM<sup>1,3</sup>, AND PAUL MÜHLETHALER<sup>1</sup>, (Member, IEEE)

Corresponding author: Iman Hmedoush (iman.hmedoush@inria.fr)

This work was supported in part by the INRIA—Nokia Bell Labs Common Labs under Research action “Network Information Theory.”

**ABSTRACT** Many technological enhancements are being developed worldwide to enable the “Internet of Things” (IoT). IoT networks largely rely on distributed access of billions of devices, but are still lagging in terms of combined reliability and low latency. To mend that shortcoming, it is paramount to adapt existing random access methods for the IoT setting. In this article, we shed light on one of the modern candidates for random access protocols fitted for IoT: the “Irregular Repetition Slotted ALOHA” (IRSA). As self-managing solutions are needed to overcome the challenges of IoT, we study the IRSA random access scheme in a distributed setting where groups of users, with fixed traffic loads, are competing for ALOHA-type channel access. To that aim, we adopt a distributed game-theoretic approach where two classes of IoT devices learn autonomously their optimal IRSA protocol parameters to optimize selfishly their own effective throughput. Through extensive simulations, we assess the notable efficiency of the game based distributed approach. We also show that our IRSA game attains the Nash equilibrium (NE) via the “better reply” strategy, and we quantify the price of anarchy in comparison with a centralized approach. Our results imply that user competition does not fundamentally impact the performance of the IRSA protocol.

**INDEX TERMS** Random access, Internet of Things, game theory, IRSA.

## I. INTRODUCTION

### A. COMMUNICATION IN THE INTERNET OF THINGS

The Internet of Things is a system of interrelated devices connected to the Internet to transfer data among each other. It applies to more than just sensors or devices: it focuses on entire use-cases. Smart buildings, connected cars, and industrial automata are examples of applications, where things need to “talk to each other” through complex interactions.

Nonetheless, with over 50 billion connected IoT devices expected by 2025, legacy approaches to resource management and channel access can no longer keep up. This is exacerbated with the ultra-dense IoT deployments, and with the increasing requirements for better throughput and energy efficiency. As a consequence, there have been new directions in the design of IoT protocols to satisfy the critical requirements of IoT applications, including modern variants of random access methods. In that line, the adoption of advanced

physical layer mechanisms such as Successive Interference Cancellation (SIC) can enhance standard random access protocols to cope with the massive connectivity of IoT networks. Furthermore, a new family of protocols, often labeled as modern Random Access (RA) [1], has been lately considered as a promising solution for the particular setting of IoT. The idea behind these protocols is to modify the traditional random access scheme of ALOHA by allowing active users to send multiple copies of their packets over the shared medium. The goal is to retrieve, through the SIC mechanism, at least one of these copies successfully at the destination despite the increased channel load. One such modern RA is the focus of the present article.

### B. MODERN RANDOM ACCESS PROTOCOLS FOR IoT COMMUNICATIONS

A recent family of modern RA has emerged as a promising solution for modern random access, coined “Irregular Repetition Slotted Aloha” (IRSA) [2], and its generalization with coding, coined “Coded Slotted Aloha” (CSA) [3].

The associate editor coordinating the review of this manuscript and approving it for publication was M. Sabarimalai Manikandan.

<footnote n="1">¹INRIA, CRI Paris, 75012 Paris, France</footnote>

<footnote n="2">²INRIA, CRI Saclay-Île-de-France, 91120 Palaiseau, France</footnote>

<footnote n="3">³DAVID Laboratory, Université de Versailles, UVSQ, 78035 Versailles, France</footnote>
It has become the focus of IoT protocol designers since it has been shown to asymptotically reach the optimal throughput of one retrieved packet per slot, in the classical random access collision model (where the maximum throughput of slotted ALOHA is $1/e$). Other variants exist such as “Polarization-Division Multiple Access” (PDMA)/IRSA [4] that have sophisticated physical layer detection and are closer to “Non-Orthogonal Multiple Access” (NOMA) [5].

The concept of these protocols is to send multiple copies of each user packet towards its destination. On the receiver side, “Successive Interference Cancellation” (SIC) is used to resolve the collisions. The transmission is done in slots. Each replica (copy) has the same payload and preamble information. However, extra information about the positions of each replica in the various slots is added to the preamble. This information helps the SIC receiver to remove the replicas of each decoded packet by subtracting the corresponding physical signal of the decoded packet at its replicas positions.

## 1) IRREGULAR REPETITION SLOTTED ALOHA (IRSA)

In this section, we present IRSA, which is one of the recent protocols of the Channel Sensing Access (CSA) family and one of the candidate protocols for random access in IoT networks. IRSA is an optimized version of “Contention Resolution Diversity Slotted Aloha” (CRDSA) [6]. In CRDSA, each user repeats every packet twice; while in IRSA, a user chooses the number of packet repetitions (repetition degree) according to a probability distribution $\Lambda = (\Lambda_0, \Lambda_1, \dots, \Lambda_D)$, where $\Lambda_i$ is the probability of using the degree $i$ and $D$ is the maximum degree. Each user repeats its packets in the same frame according to the selected degree.

After receiving all the packets in a frame, the receiver performs iterative decoding using SIC. Each decoding iteration consists of finding the non-colliding packets (referred to as the singletons) and decoding them. After decoding all the singletons in the frame, the receiver uses the preamble information to remove their physical copies from their other positions in the frame.<fnref n="1" /> At the end of one decoding iteration, some collisions are suppressed and in turn, new singletons appear and would be decoded and removed in the next iteration. The iterative decoding continues until the receiver can not find any singleton or the whole frame is decoded.

## 2) A SIMPLE ILLUSTRATIVE EXAMPLE OF IRSA

In Fig. 1, we present a simple example of successive decoding using SIC. A part of a MAC frame where 5 users send their packets on 5 slots is shown. The degrees of the users A, B, C, D and E are respectively 3, 4, 2, 2, and 2 as visible in the figure.<fnref n="2" /> The SIC receiver starts the decoding iteration by searching for the singletons. The figure shows the first singleton of user D on slot 4. The singleton on slot 4 is decoded, then

<figure><img src="image_2.png" /><figcaption>**FIGURE 1.** IRSA representation: transmissions of users in slots (top), coding theory representation to model the decoding process (Tanner graph, bottom). Note that transmissions are in the same frequency channel, hence when two users are transmitting on the same slot, there is a collision.</figcaption></figure>

its copy is subtracted from slot 5. This subtraction makes the packet of user B a new singleton on slot 5 so that it is decoded and removed from slots 1, 2, and 3. Now, slot 3 has only the packet of user A, so it is decoded on slot 3 and subtracted from slots 1 and 2. In the next iteration, the packets of users C and E on slots 1 and 2 can not be decoded since none of their replicas had ever become a singleton and they form a stopping set. At this point, the iterative decoding process stops.

In the classic collision model, where a packet is retrieved if and only if it has no collision with any other packet, IRSA has been proven to reach asymptotically the maximum achievable throughput of one packet per slot [7]. This makes IRSA, up to today, a reference protocol; which in turn explains the recent efforts to analyze and model it, for instance with the *Poisson Receiver* concept [8], or by studying other metrics such as *Age of Information* (AoI) as in [9] and [10]. Multiple IRSA variants are also being proposed, each addressing different technologies, scenarios, contexts, assumptions, or metrics.

## C. CONTRIBUTIONS AND ORGANIZATION OF THE ARTICLE

The main objective of the present work is to address the IRSA access scheme according to a competitive distributed approach. Users are grouped in classes, where users of one class share the same degree distribution, and each class has a fixed traffic load. Each class autonomously and selfishly sets its own degree probabilities to improve its effective throughput. This is naturally modeled as a non-cooperative game. In fact, only access schemes that reduce drastically signaling with a central controller in order to offer ultra-long battery lifetimes to IoT devices are feasible. Therefore, each class of devices must be able to select adequate degree distribution dynamically as the system load varies. The objective of this article is to study a distributed version of class-based IRSA

<footnote n="1">¹Note that it is an *inter-slot* SIC, instead of the more common *intra-slot* SIC, for which capture is sufficient.</footnote>

<footnote n="2">² In this case, the empirical degree distribution $\Lambda$ is: $\Lambda_2 = \frac{3}{5}$, $\Lambda_3 = \frac{1}{5}$, $\Lambda_4 = \frac{1}{5}$.</footnote>
from a game-theoretic perspective. Thus, the main questions
that this article will be addressing are the following:

* Is the performance of IRSA noticeably impacted when classes of users are autonomously setting their own IRSA parameters?

* Can we prove that users' competition will not result in permanent oscillations?

We answer these questions by studying the existence of the Nash Equilibria of the devised game. We also prove the convergence of the game towards those Nash Equilibria. In addition, we provide illustrative numerical results, including those displaying the convergence speed and the price of anarchy. Notably, we show that unrestricted class competition results in no loss of efficiency in the general case, and a very minor loss (less than 2%) in worst cases.

The remainder of this paper is organized as follows: Section II introduces related work on applying game theory to random access protocols. Section III explains the system model and states our problem. In Section IV, we explain and study our devised non-cooperative IRSA game. Finally, we present our numerical results in Section V. We conclude in Section VI.

## II. RELATED WORK

In the literature, several research directions have addressed topics that are related to modern random access protocols. Naturally, there also exists extensive literature on random access protocols themselves dating back to over several decades. In this section, we focus on research studies that applied various game-theoretic techniques to some random access protocols.

In a multiple access scheme, nodes can either cooperate or compete to achieve their objectives (e.g., optimal throughput, latency,...). Consequently, game theory has become a very useful mathematical tool to model and analyze multiple access schemes in wireless networks, and to obtain solutions for resource allocation, channel assignment, power control, and cooperation enforcement among the nodes. We can find two major game-theoretic approaches to model multiple access schemes: non-cooperative and cooperative game approaches [11]. In a non-cooperative game, the actions of the players are based on their individual payoff only. In a cooperative game, players establish an enforceable agreement in their group such that the game is between competing groups of players.

Game theory has been applied to random access for designing new random access protocols for future wireless applications. In [12], a general game-theoretic framework for designing contention-based medium access control has been presented. The behavior of selfish users who would want to transmit in every slot in an effort to get their packets successfully delivered to the receiver has also been addressed using game-theoretic approaches as in [13] and [14]. Game theory has been also applied to study the random access scenarios with power control. A variant of ALOHA involving two transmission power levels has been presented in [15].

The authors have presented two non-cooperative optimization concepts: the Nash equilibrium and the Evolutionary Stable Strategy. In [16], a multiple access game for ALOHA with (power-domain) NOMA has been formulated. The payoff function is based on an energy efficiency metric. The mixed-strategy Nash equilibrium (NE) has been derived for each user's transmission or access probability. It has been shown that the probability of transmissions can approach one as the reward of successful transmission increases. Therefore, the throughput does not approach zero, as in ALOHA, despite the packet collisions because the power levels of users are different thanks to NOMA.

The work in [17] exploits game-theoretic tools to study a non-cooperative IRSA game, and to our knowledge, this pioneering work [17] is also the only existing prior work to study IRSA from a game theory perspective. The described scenario involves a system of selfish uncoordinated users where each user tries to maximize its successful decoding probability. The aim of the study is to find the access cost that allows the degree distribution of users to be a Nash equilibrium. Thus, interestingly, the main idea is to change the cost function so that the existence of a Nash equilibrium is proven and it would be in the best interest of users to follow it. However, no proof was provided that the best response algorithm can attain the Nash Equilibria of the game. In addition, the fact that the operator does modify user utility function through pricing to enforce a predefined degree distribution may arguably seem a little artificial. And indeed, in any system, it is possible for the network operator to enforce any particular user behavior by incurring a large penalty for deviating from the operator-dictated behavior. Then [17] still left open the question of the behavior of the IRSA protocol, when users are competing and are left to their own devices, which is the topic that we are addressing.

## III. SYSTEM MODEL AND ASSUMPTIONS

### A. SYSTEM DESCRIPTION

Similar to [2], [17], and as described in Sections I-B1 and I-B2, we consider a system of *M* users sharing the same wireless channel and using IRSA as the access protocol. Time is divided into slots of equal duration and successive slots are regrouped in fixed-size frames of *N* slots. The time needed to send one packet is equal to the slot duration (including propagation delays, etc.). The load is defined by $G = \frac{M}{N}$ and it measures the average number of users per slot. We assume that the receiver is a single BS.

Each user sends its packet *l* times within the same MAC frame, where the repetition rate *l* of each user is selected randomly from a probability distribution $\Lambda$ defined by $D - 1$ probabilities: $(\Lambda_i)_{i=2,...,D}$. For $i \in \{2,...,D\}$, $\Lambda_i$ is the probability that the packet is repeated *i* times.

At the end of the frame, the SIC receiver attempts to decode the packets through iterative decoding (described in Section I-B1). In this work, we consider an idealized model of communication, as commonly assumed in the IRSA literature [2], [17], with a collision channel
model: two or more transmissions on the same slot result in a collision where no packet can be retrieved, whereas a single transmission (singleton) is always perfectly recovered. Fading effects are ignored. We assume that the SIC process is performed perfectly. It is possible to adopt more realistic assumptions on fading (see [18] and [19] for instance), on SIC errors due to residual energy after removing the signal from the slot (see [20]), etc., and this would be a subject of future work. We observe that even with the aforementioned simplifying assumptions, our game-theoretic analysis has merits as it would otherwise easily become intractable.

## B. DENSITY EVOLUTION

Density evolution is a tool for analyzing the asymptotic performance of network capability approaching error-correcting codes [21]. More recently, Density Evolution was first applied to IRSA by the pioneering article [2], to track the packet decoding process knowing some of the system parameters as $\Lambda, M, N$. By using this tool, one can estimate asymptotically how many packets will be recovered under these system parameters.

### 1) NOTATIONS FOR DENSITY EVOLUTION

As in [2], for mathematical convenience, we define the user and the slot node degree distributions through their probability-generating functions as the following:

$$ \Lambda(x) \triangleq \sum_{\ell} \Lambda_{\ell} x^{\ell} \text{ and } \Psi(x) \triangleq \sum_{\ell} \Psi_{\ell} x^{\ell} $$

where $\Lambda_{\ell}$, is the probability that a user will send $\ell$ replicas of its packet, and $\Psi_{\ell}$ is the probability there are $\ell$ collided packets on the same slot.

Degree distributions can be defined also from an edge perspective as follows:

$$ \lambda(x) \triangleq \sum_{\ell} \lambda_{\ell} x^{\ell-1} = \frac{\Lambda'(x)}{\Lambda'(1)} \text{ and } \rho(x) \triangleq \sum_{\ell} \rho_{\ell} x^{\ell-1} = \frac{\Psi'(x)}{\Psi'(1)} $$

where $\lambda_{\ell}$ is the probability that an edge is connected to a user node of a degree $\ell$, and $\rho_{\ell}$ is the probability that an edge is connected to a slot node of degree $\ell$.

We define the rate R as $R \triangleq \frac{1}{\Lambda'(1)}$, where $\Lambda'(1) = \sum_{\ell} \ell \Lambda_{\ell}$ is the average packet repetition rate. The probability that one user sends a packet mparative table of related works with respect to various approaches of game theory in terms of latency, throughput etc. can be discuson a given slot is $\frac{\Lambda'(1)}{N} = \frac{G}{RM}$. Then, the distribution $\Psi_{\ell}(x)$ follows a binomial distribution $Bin(M, \frac{1}{RM})$. When $M \to \infty$, the distribution $\Psi_{\ell}(x)$ becomes a Poisson distribution with parameter $\frac{G}{RM}$ and the edge degree distribution $\rho(x)$ becomes $\rho(x) \to e^{-G/R(1-x)}$.

### 2) ITERATED EQUATIONS FROM DENSITY EVOLUTION

In this section, for completeness, and as common in the IRSA literature, we introduce the recursive equations Eqs. (1),(2),(3), that allow the iterative computation of intermediate quantities from which the asymptotic system

performance (PLR (Packet Loss Rate), throughput) is ultimately derived in Eqs. (8),(9).

Note that they are well-known and are equivalent to those introduced by [2] by strong analogy with Low-Density Parity-Check codes (LDPC codes) [21], and later reproduced in [7], [17], etc. Still following [2], the decoding process is iterative and it is modeled by considering the probability of revealing a packet (initially all of them are unrevealed), and going back and forth between the set of slot nodes (on bottom) and the user nodes (on top) in Fig. 2.

Accordingly, let $q$ be the probability that an edge from a user node towards a slot node is unknown, while $p$ is the probability that an edge from a slot node to a user node is unrevealed (too many collisions). Pick randomly an edge on the graph, and consider the associated user node and slot node. Iterating from top to bottom, the packet of a given user could be decoded, if a replica of this packet has been decoded at least once on any other slot. Hence, $q = p^{\ell-1}$ (Fig. 2.c). In a similar fashion, iterating from bottom to top, the last edge connected to a slot node of degree $\ell$ could be decoded, if we have already removed the $\ell-1$ other edges of the $\ell-1$ other collided packets on the same slot. Hence, $(1-p) = (1-q)^{\ell-1}$ (Fig. 2.b).

Taking the average over all possible degrees, we can write:

$$ \bar{p} = \sum_{\ell} \rho_{\ell} q^{\ell-1} = \rho(q) \text{ and } \bar{q} = \sum_{\ell} \lambda_{\ell} p^{\ell-1} = \lambda(p) $$

Following the iterations of the decoding process, we obtain the well-known recursive IRSA [2] equations of the form:

$$ \bar{q}_i = f_b(\bar{p}_{i-1}), \bar{p}_i = f_s(\bar{q}_i), \text{ thus } \bar{p}_i = f_s(f_b(\bar{p}_{i-1})) \quad (1) $$

where:

$$ f_b(p) = \lambda(p) \text{ and } f_s(q) = 1 - \rho(1 - q) \quad (2) $$

$$ \text{and when } M \to \infty: f_s(q) \to 1 - e^{-\frac{G}{R}q} \quad (3) $$

The sequence $(\bar{p}_i)_{i=0,...,\infty}$ characterizes how many of the edges in the graph correspond to undecoded users at each iteration $i$. Note that the sequence $(\bar{q}_i)_{i=0,...,\infty}$ can equivalently be considered. Initial values are $\bar{q}_0 = 1$, hence $\bar{p}_0 = 1 - \rho(0)$. Alternately, picking $\bar{p}_0 = 1$ just shifts the sequence by one, as it implies that $\bar{q}_1 = \lambda(1) = 1$.

### 3) CONVERGENCE AND PROPERTIES OF ITERATED EQUATIONS

To be able to finely analyze the performance of IRSA, we prove some properties of the density evolution iterations, some of which are known for LDPC-codes [21] but need to be transposed to IRSA. When $M \to \infty$, Eqs. (1),(2),(3) yield:

$$ \bar{p}_i = 1 - e^{-\frac{G}{R}\lambda(\bar{p}_{i-1})} = 1 - e^{-G\Lambda'(\bar{p}_{i-1})} $$

We define:

$$ F(x; G, \Lambda) \triangleq 1 - e^{-G\Lambda'(x)} \quad (4) $$

then, we can re-write that:

$$ \bar{p}_i = F(\bar{p}_{i-1}; G, \Lambda) \quad (5) $$
<figure><img src="image_3.png" /><figcaption>FIGURE 2. Illustration of IRSA density evolution probabilities by knowing and revealing the edges.</figcaption></figure>

So when $M \to \infty$:

$$F(\bar{p}_{i-1}; G, \Lambda) < \bar{p}_{i-1} \text{ for all } \bar{p}_{i-1} \in [0, 1] \quad (6)$$

Similar to the proof in [21, Sect. 3.10] and specifically [21, Lemma 3.55] “Monotonicity with Respect to Iteration”, we can now prove that the sequence $(\bar{p}_i)$ is decreasing along with other properties.

This is done in Appendix A: Lemma 4 proves that $F$ is a monotone function, Lemma 5 proves that the sequence is decreasing. An important consequence is given by the Theorem 3 that proves that:

The sequence $(\bar{p}_i)$ is decreasing and converges towards a limit $p_\infty$, that is the fixed point of the equation:

$$p_\infty = F(p_\infty; G, \Lambda) \quad (7)$$

with $F$ defined in Eq. (4).

### 4) PERFORMANCE METRICS FROM DENSITY EVOLUTION

As explained in previous sections, the evolution of probabilities and their limit, the fixed point $p_\infty$, gives an indication of the amount of decoded users. It is valid when the frame size $M$ grows infinitely and can be a good approximation for a large finite frame size [2]. The two main performance metrics of density evolution that we use in this work are defined from $p_\infty$ as follows:

(a). $p_\infty$: the fixed point of Eq. (7) in Theorem 3. It is a function of $\Lambda$ and $G$. It can be mapped to the probability of a packet loss at the end of the decoding process. In more detail, as indicated in [2], $p_\infty$ is the probability that an edge in the bipartite graph of Fig. 2 is unrevealed at the end of the decoding process.

(b). The Packet Loss Rate (PLR): since the probability that a packet is not decoded after a certain number of decoding iterations is given by the probability that all its replicas are unrevealed, if the node has $\ell$ replicas, then the probability that a packet of this node is lost at the final iteration is $p_\infty^\ell$. By averaging on all the possible degrees, we have:

$$PLR(p_\infty) = \Lambda(p_\infty) \quad (8)$$

See [2, footnote 13].

(c). The throughput: the expression of the effective throughput (i.e the goodput) is the load multiplied by the PLR:

$$T(\Lambda) \triangleq G \cdot (1 - \Lambda(p_\infty)) \quad (9)$$

It measures the average number of decoded packets per slot. With a collision model, it verifies $T \le 1$, and without losses $T = G$.

Notice that because we assume that the load $G$ is constant (e.g. consider IoT applications where nodes are sending packets with fixed average rate), the throughput is essentially a proxy for the PLR.

### 5) PERFORMANCE METRICS WITH SEVERAL CLASSES

We extend the results of the previous section to a system that has two different classes $C_0$ and $C_1$ and a fixed global load $G$. Each user is assumed to belong to exactly one class, and all users of one class $c$ are assumed to use the same degree distribution $(\Lambda_{c,i})_{i \ge 2}$. $\Lambda_{C_0}$ and $\Lambda_{C_1}$ are the degree distributions of the classes, $C_0$ and $C_1$, respectively. We introduce $\alpha \in [0, 1]$, a parameter that indicates the proportion of the users that are in class $C_0$ ($\alpha = \frac{1}{2}$ implies that users are split equally among both classes).

We define $\Lambda_{\text{avg}}(x)$, the average degree distribution of both classes, as:

$$\Lambda_{\text{avg}}(x) = \alpha \Lambda_{C_0}(x) + (1 - \alpha) \Lambda_{C_1}(x) \quad (10)$$

The system behaves as if there was only one class of users, with load $G$, and degree distribution $\Lambda_{\text{avg}}$.

Then $p_\infty$ is obtained as the fixed point of $p_\infty = F(p_\infty; G, \Lambda_{\text{avg}})$. The throughput of the two classes is different and is obtained respectively as:

$$\begin{aligned} T_{C_0}(\Lambda_{C_0}, \Lambda_{\text{avg}}) &= \Lambda_{C_0}(p_\infty) \\ T_{C_1}(\Lambda_{C_1}, \Lambda_{\text{avg}}) &= \Lambda_{C_1}(p_\infty) \end{aligned} \quad (11)$$

These results can be generalized to more than one class.

## C. OPTIMAL FORMULATION FOR IRSA

Before addressing the non-cooperative version with competing users, we first describe the optimization problem for a centralized IRSA. These preliminaries will provide a performance baseline for the non-cooperative setting, and also illustrate the optimization of IRSA in general.

### 1) GENERAL OPTIMIZATION

The problem of IRSA parameters optimization has been widely tackled in the last decade. The main purpose behind studying this protocol is generally to find a better variant of
IRSA that could satisfy the needs of IoT networks. Given any IRSA system, the goal is often to find an optimized user degree distribution that maximizes a certain metric (throughput, achievable load, etc). This problem is usually formulated as an optimization problem which can be described as follows:

$$ \begin{array}{l} \underset{(\Lambda_i)}{\text{maximize}} \mathcal{O}(\Lambda_0, \Lambda_1, \dots, \Lambda_D) \\ \text{subject to} \quad 0 \le \Lambda_i \le 1 \quad \forall i \\ \quad \sum_{i=0}^{i=D} \Lambda_i = 1 \end{array} \qquad (12) $$

where $\mathcal{O}$ is the system criteria that needs to be optimized and $D$ is the maximum degree.

The IRSA optimization problem described in Eq. (12) is often difficult to solve, especially because the objective function is expected to be non-linear or and can be non-convex.<fnref n="3" /> Nevertheless, many studies have been formulated and solved this optimization problem using different tools. In [2], the author has adapted a well-known tool in “Low-Density Parity-Check” (LDPC) codes [22], the Density Evolution (DE), to analyze the asymptotic performance of framed IRSA protocol, and to find numerical solutions through the heuristic optimization algorithm differential evolution. Differential evolution is a generic derivative-free optimization algorithm (“black-box optimization”) [23]. In this work, we later use it to optimize the transmission strategy (the degree distribution) by performing a heuristic search among a very large space of candidate solutions.

## 2) OPTIMAL FORMULATION FOR A ONE-CLASS IRSA SCENARIO

In the classical IRSA system of one class of users, the aim is to find the best degree distribution that maximizes the system throughput at a given network load $G$. We describe the optimization problem as follows:

$$ \begin{array}{l} \underset{(\Lambda_i)}{\text{maximize}} T(\Lambda) \\ \text{subject to} \quad 0 \le \Lambda_i \le 1 \quad \forall i \in \{2, 3, \dots, D\} \\ \quad \sum_{i=0}^{i=D} \Lambda_i = 1 \end{array} \qquad (13) $$

where $\Lambda$ is the degree distribution shared between all users, and $T$ is the system throughput, which measures the average number of decoded packets per slot. When using density evolution, and assuming asymptotically large frame size, $T$ is given by Eq. (9), which implies computing $p_\infty(\Lambda, G)$ from Eq. (7).

## 3) OPTIMAL FORMULATION FOR A TWO-CLASS IRSA SCENARIO

We extend the optimal formulation of the previous section, to a system that have two different classes $C_0$ and $C_1$ and a fixed global load $G$. Using the performance metrics for multiple classes from Section III-B5, we can rewrite the optimization problem Eq. (12) for a class selfishly optimizing its own throughput as:

$$ \begin{array}{l} \underset{(\Lambda_i)}{\text{maximize}} T_c(\Lambda_c, \Lambda_{\text{avg}}) \\ \text{subject to} \quad 0 \le \Lambda_{c,i} \le 1 \quad \forall i \in \{2, \dots, D\} \\ \quad \sum_{i=0}^{i=D} \Lambda_{c,i} = 1 \end{array} \qquad (14) $$

The described problem in Eq. (14) can be solved by using the expression of the throughput in Eq. (11).

# IV. THE CLASS-BASED IRSA NON-COOPERATIVE GAME

In this section, we study the autonomous behavior of competing classes of users that engage in a non-cooperative strategic IRSA game. Non-cooperative game theory models the interactions between players competing for common resources. Here, the classes of users are the decision-makers or players of the game that seek selfishly to maximize their own throughput. We define a multi-player game $\mathcal{G}$ between $n$ classes of users. Each class is assumed to make its decisions without knowing the decisions of other classes.

## A. FORMALIZATION OF THE NON-COOPERATIVE IRSA GAME

The IRSA non-cooperative game $\mathcal{G} = \langle K, S, T \rangle$ can be described as follows:

* A finite set of classes $K = (C_0, \dots, C_n)$.

* For each class $c \in K$, the space of pure strategies $S_c$ is formed by the Cartesian product of each set of pure strategies $S_c = S_{c,1} \times \dots \times S_{c,L}$, where $L$ is the maximal degree.

* An action of each player (i.e. class) consists in selecting one distribution $\Lambda_c$ for a set of frames, where $\Lambda_c \in S_c$ represents a user degree distribution $\Lambda_c = \{\Lambda_{c,1}, \Lambda_{c,2}, \dots, \Lambda_{c,L}\}$. As $\Lambda_{c,k}$ is the probability of repeating a packet $k$ times for a user in class $c$, then $\Lambda_{c,k} \in [0, 1]$, for $k \in \{1, \dots, L\}$. Furthermore, as previously, the general degree distribution (strategy) of one class $c$ can be written in polynomial form as follows:

$$ \Lambda_c(x) = \sum_{\ell=2}^{L} \Lambda_{c,\ell} x^{\ell} = \Lambda_{c,2} x^2 + \Lambda_{c,3} x^3 + \dots + \Lambda_{c,L} x^L \qquad (15) $$

* A strategy profile $\Lambda = (\Lambda_1, \dots, \Lambda_n)$ specifies the strategies of all players and $S = S_1 \times \dots \times S_n$ is the set of all strategies.

* A set of utility functions $T = (T_1(\Lambda), T_2(\Lambda), \dots, T_n(\Lambda))$ where each utility function quantifies players' utility for

<footnote n="3">³For instance, if the objective is the PLR as in Eq. (8), observe that it involves $p_\infty$ an implicit function of $\Lambda$, $G$, that has no reason to be linear (nor even continuous). If the objective were the maximum throughput with the load $G$ as a variable, the expression of the throughput as $G$ times $\Lambda$ in Eq. (9) is not linear and does not point towards obvious convexity.</footnote>
a given strategy profile $\Lambda$, where $T_c: S_c \to \mathbb{R}$ measures the preference of the strategy $\Lambda_c \in S_c$ played by a player c.

Each player (class) intends to select the strategy (the degree distribution) that maximizes its utility function. The utility function of a player $c \in K$ that plays strategy $\Lambda_c \in S_c$ is the *Throughput* of this player, defined as:

$$T_c(\Lambda_c) = G \cdot (1 - \text{PLR}_c(\Lambda_c)) \quad (16)$$

where $PLR_c$ is the packet loss rate of class c users, and $G$ is the total network load. When $G$ is constant, maximizing the throughput is equivalent to minimizing the Packet Loss Rate (PLR), as in Eq. (11). This corresponds to an optimization problem as in Section III-C3 written with an arbitrary number of classes.

## B. TWO-CLASSES IRSA GAME

We consider two classes of users. The two major components of the devised two-players IRSA game are as follows:

* A finite set of players, denoted by $K$, $c \in K$ is a class of users. For clarity, we coin the two classes as class $C_0$ and class $C_1$ respectively, i.e. $K = \{C_0, C_1\}$.

* Accordingly, the strategy space of class $C_0$ (resp. class $C_1$) is denoted by $S_{C_0}$ (resp. $S_{C_1}$).

The total network load is defined as $G = \frac{N_{C_0}+N_{C_1}}{M}$, where $M$ is the number of slots in the frame and $N_{C_0}$ (resp. $N_{C_1}$) is the number of users in class $C_0$ (resp. the number of users in class $C_1$). We also define $\alpha = \frac{N_{C_0}}{N}$ as the proportion of class $C_0$ users over the total number of users $N$ (hence $(1 - \alpha)$ is the proportion of $C_1$ users) as in Section III-B5.

**Definition 1 (Restricted IRSA Game):** We define a restricted IRSA game where only two coefficients in the degree distribution are non-zero for all the strategy sets of the two players: we denote respectively by $\ell > m > 0$ with $m \neq \ell$, the two non-zero degrees:

$$\Lambda_{C_0}(x) = \Lambda_{C_0,m} \cdot x^m + \Lambda_{C_0,\ell} \cdot x^\ell = \Lambda_{C_0,m} \cdot (x^m - x^\ell) + x^\ell \quad (17)$$

where the last equality comes from the fact that $\Lambda_{C_0,m} + \Lambda_{C_0,\ell} = 1$. We note for convenience $s_c = \Lambda_{c,m}$, accordingly:

$$\Lambda_c(x) = s_c x^m + (1 - s_c)x^\ell \quad (18)$$

$$\text{and } T_c(s_c) = G \cdot (1 - \text{PLR}_c(s_c)) \quad (19)$$

where $\ell$ and $m$ are the non-zero constant integers representing the repetition degrees of the game with $\ell > m$.

Eq. (13) explains the main purpose behind IRSA optimization. Any enhancement in this protocol could be translated into an optimization problem that maximizes a given system metric (load, achieved throughput,...) or minimizes the impact of a given drawback (delay, PLR,...). In the IRSA game, instead of maximizing the total throughput as in Eq. (12), each player aims to maximize its own throughput function in Eq. (19), for a given network load.

## C. NASH EQUILIBRIUM OF THE IRSA GAME

In this section, we establish the needed proof to show that the user degree distribution $\Lambda(x)$ could be a Nash equilibrium (NE) for the 2-classes strategic IRSA game. We first use the classic definition of the Nash equilibrium as the point where no player will gain by changing its strategy unilaterally. In our case, it corresponds to:

**Definition 2 (Nash Equilibrium for IRSA Strategic Game):** A Nash equilibrium (NE) for the 2-classes IRSA strategic game is a strategy (degree distribution), $\Lambda^* = (\Lambda_c^*, \Lambda_{-c}^*)$ such that:

$$T_c(\Lambda_c^*, \Lambda_{-c}^*) \geq T_c(\tilde{\Lambda}_c, \Lambda_{-c}^*) \quad \forall \tilde{\Lambda}_c \in S_c \quad (20)$$

where $\Lambda_c^*$ is the strategy of class $c \in \{C_0, C_1\}$ and $\Lambda_{-c}^*$ is the strategy of the other class(es).

NE describes the operating point which is stable in terms of local efficiency for all players. Therefore, in our IRSA game, we seek to study the existence of pure NEs and how to attain them.

Consider the 2-classes IRSA game, defined as a static strategic non-cooperative game with complete information and a finite set of players (2 players). There exist a number of ways to establish the existence of a Nash equilibrium, one of which is the Debreu-Fan-Glicksberg theorem (see for instance the overview in [24]): with our notations, (a) if $\forall c \in \{C_0, C_1\}$, $S_c$ is a compact and convex set, (b) the utility function $T_c(\Lambda_c)$ is a continuous function in the profile of strategies $S$ and (c) it is quasi-concave in the set of a player $c$ own strategies $S_c$, then the game has at least one pure NE, according to this Debreu-Fan-Glicksberg theorem.

We actually prove this supposition in the following theorem 1:

**Theorem 1 Existence of Nash Equilibrium for the 2-Classes Restricted IRSA Game for Large G: The two-players restricted IRSA game admits a Nash Equilibrium when $G \to \infty$.** In other words, there exists a load limit $G_1 > 0$, such that for any load $G \geq G_1$, the game always admits at least one pure Nash equilibrium.

**Proof:** For our proof of the NE existence, we split the proof into three Lemmas, described later, that establish the previous conditions (a), (b), and (c). Lemma 1 is provided to prove that the set of strategies of our 2-classes IRSA game is compact and convex. Lemma 2 proves that the utility function defined in Eq. (19) is continuous in the profile of strategies $S$ under some conditions. And finally, Lemma 3 shows that the utility function of any player $c$ is quasi-concave in its own strategy, with $c \in \{C_0, C_1\}$, for all $G$ greater than a fixed limit $G_0$. As a consequence, the conditions of the Debreu-Glicksberg-Fan (1952) theorem are satisfied, which proves the existence of a Nash equilibrium. $\square$

## D. ANALYSIS OF THE UTILITY FUNCTION

In this section, we present the three necessary lemmas to prove Theorem 1.

**Lemma 1:** Let $S_c$ be the set of strategies of player $c \in \{C_0, C_1\}$, where each strategy is a degree distribution $\Lambda_c(x)$
written as:

$$S_c \triangleq \{ \Lambda_c(x) \mid \Lambda_c(x) = s_c x^m + (1 - s_c)x^l, \forall s_c \in [0, 1] \}$$

Then the set $S_c$ is compact and convex.

The proof of Lemma 1 is in Appendix B.

The second and third conditions to have a pure NE are relative to the utility function described in equation (19). Alongside Lemma 1, we need to show that the utility function for any class $c \in \{C_0, C_1\}$ is continuous in any strategy (proven in Corollary 1) and quasi-concave in its own strategy $s_c \in S_c$ (proven in Lemma 3).

As the player utility is a function of its throughput, we use the results and definitions from density evolution from Sections III-B4 and III-B5, to examine some properties of the utility function. The value of the fixed point $p_\infty$ depends on the strategies of both players $s_0 = \Lambda_{C_0}, s_1 = \Lambda_{C_1}$ and also on the load $G$, and hence can be written as $p_\infty(s_0, s_1, G)$.

In the following Lemma, we prove that, except for some set of points $S(s_0, s_1, G)$, $p_\infty$ is continuous in the strategy of one player $s_0$ (actually the stronger result is that $p_\infty$ is continuously differentiable). This lemma is a first step to prove that the utility function is also continuous in $s_0$.

**Lemma 2 Continuity and Differentiability of $p_\infty(s_0)$:** Considering that $s_1$ and $G$ are fixed, $p_\infty(s_0)$ (which becomes then a function of one variable $s_0$), is a continuously differentiable function except on a set of points coined $S(s_0, s_1, G)$. This set of points $S(s_0, s_1, G) \subset [0, 1]$ corresponds to the points where some expression $g(s_0, p_\infty(s_0))$ equates to zero.

*Proof:* We consider here that $s_1$ and $G$ are kept constant, and $p_\infty$ (also denoted $p$ in this proof for simplicity) is then a function of a single variable (the strategy of one player) $s_0$, as well for all the quantities considered in this proof. We make use of the implicit function theorem, [25, Th. 1.3.1] on $p_\infty(s_0)$ which is defined by the fixed point equation (7).

The main expression of the implicit function theorem is intuitively obtained by considering $p_\infty$ as a solution of the implicit equation $H(p) = 0$. This is equivalent to the fixed point equation Eq. (7) when introducing the notation $H(p) = F(p; G, \Lambda) - p$, and then computing the total derivative of (i.e. chain rule for) the equation $H(p) = 0$. Remember that the only variable is $s_0$, and $p$ depends on $s_0$. Differentiating both sides of $H(p) = 0$ with respect to $s_0$ gives the well-known expression, e.g. [25, Eq. (1.13)]:

$$\frac{dH}{ds_0} = \frac{\partial H}{\partial s_0} \frac{\partial s_0}{\partial s_0} + \frac{\partial H}{\partial p} \frac{\partial p}{\partial s_0} \qquad (21)$$

Thus:

$$\frac{dH}{ds_0} = 0 \Rightarrow \frac{\partial p}{\partial s_0} = -\frac{\frac{\partial H}{\partial s_0}}{\frac{\partial H}{\partial p}} \qquad (22)$$

The derivative of $p$ exists only for $s_0$ for which the denominator is not zero, so that the solution $p(s_0)$ is continuously differentiable in a neighborhood of $s_0$.

Now, using the definition $H(p) \triangleq 1 - e^{-G\Lambda'(p)} - p$, we compute:

$$\frac{\partial H}{\partial s_0} = G\alpha(m p^{m-1} - \ell p^{\ell-1})e^{-G\Lambda'(p)}$$

considering that:

$$\Lambda(p) = \alpha(s_0 p^m + (1 - s_0)p^l) + (1 - \alpha)(s_1 p^m + (1 - s_1)p^l)$$

And since $H(p) = 0$, hence $1 - p = e^{-G\Lambda'(p)}$, we obtain:

$$\frac{\partial H}{\partial s_0} = G\alpha(1 - p)(m p^{m-1} - \ell p^{\ell-1}) \qquad (23)$$

Taking the derivative of the function $H(p)$ with respect to $p$:

$$\frac{\partial H}{\partial p} = G(1 - p) \cdot \alpha \left[ (m(m - 1)s_0 p^{m-2} + \ell(\ell - 1)(1 - s_0)p^{\ell-2}) + G(1 - p) \cdot (1 - \alpha) \times \left[ (m(m - 1)s_1 p^{m-2} + \ell(\ell - 1)(1 - s_1)p^{\ell-2}) \right] - 1 \right] \qquad (24)$$

Solving equation (24) = 0 helps to find the roots where the derivative of $H(\Lambda, p)$ is zero, and for these roots, the derivative of $p$ defined in equation (22) does not exist. In other words, this gives us the set:

$$S(s_0, s_1, G) = \{s_0 \in [0, 1] \mid \text{Eq. (24) = 0 is verified.}\}$$

In addition, let us consider an interval $[a, b]$, where $S(s_0, s_1, G) \cap [a, b] = \emptyset$. For any $x \in [a, b]$, then $p_\infty$ is continuously differentiable in an open set around $x$ [25, Th. 1.3.1]. Thus, $p_\infty$ must be continuously differentiable in the whole interval $[a, b]$. $\square$

**Corollary 1 Continuity and Differentiability of the Utility Function:** Considering that $s_1$ and $G$ are fixed, the utility function defined in equation (16) could be written as $T_{C_0}(s_0) = G(1 - (s_0 p_\infty^m + (1 - s_0)p_\infty^l))$. The utility function (as a function of one variable $s_0$) is a continuously differentiable function except on some set of points $S(s_0, s_1, G)$, as it is a composition of continuous functions.

**Lemma 3 (Concavity of the Utility Function):** Considering that $s_1$ and $G$ are fixed, Let $T_{C_0}(s_0) = G(1 - \Lambda_{C_0}(s_0)) = G(1 - (s_0 p_\infty^m + (1 - s_0)p_\infty^l))$, be the utility function of class $C_0$, playing a strategy $s_0 \in S_{C_0}$ where $p_\infty$ is a fixed point given by the solution of the equation (7).

When $G \to \infty$, $T_{C_0}$ becomes a monotone function (increasing) with $s_0$.

The proof of Lemma 3 is in Appendix C. The three Lemmas of this section prove the Theorem 2.

## E. ATTAINING PURE NASH EQUILIBRIUM

The Theorem 2 established the proof of the existence of (at least) one pure Nash equilibrium. In this section, we are interested in the dynamics of the game, and the convergence to a Nash equilibrium. We start by introducing the dynamics of the game by indicating how players adapt their strategies.
The better reply strategy of player c is the one that improves its utility given other players' strategies. A better reply dynamics scheme consists of a sequence of rounds, where each class c chooses a better reply to the strategies of other classes in the previous round, but not necessarily the best one.<fnref n="4" /> In the first round, the choice of each player is a better strategy based on its arbitrary belief about what the other players will choose. In some games, the sequence of strategies generated by better reply dynamics converges to a NE, regardless of the players' initial strategies. It is the case for our game $G = \langle K = \{C_0, C_1\}, S, T \rangle$ as according to [26], two-player generic quasi-concave games have the “Weak Finite Improvement Property” (WFIP).

**Property 1 (Convergence of Better Reply under WFIP [26]):** Consider a two-player game $G = \langle K = \{C_0, C_1\}, S, T \rangle$, each player $c \in K$ has a one dimensional, compact, convex strategy set $S_c$, and a utility function $T_c$ that is twice continuously differentiable in $s_c$, $\forall c \in \{C_0, C_1\}$ and quasi-concave with respect to $s_c \in S_c$.
Then the game has the weak FIP, and this implies that from any action profile there is a finite sequence of single-player improvements leading to a Nash Equilibrium [26].

We apply this property to our problem, which builds upon Theorem 1, by providing proof for convergence towards NE:

**Theorem 2 Convergence to Nash Equilibrium for 2-Classes Restricted IRSA Game for Large $G$:** There exists a load limit $G_1 > 0$, such that for any load $G \ge G_1$, the two-classes restricted IRSA game will converge to a Nash Equilibrium when iterating better reply dynamics.

*Proof:* Under the assumption that $G \to \infty$, the existence of the NE is established by Theorem 1 for $G \ge G_1$ for some $G_1 > 0$. Also, according to Lemma 1, Lemma 3, and Corollary 1, our game is a generic two players quasi-concave game. And for $G > G_1$, $T_c$ is actually not only continuously differentiable but according to the analytic implicit function theorem [25, Section 6.1], infinitely differentiable. Hence, the conditions of Property 1 are satisfied, and therefore, following [26], better reply dynamics are guaranteed to converge to pure NEs for $G > G_1$. □

## F. GENERALIZATIONS OF THE TWO-CLASSES RESTRICTED IRSA GAME

The existence of a Nash equilibrium and the convergence to the Nash equilibrium was established for the two-classes restricted IRSA games. One important question would be: how to generalize the results?

For the case of *n*-classes restricted IRSA game (with $n \ge 3$): the performance of the system is obtained as previously, by computing a global average distribution $\Lambda_{avg}$ (generalizing the Eq. (10)), and the global $p_\infty$. When one class optimizes its utility, the system actually behaves as if all the other $n-1$ classes are equivalent to a single competing

class, and the Theorem 1 can be generalized. On the other hand, the convergence to a Nash equilibrium is no longer established, as the result of the WFIP that we are using is specifically for a two-player game [26].

The second case is the general IRSA game as opposed to the restricted IRSA game of definition 1: here, players have multivariate utility functions, and results on the quasi-concavity are more difficult to establish. The issue is that the utility is computed from a multivariate implicit function $p_\infty$ (which is also not always guaranteed to be continuous). Hence, it is an open problem but our numerical results at the end of the Section V show that the general IRSA game is behaving similarly to the restricted IRSA game.

## V. NUMERICAL RESULTS

In the following, we assess the performance of the distributed IRSA game, described in section IV, and present numerical verification that it attains Nash Equilibrium via the better reply strategy. We assume a collision channel with fixed-size frames. The users select the slots uniformly at random, however, they select the number of packet repetitions according to their degree distributions. The performance is evaluated through density evolution. The network load is varied between $G = 0$ and $G = 2$.

In Fig. 3, we show the optimal throughput of a single class of users using the IRSA protocol with two coefficients for two degrees ($m, \ell$), as in restricted IRSA (definition 1). In Fig. 3(a), we consider one single class which always uses degree $m = 2$ and another degree $\ell$ chosen from $\{3, 4, \dots, 8\}$. We formulate the centralized optimization problem Eq. (13) and numerically compute the optimal throughput in Python with the *scipy differential evolution* algorithm. We compare the obtained optimal throughput for each pair of degrees. For each pair, there is a maximum value for the obtained throughput before it starts to drop rapidly, and then, it continues to decrease slowly with the increase of load. In fact, we focus on the part where this sudden decrease occurs. In Fig. 3(b), we zoom in on this phenomenon, where we can see clearly the impact of the discontinuity of the utility function for some values of the load (the sudden decrease). We proved in Corollary 1 that the utility function (the throughput) is continuously differentiable except for some points. Thus, the highlighted decrease in Fig. 3(b) is due to the discontinuity of the throughput in one of those points, itself due to a discontinuity of $p_\infty$ in the same points. The same phenomenon happens in Fig. 3(c), if the unique class uses degree $m = 3$ and another degree $\ell$ from $\{4, 5, \dots, 8\}$. We observe that the discontinuity occurs earlier, and the throughput at high loads is lower. The maximum achieved loads when using a degree 2 and another degree are higher than the maximum achieved loads when using a degree 3 and another degree. Therefore, it is generally better to pick degree 2 and another degree (higher than 3). For the rest of the results, we will focus on the distributions with $m = 2$. In Fig. 3(d), we show clearly the discontinuity region of Fig. 3(c) where the throughput drops rapidly for some loads. The study of the optimal utility

<footnote n="4">⁴the strategy of choosing the best one, corresponds instead to the classical “best response” dynamics, for which the same hypotheses detailed later are not sufficient to establish convergence.</footnote>
<figure><img src="image_4.png" /><figcaption>**FIGURE 3.** The optimized throughput for one class using two degrees for all loads.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**FIGURE 4.** Comparison between the achieved packet loss rate of both players (classes), $C_0$ and $C_1$, when using Best Response and Better Reply strategies.</figcaption></figure>

function helps to select the right pair of degrees for a given load.

Notice that for two-classes IRSA game instead, and for instance if the selected degrees for both classes are ($m = 2, \ell = 6$) for a load of $G = 0.93$ (see the red curve in Fig. 3(b)), many classical results from game theory cannot

be directly applied owing to the fact that the utility function of the pair ($m = 2, \ell = 6$) is discontinuous for that load. Indeed, the game no longer verifies the set of conditions in Property 1 because of the discontinuity of the utility function. In other words, the existence of a Nash Equilibrium is no longer guaranteed. Note that the convergence of the
<figure><img src="image_6.png" /><figcaption>FIGURE 5. The variation of $p_{\infty}$ as a function of the strategies of both players $s_0$ and $s_1$: $m = 2, l = 6$ and $G = 0.93$.</figcaption></figure>

two-classes IRSA game to a stable point was nevertheless always empirically observed (through best reply dynamics), as shown later. Precisely, the utility function of one class, described in Eq. (16), is a function of $p_{\infty}$. In Lemma 2, we have studied the continuity and the differentiability of $p_{\infty}(s_0)$. The proof of Lemma 2 affirms that: for some points $S(s_0, s_1, G)$, the probability $p_{\infty}$ might have a discontinuity (due to a potentially infinite derivative) in $s_0$. Alongside this proof, we went further in our simulations to study the behavior of $p_{\infty}$ in the discontinuity region. For the same example, with a pair of degrees ($m = 2, \ell = 6$) and a load of $G = 0.93$, we highlight in Fig. 5 the discontinuity of $p_{\infty}$ in the strategy of the first player $s_0$ for all the possible strategies of the second player $s_1$.

The important question is whether the restricted IRSA game can attain Nash Equilibria. We have proven in Theorem 1 a sufficient condition for the convergence of better reply to NE, i.e: $G \ge G_1$; where $G_1$ originates from Lemma 3 and verifies that $\forall G > G_1$, and for any $s_0, s_1, T_{C_0}, G_1$ will be continuous and its derivative is positive. For ($m = 2, \ell = 6$), we numerically searched for $G_1$ for which the property is verified. We identify the smallest value of $G_1$: $G_1 \approx 1.295$. We also observed for $G \ge 0.938...$, $S(s_0, s_1, G) = \emptyset$, i.e. $p_{\infty}$ and $T_{C_0}$ are continuous. In the following, we experiment with all values of $G \in [0, 2]$, to explore whether convergence is still always experimentally observed.

We explore the convergence towards Nash Equilibrium points using the better reply algorithm implemented in the following way: the two players (classes) select in turn a better reply based on the knowledge of the other player strategy. At each iteration, each player randomly chooses a number of distributions (100 in our case) and picks randomly one among the ones that give better or equal throughput compared to the selected distribution in the previous iteration. As shown in Fig. 4(b), we test the better reply algorithm for a pair of degrees ($m = 2, \ell = 6$) and a load of $G = 0.96$. The sequence of selected strategies by the better reply algorithm starts to converge towards the point ($T_{C_0} \approx 0.42, T_{C_1} \approx 0.42$) after almost 850 rounds. Furthermore, we also used the best

response algorithm for the same settings. In the best response dynamics, each player chooses in turn the strategy that has the best outcome knowing the other player's strategies, according to Eq. 14. The best response algorithm converges after approximately 100 iterations towards the same equilibrium point. Fig. 4(a) shows distinctly that the best response algorithm converges much faster than the better reply algorithm.

In addition to the comparison between the convergence of better reply and best response towards a Nash Equilibrium, we show in Fig. 6 how the strategies change with the load: precisely we show the coefficients $s_0, (1-s_0), s_1$, and $(1-s_1)$ at the final iterations. For low loads, many possible strategies could be Nash Equilibrium points. As the network is low-loaded the asymptotic PLR of 0 can be achieved, many degree distributions (strategies) with two degrees from $\{2, 3, ... 8\}$ may achieve this asymptotic zero packet loss rate. As a consequence, these strategies can obtain a throughput equal to 0 for both players. Therefore, in both figures, Fig. 6(a) and Fig. 6(b), we have replaced the selected strategies (coefficients) by zeros whenever we had zero packet loss rate: at convergence, the strategies are the random outcome of the iterative selection among a set of many possible strategies that lead to the same equilibrium point ($T_{C_0} = 0, T_{C_1} = 0$). Furthermore, Fig. 6(a) and Fig. 6(b) show how both players behave in the discontinuity region $G \in [0.86, 0.95]$. We observe that as the first player (class $C_0$) always chooses degree 2 (as $s_0 = 1$), the other player (class $C_1$) always chooses degree 6 (i.e. $s_1 = 0$). For higher loads $G > 0.95$, both players converge towards the same strategy and use degree 2 (i.e. $s_0 \to 1$ and $s_1 \to 1$). This is because when the network is highly loaded, repeating the packets creates more collisions and worsens the network load, hence the smallest degree is the best option for both classes.

Furthermore, we measure the inefficiency of the equilibrium for our restricted IRSA game in comparison with a centralized optimal approach obtained by solving eq. 13 for one class through computing the Price of Anarchy (PoA). In Fig. 7, we show how the selfish behavior of the two players (classes) is close to the optimal solution. In Fig. 7(a), the discrepancy between the summed throughput (the sum of the throughput of both players) obtained by the IRSA game and the optimized throughput is very small. This discrepancy is only noticeable around and in the discontinuity region when the best response strategy is used. Fig. 7(b) shows the computed difference between the throughput of the optimal and the best response algorithm for the IRSA game. It appears that it is less than 2%. The same impact can be seen in Fig. 7(c), where the better reply algorithm is used, and indeed the performance of both best response and better reply is nearly identical.

The reasoning is that, for low loads, many equilibrium points could lead to a zero packet loss rate and coincide with the optimal solutions. For high loads (more than 1.25), the players (classes) keep using the smallest degrees with a probability almost equal to 1 to reduce collisions. Otherwise, a slight change in the strategy of one player could lead to more
<figure><img src="image_7.png" /><figcaption>(a) The changes of the two players degrees as a function of load, with (b) The changes of the two players degrees as a function of load, with best response strategy better reply strategy</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>(a) The Price of Anarchy for the best response strategy</figcaption></figure>

<caption>(b) The Price of Anarchy (difference with optimal) for the best response strategy</caption>

<caption>(c) The Price of Anarchy (difference with optimal) for the better reply strategy</caption>

<figure><img src="image_9.png" /><figcaption>**FIGURE 8.** Convergence iterations with different loads.</figcaption></figure>

<caption>**FIGURE 9.** The comparison between the price of anarchy for the case of two degrees with the case of all possible degrees.</caption>

collisions and this, in turn, makes all the players lose. For that reason, the only equilibrium points are the optimal points.

We display in Fig 8 the iterations where the better reply algorithm heads towards convergence. It is clear that the better reply algorithm takes more iterations to converge in the discontinuity region, which also corresponds to the results shown in Fig 4(b) (average of 100 simulations per point).

In the theoretical study, we focused on restricted IRSA games. In Fig 9, we compare the price of anarchy between two types of games: the first game is the restricted IRSA game, where players have only two different degrees to choose from, and the second game is the general IRSA game, where the players have all possible degrees to choose from (up to a maximum degree). The goal of this comparison is
to understand if both types of games lead to different results. We focus on the price of anarchy, as it is the efficiency loss caused by competition, which is one of our main questions. We observe that there is very little discrepancy between the price of anarchy obtained by both types of IRSA games (restricted or general).

This illustrates empirically that the number of possible degrees in the game has little impact on the game outcomes in our scenarios, and that we might expect the general IRSA game to behave similarly to the restricted IRSA game.

## VI. CONCLUSION

In this article, we studied one of the modern random access protocols, Irregular Repetition Slotted Aloha (IRSA). We addressed the IRSA access scheme in a distributed fashion where users are grouped in competing classes, with users of the same class sharing the same degree distribution. The distributed approach is modeled as a non-cooperative game where the classes autonomously and selfishly set their degree probabilities to improve their own throughput. We gave proof for the existence of the Nash Equilibria and how to attain them. We provided extensive numerical results that assess the notable improvement brought by the devised approaches and the small discrepancy of the distributed game-based approach in comparison with a centralized class-based IRSA approach.

## APPENDIX A

### PROOFS OF DENSITY EVOLUTION LEMMAS AND THEOREM

**Lemma 4 Monotonicity (Increasing) of F(x; G, Λ) With Respect to x:** Let (Λ, λ) be the node and edge degree distribution pair. The function F(x; G, Λ) defined in (4) is monotone increasing with its argument x.

*Proof:* Consider some $x^* \in [0, 1]$ and $x \in [0, 1]$ with $x^* > x$:

$$ 
\begin{align*}
x^* > x &\Rightarrow \lambda(x^*) > \lambda(x) \\
&\text{(since } \lambda(x) \text{ is a polynomial with only positive coefficients)} \\
&\Rightarrow -G\Lambda'(1)\lambda(x^*) < -G\Lambda'(1)\lambda(x) \\
&\Rightarrow -e^{-G\Lambda'(1)\lambda(x^*)} > -e^{-G\Lambda'(1)\lambda(x)} \\
&\Rightarrow 1 - e^{-G\Lambda'(1)\lambda(x^*)} > 1 - e^{-G\Lambda'(1)\lambda(x)} \\
&\Rightarrow 1 - e^{-G\Lambda'(p^*)} > 1 - e^{-G\Lambda'(p)} \\
&\Rightarrow F(x^*; G, \Lambda) > F(x; G, \Lambda)
\end{align*}
$$

and thus $F(x; G, \Lambda)$ is monotone increasing with $x$ for any $x \in [0, 1]$. □

**Lemma 5 (Decreasing of the Sequence (pᵢ) With Respect to Iterations):** For all the iterations $i = 1, 2, 3, \dots, pᵢ = F(pᵢ-1; G, Λ)$ is a monotone, decreasing, sequence. *Proof:* By induction: if for some $i \ge 1$: $pᵢ \le pᵢ-1$, then:

$$ 
\begin{align*}
p_i \le p_{i-1} &\Rightarrow F(p_i) = p_{i+1} \le F(p_{i-1}) = p_i
\end{align*}
$$

(since F is monotone increasing with $p$)

$$ \Rightarrow p_{i+1} \le p_i \le p_{i-1} $$

Now consider $p₀ = 1$ and $p₁ = F(p₀; G, Λ)$. We have $p₁ = 1 - e^{G\Lambda'(p₀)} < 1$ thus $p₁ < p₀$, the induction hypothesis for $i = 1$. This proves the monotonicity and decreasing of the sequence {$pᵢ$}$_{i \ge 0}$.

Notice that sequence is also lower bounded by 0 and hence it must converge. □

**Theorem 3 (Convergence of the sequence (pᵢ)): The sequence (pᵢ) is decreasing and converges towards a limit p∞, that is the fixed point of the equation:**

$$ p_{\infty} = F(p_{\infty}; G, \Lambda) \text{ with } F(x; G, \Lambda) = 1 - e^{-G\Lambda'(x)} \quad (25) $$

*Proof:* From Lemma 5, (pᵢ) is a decreasing sequence. In addition, it is lower-bounded by 0, and F(x; G, Λ) is continuous in x. Then the Theorem is a direct consequence of fixed-point theorems. □

## APPENDIX B

### PROOF OF LEMMA 1

*Proof:* It is easy to show that **the set is compact**:

1. **The set S<sub>c</sub> is closed:** The set S<sub>c</sub> of strategies is closed as it contains its limit points 0 and 1.

2. **The set S<sub>c</sub> is bounded:** The set is upper bounded by a vector U and lower bounded by a vector L. $\forall s<sub>c</sub> \in S<sub>c</sub> : \exists L : s<sub>c</sub> \ge L, \exists U : s<sub>c</sub> \le U$.

From 1 and 2, we deduce that the set is compact. **The set is convex:**

1. $\forall s_i, s_j \in S_c$:

$$ 
\begin{align*}
0 \le s_i \le 1, \Rightarrow 0 \le \theta s_i \le \theta \\
0 \le s_j \le 1, \Rightarrow 0 \le (1 - \theta) s_j \le (1 - \theta)
\end{align*}
$$

$\Rightarrow 0 \le \theta s_i + (1 - \theta) s_j \le 1$, each component of the new vector will be in $[0, 1]$. 2. $\forall s_i, s_j \in S_c$:

$$ 
\begin{align*}
s_i + (1 - s_i) &= 1 \Rightarrow \theta s_i + \theta(1 - s_i) = \theta \\
s_j + (1 - s_j) &= 1 \Rightarrow (1 - \theta)s_j + (1 - \theta)(1 - s_j) = 1 - \theta
\end{align*}
$$

By combining both:

$$ \theta s_i + \theta(1 - s_i) + (1 - \theta)s_j + (1 - \theta)(1 - s_j) = 1, $$

the sum of all components of the new vector is equal to one. From 1 and 2, we conclude that the set S<sub>c</sub> is convex. □

## APPENDIX C

### PROOF OF LEMMA 3

*Proof:* Differentiating $T_{C₀}(s₀)$ with respect to s₀ yields:

$$ 
\begin{align*}
& \frac{dT_{C_0}}{ds_0} \\
&= -G \left[ p_{\infty}^m - p_{\infty}^{\ell} + \frac{\partial p_{\infty}}{\partial s_0} \left( s_0 m p_{\infty}^{m-1} + (1 - s_0) \ell p_{\infty}^{\ell-1} \right) \right]
\end{align*}
$$
The expression $\frac{\partial p_{\infty}}{\partial s_0}$ appearing here can be obtained from Lemma 2, using Eq. (23), Eq. (24) and for any $s_0 \notin S(s_0, s_1, G)$, it is:

$$ \frac{\partial p_{\infty}}{\partial s_0} = -G\alpha(1-p_{\infty})(mp_{\infty}^{m-1} - \ell p_{\infty}^{\ell-1}) / \left\{ G(1-p_{\infty}) \cdot \alpha \left[ (m(m-1)s_0p_{\infty}^{m-2} + \ell(\ell-1)(1-s_0)p_{\infty}^{\ell-2}) + G(1-p_{\infty}) \cdot (1-\alpha) \times \left[ (m(m-1)s_1p_{\infty}^{m-2} + \ell(\ell-1)(1-s_1)p_{\infty}^{\ell-2}) \right] - 1 \right] \right\} $$

When $G \to \infty$, we will prove that $p_{\infty} \to 1$; for convenience, we do a change of variable of $p_{\infty}$ to $\varepsilon$, defined as $p_{\infty} \triangleq 1 - \varepsilon$. This allows us to study such limits. However, one technicality is that we need to prove bounds and limits independently of the values of $s_0$ and $s_1$. We introduce the following variants of the Bachmann-Landau notation (the family of Big O Notations), to be able to express this, as follows:

* Assuming $G \to \infty$:

* $f(x; s_0, s_1) = \tilde{o}(g(x; s_0, s_1))$ [f is dominated by g asymptotically] $\Rightarrow \forall \eta > 0 \exists N$ such that $\forall x \ge N \forall(s_0, s_1) \in [0, 1]^2 : [f(x; s_0, s_1)] \le \eta|g(x; s_0, s_1)|$

* $(x; s_0, s_1) = \Theta(g(x; s_0, s_1))$ [f is bounded both above and below by g asymptotically] $\Rightarrow \exists k_1 > 0 \exists k_2 > 0 \exists N : \forall x \ge N, \forall(s_0, s_1) \in [0, 1]^2 : k_1 g(x; s_0, s_1) \le f(x; s_0, s_1) \le k_2 g(x; s_0, s_1)$

Notice the only difference with classical Bachmann-Landau notation definitions $o(x)$ and $\Theta(x)$, are the "$\forall(s_0, s_1)$".

Our first preliminary proof is on the limit of $G\varepsilon$. For fixed $s_0 \in [0, 1]$ and $s_1 \in [0, 1]$, we have:

$$ \lim_{G \to \infty} G\varepsilon \stackrel{(a)}{=} \lim_{G \to \infty} G(1-p_{\infty}) \stackrel{(b)}{=} \lim_{G \to \infty} G(1 - (1 - e^{-G\Lambda'(p_{\infty})})) \stackrel{(c)}{=} \lim_{G \to \infty} G e^{-G\Lambda'(p_{\infty})} \stackrel{(d)}{=} 0 $$

where (a) is by definition of $\varepsilon$, (b) is because $p_{\infty}$ is the fixed point of Eq. (7), (c) is immediate, (d) is because $\Lambda'(x)$ is bounded by $\Lambda'(x) \le \max(\ell, m) = \ell$ for any $x \in [0, 1]$ and because $\lim_{G \to \infty} G e^{-G \cdot K} = 0$ for any constant $K > 0$.

The key part in the previous reasoning (d), is the use of the bound: $\Lambda'(x) \le \Lambda'(1) \le \ell$, valid for any $x \in [0, 1]$. This bound does not depend on $s_0$ and $s_1$, hence the same reasoning can be applied, to $\max_{s_0, s_1} p_{\infty}$, and thus this proves the following slightly more general result, independent of $s_0$ and $s_1$:

$$ \lim_{G \to \infty} \left( \max_{(s_0, s_1) \in [0, 1]^2} G\varepsilon \right) = 0 \quad (26) $$

or with our notation: when $G \to \infty$, $G\varepsilon = \tilde{o}(1)$ (27)

Notice that this is a stronger result that implies the following: when $G \to \infty$, $\varepsilon = \tilde{o}(1)$ or in other terms, $p_{\infty} = 1 + \tilde{o}(1)$.

Armed with these definitions, and preliminary results, we can write $\frac{\partial T_{C_0}}{\partial s_0}$ with a Taylor expansion of $(1 - \varepsilon)^\ell$

and $(1 - \varepsilon)^m$:

$$ \frac{\partial T_{C_0}}{\partial s_0} = G \left\{ -(1 - m\varepsilon) + (1 - \ell\varepsilon) + \tilde{o}(\varepsilon) + G\alpha\varepsilon(m - \ell) \cdot \left[ \begin{aligned} & s_0 m(1 - m\varepsilon + \varepsilon) + (1 - s_0)\ell(1 - \ell\varepsilon + \varepsilon) + \tilde{o}(\varepsilon) \\ & \quad \bigg/ \left( G\alpha \left[ (m^2 - m)s_0\varepsilon + (\ell^2 - \ell)(1 - s_0)\varepsilon + \tilde{o}(\varepsilon) \right] + G(1 - \alpha) \right. \\ & \quad \left. \times \left[ (m^2 - m)s_1\varepsilon + (\ell^2 - \ell)(1 - s_1)\varepsilon + \tilde{o}(\varepsilon) \right] - 1 \right] \end{aligned} \right\} $$

Hence:

$$ \frac{\partial T_{C_0}}{\partial s_0} = G\varepsilon(m - \ell + \tilde{o}(1)) \times \left[ 1 + \frac{G\alpha(s_0 m + (1 - s_0)\ell + \tilde{o}(1))}{G\varepsilon(D + \tilde{o}(1)) - 1} \right] + \tilde{o}(1) \quad (28) $$

$$ \text{with } D = \alpha \left[ (m^2 - m)s_0 + (\ell^2 - \ell)(1 - s_0) \right] + (1 - \alpha) \left[ (m^2 - m)s_1 + (\ell^2 - \ell)(1 - s_1) \right] \quad (29) $$

Now considering again the different parts of the expression Eq. (28) when $G \to \infty$:

* $G\varepsilon(D + \tilde{o}(1)) - 1 = -1 + \tilde{o}(1)$ because $G\varepsilon = \tilde{o}(1)$

* Therefore $\frac{G\alpha(s_0 m + (1 - s_0)\ell)}{G\varepsilon D - 1} = -\tilde{\Theta}(G)$

* Hence: $1 + \frac{G\alpha(s_0 m + (1 - s_0)\ell)}{G\varepsilon D - 1} = -\tilde{\Theta}(G)$

* Thus finally: $\frac{\partial T_{C_0}}{\partial s_0} = -G\varepsilon(m - \ell + \tilde{o}(1))\tilde{\Theta}(G)$

We have the sign of every quantity involved in the product in the last expression when $G \to \infty$: it is ultimately positive. Therefore, we conclude that:

$$ \exists G_0 > 0 : \forall G > G_0, \quad \forall s_0 \in [0, 1], \forall s_1 \in [0, 1], \frac{\partial T_{C_0}}{\partial s_0} > 0 \quad (30) $$

And this proves that there exists a $G_0 > 0$, such that the utility function is a monotone (increasing) function with $s_0$ for any $G \ge G_0$. □

## REFERENCES

[1] M. Berioli, G. Cocco, G. Liva, and A. Munari, "Modern random access protocols," *Found. Trends Netw.*, vol. 10, no. 4, pp. 317–446, 2016.

[2] G. Liva, "Graph-based analysis and optimization of contention resolution diversity slotted ALOHA," *IEEE Trans. Commun.*, vol. 59, no. 2, pp. 477–487, Feb. 2011.

[3] E. Paolini, G. Liva, and M. Chiani, "Coded slotted ALOHA: A graph-based method for uncoordinated multiple access," *IEEE Trans. Inf. Theory*, vol. 61, no. 12, pp. 6815–6832, Dec. 2015.

[4] C. R. Srivatsa and C. R. Murthy, "Throughput analysis of PDMA/IRSA under practical channel estimation," in *Proc. IEEE 20th Int. Workshop Signal Process. Adv. Wireless Commun. (SPAWC)*, Jul. 2019, pp. 1–5.

[5] B. Makki, K. Chitti, A. Behravan, and M.-S. Alouini, "A survey of NOMA: Current status and open research challenges," *IEEE Open J. Commun. Soc.*, vol. 1, pp. 179–189, 2020.

[6] E. Casini, R. De Gaudenzi, and O. del Rio Herrero, "Contention resolution diversity slotted ALOHA (CRDSA): An enhanced random access scheme for satellite access packet networks," *IEEE Trans. Wireless Commun.*, vol. 6, no. 4, pp. 1408–1419, Apr. 2007.

[7] K. R. Narayanan and H. D. Pfister, "Iterative collision resolution for slotted ALOHA: An optimal uncoordinated transmission policy," in *Proc. 7th Int. Symp. Turbo Codes Iterative Inf. Process. (ISTC)*, Aug. 2012, pp. 136–139.
[8] C.-H. Yu, L. Huang, C.-S. Chang, and D.-S. Lee, "Poisson receivers: A probabilistic framework for analyzing coded random access," *IEEE/ACM Trans. Netw.*, vol. 29, no. 2, pp. 862-875, Apr. 2021.

[9] A. Munari, "Modern random access: An age of information perspective on irregular repetition slotted Aloha," *IEEE Trans. Commun.*, vol. 69, no. 6, pp. 3572-3585, Jun. 2021.

[10] S. Saha, V. B. Sukumaran, and C. R. Murthy, "On the minimum average age of information in IRSA for grant-free mMTC," *IEEE J. Sel. Areas Commun.*, vol. 39, no. 5, pp. 1441-1455, May 2021.

[11] K. Akkarajitsakul, E. Hossain, D. Niyato, and D. I. Kim, "Game theoretic approaches for multiple access in wireless networks: A survey," *IEEE Commun. Surveys Tuts.*, vol. 13, no. 3, pp. 372-395, 3rd Quart., 2011.

[12] T. Cui, L. Chen, and S. H. Low, "A game-theoretic framework for medium access control," *IEEE J. Sel. Areas Commun.*, vol. 26, no. 7, pp. 1116-1127, Sep. 2008.

[13] A. B. MacKenzie and S. B. Wicker, "Selfish users in aloha: A game-theoretic approach," in *Proc. IEEE 54th Veh. Technol. Conf. (VTC Fall)*, vol. 3, Oct. 2001, pp. 1354-1357.

[14] H. Inaletkin and S. B. Wicker, "The analysis of Nash equilibria of the one-shot random-access game for wireless networks and the behavior of selfish nodes," *IEEE/ACM Trans. Netw.*, vol. 16, no. 5, pp. 1094-1107, Oct. 2008.

[15] E. Altman, N. Bonneau, M. Debbah, and G. Caire, "An evolutionary game perspective to Aloha with power control," in *Proc. 19th Int. Teletraffic Congr.*, Beijing, China, Aug. 2005, pp. 1-10.

[16] J. Choi, "A game-theoretic approach for NOMA-ALOHA," in *Proc. Eur. Conf. Netw. Commun. (EuCNC)*, Jun. 2018, pp. 9-54.

[17] F. Clazzer, "Selfish users in graph-based random access," in *Proc. IEEE 29th Annu. Int. Symp. Pers., Indoor Mobile Radio Commun. (PIMRC)*, Sep. 2018, pp. 1960-1966.

[18] F. Clazzer, E. Paolini, I. Mambelli, and Č. Stefanović, "Irregular repetition slotted Aloha over the Rayleigh block fading channel with capture," in *Proc. IEEE Int. Conf. Commun. (ICC)*, May 2017, pp. 1-6.

[19] I. Hmedoush, C. Adjih, P. Mühlethaler, and L. Salaun, "Multi-power irregular repetition slotted Aloha in heterogeneous IoT networks," in *Proc. 9th IFIP Int. Conf. Perform. Eval. Modeling Wireless Netw. (PEMWN)*, Dec. 2020, pp. 1-6.

[20] C. Dumas, L. Salaun, I. Hmedoush, C. Adjih, and C. S. Chen, "Design of coded slotted Aloha with interference cancellation errors," *IEEE Trans. Veh. Technol.*, vol. 70, no. 12, pp. 12742-12757, Dec. 2021.

[21] T. Richardson and R. Urbanke, *Modern Coding Theory*. Cambridge, U.K.: Cambridge Univ. Press, 2008.

[22] W. Lin, X. Juan, and G. Chen, "Density evolution method and threshold decision for irregular LDPC codes," in *Proc. Int. Conf. Commun., Circuits Syst.*, vol. 1, Jun. 2004, pp. 25-28.

[23] R. Storn and K. Price, "Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces," *J. Global Optim.*, vol. 11, no. 4, pp. 341-359, 1997.

[24] S. Lasaulce, M. Debbah, and E. Altman, "Methodologies for analyzing equilibria in wireless games," *IEEE Signal Process. Mag.*, vol. 26, no. 5, pp. 41-52, Sep. 2009.

[25] S. G. Krantz and H. R. Parks, *The Implicit Function Theorem: History, Theory, and Applications*. Springer, 2012.

[26] J. W. Friedman and C. Mezzetti, "Learning in games by random sampling," *J. Econ. Theory*, vol. 98, no. 1, pp. 55-84, May 2001.

<figure><img src="image_10.png" /></figure>

**IMAN HMEDOUSH** was born in Lattakia, Syria, in 1992. She received the bachelor's degree in telecommunication and electronics engineering from Tishreen University, in 2014, and the master's degree in telecommunication engineering from Supélec, France, in 2018. She is currently pursuing the Ph.D. degree in telecommunication engineering with INRIA. Her research interests include random access technologies for IoT networks, protocol design for MAC layer, resource management, and machine learning.

<figure><img src="image_11.png" /></figure>

**CÉDRIC ADJIH** was born in Lille, France, in 1971. He received the Graduate degree from ECP (CentraleSupelec), in 1994, and the Ph.D. degree from the University of Versailles Saint-Quentin-en-Yvelines, France, in 2001. He is currently a Research Scientist with the Research Center of the Saclay-Île-de-France, INRIA. His research interests include random access technology in the IoT, and in general, communications, the IoT, and machine learning for networking and for embedded systems.

<figure><img src="image_12.png" /></figure>

**KINDA KHAWAM** received the Engineering degree from the Ecole Supérieure d'Ingénieurs de Beyrouth, Beirut, Lebanon, in 2002, and the master's degree in computer networks and the Ph.D. degree from Télécom ParisTech (ENST), Paris, France, in 2003 and 2006, respectively. She was a Postdoctoral Fellow Researcher with Orange Laboratories, Issy-Les-Moulineaux, France, in 2007. Actually, she is currently an Associate Professor and a Researcher with the University of Versailles, France. Her research interests include radio resource management, modeling, and performance evaluation of mobile networks.

<figure><img src="image_13.png" /></figure>

**PAUL MÜHLETHALER** (Member, IEEE) was born in February, in 1961. He received the degree from the École Polytechnique, Palaiseau, France, in 1984, and the Ph.D. and Habilitation degrees from Paris Dauphine University, Paris, France, in 1989 and 1998, respectively. He has been a Researcher with the Institut National de Recherche en Informatique et en Automatique (INRIA), Paris, since 1988, and is currently the Research Director with INRIA, where he is leading the EVA Team. His research interests include protocols for networks with a specialty in wireless networks, vehicular networks, and the IoT. He had also a few, often referenced, results on scheduling issues. In wireless networks, he has actively worked at ETSI and IETF for the HiPERLAN and OLSR standards. He is also following the European standardization for vehicular networks. He is also particularly interested in understanding the achievable performance of multihop *ad hoc* networks and in tracking all the possible optimization ways of such networks. He was among the First contributors for the OLSR protocol, in 1997. He was a recipient of the price "Science et Defense" for his work on mobile *ad hoc* networks, in 2004.