# Games among selfish and team stations in polling systems

Khushboo Agarwal, Eitan Altman

► To cite this version:

Khushboo Agarwal, Eitan Altman. Games among selfish and team stations in polling systems. VAL-UETOOLS 2024 - 17th EAI International Conference on Performance Evaluation Methodologies and Tools, Dec 2024, Milan, Italy. hal-04829591

HAL Id: hal-04829591

https://inria.hal.science/hal-04829591v1

Submitted on 23 Dec 2024

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
# Games among selfish and team stations in polling systems*

Khushboo Agarwal and Eitan Altman

INRIA, 2004 Route des Lucioles, 06902 – Sophia Antipolis, France
{khushboo.agarwal, eitan.altman}@inria.fr

**Abstract.** The paper focuses on a particular polling system known as the cyclic Bernoulli polling (CBP) system, where a server moves cyclically between the stations and serves the queue at a station with a certain probability when polled. Each station follows either a gated or partially exhaustive service discipline.

In the steady state of such a system, we study a new game-theoretic aspect, where, the stations strategically choose the probability of accepting or rejecting the service from the server when polled. We examine three variants of non-cooperative games among stations: (i) each station self-ishly minimizes its expected waiting time, (ii) a team game where each station minimizes the expected workload of the system, and (iii) stations act with partial cooperation, incurring an additional linear cost.

We begin by presenting a new result for the CBP system regarding the continuity of expected waiting times in relation to the probabilities selected by the stations. For each game, we then investigate the existence and uniqueness of the Nash equilibrium (NE). In some cases, the NE is explicitly derived, while in others, characterizing the NE remains challenging due to the complex dependence of waiting times on the non-trivial buffer occupancy equations. Nonetheless, we analyze the NE and its properties through numerical experiments. Notably, in many instances, stations opt to accept service with a probability less than 1 — a trend observed even among selfish stations.

**Keywords:** Strategic stations · Cyclic Bernoulli polling · Game theory.

## 1 Introduction

Queues are everywhere; therefore, it is no surprise that the study of queuing systems is rich today. The questions about whether or not to queue, where to queue, when to queue, etc. are all explored to great lengths [2]. The polling system is a particular queuing system that caters to several applications like computer networks, telecommunications, production systems, traffic and transportation systems [6], and is of interest to us. In the simplest form and words,

<footnote>* This work was supported in part by the French National Agency for Research (ANR) via the project n°ANR-22-PEFT-0010 of the France 2030 program PEPR réseaux du futur, and partially by DST-INRIA project LION.</footnote>
there is a single server in a polling system which moves in a given (random or fixed) order around the stations to check if there are customers queued up at the stations (polls) and then serves some or all customers at the polled station. The literature on polling systems is vast, and critical metrics like cycle duration, mean waiting times, and mean number of jobs waiting are analyzed for different kinds of routing mechanisms of the server(s), service discipline used by the queues, and in both discrete/continuous framework; one should refer to the excellent work culminated in [21, 22], along with [15, 16, 23, 24], for example.

The authors in [4] deviated from the classical polling systems by studying 'cyclic Bernoulli polling (CBP) systems' where the server moves cyclically among $N < \infty$ stations, and it may or may not provide service to the polled station with some probability. Here, the switching time (between two stations) is the sum of walking time (required to move) and the switch-in time (incurred while setting up the server if service is provided).

In this paper, we further deviate from the work in [4] as follows: when the server polls a station, the station accepts or rejects the service from the server with some probability. The system evolves in continuous time and reaches a steady state under natural assumptions. In such a state of the system, we study the non-cooperative game among stations that attempt to minimize some cost function, where pure strategies refer to the probability of accepting or rejecting the service. Thus, the strategy space for each station is a closed, convex set. Each station makes its decision by anticipating the decisions taken by the other stations.

To our knowledge, the literature on games in polling systems is limited to the work in [1] and [9]. In [1], a routing game is studied for customers in a two-queue polling system. While in [9], there is a game between the server and the customers in a tandem queue: the server decides the operating scheme and the price charged to the customers; the customers decide whether to join the queue or balk. Our work is novel for analyzing strategic stations in polling systems. This new line of research parallels the sub-field of queuing theory, named strategic queuing, where customers, servers, etc., make decisions. For a compact reference on strategic queuing, see the books [13, 14] and recent studies like [5, 8, 12, 18].

We specifically consider three kinds of cost functions for each station, which implies three different games:

- expected waiting time, leading to the *game among selfish stations*;

- expected workload in the system, which represents the *team approach to cooperative stations*;

- expected workload in the system plus the linear cost, leads to the *game among partially-cooperative stations*.

In the first game, all the stations either use gated or partially exhaustive service discipline, each of which is explained below:

- gated service: all the customers present at the arrival instant of the server are served by the server, and no other customer is served;
- partially exhaustive service: all the customers present at the polling instant and arriving during the service of the customers at the queue are served; however, the customers arriving during the switch-in time are not served.

A mix of service disciplines is allowed in the other two games.

In Section 2, we summarize the CBP systems which form the necessary background for our study. The games are introduced formally in Section 3 and analyzed in Section 4.

The key metric for the game among selfish stations is the expected waiting time, which is evaluated via a set of $N^3$ linear equations known as buffer occupancy equations. It is first shown that these equations admit a unique solution for the CBP system, and then we show that the expected waiting time is continuous in the probabilities of accepting the service concerning each station. Finally, the existence of a mixed strategy Nash equilibrium (NE) is proved. Here, it is important to note that further theoretical analysis is challenged due to the non-trivial form of the buffer-occupancy equations.

Further, the NE is shown to exist for the game among cooperative or partially cooperative stations. In many cases, the NE is pure and unique, and is characterized explicitly when the switch-in times are zero. In Section 5, we numerically study if a station accepts or rejects service with probability (w.p.) lesser or equal to one, how the cost varies at equilibrium and the price of anarchy. Interestingly, we show that in a competitive environment, even a selfish station does not accept the service w.p. 1. Also, contrary to the anticipation, costs at NE do not always increase with switch-in time, and the system performance at NE improves as the expected switch-in time increases. We conclude the work and provide several possible future research directions in Section 6.

## 2 Background

Following [4], the paper considers the cyclic Bernoulli polling (CBP) system with $N < \infty$ stations. Each station has a queue of customers who need service. However, unlike the classical polling models, we examine the decision-making of the stations which strategically decide to accept/reject service from the server, with a certain probability, to minimize specific cost functions. Under the steady state of CBP system, these interactions are modelled as a non-cooperative game among the stations. To this end, it is first essential to understand the CBP system, and we focus precisely on this in the immediate next.

Consider a polling system with $N$ stations, each consisting of a queue. For queue $i \in \{1, \dots, N\}$, the inter-arrival time for customers is distributed as an exponential random variable with rate $\lambda_i$. The customers in each station/queue are served by a single server, which moves cyclically. The time taken for a customer to be served in queue $i$ is distributed as $B_i$ such that the expected service time is $b_i$ and the second moment of service time is $b_i^{(2)}$. Thus, each queue is modelled as a M/G/1 queuing system. Note that the words station and queue are sometimes used interchangeably, and the usage will be evident per the context.
The traffic offered to queue $i$ is given by $\rho_i := \lambda_i b_i$, and we assume the following to ensure the stability of the system:

$$K_1: \text{The traffic offered to the system } \rho := \sum_{i=1}^{N} \rho_i < 1.$$

The time instant when the server arrives at a queue is called the polling instant. At each arrival instant, the server chooses to provide or not provide the service to the station. This decision with respect to (w.r.t.) station $i$ is assumed to be Bernoulli distributed with parameter $p_i$; thus, $p_i$ are the control variables for the server. To ensure that the system remains stable, in addition to $K_1$, it is further assumed that:

$$K_2: \text{The probability } p_i > 0 \text{ for each } i.$$

If the server does not provide the service to the customers waiting at station/queue $i$, it simply moves on to the next station/queue, as depicted in Figure 1. The time taken to walk is then denoted by $D_i$, which has $d_i$ and $d_i^{(2)}$ as the expectation and second moment, respectively. The total walking time in a complete cycle is given by $D := \sum_{i=1}^{N} D_i$, with the first and second moment represented by $d$ and $d^{(2)}$ respectively.

<figure><img src="image_2.png" /><figcaption>Fig. 1: Timeline of events in CBP system: when the server does not provide service to queue $i + 1$ (in game-theoretic framework, it represents the scenario where the station rejects the service)</figcaption></figure>

However, if the station $i$ receives service from the server, then it takes some time to start the service after arrival; new arrivals are possible during this time, which may or may not be served depending upon the service discipline used by the station; this scenario is depicted in Figure 2. The time difference between the start of the service at queue $i$ and the polling instant of queue $i$ is called the $i$-th switch-in time (denoted as $R_i$). The expectation and the second moment for $R_i$ are represented by $r_i$ and $r_i^{(2)}$, respectively. After service completion, the server again takes a random amount of time ($D_i$) to walk between the departure instant (when service ends) of queue $i$ and the polling instant for queue ($i + 1$). As in [4], we assume that:
K₃: The inter-arrival, service and walking times are mutually independent.

<figure><img src="image_3.png" /><figcaption>Fig. 2: Timeline of events in CBP system: when the server provides service to station $i+1 \in G$ (in game-theoretic framework, it represents the scenario where the station accepts the service)</figcaption></figure>

Further, we assume each queue can be served according to the gated ($G$) or the partially exhaustive ($P$) discipline. With slight abuse of notation, we represent the set of queues served according to the gated and exhaustive discipline by $G$ and $P$, respectively.

Let $\tilde{X}_n^j$ be the number of customers in queue $j$ at $n$-th time that a queue is polled. Then, under $K_1-K_3$, using [3, Proposition 3.2], it can be shown that the Markov chain $\{\tilde{X}_n^1, \dots, \tilde{X}_n^N\}_n$ is ergodic. Let $X_i^j$ be the number of customers at queue $j$ when queue $i$ is polled in the steady state. The evolution of these random variables $(X_i^j)$ is described in [4, 1) for gated and in [4, 13)] for partially exhaustive disciplines. This completes the description of the CBP system.

With this background, we finally proceed towards the game formulation. Note that the rest of the paper assumes the system to be in a steady state under the assumptions $K_1-K_3$.

## 3 Non-cooperative games in CBP systems

Consider the CBP system from the previous section. However, now, focus on the scenarios where the stations are decision-makers instead of the server being a decision-maker. Thus, the server does not decide the probability of providing service to a station; instead, the stations decide the probability with which they accept the service from the server when polled by the server.

The probability that station $i$ accepts the service is again denoted by $p_i \in (0, 1]$ for each $i$. Recall that $p_i \neq 0$, as it leads to an explosive, and thus an
unstable, system. Each station knows the system parameters (like mean arrival, service, switch-in and walking times) and the service discipline used by each station. However, the position of the server and the lengths of other queues may not be observable to the stations. In such a situation, each station chooses the probability (of accepting/rejecting the service) given a specific cost, which is affected not only by its choice but also by the choices made by the other stations.

Thus, the resultant interaction leads to a non-cooperative game, which we formally define by the tuple $\langle \mathcal{N}, (\mathcal{A}_i)_i, (c_i)_i \rangle$, where:

- Each station acts as a player, and thus, $\mathcal{N} := \{1, \dots, N\}$ is the set of players;

- The probability $p_i > 0$ is a strategy for the station $i$. For mathematical tractability, we assume that $p_i \ge \underline{p}_i$, for some $\underline{p}_i > 0$, for each $i$. Therefore, $\mathcal{A}_i := [\underline{p}_i, 1]$ is set of strategies;

- The cost function of the station $i$ (in steady state) is denoted by $c_i : \prod_{i=1}^N \mathcal{A}_i \to \mathbb{R}$. That is, if the station $i$ chooses strategy $p_i$ and all other stations choose $p_{-i} := (p_1, \dots, p_{i-1}, p_{i+1}, \dots, p_N)$, then it incurs a cost of $c_i(p_i, p_{-i})$.

We emphasize that $p_i$ is a pure strategy for the station $i$. The mixed strategy for player $i$ is a probability distribution over pure strategies in $\mathcal{A}_i$, and the formal description is as below:

**Definition 1.** [17] For a station $i$ with $\mathcal{A}_i$ as the set of pure strategies, $\sigma_i : \mathcal{A}_i \to [0, 1]$ is a mixed strategy if it assigns to each pure strategy $p_i \in \mathcal{A}_i$, a probability $\sigma_i(p_i)$ such that $\sum_{p_i \in \mathcal{A}_i} \sigma_i(p_i) = 1$.

In the coming, we question the existence of Nash equilibrium (defined in the immediate next) for various games among stations, dictated by the cost functions that stations attempt to optimize.

**Definition 2.** [11] For a non-cooperative game $\langle \mathcal{N}, (\mathcal{A}_i)_i, (c_i)_i \rangle$, a (mixed) strategy profile $(\sigma_1^*, \dots, \sigma_N^*)$ is called a Nash equilibrium if:

$$c_i(\sigma_i^*, \sigma_{-i}^*) \le c_i(p_i, \sigma_{-i}^*), \text{ for all } p_i \in \mathcal{A}_i, \text{ for all } i \in \mathcal{N}.$$

If a mixed Nash equilibrium is such that $\sigma_i^*(p_i^*) = 1$ for some $p_i^* \in \mathcal{A}_i$ for all $i \in \mathcal{N}$, then, the strategy profile $\mathbf{p}^* := (p_i^*, p_{-i}^*)$ is known as a pure strategy Nash equilibrium.

## Game among selfish stations

Let $W_i$ be the waiting time of a customer in queue $i$. The first game that we consider is the one where the station $i$ decides its strategy to minimize its customers' expected waiting time ($E[W_i]$). Here, we study two scenarios: (i) all the stations use $\mathcal{G}$-discipline, and (ii) all the stations use $\mathcal{P}$-discipline. The waiting time w.r.t. the station/queue $i$ not only depends on $p_i$, but also on the probabilities with which other stations take the service ($p_{-i}$). To be precise, the cost
function for station i is given by (see [4, (8), (12)] for gated, and [4, (12), (28)] for partially-exhaustive station):

$$c_i(\mathbf{p}) := E[W_i(\mathbf{p})] = \begin{cases} \frac{1+\rho_i}{2\lambda_i} \frac{f_i(i,i;\mathbf{p})}{f_i(i;\mathbf{p})} + r_i, & \text{if } i \in \mathcal{G}, \\ \frac{\lambda_i b_i^{(2)}}{2(1-\rho_i)} + \frac{f_i(i,i;\mathbf{p})}{2\lambda_i f_i(i;\mathbf{p})} + r_i, & \text{if } i \in \mathcal{P}, \end{cases} \quad (1)$$

where $f_k(i; \mathbf{p}) := E[X_k^i]$ is the expected number of customers in queue i, when station k is polled and

$$f_k(l, i; \mathbf{p}) := \begin{cases} E[X_k^l X_k^i], & \text{if } k \neq l \neq i, \\ E[X_i^i (X_i^i - 1)], & \text{if } k = l = i. \end{cases} \quad (2)$$

The exact form of $f_i(i; \mathbf{p})$ is provided in [4], however, this is not the case for $f_i(i, i; \mathbf{p})$. The latter is obtained via the solution of some linear equations. We discuss these equations more and write the explicit forms of the cost functions in the next section, where we analyze the game.

Notice from (1) that via this game, we attempt to study selfish strategic stations with selfish objectives of minimizing their expected waiting times. In such a scenario, one would anticipate that all the stations would choose to accept the service w.p. 1 at equilibrium, as otherwise, the one with less probability may observe a large waiting time. However, surprisingly, the contrary occurs as we illustrate later — all the stations can choose to accept the service w.p. < 1 at the equilibrium.

## Team approach to cooperative stations

We consider the same framework as the above-decentralized setting; however, now, the stations share the common objective of minimizing the expected workload in the system. Thus, the stations collaboratively attempt to minimize the following cost function:

$$c_i(\mathbf{p}) := \sum_{i=1}^{N} \rho_i E[W_i(\mathbf{p})] \\ = \rho \frac{\sum_{i=1}^{N} \lambda_i b_i^{(2)}}{2(1-\rho)} + \frac{\rho^2 - \sum_{i=1}^{N} \rho_i^2}{2(1-\rho)} \sum_{i=1}^{N} (d_i + p_i r_i) \\ + \rho \left( \frac{d^{(2)} + 2d \sum_{i=1}^{N} p_i r_i + \sum_{i=1}^{N} p_i r_i^{(2)} + \sum_{i=1, i \neq j}^{N} p_i p_j r_i r_j}{2 \sum_{i=1}^{N} (d_i + p_i r_i)} \right) (3) \\ + \sum_{i \in \mathcal{G}} \rho_i \left[ p_i r_i + \frac{\sum_{j=1}^{N} (d_j + p_j r_j)}{(1-\rho)} \left( \frac{1}{p_i} - (1-\rho_i) \right) \right] \\ + \sum_{i \in \mathcal{P}} \rho_i \left[ p_i r_i + \frac{\sum_{j=1}^{N} (d_j + p_j r_j)(1-\rho_i)}{(1-\rho)} \left( \frac{1}{p_i} - 1 \right) \right].$$
where the last equality follows by [4, (36)]. Observe from the equation above that here we allow some stations to use the G-discipline, while others can use the P-discipline. Using this game, we aim to understand the effect of strategic decision-making of stations on the overall system performance.

## Game among partially-cooperative stations

In the last variant, we model stations which act as a team player in the sense of (3), but also incur an additional cost for accessing service with higher probability. In particular, we consider that the station i incurs a linear (perceived) cost $Q_i p_i$, for some $Q_i \ge 0$, if it accepts the service w.p. $p_i$; here, $Q_i > 0$ at least for one station. Thus, the cost function for station i in such a case is given as below:

$$c_i(\mathbf{p}) := \left( \sum_{i=1}^{N} \rho_i E[W_i(\mathbf{p})] \right) + Q_i p_i. \quad (4)$$

Observe from above that the stations in this case are not fully cooperative (like team players, discussed previously) but act in a slightly selfish and partially cooperative manner due to the additional cost.

*Remark 1.* As the cost functions in (3), (4) are the same for all the players, the two respective games fall into a sub-category of non-cooperative games, called ‘common payoff/cost games’ or ‘coordination games’. Unlike the name suggests, a NE need not lead to the minimum possible cost; for instance, see the simple example in [17, sub-section 4.5].

# 4 Analysis

As with any game theory-based analysis, the first question to address is the existence of an equilibrium. In this section, we specifically examine this issue in relation to the previously introduced games. Notably, the strategy space in our case is not finite but forms a compact convex set. Therefore, we discuss the existence of NE by drawing on the results from [11].

## 4.1 Analysis for the game among selfish stations

Recall from (1) that the cost function depends on the first $(f_i(i; \mathbf{p}))$ and second $(f_i(i, i; \mathbf{p}))$ moments of the number of customers waiting at each station when it is polled. Thus, we begin the analysis by explicitly writing the cost function only in terms of the system parameters and the strategies chosen by the stations. At station i, the server incurs $d_i$ amount of time to walk, and then it further incurs $r_i$ time (on average) to set up if the station accepts the service. Therefore,
$\bar{d}_i := d_i + r_i p_i$ is the switching time of i-th station and $\bar{d} := \sum_{i=1}^N \bar{d}_i$ is the total switching time. From [4], the first moment $f_i(i; \mathbf{p})$ is explicitly given by:

$$f_i(i; \mathbf{p}) = \begin{cases} \frac{\lambda_i \bar{d}}{(1-\rho)p_i}, & \text{if } i \in \mathcal{G}, \\ \frac{\lambda_i \bar{d}(1-\rho_i)}{(1-\rho)p_i}, & \text{if } i \in \mathcal{P}. \end{cases} \qquad (5)$$

The derivation of second moments via $f_i(i, i)$ is not straightforward in any polling model. One uses the state-transition equations for the number of customers in the system at the polling instants to derive these moments (see [4, 7, 21]). The resultant leads to $N^3$ linear equations for $f_k(l, i; \mathbf{p})$ (see (2)); newer methods require only $N^2$ linear equations (see [10,21]). For the CBP system, [4] provides its own set of so-called buffer occupancy equations, with some errors, which we correct here and re-write below.

Buffer occupancy equations when all stations use G-discipline

* when $k \neq i, k \neq l$:

$$f_{k+1}(i, l) = p_k \left\{ \begin{aligned} & \lambda_i \lambda_l [d_k^{(2)} + 2d_k r_k + r_k^{(2)}] + (d_k + r_k)[\lambda_l f_k(i) + \lambda_i f_k(l)] \\ & + f_k(k) \lambda_i \lambda_l [2(d_k + r_k)b_k + b_k^{(2)}] + f_k(i, l) + b_k \lambda_l f_k(k, i) + b_k \lambda_i f_k(k, l) \\ & + b_k^2 \lambda_i \lambda_l f_k(k, k) \end{aligned} \right\} + (1-p_k) \left\{ \begin{aligned} & \lambda_i \lambda_l d_k^{(2)} + [\lambda_i f_k(l) + \lambda_l f_k(i)] d_k + f_k(i, l) \end{aligned} \right\}. \qquad (6)$$

* when $k \neq l$:

$$f_{k+1}(k, l) = p_k \left\{ \begin{aligned} & \lambda_k \lambda_l [d_k^{(2)} + 2d_k r_k + r_k^{(2)}] + (d_k + r_k) \lambda_k f_k(l) \\ & + f_k(k) \lambda_k \lambda_l [2(d_k + r_k)b_k + b_k^{(2)}] + b_k \lambda_k f_k(k, l) + b_k^2 \lambda_k \lambda_l f_k(k, k) \end{aligned} \right\} + (1-p_k) \left\{ \begin{aligned} & \lambda_k \lambda_l d_k^{(2)} + [\lambda_k f_k(l) + \lambda_l f_k(k)] d_k + f_k(k, l) \end{aligned} \right\}. \qquad (7)$$

* for any $k$:

$$f_{k+1}(k, k) = p_k \left\{ \begin{aligned} & \lambda_k^2 [d_k^{(2)} + 2d_k r_k + r_k^{(2)}] + f_k(k) \lambda_k^2 [2(d_k + r_k)b_k + b_k^{(2)}] \\ & + b_k^2 \lambda_k^2 f_k(k, k) \end{aligned} \right\} + (1-p_k) \left\{ \begin{aligned} & \lambda_k^2 d_k^{(2)} + 2 \lambda_k d_k f_k(k) + f_k(k, k) \end{aligned} \right\}. \qquad (8)$$

In the above, $f_{N+1}$ is interpreted as $f_1$ due to the cyclic nature of the equations (governed by the cyclic movement of the server).

Buffer occupancy equations when all stations use P-discipline
• when $k \neq i, k \neq l$:

$$f_{k+1}(i, l) = p_k \left\{ \lambda_i \lambda_l [d_k^{(2)} + 2d_k r_k + r_k^{(2)}] + (d_k + r_k)[\lambda_l f_k(i) + \lambda_i f_k(l)] + f_k(i, l) \right. \\ \left. + f_k(k) \lambda_i \lambda_l \left[ \frac{2(d_k + r_k)b_k}{1 - \rho_k} + \frac{b_k^{(2)}}{(1 - \rho_k)^3} \right] + \frac{b_k}{1 - \rho_k} [\lambda_l f_k(k, i) + \lambda_i f_k(k, l)] \right. \\ \left. + \frac{b_k^2 \lambda_i \lambda_l f_k(k, k)}{(1 - \rho_k)^2} \right\} + (1 - p_k) \left\{ \lambda_i \lambda_l d_k^{(2)} + [\lambda_i f_k(l) + \lambda_l f_k(i)] d_k + f_k(i, l) \right\}. \quad (9)$$

• when $k \neq l$:

$$f_{k+1}(k, l) = p_k \left\{ \lambda_k \lambda_l [d_k^{(2)} + 2d_k r_k + r_k^{(2)}] + (d_k + r_k) \lambda_k \left[ f_k(l) + \frac{f_k(k) \lambda_l b_k}{1 - \rho_k} \right] \right\} \\ + (1 - p_k) \left\{ \lambda_k \lambda_l d_k^{(2)} + [\lambda_k f_k(l) + \lambda_l f_k(k)] d_k + f_k(k, l) \right\}. \quad (10)$$

• for any $k$:

$$f_{k+1}(k, k) = p_k \lambda_k^2 \left\{ d_k^{(2)} + 2d_k r_k + r_k^{(2)} \right\} \\ + (1 - p_k) \left\{ \lambda_k^2 d_k^{(2)} + 2\lambda_k d_k f_k(k) + f_k(k, k) \right\}. \quad (11)$$

Finally, the cost function (1) is simplified using (5) and the solutions of the equations (6)-(11). Now, at this point, it is important to note that the game formulation is meaningful if the cost function is well-defined, which holds only if there is a unique solution to the equations in (15). We prove the latter in the immediate next.

**Theorem 1.** *The buffer occupancy equations for the system with all stations using G or P-discipline admit a unique solution.*

*Proof.* Fix a service discipline (gated or partially exhaustive). For each station/queue $k \in \{1, \dots, N\}$, define the vector

$$f_k := (f_k(1, 1), \dots, f_k(1, N), \dots, f_k(N, 1), \dots, f_k(N, N))^T.$$

The main idea is to define a mapping $T: \mathbb{R}^{N^2} \to \mathbb{R}^{N^2}$ such that $T(f_1) = f_1$, and show that this mapping is a contraction. Then, the Banach fixed point Theorem implies the claim for $f_1$. Similar steps can be followed for $f_k, k > 1$. This approach is as in [15] but is adopted here for the Bernoulli setting. We prove the steps explicitly in Appendix 7. □

The above result confirms that the game is indeed well-defined. Notice here that the cost function in this game is complex, and to the best of our knowledge, there is no characterization of the expected waiting times (cost function) which can be exploited to comment on the existence of NE. Therefore, we prove another important result for CBP system:
**Theorem 2.** The expected waiting time $E[W_i(\mathbf{p})]$ is continuous in $\mathbf{p}$, for each station $i$.

*Proof.* From (1) and (5), it is clear that $E[W_i(\mathbf{p})]$ is continuous in $\mathbf{p}$ if $f_i(i, i; \mathbf{p})$ is continuous in $\mathbf{p}$. Thus, the idea is to construct an appropriate optimization problem, parameterized by $\mathbf{p}$, whose optimizer is $\mathbf{f} := (f_1, \dots, f_N)$. Then, we apply the Maximum Theorem [20, Theorem 9.14] to complete the proof. The exact details are provided in the Appendix 7. □

As a result of Theorem 2, the existence of the NE is guaranteed using [11, Theorem 1.3].

**Theorem 3.** Consider the game among selfish stations. If all the stations use $\mathcal{G}$-discipline, then a mixed strategy NE exists. The same holds for the game when each station uses $\mathcal{P}$-discipline. □

As noted in the introduction, theoretical analysis of this game becomes challenging beyond this stage. To understand this, note that the derivation of the best response of player $i$ against the strategies chosen by others $p_{-i}$ requires the following:

$$ \frac{\partial c_i(\mathbf{p})}{\partial p_i} = \frac{1 + \rho_i f_i(i; \mathbf{p}) \frac{\partial f_i(i, i; \mathbf{p})}{\partial p_i} - f_i(i, i; \mathbf{p}) \frac{\partial f_i(i; \mathbf{p})}{\partial p_i}}{(f_i(i; \mathbf{p}))^2}, \quad \text{if } i \in \mathcal{G}. $$

Similar expression can be derived if $i \in \mathcal{P}$. Now, due to the inherent complex structure of the buffer occupancy equations (and thus, of second moments $f_i(i, i; \mathbf{p})$) (see (1) and (6)-(11)), it is not easy to analyze the above equation further. In future, one can leverage upon the insights derived from the numerical analysis presented in Section 5 and further analyze the game.

## 4.2 Analysis of game among (partially) cooperative stations

In this sub-section, we provide the combined analysis of the two games among cooperative and partially cooperative stations. To begin with, let us consider the simple case where the server only incurs the walking time but no switch-in time for any station, i.e., $r_i = 0$ for each $i$. This condition implies that the server can start the service immediately after arrival if the station accepts the service.

Define the following required to characterize the NE for the underlying game:

$$ \tilde{p}_i = \sqrt{\frac{d\rho_i}{(1-\rho)Q_i}} 1_{i \in \mathcal{G}} + \sqrt{\frac{d\rho_i(1-\rho_i)}{(1-\rho)Q_i}} 1_{i \in \mathcal{P}}. \quad (12) $$

**Theorem 4.** Let $r_i = 0$ for each station $i$. Then, the following statements hold:

(i) For the game among fully cooperative stations, a unique pure strategy NE exists such that $p_i^* = 1$ for each $i$.

(ii) For the game among partially cooperative stations, a unique pure strategy NE exists such that $p_i^* = \min\{1, \max\{\tilde{p}_i, \tilde{p}_i\}\}$ for each $i$.
*Proof.* See Appendix 7. □

Thus, the above result not only implies the existence of ‘pure’ strategy NE, but it also asserts that the NE is unique.

Further, if the stations act as team players (when $Q_i = 0$), all the stations choose to accept the service w.p. 1. Observe that the game, in this case, is exactly the same as the optimization problem considered in [4], where the server chooses the probabilities of providing service to the stations to minimize the system’s expected workload. Thus, the solution to the optimization problem,

$$ \min_{\mathbf{p}=(p_1, \dots, p_N)} \sum_{i=1}^{N} \rho_i E[W_i(\mathbf{p})] \text{ subject to } p_i \in [0, 1], $$

is also $\mathbf{p} = (1, \dots, 1)$; this result is proved in [4, Proposition 1] only with a single station.

However, when stations are partially cooperative, a threshold-based equilibrium strategy exists, dependent on $Q_i$ and the type of service discipline the station uses. At equilibrium, the station $i$ chooses service w.p. 1, if $Q_i \le \Delta_i$ and chooses service w.p. $\max\{\tilde{p}_i, \underline{p}_i\} < 1$ otherwise, where the threshold

$$ \Delta_i := \frac{d\rho_i}{1-\rho} 1_{i \in G} + \frac{d\rho_i(1-\rho_i)}{1-\rho} 1_{i \in \mathcal{P}}. $$

Notice that $\tilde{p}_i$ decreases in the additional cost $Q_i$, see (12); thus, if the stations perceive taking service to be more expensive, then (naturally) the equilibrium strategy is to accept the service with lower probability. However, it is important to note that the stations with $G$-discipline have higher tolerance for an additional cost, as they take service w.p. 1 for larger values of $Q_i$ (observe that $\Delta_{i \in G} > \Delta_{i \in \mathcal{P}}$). Also, as one may anticipate, the overall system performance degrades when the stations are partially cooperative.

Next, we analyze the two games when the server invests some time in set-up before actually starting the service after arrival at a station.

**Theorem 5.** When $r_i > 0$ for each station $i$, then the following statements hold for the game among team stations:

(i) There exists a mixed strategy NE.

(ii) There exists $\underline{\rho}_i \in (0, 1)$ for each $i$ such that for all $\rho_i \ge \underline{\rho}_i$, there exists a unique pure strategy NE.

The above is true even for the game among partially cooperative stations.

*Proof.* See Appendix 7. □

Therefore, a NE exists for the game among (partially) cooperative stations. A stronger conclusion can be drawn when the traffic load at each station is sufficiently high, as a unique pure strategy NE is guaranteed in such cases. The exact NE can be obtained by solving for the smallest zero (in $A_i$) of the function (of degree four) given in (20) in the Appendix 7, for each $i$.
# 5 Numerical analysis

For all the games discussed in this paper, it has been shown that a NE exists; it is further shown to be unique in some cases of the team game and the game among partially cooperative stations. Beyond this point, one may ponder over the following questions:

- Is NE strategy for a player lesser than or equal to 1 in different settings? That is, does a station accepts service from the server w.p. less than or equal to 1?

- How does the cost vary at equilibrium?

- How does the (in)efficiency of the system compare w.r.t. that at the NE?

We attempt to answer all these questions in this section using numerical experiments, and obtain some interesting insights. For the last question, we use the well-known metric named Price of Anarchy (PoA)<fnref n="1" />:

$$PoA = \frac{\max_{\mathbf{p}^*} \sum_{i=1}^{N} c_i(\mathbf{p}^*)}{\min_{\mathbf{p} \in A_1 \times \dots \times A_N} \sum_{i=1}^{N} c_i(\mathbf{p})}$$

where $p^*$ is an equilibrium strategy profile. For the sake of experiments, we consider only two stations. For each station, $p_i = 0.01$, and thus, $A_i = [0.01, 1]$ for each $i \in \{1, 2\}$. The strategy space is partitioned with the step size of 0.001. The NE is evaluated by comparing the best responses, and in all experiments, a unique pure strategy NE is obtained.

## 5.1 Numerical analysis of the game among selfish players

Recall here that in this game, each player (station) selfishly chooses the probability of accepting service from the server to minimize the expected waiting time of customers in its queue. As commented before, the analysis of this game is not straightforward, and the equations for the second moments (see (6)-(11)) seem to be the bottleneck. Nonetheless, some observations can be made with the aid of numerical experiments. We fix the following parameters (written here with accuracy upto 3 decimal places):

$$ \begin{array}{l} \text{Setting 1: } \lambda_1 = 0.393, \lambda_2 = 0.420, d_1 = 0.137, d_2 = 0.292, b_1 = 0.009, \\ b_2 = 2.210, b_1^{(2)} = 4.999, b_2^{(2)} = 9.000, d_1^{(2)} = 0.609, d_2^{(2)} = 0.892 \end{array} \qquad (13) $$

and consider that $r_1 = r_2 = r$ with $r_i^{(2)} = \theta_i + r^2$ for $\theta_i \stackrel{d}{=} \text{Unif}(0, 1)$. In Figure 3, for the two games with both stations using $G$-discipline (black curves) or $P$-discipline (red curves), we illustrate the behaviour of NE, cost of each player at NE and the PoA for the game. From the left sub-figure, one can see that the two stations using $G$-discipline greedily choose $p_i^* = 1$ for all values of $r$. However, under $P$-discipline, the NE $\mathbf{p}^* \neq (1, 1)$ always (see red curves), but eventually, $\mathbf{p}^* = (1, 1)$ as the mean switch-in time ($r$) increases.

<footnote n="1">¹ The PoA of the two games among selfish and cooperative players can not be compared, as the NE(s) of the two games can not be immediately compared.</footnote>
<figure><img src="image_4.png" /><figcaption>Fig. 3: Understanding NE for the game among selfish stations</figcaption></figure>

Interestingly, one might expect the cost (i.e., expected waiting time) at the Nash equilibrium ($c_i^* := c_i(p^*)$) to increase monotonically with $r$, but this is not the case (as shown in the middle sub-figure). Further, recall that in the $P$-discipline, customers arriving at a queue during an ongoing service are served, whereas, in the $G$ discipline, they are not. As a result, under the $G$ discipline, stations with higher arrival rates ($\lambda$) experience greater costs because new arrivals must wait for the server to return after completing the current service (see the comparison between two black curves). In contrast, under the $P$ discipline, these new arrivals are served during the ongoing service, leading to lower costs for stations with higher $\lambda$ (compare the red curves).

Lastly, the right sub-figure indicates that the stations may incur slightly more cumulative cost at equilibrium than the social optimum ($PoA > 1$), which gradually equalizes ($PoA = 1$) as $r$ increases. Thus, at equilibrium, the system's performance improves when the server takes some time to set up.

## 5.2 Numerical analysis of the team game

In Figure 4, we analyze the game among cooperative stations for the following parameters:

$$ \text{Setting 2: } \lambda_1 = 0.153, \lambda_2 = 0.341, d_1 = 0.607, d_2 = 0.192, b_1 = 4.835, \\ b_2 = 0.766, b_1^{(2)} = 32, b_2^{(2)} = 3, d_1^{(2)} = 0.917, d_2^{(2)} = 0.269 \qquad (14) $$

and again consider that $r_1 = r_2 = r$ with $r_i^{(2)} = \theta_i + r^2$ for $\theta_i \stackrel{d}{=} \text{Unif}(0, 1)$. Three scenarios are compared here: (i) stations $1, 2 \in G$ (black curves), (ii) stations $1, 2 \in P$ (red curves), and (iii) stations $1 \in G, 2 \in P$ (blue curves).

Recall that in this game, all the stations try to optimize the 'same' cost function (see (3)). Thus, as the expected switch-in time ($r$) increases, the station with a lesser workload ($\rho_i$) makes a strategic compromise and accepts service with lesser probability. This observation again goes in line with the paradox observed in [4] for the same objective function — neither the server would optimally give
<figure><img src="image_5.png" /><figcaption>Fig. 4: Understanding NE for the team game</figcaption></figure>

service to the stations w.p. 1, nor all the stations would accept service w.p. 1 in a strategic framework.

Further, note that the expected workload of the system (cost) increases with $r$, and following holds:

$$c_i^*|_{1,2 \in \mathcal{G}} > c_i^*|_{1,2 \in \mathcal{P}} > c_i^*|_{1,2 \in \mathcal{P}}, \text{ for each } i \in \{1,2\}.$$

Furthermore, the last sub-figure shows that $PoA= 1$; thus, the system is as efficient at NE as possible.

## 5.3 Numerical analysis of the game among partially cooperative players

In this sub-section, the aim is to understand the effect of additional (linear) cost introduced in a team game on the equilibrium. Towards this, we consider an interesting scenario where the station has to pay more to accept the service with higher probability, an urgency which may be caused due to higher workload ($\rho_i$). In particular, it is assumed that $Q_i = \frac{\rho_i d}{1-\rho} + 100$. The analysis is summarised in Figure 5, for the same parameters as in setting 2 (see (14)).

Now, observe that when $1, 2 \in \mathcal{G}$, the station with higher workload (i.e., station 1) accepts the service with higher probability, and this probability increases as $r$ increases; interestingly, all of this occurs despite the higher cost $Q$. While if $1, 2 \in \mathcal{P}$, then the station with less workload (and thus lesser cost $Q$) accepts service with higher probability. And as one would anticipate, if the stations use different service disciplines, then the station $1 \in \mathcal{G}$ needs to take service with higher probability (as even the new arrivals during the service at station 2 are served by the server, when station 2 is polled, thus possibly leading to higher queues at station 1). Here again, the NE $\mathbf{p}^* \neq (1, 1)$ always.

The trends for the costs incurred at equilibrium are the same as in the team game, except for the fact that the station with a higher workload (and thus, higher additional cost) incurs more cost. Further, the last sub-figure suggests that the system is inefficient at equilibrium when the stations use $\mathcal{P}$-discipline, which is surprising.
<figure><img src="image_6.png" /><figcaption>Fig. 5: Understanding NE for the game among partially-cooperative stations</figcaption></figure>

# 6 Conclusions

In a cyclic Bernoulli polling (CBP) system, there is a single server which moves in a cyclic manner and provides service to the polled station with some probability. In this paper, we proposed a novel game formulation concerning such polling systems where the stations are decision-makers. In particular, they can accept or reject the service from the server, when polled, with some probability, so as to minimize some cost function. Thus, the resultant is a continuous non-cooperative game, where a pure strategy signifies the probability of acceptance of service. Three different variants of games are examined with (i) fully selfish stations, (ii) fully cooperative stations, and (iii) partially cooperative stations, governed by the specific cost functions in each game.

The stations can use either the gated or partially exhaustive service discipline. In each game, we prove that a (mixed/pure) strategy Nash equilibrium (NE) exists; further, in some cases, it is shown to be unique and explicitly characterized. Additionally, we present two new results for CBP systems, including the uniqueness of buffer occupancy solutions and the continuity of expected waiting times w.r.t. the acceptance probabilities.

Through numerical experiments, we observed that NE is always unique, and interestingly, stations (even the selfish ones) do not accept the service w.p. one at equilibrium.

**Future directions:** This work is an initial exploration of strategic decision-making by the stations in polling systems. Future research could focus on characterizing the NE in unresolved cases, studying alternative service disciplines and routing mechanisms, and investigating the cooperative counterpart to the non-cooperative games analyzed here.

# References

1. Adan, I.J., Kulkarni, V.G., Lee, N., Lefeber, E.: Optimal routing in two-queue polling systems. Journal of Applied Probability 55(3), 944–967 (2018)
2. Altman, E.: Applications of dynamic games in queues. In: Advances in dynamic games: Applications to economics, finance, optimization, and stochastic control, pp. 309–342. Springer (2005)

3. Altman, E., Konstantopoulos, P., Liu, Z.: Stability, monotonicity and invariant quantities in general polling systems. Queueing Systems 11, 35–57 (1992)

4. Altman, E., Yechiali, U.: Cyclic bernoulli polling. Zeitschrift für Operations Research 38, 55–76 (1993)

5. Bendel, D., Haviv, M.: Cooperation and sharing costs in a tandem queueing network. European Journal of Operational Research 271(3), 926–933 (2018)

6. Boon, M.A., van der Mei, R.D., Winands, E.M.: Applications of polling systems. Surveys in operations research and management science 16(2), 67–82 (2011)

7. Boxma, O.J., Groenendijk, W.P.: Pseudo-conservation laws in cyclic-service systems. Journal of applied probability 24(4), 949–964 (1987)

8. Burnetas, A., Economou, A., Vasiliadis, G.: Strategic customer behavior in a queueing system with delayed observations. Queueing Systems 86, 389–418 (2017)

9. Dvir, N., Hassin, R., Yechiali, U.: Strategic behaviour in a tandem queue with alternating server. Queueing Systems 96(3), 205–244 (2020)

10. Ferguson, M., Aminetzah, Y.: Exact results for nonsymmetric token ring systems. IEEE Transactions on Communications 33(3), 223–231 (1985)

11. Fudenberg, D., Tirole, J.: Game theory. MIT press (1991)

12. Gaitonde, J., Tardos, É.: Stability and learning in strategic queuing systems. In: Proceedings of the 21st ACM Conference on Economics and Computation. pp. 319–347 (2020)

13. Hassin, R.: Rational queueing. CRC press (2016)

14. Hassin, R., Haviv, M.: To queue or not to queue: Equilibrium behavior in queueing systems, vol. 59. Springer Science & Business Media (2003)

15. Levy, H.: Delay computation and dynamic behavior of non-symmetric polling systems. Performance evaluation 10(1), 35–51 (1989)

16. Liu, Z., Nain, P., Towsley, D.: On optimal polling policies. Queueing Systems 11, 59–83 (1992)

17. Narahari, Y.: Game theory and mechanism design, vol. 4. World Scientific (2014)

18. Rosokha, Y., Wei, C.: Cooperation in queueing systems. Management Science (2024)

19. Royden, H., Fitzpatrick, P.M.: Real analysis. China Machine Press (2010)

20. Sundaram, R.K.: A first course in optimization theory. Cambridge university press (1996)

21. Takagi, H., Kleinrock, L.: A Tutorial on the Analysis of Polling Systems. Report (University of California, Los Angeles. Computer Science Dept.), UCLA Computer Science Department (1985), https://books.google.fr/books?id=yugzHQAACAAJ

22. Takagi, H.: Analysis of polling systems. MIT press (1986)

23. Wierman, A., Winands, E.M., Boxma, O.J.: Scheduling in polling systems. Performance Evaluation 64(9-12), 1009–1028 (2007)

24. Yechiali, U.: Analysis and control of polling systems. In: IFIP International Symposium on Computer Performance Modeling, Measurement and Evaluation. pp. 630–650. Springer (1993)

# 7 Appendix

**Proof of Theorem 1:** The proof of the underlying Theorem follows exactly as in [15] (where every station is served w.p. 1). Nonetheless, we explicitly provide
the proof for $N = 2$ in CBP framework, when both stations use $\mathcal{G}$-policy, to illustrate the necessary steps with minimal notations — these steps can be easily extended for any $1 < N < \infty$, as in [15].

The equations (6)-(8) corresponding to $f_k$ can be written compactly as:

$$f_{k+1} = W_k f_k + b_k, \quad \text{where} \tag{15}$$

the matrix $W_k$ for each $k$ is:

$$\begin{align*}
W_1 &:= \begin{bmatrix}
1 - p_1(1 - \rho_1^2) & 0 & 0 & 0 \\
p_1\rho_1 b_1 \lambda_2 & 1 - p_1(1 - \rho_1) & 0 & 0 \\
p_1\rho_1 b_1 \lambda_2^2 & 0 & 1 - p_1(1 - \rho_1) & 0 \\
p_1 b_1^2 \lambda_2^2 & p_1 \lambda_2 b_1 & p_1 \lambda_2 b_1^2 & 1
\end{bmatrix}, \\
W_2 &:= \begin{bmatrix}
1 & p_2 \lambda_1 b_2 & p_2 \lambda_1 b_2 & p_2 b_2^2 \lambda_1^2 \\
0 & 1 - p_2(1 - \rho_2) & 0 & p_2 \rho_2 b_2 \lambda_1 \\
0 & 0 & 1 - p_2(1 - \rho_2) & p_2 \rho_2 b_2 \lambda_1^2 \\
0 & 0 & 0 & 1 - p_2(1 - \rho_2^2)
\end{bmatrix}.
\end{align*}$$

and an appropriate vector $b_k$ for each $k$ with terms composed of system parameters and $p_1, p_2$.

Now, define the transformation $T_i : f_i \mapsto W_i f_i + b_i$, for each $i$. Further, define $T = T_2 \circ T_1$. Observe that $f_1$ is a fixed point of $T$. For each $i, k, l \in \{1, 2\}$, define (as in [15, (4.2)])

$$g_k(i, l) := b_i b_l f_k(i, l) \tag{16}$$

and then, let $g_k := (g_k(1, 1), g_k(1, 2), g_k(2, 1), g_k(2, 2))^T$, for each $k$. Again, from (15), we have $g_{k+1} = \tilde{T}_k(g_k)$ where $\tilde{T}_k : g_k \mapsto \tilde{W}_k g_k + \tilde{b}_k$ for $\tilde{b}_k$ obtained by appropriately scaling $b_k$ and the matrices $\tilde{W}_k$ given as below:

$$\begin{align*}
\tilde{W}_1 &:= \begin{bmatrix}
1 - p_1(1 - \rho_1^2) & 0 & 0 & 0 \\
p_1\rho_1\rho_2 & 1 - p_1(1 - \rho_1) & 0 & 0 \\
p_1\rho_1\rho_2^2 & 0 & 1 - p_1(1 - \rho_1) & 0 \\
p_1\rho_2^2 & p_1\rho_2 & p_1\rho_2 & 1
\end{bmatrix}, \quad \text{and} \\
\tilde{W}_2 &:= \begin{bmatrix}
1 & p_2\rho_1 & p_2\rho_1 & p_2\rho_1^2 \\
0 & 1 - p_2(1 - \rho_2) & 0 & p_2\rho_2\rho_1 \\
0 & 0 & 1 - p_2(1 - \rho_2) & p_2\rho_2\rho_1^2 \\
0 & 0 & 0 & 1 - p_2(1 - \rho_2^2)
\end{bmatrix}.
\end{align*}$$

Define $\tilde{T} = \tilde{T}_2 \circ \tilde{T}_1$ and observe that $g_1$ is a fixed point of $\tilde{T}$. We claim that $\tilde{T}$ is a contraction under the vector norm $|| \cdot ||_1$. Define $\tilde{W}$ to be product $\tilde{W}_2 \tilde{W}_1$. Let $\tilde{W}(j, k; l, m)$ be the element of the matrix $\tilde{W}$ corresponding to row $(l, m)$ and column $(j, k)$; for example, $\tilde{W}(1, 2; 2, 2)$ refers to element of $\tilde{W}$ in second row and fourth column. Now, note that:

$$||\tilde{T}(g_1) - \tilde{T}(g'_1)||_1 = ||\tilde{W}(g_1 - g'_1)||_1 = \sum_{j,k} \sum_{l,m} |\tilde{W}(j,k;l,m)|| (g_1 - g'_1)(j,k)|.$$

At first, observe that all the entries of the matrices $\tilde{W}_1$ and $\tilde{W}_2$ are non-negative, therefore, $\sum_{l,m} |\tilde{W}(j, k; l, m)| = \sum_{l,m} \tilde{W}(j, k; l, m)$. In the coming, we upper-bound this summation term, for each $j, k$, by a quantity strictly smaller than 1; this would conclude the proof.

(i) For column $(2, 2)$, $\sum_{l,m} \tilde{W}(2, 2; l, m) = 1 - p_2(1 - \rho^2) =: c_1 < 1$.
(ii) For column (1, 2) and (2, 1), define $\theta := 1 - p_1 p_2 (1 - \rho^2)$, and observe,

$$
\begin{align*}
\sum_{l,m} \tilde{W}(2, 1; l, m) &= \sum_{l,m} \tilde{W}(1, 2; l, m) \\
&= p_2 \rho_1 \{1 - p_1(1 - \rho_1)\} + p_1 p_2 \rho_1^2 \rho_2 + 2p_1 p_2 \rho_1 \rho_2^2 \\
&\quad + (1 - p_1(1 - \rho_1))(1 - p_2(1 - \rho_2)) + \{1 - p_2(1 - \rho_2^2)\} p_1 \rho_2 \\
&= \theta - 1 + p_1 p_2 (1 - \rho^2) + p_2 \rho_1 (1 - p_1(1 - \rho_1)) + p_1 p_2 \rho_1^2 \rho_2 + 2p_1 p_2 \rho_1 \rho_2^2 \\
&\quad + (1 - p_1(1 - \rho_1))(1 - p_2(1 - \rho_2)) + (1 - p_2(1 - \rho_2^2)) p_1 \rho_2 \\
&= \theta + p_1 p_2 - 1 - p_1 p_2 t_1 + p_2 \rho_1 (1 - p_1(1 - \rho_1)) \\
&\quad + (1 - p_1(1 - \rho_1))(1 - p_2(1 - \rho_2)) + (1 - p_2(1 - \rho_2^2)) p_1 \rho_2,
\end{align*}
$$

where $t_1 := \rho^2 - \rho_1^2\rho_2 - 2\rho_1\rho_2^2 = (\rho_1^2 + 2\rho_1\rho_2)(1 - \rho_2) + \rho_2^2$. On substitution and further simplification, we get:

$$
\begin{align*}
\sum_{l,m} \tilde{W}(2, 1; l, m) &= \sum_{l,m} \tilde{W}(1, 2; l, m) \\
&= \theta - 1 + p_1 p_2 (1 - \rho_2)(1 - \rho^2) + p_1 p_2 \rho_2 (1 - \rho_2^2) \\
&\quad + (1 - p_1(1 - \rho_1))(1 - p_2(1 - \rho_1)) + (1 - p_2(1 - \rho_2^2)) p_1 \rho_2 \\
&= \theta - 1 + p_1 p_2 (1 - \rho_2)(1 - \rho^2) + (1 - p_1(1 - \rho_1))(1 - p_2(1 - \rho_1)) + p_1 \rho_2 \\
&< \theta - 1 + p_1 p_2 (1 - \rho^2) + (1 - p_1(1 - \rho_1))(1 - p_2(1 - \rho_1)) + p_1 \rho_2 \\
&= (1 - p_1(1 - \rho_1))(1 - p_2(1 - \rho_1)) + p_1 \rho_2 \\
&< 1 - p_1(1 - \rho_1) + p_1 \rho_2 = 1 - p_1(1 - \rho) =: c_2 < 1.
\end{align*}
$$

(iii) For column (1, 1),

$$
\begin{align*}
\sum_{l,m} \tilde{W}(1, 1; l, m) &= 1 - p_1(1 - \rho_1^2) + 2p_1 p_2 \rho_1^2 \rho_2 + p_1 p_2 \rho_1^2 \rho_2^2 \\
&\quad + 2\{1 - p_2(1 - \rho_2)\} p_1 \rho_1 \rho_2 + p_1 p_2 \rho_1 \rho_2^3 + \{1 - p_2(1 - \rho_2^2)\} p_1 \rho_2^2 \\
&= 1 - p_1(1 - \rho^2) - p_1 p_2 (2\rho_1 \rho_2 (1 - \rho) + \rho_2^2 (1 - \rho^2)) =: c_3 < 1.
\end{align*}
$$

Using (i)-(iii), we obtain that $||\tilde{T}(g_1) - \tilde{T}(g'_1)||_1 \le c||g_1 - g'_1||_1$, where $c := \max\{c_1, c_2, c_3\} < 1$.

Importantly, note that the transformation (16) is required even for the case with partially exhaustive discipline. □

**Proof of Theorem 2:** Let $C: A_1 \times \dots \times A_N \to P(\mathbb{R}^{N^3})$ be such that the set $C(\mathbf{p})$ is compact, where $P(\mathbb{R}^{N^3})$ represents the set of all nonempty subsets of $\mathbb{R}^{N^3}$. Recall the iterative form of $f_i$ from (15) and (similar to the notation defined in the proof of Theorem 1) let $W_i(l, m; j, k)$ be the element of $W_i$ matrix from $(l, m)$-th column and $(j, k)$-th row. Let the vector $\mathbf{f} := (f_1, \dots, f_N)$ and consider the function $F: C(\mathbf{p}) \times \prod_{i=1}^N A_i \to \mathbb{R}^+ \cup \{0\}$ defined as:
$$F(\mathbf{f}; \mathbf{p}) = - \sum_{i} \sum_{j,k} \left( f_{i+1}(j, k; p) - \left( \sum_{l,m} W_i(l, m; j, k; p) f_i(l, m; p) + b_i(j, k; p) \right) \right)^2. \quad (17)$$

Further, consider the following optimization problem, parameterized by **p**:

$$\sup_{\mathbf{f} \in C(p)} F(\mathbf{f}; \mathbf{p}), \quad \text{for each } \mathbf{p} \in \prod_{i=1}^{N} A_i. \qquad (18)$$

By Theorem 1, it is easy to see that the optimizer of (18):

$$\mathbf{f}^*(\mathbf{p}) := \arg \sup_{\mathbf{f} \in C(\mathbf{p})} F(\mathbf{f}; \mathbf{p}) \text{ for each } \mathbf{p} \in \prod_{i=1}^{N} A_i,$$

is uniquely given by the solution of (15) for each $k$, if $\mathbf{f}^*(\mathbf{p}) \in C(\mathbf{p})$.

In order to prove that $\mathbf{f}^*(\mathbf{p}) \in C(\mathbf{p})$, observe $0 \le f_k^*(l, i; \mathbf{p}) = E[X_k^i X_k^l] \le (E[(X_k^l)^2]E[(X_k^i)^2])^{1/2}$, by Cauchy-Schwartz inequality. Further, $f_i^*(i, i; \mathbf{p}) = E[X_i^i(X_i^i - 1)] \in [0, E[X_i^i]^2]$. Thus, $|f_k^*(l, i; \mathbf{p})| \le \gamma$ for some constant $\gamma < \infty$, for each $k, l, i$. This implies that $f_k^*$ lies in the projection $C_k$ of $C$. Since each $C_k$ is compact, therefore, $\mathbf{f}^*(\mathbf{p}) \in C(\mathbf{p}) = \prod_i C_i(\mathbf{p})$, where the latter is compact by Tychonoff's Theorem [19].

Note that all elements of the matrix $W_i$ and vector $b_i$ are continuous in **p** and thus, it is easy to observe from (17) that $F(\mathbf{f}; \mathbf{p})$ is continuous in $(\mathbf{f}; \mathbf{p})$. Finally, Maximum Theorem implies that $\mathbf{f}^*(\cdot)$ is upper-semi continuous, and to be precise, $\mathbf{f}^*(\cdot)$ is continuous by [20, Theorem 9.12]. Thus, $E[W_i(\mathbf{p})]$, a function of $f_i(i, i; \mathbf{p})$, is continuous in **p**. $\square$

**Proof of Theorem 4:** Given $r_i = 0$ for each $i$, and thus, from (3) and (4), the cost function for station $i$ is given by:

$$c_i(\mathbf{p}) = \text{constant} + \frac{d}{1-\rho} \sum_{i \in \mathcal{G}} \frac{\rho_i}{p_i} + \frac{d}{1-\rho} \sum_{i \in \mathcal{P}} \frac{\rho_i(1-\rho_i)}{p_i}, \quad (19)$$

where the constant is easily identified. Now, note that:

$$\frac{\partial c_i(\mathbf{p})}{\partial p_i} = - \frac{d}{1-\rho} \frac{\rho_i}{(p_i)^2} + Q_i, \quad \text{and} \quad \frac{\partial^2 c_i(\mathbf{p})}{\partial (p_i)^2} = \frac{2d}{1-\rho} \frac{\rho_i}{(p_i)^3}, \quad \text{if } i \in \mathcal{G},$$

$$\frac{\partial c_i(\mathbf{p})}{\partial p_i} = - \frac{d}{1-\rho} \frac{\rho_i(1-\rho_i)}{(p_i)^2} + Q_i, \quad \text{and} \quad \frac{\partial^2 c_i(\mathbf{p})}{\partial (p_i)^2} = \frac{2d}{1-\rho} \frac{\rho_i(1-\rho_i)}{(p_i)^3}, \quad \text{if } i \in \mathcal{P}.$$

It is clear that the cost function $c_i(\mathbf{p})$ is convex, and the minimizer of this function in $\mathbb{R}^+ \cup \{0\}$ is $\tilde{p}_i$, given the actions chosen by other stations $p_{-i}$. Thus, the best response of station $i$ against $p_{-i}$ is uniquely given by $\tilde{p}_i$ if $\tilde{p}_i \in [\underline{p}_i, 1]$, or by $\underline{p}_i$ if $\tilde{p}_i < \underline{p}_i$, or by 1 if $\tilde{p}_i > 1$. This completes the proof. $\square$
**Proof of Theorem 5:** (i) It is clear from (3) and (4) that the cost function $c_i(\mathbf{p})$ is continuous in $\mathbf{p}$, for each $i$. Thus, by [11, Theorem 1.3], the game has a mixed strategy NE.

(ii) Consider the station $i \in \mathcal{G}$. Further, define

$$h_1(\mathbf{p}) := d^{(2)} + 2d \sum_{i=1}^{N} p_i r_i + \sum_{i=1}^{N} p_i r_i^{(2)} + \sum_{i=1, i \neq j}^{N} p_i p_j r_i r_j.$$

Observe that:

$$\frac{\partial c_i(\mathbf{p})}{\partial p_i} = \frac{\rho^2 - \sum_{i=1}^{N} \rho_i^2}{2(1-\rho)} r_i + \frac{\rho}{2} \frac{h_2(\mathbf{p})}{\bar{d}^2} + \sum_{j \in \mathcal{G}, j \neq i} \frac{r_i \rho_j}{1-\rho} \left( \frac{1}{p_j} - (1-\rho_j) \right) + \rho_i \left\{ r_i \left( 1 - \frac{1-\rho_i}{1-\rho} \right) + \frac{r_i p_i - \bar{d}}{(1-\rho)(p_i)^2} \right\} + Q_i, \text{ where} \quad (20)$$

$$h_2(\mathbf{p}) := \bar{d} \left( 2dr_i + r_i^{(2)} + \sum_{j \neq i} p_j r_i r_j \right) - h_1(\mathbf{p}) r_i.$$

Thus, we have:

$$\frac{\partial^2 c_i(\mathbf{p})}{\partial(p_i)^2} = \frac{2\rho_i}{1-\rho} \frac{(d + \sum_{j \neq i} p_j r_j)}{(p_i)^3} - \frac{\rho h_2(\mathbf{p}) r_i}{(\bar{d})^3}.$$

Since $\bar{d} > p_i r_i$ and $\rho < 1$, therefore, $\frac{\partial^2 c_i(\mathbf{p})}{\partial(p_i)^2} > \frac{1}{(p_i)^3} g(\rho_i)$, where, the function $g: \mathbf{R} \to \mathbf{R}$ is defined as:

$$g(x) = \frac{2x}{1-x} \left( d + \sum_{j \neq i} p_j r_j \right) - \frac{h_2(\mathbf{p})}{(r_i)^2}.$$

Observe that $g(0) < 0$, $g(1) = +\infty$ and $g$ is a convex increasing function in $[0, 1]$. Thus, there exists a $\underline{\rho}_i \in (0, 1)$ such that $g(x) > 0$ for all $x \ge \underline{\rho}_i$. Here onwards, consider $\rho_i \ge \underline{\rho}_i$. Then, it is proved that $\frac{\partial^2 c_i(\mathbf{p})}{\partial(p_i)^2} > 0$, which implies that the cost function $c_i(\mathbf{p})$ is convex (and thus, quasi-convex) in $p_i$, for each $i \in \mathcal{G}$. This conclusion can be derived even for the stations using partially exhaustive discipline. Thus, by [11, Theorem 1.2], there exists a pure strategy NE.

From (20), it is clear that there are at most four zeroes of $c_i(\mathbf{p})$ in $[0, 1]$. Further, since the $c_i(\mathbf{p})$ is convex in $p_i$, therefore, there exists a unique minimizer of $c_i(\mathbf{p})$ in $[\underline{p}_i, 1]$. Using same arguments as in Theorem 4, we conclude that there exists a unique pure strategy NE. $\square$