22 2102

# Nonatomic Non-Cooperative Neighbourhood Balancing Games

David Auger  Johanne Cohen  Antoine Lobstein  David Auger
Université Paris-Saclay ”This work was supported by a public grant as part of
the Investissement d’avenir project, reference ANR-11-LABX-0056-LMH, LabEx
LMH.” UVSQ  DAVID
78035  Versailles  France
<EMAIL_ADDRESS>Johanne Cohen
Université Paris-Saclay idem CNRS  LISN
91405  Orsay  France.
<EMAIL_ADDRESS>Antoine Lobstein
Université Paris-Saclay  CNRS  LISN
91405  Orsay  France.
Antoine<EMAIL_ADDRESS>
###### Abstract

We introduce a game where players selfishly choose a resource and endure a
cost depending on the number of players choosing nearby resources. We model
the influences among resources by a weighted graph, directed or not. These
games are generalizations of well-known games like Wardrop and congestion
games. We study the conditions of equilibria existence and their efficiency if
they exist. We conclude with studies of games whose influences among resources
can be modelled by simple graphs.

###### keywords:

Neighbourhood Balancing Games, Nash equilibrium, graph theory.

††volume: 185††issue: 1

Neighbourhood Balancing Games

##  1 Introduction

Summer is at its peak, and you spend the day at the beach with your whole
family. Unfortunately, you were not the only one with this idea, and the beach
is crowded with optimization specialists. Where will you put your towels? You
should find a place as lovely as possible, sheltered from the wind and close
to the sea, and as isolated as possible from other people to enjoy a little
privacy. Optimizing even more, it could be a good thing to leave no good spots
too close to you because a new family coming to the beach could have the
incentive to move there and ruin your spot.

Sit on a bus, a train, or an auditorium: Where should you sit to enjoy privacy
and comfort so that others arriving later will have no incentive to sit too
close? Another (more technical and less antisocial) analogy is to imagine a
load-balancing context with local influences. Assume that there are $n$
processors with $m$ computation tasks to solve but that solving a task on a
processor impacts other processors around (say, for instance, that nearby
processors share a resource of energy). How should the tasks be distributed to
processors? Can this distribution be efficiently computed?

###  1.1 Our model

Many problems in wireless communication networks have been modelled using
game-theoretic approaches and have received considerable attention (see [22]
for an overview). To handle access to the communication medium, one must
consider interference problems. For example, in the base station selection
[2], a user’s cost (throughput) depends simultaneously on the number of users
associated with the base station and its neighbourhood.

To model these situations, we introduce the notion of Neighbourhood Balancing
Game (NBG). In such a game, players must choose a single resource in a set of
$n$ possibilities. They endure a cost depending on how many players chose the
same resource, but also nearby resources (as opposed, for instance, to
congestion games where the cost of players depends only on the number of
players who chose the same resource). Thus stated, the model of NBG is quite
general, so we shall consider particular cases and use graph-theoretic
terminology to model this notion of proximity between resources and infer
results from the graph topology.

We shall be very interested in equilibria, configurations of players’ choices
such that no player can improve its situation by changing location if other
players do not move. We shall examine these equilibria’s existence, structure,
and computational tractability.

While we can develop a similar theory with atomic players, here we focus on
the nonatomic case and consider a continuum of players, or mass distribution,
to avoid side effects based on divisibility issues. As will be seen, this case
is rich enough to provide many interesting examples.

Our model of nonatomic Neighbourhood Balancing Games lies somewhere between
the model of nonatomic selfish routing (or ”Wardrop model”, see [34]), selfish
load balancing and congestion games.

As will be seen, our framework is more straightforward than the previous ones
in many cases, but many examples already manifest a great depth of complexity.

###  1.2 State of the Art

The general framework of neighbourhood balancing games extends the congestion
games defined by Rosenthal [25]. Congestion games are non-cooperative games in
which the players compete to share a set of resources, and the cost of each
player depends on the number of players choosing the same resource. There are
two types of games: atomic (a finite number of players) and nonatomic (a
continuous number of players).

For nonatomic congestion games, a well-known game theoretic traffic model is
due to Wardrop [34]. Wardrop equilibria have been introduced to model network
behaviours in which travellers (for transportation context) or packets
(telecommunication context) choose routes they perceive as the shortest (see
survey [14] for more details). This model was conceived to represent road
traffic with the idea of an infinite number of agents responsible for an
infinitesimal amount of traffic each. Beckmann et al. [5] proved that Wardrop
equilibrium is a solution of a convex optimization program and is unique.

In algorithmic game theory, a question arises about the impact of the
degradation of the social cost of agents, taking into account their interests.
This measure is called the price of anarchy [21] (ratio between the worst
equilibria and the optimal solution).

This question has been intensively studied for congestion games.

For nonatomic congestion games with affine costs, the price of anarchy is
upper-bounded by $4/3$, and this bound is sharp [28]. Indeed, the simple game
introduced by Pigou is defined as a network with two parallel routes composed
of a single edge connecting a source to a destination. Its price of anarchy is
$4/3$. Moreover, using the same topology and considering that the network’s
cost functions are polynomials of degree at most $p$, Roughgarden [26] proved
that the price of anarchy for such networks is large (the order of magnitude
is $\Theta(p/\log p)$). Recently, some extensions of the price of anarchy have
been thought about in this type of network, considering the traffic variation
[13, 12, 35].

For atomic congestion games, the games that seem most similar to those studied
in this work are load balancing games, or selfish load balancing. The
underlying model, known as the KP-model, was introduced by Koutsoupias and
Papadimitriou in [21], where they define measures for the quality of
equilibria. These problems have been studied widely (see chapter 20 of [24]
for a survey). Indeed, besides their conceptual simplicity (some machines are
shared between selfish users who decide which machines they will assign their
tasks to), these problems are crucial in distributed environments. Koutsoupias
and Papadimitriou proved the existence of Nash equilibria and computed the
price of anarchy when machines are identical. Czumaj and Vöcking [15] gave the
tight bound $\Theta(\log m/\log\log m)$ for the price of anarchy on $m$
uniformly related machines. In such environments, Christodoulou _et al._ [10]
introduced the coordination mechanisms (a set of scheduling policies, one for
each machine) to obtain socially desirable solutions despite the selfishness
of the agents. Several works analyzed the existence of pure Nash equilibria
(see [17, 20, 32] for example) and their prices of anarchy [1, 3, 18, 27, 30]
for these models (for uniform machines or unrelated machines, for weighted or
not players).

Moreover, the price of stability [29] (ratio between the best equilibria and
the optimal solution) is another measure when the game admits several
equilibria. Since nonatomic congestion games have a unique equilibrium, their
prices of anarchy and stability are identical. This reason is why it has been
studied only for atomic congestion games; the price of stability is known for
congestion games with linear cost functions [7, 9] and is upper-bounded [8]
for congestion games with polynomial cost functions.

One of the closest games related to our model is the facility location game
introduced by Vetta [33]. Competitive facility location games deal with the
placement of sites by competing market players. The _facility location game_
plays on weighted bipartite graphs in which each player chooses to open a
single facility within the set of facilities the suppliers will serve,
according to the distribution of users on some vertices. Given a strategy
profile, a supplier $s$ serves the facilities closest to $s$ and receives a
payment from these facilities. Vetta [33] proved that the facility location
game always admitted a Nash equilibrium and gave an upper bound on the price
of anarchy. This has been extended in literature in several papers.

The _discrete Voronoi game_ corresponding to a simple model for the
competitive facility location is very similar to neighbourhood balancing
games. The discrete Voronoi game plays on a given graph with two players.
Every player has to choose a set of vertices, and every vertex is assigned to
the closest player. Dürr and Thang [16], and Teramoto _et al._ [31]
independently proved that deciding the existence of a Nash equilibrium for a
given graph is NP-hard. Several works have been devoted to extending similar
results on various types of graphs (cycles [16], trees [4]).

###  1.3 Outline of the Paper

Section 2 is devoted to defining the games that we shall call NBG and the
variants we shall study. Section 3 will describe the notion of equilibrium and
$\delta$-strong equilibrium. We shall also prove a sufficient condition on the
costs for the game to admit an equilibrium. Moreover, in Subsection 3.4, we
prove that knowing whether a game admits a strong equilibrium is NP-complete.
Furthermore, we adapt the notion of potential to our games to prove that
symmetric graphical games admit a potential function. Subsections 3.9 and 3.10
focus on the efficiency of equilibria. Finally, in Section 4, we focus on
characterizing equilibria in games where very simple graphs represent
interactions between resources.

##  2 Neighbourhood Balancing Games (NBGs)

In this section, we present and discuss our model, starting from the general
case and refining particular cases and properties that will be needed later.

###  2.1 General Model

Let $n\geq 1$ be an integer. Integers from $1$ to $n$, whose set we denote as
$[n]$, will be called vertices ; those are the resources (we use a graph-
theoretical vocabulary for reasons that will appear soon). In the paper,
symbols $i,j$ are for vertices; if omitted, their scope is the set $[n]$.

A mass distribution on $[n]$ is a vector
${\mathbf{x}}=(x_{1},x_{2},\cdots,x_{n})$ with real nonnegative entries, where
$x_{i}$ is to be thought of as the mass on vertex $i$. The total mass of such
a distribution is the sum of all $x_{i}$’s for ${i\in[n]}$ and will be denoted
by $r$. A mass distribution can be considered as a continuum of players, each
choosing a single vertex as a strategy. We also refer to such an imaginary
player by the expression ”infinitesimal unit of mass”.

We shall denote $\Delta_{r}(n)$ the set of $n$-dimensional mass distributions
with total mass $r>0$. Given ${\mathbf{x}}\in\Delta_{r}(n)$, we say that a
vertex $i$ is charged if $x_{i}>0$, otherwise it is uncharged. The support of
${\mathbf{x}}$ is the set of charged vertices.

A cost function on vertex $i$ is a function

$C_{i}:{\mathbf{x}}\mapsto C_{i}({\mathbf{x}})\in{\mathbb{R}}^{+}$

mapping every mass distribution ${\mathbf{x}}\in\Delta_{r}(n)$ (for a given
$r$) to a nonnegative real number, the cost of vertex $i$ under mass
distribution ${\mathbf{x}}$.

We interpret the cost $C_{i}({\mathbf{x}})$ as the price paid by individuals
in the continuum of players that have chosen vertex $i$ as their strategy. Of
course, each player has a goal of minimizing such a cost. This can also be
viewed as people in location $i$ enduring a nuisance, based on the total
number of people in their location and other locations.

To aggregate all this, we define a Neighbourhood Balancing Game (NBG for
short) as a triple $(n,r,C)$, where $n\geq 1$, $r>0$, and
$C=(C_{i})_{i\in[n]}$ is the $n$-dimensional vector of cost functions
$C_{i}:\Delta_{r}(n)\rightarrow{\mathbb{R}}^{+}$.

Given this, the definition is quite general, and we shall be interested in
NBGs where cost functions have prescribed forms, which we shall describe
afterwards.

####  2.1.1 A first example: two-commodity dilemma game (see Figure 1)

Let us consider a first, simple NBG: the NBG $(2,1,C)$ with
$C_{1}(x_{1},x_{2})=4x_{1}x_{2}$ and $C_{2}(x_{1},x_{2})=x_{1}$. This can be
thought of as a two-commodity dilemma with a total mass $1$ of players
simultaneously deciding between commodities $1$ and $2$, then enduring the
cost $C_{i}$ depending on their choice and the repartition of the mass.

Since for all $(x_{1},x_{2})\in\Delta_{1}(2)$ we have $x_{1}+x_{2}=1$, we can
rewrite these costs as functions of $x_{1}$ only i.e.
$C_{1}(x_{1})=4x_{1}(1-x_{1})$ ans $C_{2}(x_{1})=x_{1}$; these are depicted in
Figure 1. As can be seen, costs are equal when $x_{1}=0$ and
$x_{1}=\frac{3}{4}$. When $x_{1}<\frac{3}{4}$, vertex $2$ has a lower, hence
better cost. Hence, the mass on vertex $1$ might want to move to $2$,
decreasing $x_{1}$ in the process. When $x_{1}>\frac{3}{4}$, the cost is
better on vertex $1$, hence the mass on $2$ might want to move to $1$,
increasing $x_{1}$. Thus, we can expect that if we let the mass continuously
move, starting from $x_{1}\neq\frac{3}{4}$, we would obtain stabilization at
either $x_{1}=0$ or $x_{1}=1$ depending on the case. If $x_{1}$ is exactly
$\frac{3}{4}$, the two costs are equal, and we can interpret this as a case
where no player can improve its cost by switching from one vertex to the
other.

We shall define mass distributions such as $x_{1}=0$, $x_{1}=\frac{3}{4}$ and
$x_{1}=1$, where no mass has the incentive to move, as equilibria, and it will
be our main endeavour to try and understand them; see Section 3 for a
definition.

0$r=1$$1$$\frac{3}{4}$$\frac{1}{2}$$\frac{3}{4}$$x_{1}$cost$C_{2}$$C_{1}$
Figure 1: Costs functions for the example in Subsection 2.1.1. The cost
$C_{1}$ (resp. $C_{2}$) is represented by the dotted curve (resp. solid). The
$x$-axis is the mass of vertex $1$.

###  2.2 Graphical NBGs

####  2.2.1 Definition

In this section, we define a subclass of NBGs, which will be our main focus
for the rest of the paper. In addition to being a natural and more
straightforward case, Subsection 3.6 will explain the reason for this
particular class.

We now consider only the cost functions of the form

$C_{i}({\mathbf{x}})=f_{i}(x_{i})+\sum_{j\neq i}\alpha_{j,i}x_{j}$

where:

  1. (i)

$f_{i}:[0,r]\rightarrow{\mathbb{R}}^{+}$ is a continuous non-decreasing
function, such that

$t>0\Rightarrow f_{i}(t)>0$

(hence values are positive except possibly for $t=0$);

  2. (ii)

$\alpha_{j,i}$, for every $i\neq j$ in $[n]$, are nonnegative real numbers.

Functions $f_{i}$ are called _vertex-cost functions_ and are not to be
confused with proper cost functions $C_{i}$ that are deduced from $f_{i}$’s
and $\alpha_{i,j}$’s.

We call such a game a _graphical_ NBG and it will be denoted

$(n,r,f,\alpha),$

where $f=(f_{i})_{i\in[n]}$ and $\alpha=(\alpha_{i,j})_{i\neq j\in[n]}$. If
furthermore for all $i,j\in[n]$, $i\neq j$, we have
$\alpha_{j,i}=\alpha_{i,j}$, we say that the game is _symmetric_.

To a graphical NBG, we can associate an _underlying graph_ (hence the name),
which is either a directed graph $(V,A)$ (in the general, non-symmetric case)
or an undirected graph $(V,E)$ (if the game is symmetric), where $V=[n]$ and
either

$A=\\{(i,j):1\leq i\neq j\leq n\text{ and }\alpha_{i,j}>0\\}$

is the set of arcs in the directed case or

$E=\\{\\{i,j\\}:1\leq i\neq j\leq n\text{ and }\alpha_{i,j}>0\\}$

is the set of edges in the symmetric case.

Let us go back to the example in Subsection 2.1.1. It is not graphical since
$C_{1}({\mathbf{x}})=4x_{1}x_{2}$ is not of the prescribed form. If we had
$C_{1}({\mathbf{x}})=x_{1}+x_{2}$ and still $C_{2}({\mathbf{x}})=x_{1}$, the
example would have been graphical and even symmetric, with
$f_{1}(x_{1})=x_{2}$, $f_{2}(x_{2})=0$ and $\alpha_{1,2}=\alpha_{2,1}=1$.

####  2.2.2 Special case where there are two resources ($n=2$)

The case $n=2$ is, of course, more straightforward than the general case but
is still rich enough to provide examples and counterexamples. We shall
represent a symmetric graphical NBG as:

$1$$2$$\alpha_{1,2}=\alpha$$f_{1}(x_{1})$$f_{2}(x_{2})$

The following proposition will be used to build examples. It shows that in the
case $n=2$, if some regularity conditions are satisfied, we can always find
$\alpha_{1,2}$ and vertex-cost functions to obtain any couple of cost
functions on vertices, up to translation.

###### Proposition 2.1

Let $D_{1}$ and $D_{2}$ be two continuously differentiable functions on
$\Delta_{r}(2)$ for a given $r>0$. We can find a real number $c$, a positive
$\alpha>0$ and two functions $f_{1}$ and $f_{2}$ such that
$(2,r,f=(f_{1},f_{2}),\alpha)$ is a symmetric graphical NBG with cost
functions $C_{1}=D_{1}+c$ and $C_{2}=D_{2}+c$.

###### Proof 2.2

For $x\in\Delta_{r}(2)$ we want

$D_{1}(x_{1},x_{2})+c=C_{1}(x_{1},x_{2})=f_{1}(x_{1})+\alpha
x_{2}=f_{1}(x_{1})+\alpha(r-x_{1}),$

so we define on $[0,r]$

$f_{1}(x_{1})=D_{1}(x_{1},r-x_{1})+c-\alpha(r-x_{1})$

and likewise

$f_{2}(x_{2})=D_{2}(r-x_{2},x_{2})+c-\alpha(r-x_{2})$

where $c$ and $\alpha$ are to be defined.

What remains to do is to find values $\alpha\geq 0$ and $c$ such that $f_{1}$
and $f_{2}$ will be positive and non-decreasing. Both functions are
continuously differentiable and for $x_{1}\in[0,r]$ we have

$f^{\prime}(x_{1})=\frac{\partial D_{1}}{\partial
x_{1}}(x_{1},r-x_{1})-\frac{\partial D_{1}}{\partial
x_{2}}(x_{1},r-x_{1})+\alpha,$

hence if we want $f_{1}$ and $f_{2}$ non-decreasing it is enough to use any
$\alpha$ satisfying

$\displaystyle\alpha\geq\max\Big{(}$
$\displaystyle\max_{x\in[0,r]}\left\\{-\frac{\partial D_{1}}{\partial
x_{1}}(x,r-x)+\frac{\partial D_{1}}{\partial x_{2}}(x,r-x)\right\\},$
$\displaystyle\max_{x\in[0,r]}\left\\{\frac{\partial D_{2}}{\partial
x_{1}}(r-x,x)-\frac{\partial D_{2}}{\partial x_{2}}(r-x,x)\right\\}\Big{)}$

and then we can easily find $c$ such that both functions are positive.

###  2.3 Affine, Linear, Normal, Uniform NBGs

We shall restrict graphical NBGs by considering the following definitions for
a graphical NBG $G=(n,r,f,\alpha)$:

  * •

$G$ is _affine_ if all vertex-cost functions $f_{i}$ for $i\in V$ are of the
form

$f_{i}(x_{i})=\alpha_{i,i}x_{i}+b_{i},$

where $\alpha_{i,i},b_{i}$ are nonnegative. Cost functions are then of the
form

$C_{i}({\mathbf{x}})=b_{i}+\sum_{j\in V}\alpha_{j,i}x_{j}$

hence are also affine functions. An affine graphical NBG can be symmetric or
not.

  * •

if $G$ is affine and moreover all $b_{i}$’s satisfy $b_{i}=0$, then the NBG is
_linear_ and all cost functions $C_{i}$ for $i\in V$ are of the form

$C_{i}({\mathbf{x}})=\sum_{j\in V}\alpha_{j,i}x_{j},$

where the $\alpha_{i,j}$’s are nonnegative. A linear NBG is said to be
_normal_ if $\alpha_{i,i}=1$ for all $i$.

  * •

$G$ is an $\alpha$-uniform NBG if it is a normal linear NBG where all nonzero
$\alpha_{i,j}$’s for $i\neq j$ have a common value $\alpha$, or in other words
all cost functions $C_{i},i\in V$, are of the form

$C_{i}({\mathbf{x}})=x_{i}+\alpha\sum_{j\in N[i]}x_{j},$

where $N[i]\subseteq V\setminus\\{i\\}$ is a set of vertices which we call
neighbours of $i$ using graph-theoretic terminology. If the game is symmetric,
these neighbours are precisely the neighbours in the underlying undirected
graph (otherwise, they are the in-neighbours in the underlying directed
graph).

We shall recall these definitions when needed.

###  2.4 Summary

Here is a table to sum up the different cases:

Class of NBG | condition on cost functions $C_{i}$
---|---
general | $C_{i}({\mathbf{x}})\geq 0$
| $C_{i}({\mathbf{x}})=f_{i}(x_{i})+\sum_{j\neq i}\alpha_{j,i}x_{j}$
graphical |  $f_{i}$ continuous non-decreasing
| $t>0\Rightarrow f_{i}(t)>0$
|  $f_{i}(0)\geq 0$, $\alpha_{j,i}\geq 0$
affine | $C_{i}({\mathbf{x}})=b_{i}+\sum_{j}\alpha_{j,i}x_{j}$
|  $b_{i}\geq 0$, $\alpha_{j,i}\geq 0$
linear | $C_{i}({\mathbf{x}})=\sum_{j}\alpha_{j,i}x_{j}$
| $\alpha_{j,i}\geq 0$
normal | linear with $\alpha_{i,i}=1$
$\alpha$-uniform | normal linear with
| $j\neq i,\alpha_{j,i}>0\Rightarrow\alpha_{j,i}=\alpha$

Each class contains the classes below it in the table, and all classes
included in the Graphical class can be either symmetric
($\alpha_{j,i}=\alpha_{i,j}$ for all $i\neq j$) or not.

##  3 Equilibria

Equilibria of NBGs are our main focus in this paper. An equilibrium is a mass
distribution such that no infinitesimal player has the incentive to move
because, in that distribution, every player has made the best choice for
itself. This notion relates to the $n$-player games definition of Nash
equilibria and the definitions of equilibria in other nonatomic games such as
Wardrop games or nonatomic congestion games. We consider only pure equilibria
here because infinitesimal players do not use mixed strategies.

In this section, after properly defining equilibria and proving their
existence in the general case, we establish an algorithmic complexity result
for the existence of a refined notion of equilibria, $\delta$-strong
equilibria. We then introduce the notion of the potential function and prove
that symmetric graphical games enjoy the existence of such a function, which
is a tool to compute equilibria.

###  3.1 Definition

An equilibrium is a mass distribution such that no infinitesimal mass quantity
can get a lower cost by moving from one vertex to another. Formally,
${\mathbf{x}}^{*}\in\Delta_{r}(n)$ is an equilibrium if

$\forall i,j\in[n],\quad x^{*}_{i}>0\Rightarrow C_{i}({\mathbf{x}}^{*})\leq
C_{j}({\mathbf{x}}^{*}).$

This definition implies that in an equilibrium, all charged vertices share the
same cost, while uncharged vertices have at least the same cost as the charged
vertices.

For $\delta\geq 0$, a $\delta$-strong equilibrium is a
${\mathbf{x}}^{*}\in\Delta_{r}(n)$ such that no mass quantity
$0\leq\epsilon\leq\delta$ can improve its cost by moving from one vertex to
another. Formally,

$\forall 0\leq\epsilon\leq\delta,\forall
i,j\in[n],x^{*}_{i}\geq\epsilon\Rightarrow C_{i}({\mathbf{x}}^{*})\leq
C_{j}({\mathbf{x}}^{*}-\epsilon\cdot{\mathbf{e}}_{i}+\epsilon\cdot{\mathbf{e}}_{j}),$
(1)

where $({\mathbf{e}}_{i})_{i\in[n]}$ is the canonical basis of
${\mathbb{R}}^{n}$. If $\delta\leq\delta^{\prime}$, a $\delta^{\prime}$-strong
equilibrium is $\delta$-strong, particularly all $\delta$-strong equilibria
are $0$-strong, which amounts to saying that it is an equilibrium in the sense
defined above.

We say that an equilibrium is strong if it is $\delta$-strong for some
$\delta>0$. See Figures 2 and 3 for examples of equilibria, strong or not.
Thanks to Proposition 2.1, we do not need to define these examples explicitly
where only the curves’ relative positions and shapes are relevant.

0$r$$\gamma$$x_{1}$cost$C_{1}$$C_{2}$ Figure 2: We consider a game with $2$
vertices. The curves represent the costs of the two vertices as a function of
the mass on vertex $1$. There are three equilibria in this case: $x_{1}=0$,
$x_{1}=\gamma$ (second intersection of the costs curves) and $x_{1}=r$.
Equilibria $x_{1}=0$ and $x_{1}=r$ are strong; however $x_{1}=\gamma$ is not
strong since a small quantity $\epsilon$ of mass can always move from $2$ to
$1$ and improve its cost. 0$r$$x_{1}$cost$C_{1}$$C_{2}$ Figure 3: We consider
a game with $2$ vertices. The curves represent the costs of the two vertices
as a function of the mass on vertex $1$. There is only one equilibrium in
$x_{1}=0$, which is not strong.

###  3.2 Existence of Equilibria

Here, we consider general cost functions and show the existence of an
equilibrium under the condition of continuity. The proof is adapted from
Nash’s proof of the existence of a mixed symmetric Nash equilibrium in a
symmetric game [23].

###### Theorem 3.1

Let $(n,r,C)$ be a general NBG, and suppose that cost functions
$(C_{i})_{i\in[n]}$ are continuous. Then, the game admits an equilibrium.

###### Proof 3.2

Define, for all $i,j\in[n]$, a function
$g_{i,j}:\Delta_{r}(n)\rightarrow{\mathbb{R}}^{+}$ by

$g_{i,j}({\mathbf{x}})=x_{j}\cdot\max\left(0,C_{j}({\mathbf{x}})-C_{i}({\mathbf{x}})\right)$

and $F_{i}:\Delta_{r}(n)\rightarrow{\mathbb{R}}^{+}$ by

$F_{i}({\mathbf{x}})=\frac{x_{i}+r\cdot\sum_{j\in[n]}g_{i,j}({\mathbf{x}})}{1+\sum_{i,j\in[n]}g_{i,j}({\mathbf{x}})}.$

This definition guarantees that $F=(F_{1},F_{2},\cdots,F_{n})$ takes values in
$\Delta_{r}(n)$ and is continuous, hence has a fixed point ${\mathbf{x}}^{*}$
by Brouwer’s fixed point theorem. Consider $k\in[n]$ such that
$C_{k}({\mathbf{x}}^{*})=\max\\{C_{j}({\mathbf{x}}^{*}):x^{*}_{j}>0\\}$ and
$x^{*}_{k}>0$. Then

$C_{j}({\mathbf{x}}^{*})>C_{k}({\mathbf{x}}^{*})\Rightarrow x^{*}_{j}=0,$

so that $g_{k,j}({\mathbf{x}}^{*})=0$ for all $j\in[n]$. In particular, we
have $F_{k}({\mathbf{x}}^{*})=x^{*}_{k}$, hence

$\frac{x^{*}_{k}}{1+\sum_{i,j\in[n]}g_{i,j}({\mathbf{x}}^{*})}=x^{*}_{k}.$

Since $x^{*}_{k}>0$, this implies that $g_{i,j}({\mathbf{x}}^{*})=0$ for all
$i,j\in[n]$. In particular, for $i,j$ with $x^{*}_{j}>0$, we have
$\max(0,C_{j}({\mathbf{x}}^{*})-C_{i}({\mathbf{x}}^{*}))=0$, which is the
definition of an equilibrium.

###  3.3 Games with no Equilibria

A non-continuous game does not need to have an equilibrium. Consider for
instance $(2,1,C)$ with $C_{1}({\mathbf{x}})=1$, and $C_{2}({\mathbf{x}})=2$
when $x_{1}<\frac{1}{2}$, and $C_{2}({\mathbf{x}})=0$ otherwise. When
$x_{1}<\frac{1}{2}$, we have $x_{2}>0$ but
$C_{1}({\mathbf{x}})<C_{2}({\mathbf{x}})$, hence not an equilibrium, and for
$x_{1}\geq\frac{1}{2}$ we have $x_{1}>0$ and
$C_{2}({\mathbf{x}})<C_{1}({\mathbf{x}})$ hence also not an equilibrium.

###  3.4 Structure and Complexity of Equilibria

Here, we study the structure of equilibria in one particular case, namely
normal linear NBGs. This enables us to derive complexity results for the
problem of finding an equilibrium in a given NBG.

So we consider a (possibly non-symmetric) normal linear NBG $G$ and its
underlying directed graph $D$, i.e. its cost functions are of the form

$C_{i}({\mathbf{x}})=x_{i}+\sum_{j\neq i}\alpha_{j,i}x_{j},$ (2)

where $\alpha_{i,j}$ may be different from $\alpha_{j,i}$.

Let us recall that for a directed graph $D=(V,A)$, a kernel is a set of
vertices $K\subseteq V$ such that:

  * •

for any two distinct vertices $v,w\in K$, arcs $(v,w)$ and $(w,v)$ do not
belong to $A$ (hence $K$ is a directed stable set);

  * •

if $z\not\in K$, then there is $v\in K$ with $(v,z)\in A$ ($K$ is a directed
dominating set).

###### Proposition 3.3

Let $G=(n,r,C)$ be an NBG with normal linear cost functions and underlying
graph $D$; suppose furthermore that

$\;\alpha_{i,j}>0\Rightarrow\alpha_{i,j}>1\;\;and\;\;\alpha_{i,j}+\alpha_{j,i}>2\;\;(i\neq
j).$

Then, the supports of strong equilibria are exactly the kernels of $D$.

###### Proof 3.4

First, consider a kernel $K$ of $D$ of size $k$ and define ${\mathbf{x}}^{*}$
by $x_{i}^{*}=\frac{r}{k}$ if $i\in K$ and $x_{i}^{*}=0$ otherwise. Since $K$
is a stable set, the cost inside $K$ is exactly $\frac{r}{k}$, and since $K$
is dominating and any nonzero $\alpha_{i,j}$ is at least one, the cost is at
least $\frac{r}{k}$ outside $K$. Let $0\leq\epsilon\leq\frac{r}{k}$ and
consider a mass $\epsilon$ moving from vertex $i\in K$ to $j$.

If $j\in K$, the cost in $j$ after the change will be $\frac{r}{k}+\epsilon$,
which is worse. If $j\not\in K$, then there is an arc $(i^{\prime},j)$ from a
vertex $i^{\prime}\in K$ to $j$. The worst case is when $i^{\prime}=i$, and in
this case, the cost in $j$ will be at least

$\epsilon+\alpha_{i,j}(\frac{r}{k}-\epsilon)=(\alpha_{i,j}-1)(\frac{r}{k}-\epsilon)+\frac{r}{k}\geq\frac{r}{k},$

which is also not better. Hence, $K$ is the support of a $\frac{r}{k}$-strong
equilibrium.

Conversely, suppose now that ${\mathbf{x}}^{*}$ is a $\delta$-strong
equilibrium of $G$ for a $\delta>0$, and $i,j\in[n]$ are two charged vertices
with $\alpha_{i,j}>0$, i.e. $(i,j)$ is an arc of $D$. Consider an $\epsilon>0$
as in Definition (1), and suppose furthermore that
$\epsilon<\min(\delta,x_{i}^{*},x_{j}^{*})$. Then

$C_{i}({\mathbf{x}}^{*})\leq
C_{j}({\mathbf{x}}^{*}+\epsilon\cdot{\mathbf{e}_{j}}-\epsilon\cdot{\mathbf{e}_{i}})$

and

$C_{j}({\mathbf{x}}^{*})\leq
C_{i}({\mathbf{x}}^{*}+\epsilon\cdot{\mathbf{e}_{i}}-\epsilon\cdot{\mathbf{e}_{j}}).$

Let $A_{i}=\sum_{k\neq i,j}\alpha_{k,i}x_{k}^{*}$ and $A_{j}=\sum_{k\neq
i,j}\alpha_{k,j}x_{k}^{*}$. Then, the inequalities above can be written

$x_{i}^{*}+\alpha_{j,i}x_{j}^{*}+A_{i}\leq
x_{j}^{*}+\epsilon+\alpha_{i,j}(x_{i}^{*}-\epsilon)+A_{j}$

and

$x_{j}^{*}+\alpha_{i,j}x_{i}^{*}+A_{j}\leq
x_{i}^{*}+\epsilon+\alpha_{j,i}(x_{j}^{*}-\epsilon)+A_{i}.$

Summing these two inequalities, we obtain after cancellations

$0\leq 2\epsilon-\epsilon(\alpha_{i,j}+\alpha_{j,i}),$

so that $\alpha_{i,j}+\alpha_{j,i}\leq 2$, contradicting our hypothesis. So,
there can be no arc between charged vertices, and the support of the
equilibrium is a stable set.

Moreover, if $j$ is uncharged, then its cost must be positive by the
definition of equilibria; hence, there must be some charged vertex $i$ with
$\alpha_{i,j}>0$. Therefore, the support of a strong equilibrium is a kernel
of $D$.

For a normal linear NBG or even an affine NBG, checking if a mass distribution
is a strong equilibrium is a simple task and amounts to checking a quadratic
number of inequalities. Now, observe that determining whether a given digraph
admits kernels is NP-complete ([11], [19, p. 204]). Also, there is a
straightforward polynomial reduction from kernels to strong equilibria by
changing a digraph into a normal linear NBG simply by choosing some
$\alpha_{i,j}>1$ on all arcs. Hence:

###### Corollary 3.5

Determining whether an affine NBG admits a strong equilibrium is NP-complete.

In general, checking if a distribution is a strong equilibrium depends on the
model used to define functions. However, we still have that:

###### Corollary 3.6

Determining whether an NBG admits a strong equilibrium is NP-hard.

As a conclusion to this subsection, let us mention a simple example where the
game admits an equilibrium (not strong), and the graph has no kernel. We
consider the normal linear NBG on three vertices {1,2,3} with arcs $(1,2)$,
$(2,3)$ and $(3,1)$, with a coefficient $\alpha>0$ on each arc. Consider the
mass distribution $(1/3,1/3,1/3)$: it is an equilibrium. However, this
equilibrium is not strong, and the graph admits no kernel.

###  3.5 Potential Function

Let $G=(n,r,C)$ be an NBG. A potential function for $G$ is a differentiable
function $\Phi$ defined on a neighbourhood of $\Delta_{r}(n)$ such that

$\forall i\in[n],\frac{\partial\Phi({\mathbf{x}})}{\partial
x_{i}}=C_{i}({\mathbf{x}}).$

A potential function is a tool to study equilibria. In particular

###### Proposition 3.7

If an NBG, $G=(n,r,C)$, admits a potential function $\Phi$, then the local
minima of $\Phi$ on $\Delta_{r}(n)$ are equilibria of the game.

###### Proof 3.8

Let ${\mathbf{x}}^{*}$ denote a local minimum of $\Phi$ on $\Delta_{r}(n)$. In
particular, if $x_{i}^{*}>0$ and $j\in[n]$, $j\neq i$, there is an
$\epsilon>0$ such that if $x_{i}^{*}-\epsilon\geq 0$, we have

$\Phi({\mathbf{x}}^{*})\leq\Phi({\mathbf{x}}^{*}-t\cdot\epsilon\cdot{\mathbf{e}_{i}}+t\cdot\epsilon\cdot{\mathbf{e}_{j}})$

for all $t\in[0,1]$. Defining

$f(t)=\Phi({\mathbf{x}}^{*})-\Phi({\mathbf{x}}^{*}-t\cdot\epsilon\cdot{\mathbf{e}_{i}}+t\cdot\epsilon\cdot{\mathbf{e}_{j}}),$

we see that $f$ is differentiable on $[0,1]$ and is nonpositive while
$f(0)=0$. Hence, we have $f^{\prime}(0)\leq 0$ and thus

$\epsilon\cdot C_{i}({\mathbf{x}}^{*})-\epsilon\cdot
C_{j}({\mathbf{x}}^{*})\leq 0,$

which is the definition of equilibria.

Remark. Following the proof above, an interpretation of the potential function
$\Phi$ is that for $|t|$ small enough, if $x_{i}>0$ we have

$\Phi({\mathbf{x}}+t\cdot{\mathbf{e}_{i}}-t\cdot{\mathbf{e}_{j}})-\Phi({\mathbf{x}})=t\cdot(C_{i}({\mathbf{x}})-C_{j}({\mathbf{x}}))+o(|t|),$

hence the total quantity of cost variation when moving between $i$ and $j$ can
be deduced from the difference of potential.

Remark. An equilibrium corresponding to the minimum of a potential function is
not necessarily strong. See Figure 3 for an example with a unique, not strong,
equilibrium, which must be the global minimum of the potential function (this
example is a graphical symmetric NBG, so it admits a potential function by
Proposition 3.9).

Remark. The converse is false: an equilibrium does not always correspond to a
local minimum of the potential. See a counterexample in Figure 4.

021$r=1$$x_{1}$cost$C_{1}$$C_{2}$ Figure 4: With $n=2$ and $r=1$ (so that
$x_{2}=1-x_{1}$), consider $\alpha_{1,2}=\alpha_{2,1}=1$, $f_{1}(x_{1})=1$ and
$f_{2}(x_{2})=1+x_{2}$. This gives $C_{1}({\mathbf{x}})=2-x_{1}$,
$C_{2}({\mathbf{x}})=2$, and
$\Phi({\mathbf{x}})=x_{1}+(x_{2}+\frac{1}{2}x_{2}^{2})+x_{1}x_{2}=(3-x_{1}^{2})/2$
(this potential function is given by Equation (3) in the upcoming Proposition
3.9; we can check that this is indeed a potential. Otherwise, other potentials
are equal to this one up to an additive constant; also note that a potential
can be expressed with $x_{1}$ alone, with $x_{2}$ alone, or with both $x_{1}$
and $x_{2}$). There are two equilibria, one in $x_{1}=1$ which is a minimum of
the potential function, and one in $x_{1}=0$, which is a maximum.

Note that since $\Phi$ is continuous on the compact set $\Delta_{r}(n)$, it
admits a global minimum on $\Delta_{r}(n)$, which gives another, more
constructive, proof of the existence of an equilibrium when there is a
potential function.

###  3.6 Potential Function and Graphical NBGs

To build examples where there is a potential function, one could consider a
differentiable function $\Phi$ and define $C_{i}({\mathbf{x}})$ as
$\frac{\partial\Phi({\mathbf{x}})}{\partial x_{i}}$.

However, to identify classes of games where there always exists a potential
function, we can restrict our attention to cost functions which are
decomposable in the following natural way:

$C_{i}({\mathbf{x}})=f_{i}(x_{i})+\sum_{j\neq i}f_{j,i}(x_{j})$

where the $f_{i}$’s and $f_{i,j}$’s are continuously differentiable functions
(for practical reasons).

Supposing that the game admits a potential function $\Phi$, by Schwarz’s
theorem, we must have for all $i\neq j$

$\frac{\partial^{2}\Phi}{\partial x_{i}\partial
x_{j}}({\mathbf{x}})=\frac{\partial^{2}\Phi}{\partial x_{j}\partial
x_{i}}({\mathbf{x}}),$

so

$\frac{\partial f_{j,i}(x_{j})}{\partial x_{j}}=\frac{\partial
f_{i,j}(x_{i})}{\partial x_{i}}.$

Therefore, these functions must be linear, of the form $f_{j,i}=cx_{j}$ and
$f_{i,j}=cx_{i}$ for a $c\in{\mathbb{R}}$; whence the definition of symmetric
graphical games.

The following is then easy to check.

###### Proposition 3.9

Let $G=(n,r,f,\alpha)$ be a symmetric graphical game. Define:

$\Phi:\Delta_{r}(n)\longrightarrow{\mathbb{R}}$

by

$\Phi({\mathbf{x}})=\sum_{i}\int_{0}^{x_{i}}f_{i}(t)dt+\sum_{i<j}\alpha_{i,j}x_{i}x_{j}.$
(3)

Then $\Phi$ is a potential function for $G$.

Remark. A graphical NBG which is not symmetric may admit no potential. Indeed,
by the discussion above, if $\alpha_{i,j}\neq\alpha_{j,i}$ and the $f_{i}$’s
are continuously differentiable, then we see by Schwarz’s theorem that a
potential function cannot exist.

In the following, we investigate how our model of NBG leads to equilibria that
can be good or bad from a social viewpoint.

###  3.7 Social Costs

A social cost is a way to average all the costs paid by the infinitesimal
players in the game and quantify by a single number the cost, hence the
quality of equilibria, if we want to compare them.

We define two social costs:

  * •

The utilitarian social cost, defined as

${\mathcal{C}}_{u}({\mathbf{x}})=\frac{1}{r}\sum_{i\in[n]}x_{i}C_{i}({\mathbf{x}}),$

is simply the average cost of an infinitesimal mass in the graph. It can be
low even if a small fraction of the mass pays a high cost.

  * •

The egalitarian social cost, defined as

${\mathcal{C}}_{e}({\mathbf{x}})=\max_{i\in[n],x_{i}>0}C_{i}({\mathbf{x}})$

is the maximum cost encountered among vertices with a positive quantity of
mass. Minimizing this cost is more complicated than minimizing the utilitarian
cost since it considers all infinitesimal players.

We should note that for all ${\mathbf{x}}\in\Delta_{r}(n)$, we have
${\mathcal{C}}_{u}({\mathbf{x}})\leq{\mathcal{C}}_{e}({\mathbf{x}})$, and that
there is equality if ${\mathbf{x}}$ is an equilibrium.

###  3.8 A Braess-like Paradox

Braess’s Paradox was discovered by Braess [6] in the context of nonatomic
selfish routing. In this model of routing a continuous mass of vehicles from a
source to a destination, one shows the paradoxical phenomenon that opening a
new road leads to a dramatic increase in the social cost of the (unique)
equilibrium of the model.

Despite being even more straightforward than the nonatomic selfish routing
model, we show that our NBG model admits examples that lead to similar
conclusions.

Consider the following example with two vertices:

$1$$2$$\alpha_{1,2}=\frac{1}{4}$$f_{1}(x_{1})=1$$f_{2}(x_{2})=x_{2}+b_{2}$

with total mass $r=1$. We can write a mass distribution as
${\mathbf{x}}=(x_{1},1-x_{1})$ and costs, as a function of $x_{1}$, are:

$C_{1}({\mathbf{x}})=1+\frac{1}{4}(1-x_{1})=-\frac{1}{4}x_{1}+\frac{5}{4}$

and

$C_{2}({\mathbf{x}})=1-x_{1}+b_{2}+\frac{1}{4}x_{1}=-\frac{3}{4}x_{1}+1+b_{2}.$

If $b_{2}\in[\frac{1}{4},\frac{3}{4}]$, costs intersect in
$2b_{2}-\frac{1}{2}$ and there are no other equilibria (see Figure 5). The
common value of both costs is then $\frac{11}{8}-\frac{b_{2}}{2}$, which grows
when $b_{2}$ decreases; it is also the social cost (utilitarian or
egalitarian) in this equilibrium. This means that a lower vertex-cost function
can lead to a worse equilibrium in the sense of both social costs.

$b_{2}=1/4$0$r=1$$x_{1}$cost1/215/4$C_{1}$$C_{2}$$b_{2}=1/2$0$r=1$$1/2$$x_{1}$cost3/419/85/43/2$C_{1}$$C_{2}$$b_{2}=3/4$0$r=1$$x_{1}$cost15/47/4$C_{2}$$C_{1}$
Figure 5: The costs and equilibria for three different values of $b_{2}$.

Note that for each mass distribution ${\mathbf{x}}$, social costs
${\mathcal{C}}_{u}({\mathbf{x}})$ and ${\mathcal{C}}_{e}({\mathbf{x}})$ always
decrease when we reduce $b_{2}$ or, more generally, vertex-cost functions;
here, what increases when we reduce $b_{2}$ is the social cost of the unique
equilibrium. Also, note that we obtained this paradox in the simple context of
a symmetric affine NBG. In this case, a potential function with a unique
minimum exists (so it is not a protection against these paradoxes).

###  3.9 The Price of Anarchy

The concept of a price of anarchy (PoA) is a popular measure for the
inefficiency of equilibria in games. If there are multiple equilibria, we
consider the worst case and quantify the cost of this worst equilibrium
regarding the best configuration of the game, i.e. an optimal outcome where we
do not have the constraints of equilibria.

Let $Eq\subseteq\Delta_{r}(n)$ denote the set of equilibria of an NBG
$G=(n,r,C)$. We define the price of anarchy for the utilitarian social cost,
$PoA_{u}(G)$, as follows:

$PoA_{u}(G)=\frac{\displaystyle\max_{{\mathbf{x}}\in
Eq}{\mathcal{C}}_{u}({\mathbf{x}})}{\displaystyle\min_{{\mathbf{x}}\in\Delta_{r}(n)}{\mathcal{C}}_{u}({\mathbf{x}})},$
(4)

and $PoA_{e}(G)$ is defined likewise for the egalitarian social cost.
Unfortunately, the existence of several equilibria in NBGs leads to the price
of anarchy unbounded even in elementary classes of NBGs.

###### Proposition 3.10

The price of anarchy (with both social costs) is unbounded on normal
$\alpha$-uniform NBGs.

###### Proof 3.11

Consider the following example on two vertices, where $r=1$.

$1$$2$$\alpha_{1,2}=\alpha>1$$f_{1}(x_{1})=x_{1}$$f_{2}(x_{2})=x_{2}$

We can write both cost functions as functions of $x_{1}$ and obtain

$C_{1}(x_{1})=(1-\alpha)x_{1}+\alpha$

and

$C_{2}(x_{1})=(\alpha-1)x_{1}+1$

There are three equilibria:

  * •

in $x_{1}=0$ we have $C_{1}(0)=\alpha>1=C_{2}(0)$ ; the social cost is 1;

  * •

likewise in $x_{1}=1$, the social cost is 1 also. It is easy to see that this
is a global optimum for the social cost;

  * •

in $x_{1}=0.5$, we have $C_{1}(0.5)=C_{2}(0.5)=\frac{1+\alpha}{2}$, this
common value being the social cost.

Hence, we see in this example that the price of anarchy is
$\frac{1+\alpha}{2}$, but we can consider $\alpha$ as large as needed.

We could derive bounds on the price of anarchy in simple cases (for normal
linear NBGs, for instance) based on the size of the coefficients that appear.
But instead, we shall now focus on another measure, more suited to the case of
NBGs.

###  3.10 The Price of Stability

The price of stability (PoS) of the game, for the utilitarian social cost, is
defined as

$PoS_{u}(G)=\frac{\displaystyle\min_{{\mathbf{x}}\in
Eq}{\mathcal{C}}_{u}({\mathbf{x}})}{\displaystyle\min_{{\mathbf{x}}\in\Delta_{r}(n)}{\mathcal{C}}_{u}({\mathbf{x}})}.$
(5)

The price of stability of the egalitarian social cost, $PoS_{e}(G)$, is
defined similarly, using ${\mathcal{C}}_{e}$. The so-called stability
corresponds to the fact that we require the mass distribution to be an
equilibrium, hence stable concerning unilateral deviation of infinitesimal
players; hence the price of stability is a measure of the increase of global
social cost due to this stability.

Note that for both social costs, we have $PoA(G)\geq PoS(G)\geq 1$. It is also
easily noted that

$PoS_{e}(G)\leq PoS_{u}(G).$ (6)

We now give upper bounds on $PoS(G)$ in different cases.

###### Proposition 3.12

Let $\cal C$ be a class of vertex-cost functions and $0<\gamma\leq\frac{1}{2}$
such that, for all $f\in\cal C$, one has

$\int_{0}^{x}f(t)dt\geq\gamma xf(x).$

Then, the price of stability for all graphical symmetric NBGs with cost
functions in $\cal C$ is at most $\frac{1}{\gamma}$ for both social costs.

We prove the result for the utilitarian social cost, and the other case
follows from (6). To prove Proposition 3.12, we first prove the following
lemma.

###### Lemma 3.13

With $\gamma$ as defined in the previous Proposition, and for all mass
distributions ${\mathbf{x}}$ of a graphical symmetric NBG $G$ with potential
function $\Phi$ (as defined in Proposition 3.9), one has

$\gamma\cdot{\mathcal{C}}_{u}({\mathbf{x}})\leq\Phi({\mathbf{x}})\leq{\mathcal{C}}_{u}({\mathbf{x}}).$

###### Proof 3.14

In the case of a symmetric graphical game $(n,r,f,\alpha)$, the utilitarian
social cost is equal to:

${\mathcal{C}}_{u}({\mathbf{x}})=\sum_{i}x_{i}f_{i}(x_{i})+2\sum_{i<j}\alpha_{i,j}x_{i}x_{j}.$
(7)

Since vertex-cost functions $f_{i}$ are non-decreasing, the upper bound is
clear from (3) and (7). The lower bound comes from the definition of $\gamma$
and $\gamma\leq\frac{1}{2}$.

Proof of Proposition 3.12. Let ${\mathbf{x}}_{b}$ be a best equilibrium, i.e.
an equilibrium that minimizes the utilitarian social cost ${\mathcal{C}}_{u}$;
let ${\mathbf{x}}_{\phi}$ be a mass distribution that minimizes the potential
function $\Phi$, which is an equilibrium by Proposition 3.7, and let
${\mathbf{x}}^{*}$ be a mass distribution that minimizes ${\mathcal{C}}_{u}$,
so that
$PoS_{u}(G)=\frac{{\mathcal{C}}_{u}({\mathbf{x}}_{b})}{{\mathcal{C}}_{u}({\mathbf{x}}^{*})}$.
Then we have

$\displaystyle{\mathcal{C}}_{u}({\mathbf{x}}_{b})$
$\displaystyle\leq{\mathcal{C}}_{u}({\mathbf{x}}_{\phi})\hskip
28.45274pt\text{\small(since ${\mathbf{x}}_{b}$ minimizes ${\mathcal{C}}_{u}$
among equilibria)}$
$\displaystyle\leq\frac{1}{\gamma}\Phi({\mathbf{x}}_{\phi})\hskip
28.45274pt\text{\small(by Lemma \ref{lem:phiEncadre})}$
$\displaystyle\leq\frac{1}{\gamma}\Phi({\mathbf{x}}^{*})\hskip
28.45274pt\text{\small(by definition of ${\mathbf{x}}_{\phi}$)}$
$\displaystyle\leq\frac{1}{\gamma}{\mathcal{C}}_{u}({\mathbf{x}}^{*})\hskip
28.45274pt\text{\small(by Lemma \ref{lem:phiEncadre}), }$

hence

$PoS_{u}(G)\leq\frac{1}{\gamma}.$

$\QED$

Using the previous relation and Inequality (6), we can deduce that:

###### Corollary 3.15

On the class of polynomial functions with real nonnegative coefficients of
degree $d\geq 1$, both prices of stability are at most $d+1$.

For $d=0$, the price of stability is at most 1, hence equal to 1. For $d=1$
(the affine case), the price of stability is between $1$ and $2$, and we can
give a family of examples reaching asymptotically the bound $2$, see Figure 6.

0$r=1$$x_{1}$cost$\small 2+2\lambda$$\small 1+2\lambda$$\small
1+\lambda$$C_{1}$$C_{2}$ Figure 6: A family of graphical games reaching the
maximum price of stability of $2$ for affine vertex-cost functions. With $n=2$
and $r=1$, consider $\alpha_{1,2}=\alpha_{2,1}=1$, $f_{1}(x_{1})=1+2\lambda$
and $f_{2}(x_{2})=(2+\lambda)x_{2}+\lambda$. This gives
$C_{1}({\mathbf{x}})=2+2\lambda-x_{1}$ and
$C_{2}({\mathbf{x}})=2+2\lambda-(1+\lambda)x_{1}$. The only equilibrium of the
game has cost $2+2\lambda$, while the best utilitarian social cost is obtained
for $x_{1}=1$ and is equal to $1+2\lambda$ (this social cost is decreasing on
$[0,1]$ if $0<\lambda<1$). Thus, we can reach the bound of $2$ for $PoS(G)$ by
letting $\lambda$ go to $0$.

We can be more specific when all vertex-cost functions are linear: the
utilitarian social cost and the potential functions (as defined by Equations
(3) and (7)) are related by:

${\mathcal{C}}_{u}({\mathbf{x}})=2\Phi({\mathbf{x}}).$

Observe by Proposition 3.7 that there exists an equilibrium corresponding to
the minimum of $\Phi$. Since ${\mathcal{C}}_{u}$ and $\Phi$ are minimum on the
same mass distributions and using Inequality (6), we get

###### Corollary 3.16

On the class of linear functions with real nonnegative coefficients, both
prices of stability are $1$.

##  4 The $\alpha$-Uniform Graphical NBG for Some Graphs

This section considers that the underlying undirected graph can be path, cycle
and complete bipartite graph. From the example of the path, we derive the
embryo of an algorithm outputting an equilibrium, which could be adapted to
general graphs. Using the linearity of the cost functions, without loss of
generality, we can assume that the total mass is equal to $1$ ($r=1$).

We can observe that, in a $\alpha$-uniform NBG,

###### Rule 1

An equilibrium cannot have an uncharged vertex with only uncharged neighbours.

Indeed, the cost of an uncharged vertex with uncharged neighbours is zero, and
the mass distribution cannot be an equilibrium because the costs of vertices
are strictly positive.

###### Rule 2

An equilibrium cannot have one uncharged vertex with only one charged
neighbour, unless $\alpha\geq 1$.

Indeed, the cost of an uncharged vertex with only one charged neighbour is
less than that of the charged neighbour itself when $\alpha<1$, and the mass
distribution cannot be an equilibrium by definition.

###### Rule 3

If an equilibrium ${\mathbf{x}}$ has an uncharged vertex $i$ with $k$ charged
neighbours, then $\alpha\geq\frac{1}{k}$. If $\alpha=\frac{1}{k}$, then all
the neighbours of $i$ have the same mass, and none of them has charged
neighbours.

Indeed, suppose that vertex $i$ is not charged in ${\mathbf{x}}$. The
definition of equilibrium in $\alpha$-uniform NBGs implies these inequalities:
for any neighbour $j$ of $i$, $C_{j}({\mathbf{x}})\geq x_{j}$, and
$C_{i}({\mathbf{x}})=\alpha\sum_{\ell\in N[i]}x_{\ell}\geq
C_{j}({\mathbf{x}})$ . These inequalities are valid when
$\alpha\geq\frac{1}{k}$. If $\alpha=\frac{1}{k}$, then
$C_{i}({\mathbf{x}})=\frac{1}{k}\sum_{\ell\in N[i]}x_{\ell}\geq x_{j}$ for all
$j\in N[i]$, i.e., the average of the $k$ neighbours masses is at least the
mass of each neighbour, so all masses are equal. Moreover,
$C_{i}({\mathbf{x}})=C_{j}({\mathbf{x}})$ for all $j$, so no neighbour of $i$
can receive an additional cost from a neighbour.

###### Rule 4

Let $u$ and $v$ be two vertices having the same neighbourhood. If a mass
distribution ${\mathbf{x}}$ is an equilibrium, then $x_{u}=x_{v}$.

Indeed, if we let $N=\alpha\sum_{\ell\in N[u]}x_{\ell}=\alpha\sum_{\ell\in
N[v]}x_{\ell}$, then the definition of equilibrium in $\alpha$-uniform NBGs
implies the equalities $C_{u}({\mathbf{x}})=x_{u}+N$ and
$C_{v}({\mathbf{x}})=x_{v}+N$. Then $x_{u}\neq x_{v}$, say $x_{u}>x_{v}$,
implies that $C_{u}({\mathbf{x}})>C_{v}({\mathbf{x}})$, so $x_{u}$ is
uncharged, contradicting $x_{u}>x_{v}$.

###  4.1 The Case When the Underlying Graph is a Path

In this subsection, we consider the $\alpha$-uniform case for different values
of $\alpha$, in a quite simple graph: the path with $n$ vertices, $P_{n}$.

Paths are seemingly harder to deal with than cycles; even in the uniform case,
they provide different interesting cases: for instance, for given $n$ and
$\alpha$, one may have infinitely many equilibria. In the following, we do not
necessarily provide the complete computations.

First, we can look for equilibria ${\mathbf{x}}=(x_{1},\ldots,x_{n})$ where
all vertices are charged or, if uncharged, have the same cost as charged
vertices. We shall call such equilibria uniform-cost or simply uniform. Hence:

$\forall i,j\in V,\quad C_{i}({\mathbf{x}})=C_{j}({\mathbf{x}}).$

Let $c$ denote this common cost. To calculate this type of equilibrium, we
shall consider it as a solution to the system of equations (8) below. This
allows having a system of equalities rather than inequalities; on the other
hand, there are more unknowns. The first three equations represent the fact
that the costs of the vertices are identical: the first and the third
correspond to the vertices $1$ and $n$. The fourth one corresponds to the
constraint that the total mass equals $1$.

We then have:

$\displaystyle x_{1}+\alpha x_{2}$ $\displaystyle=c$ (8)
$\displaystyle\forall\,1<i<n,\;\;\alpha x_{i-1}+x_{i}+\alpha x_{i+1}$
$\displaystyle=c$ $\displaystyle\alpha x_{n-1}+x_{n}$ $\displaystyle=c$
$\displaystyle\sum_{i\in[n]}x_{i}$ $\displaystyle=1$
$\displaystyle\forall\,1\leq i\leq n,\;\;x_{i}$ $\displaystyle\geq 0.$

If we denote $M_{n,\alpha}$ the $(n+1)\times(n+1)$ matrix

$\begin{pmatrix}1&\alpha&&&&&&-1\\\ \alpha&1&\alpha&&&&&-1\\\
&\ddots&\ddots&\ddots&&&&-1\\\ &&\alpha&1&\alpha&&&-1\\\
&&&\ddots&\ddots&\ddots&&-1\\\ &&&&&\alpha&1&-1\\\ 1&1&\cdots&1&1&1&1&0\\\
\end{pmatrix},$

where all blank entries are $0$, a solution of System (8) above gives in
particular a solution to the linear system

$M_{n,\alpha}\cdot(x,c)=\begin{pmatrix}0\\\ 0\\\ \vdots\\\ 0\\\ 1\\\
\end{pmatrix},$ (9)

which will help us to find an equilibrium in $P_{n}$ (we know that there
exists at least one). The same is true for cycles, with only a slight
modification of the matrix (see Section 4.2).

The solutions corresponding to uniform-cost equilibria depend on the
determinant of matrix $M_{n,\alpha}$ and thus also on the value of $\alpha$.

##### Case when $n=2$.

We have $det(M_{2,\alpha})=-2\alpha+2.$

For $\alpha=1$, we have $det(M_{2,\alpha})=0$ and any mass distribution is a
uniform-cost equilibrium. For $\alpha\neq 1$, we have at most one uniform-cost
equilibrium. For reasons of symmetry this equilibrium is
$(\frac{1}{2},\frac{1}{2})$.

##### Case when $n=3$.

By computation, we get $det(M_{3,\alpha})=-4\alpha+3.$ Hence, using the same
argument as previously, there is at most one uniform-cost equilibrium for
$\alpha\neq\frac{3}{4}$. By computation, this equilibrium would be

${\mathbf{x}}_{0}^{*}=\left(\frac{\alpha-1}{4\alpha-3},\frac{2\alpha-1}{4\alpha-3},\frac{\alpha-1}{4\alpha-3}\right).$

For this to be an equilibrium, its entries must be nonnegative, which is the
case if and only if $0\leq\alpha\leq\frac{1}{2}$ or $\alpha\geq 1$.

For $\alpha=\frac{3}{4}$, System (9) has no solution. Hence, there is no
uniform-cost equilibrium. We can look for non-uniform equilibria (with at
least one uncharged vertex). Two cases are possible:

  * •

if the middle vertex $2$ is uncharged, then the only equilibrium must be
${\mathbf{x}}_{1}^{*}=(\frac{1}{2},0,\frac{1}{2})$, and this is a valid
equilibrium only if $\alpha\geq\frac{1}{2}$.

  * •

there is no equilibrium where vertex $1$ or $3$ is uncharged, say $x_{1}=0$,
$x_{2}>0$, $x_{3}>0$, since the cost in vertex $1$ would be less than the cost
in vertex $3$. The equilibrium ${\mathbf{x}}_{2}^{*}=(0,1,0)$ is possible only
if $\alpha\geq 1$.

So, to sum up, there are three equilibria, ${\mathbf{x}}_{0}^{*}$,
${\mathbf{x}}_{1}^{*}$ and ${\mathbf{x}}_{2}^{*}$ if $\alpha>1$. Otherwise, if
$\alpha=1$, there are two equilibria,
${\mathbf{x}}_{2}^{*}\;(={\mathbf{x}}_{0}^{*})$ and ${\mathbf{x}}_{1}^{*}$. If
$1>\alpha>\frac{1}{2}$, then ${\mathbf{x}}_{1}^{*}$ is the only equilibrium.
If $\alpha=\frac{1}{2}$, the only equilibrium is
${\mathbf{x}}_{1}^{*}\;(={\mathbf{x}}_{0}^{*})$. And if
$\frac{1}{2}>\alpha\geq 0$, then ${\mathbf{x}}_{0}^{*}$ is the only
equilibrium.

#####  Case when $n=4$:

We have $det(M_{4,\alpha})=2(\alpha^{2}+\alpha-1)(\alpha-2)$, whose
nonnegative roots are $2$ and $\phi=\frac{\sqrt{5}-1}{2}\approx 0.618$.

Hence, if $\alpha\neq 2$ and $\alpha\neq\phi$, we have at most one uniform-
cost equilibrium. The solution to System (9) is then
$x_{1}=x_{4}=\frac{1}{4-2\alpha}$, $x_{2}=x_{3}=\frac{1-\alpha}{4-2\alpha}$,
which yields nonnegative values, i.e., a uniform equilibrium when
$0\leq\alpha\leq 1$. As mentioned above, a search for non-uniform equilibria
can be easily done, but we prefer to focus on the case $\alpha=\phi$ because
it leads to infinitely many equilibria. First, any quadruple
$(x_{1},x_{2},x_{3},x_{4})$ such that

$x_{1}+x_{4}=\frac{1}{2-\phi}\approx 0.724,$ (10)
$x_{2}=\frac{-\phi}{2-\phi}+x_{4}(1+\phi)\approx-0.447+1.618\,x_{4},$ (11)
$x_{3}=\frac{1}{2-\phi}-x_{4}(1+\phi)\approx 0.724-1.618\,x_{4}$ (12)

is a solution to System (9). The nonnegativity condition then implies that
$x_{4}\in\;[\frac{\phi}{(\phi+1)(2-\phi)},$ $\frac{1}{(\phi+1)(2-\phi)}]$,
i.e. $\approx 0.276\leq x_{4}\leq\approx 0.447$; then any triple
$(x_{1},x_{2},x_{3})$ verifying (10)–(12) gives, together with $x_{4}$, a
uniform equilibrium. All these solutions have the same cost, namely
$\frac{1-\phi^{2}}{2-\phi}\approx 0.447$.

#####  Case when $n=5$:

We obtain $det(M_{5,\alpha})=(\alpha+1)(\alpha-1)(\alpha^{2}+8\alpha-5),$
whose nonnegative roots are $1$ and $\phi=\sqrt{21}-4\approx 0.583$.

Calculations show that there is no solution to System (9) when $\alpha=\phi$,
implying that there is no uniform equilibrium. More calculations lead to the
following results for $\alpha\in[0,1]$:

  * •

if $0\leq\alpha\leq\frac{1}{2}$, there is a unique solution: a uniform
equilibrium.

  * •

if $\frac{1}{2}\leq\alpha<1$, then
${\mathbf{x}}_{0}^{*}=(\frac{1}{3},0,\frac{1}{3},0,\frac{1}{3})$ is the only
equilibrium, and it is non-uniform unless $\alpha=\frac{1}{2}$.

  * •

if $\alpha=1$, ${\mathbf{x}}_{0}^{*}$ is an equilibrium, and any 5-tuple
$(x_{1},x_{2},0,x_{4},x_{5})$ such that $x_{1}+x_{2}=x_{4}+x_{5}=\frac{1}{2}$
and $x_{2}+x_{4}\geq\frac{1}{2}$ (e.g.,
$(\frac{1}{8},\frac{3}{8},0,\frac{1}{4},\frac{1}{4})$) is a non-uniform
equilibrium, except the distributions $(x_{1},x_{2},0,x_{1},x_{2})$, which are
uniform, with cost $x_{1}+x_{2}=\frac{1}{2}$.

##### General case:

We observe that the four previous determinants, $det(M_{2,\alpha})$,
$det(M_{3,\alpha})$, $det(M_{4,\alpha})$, $det(M_{5,\alpha})$, show no
regularity, and it looks hard to find a general form for them, for their
roots, and for the solutions to System (9).

The first three Rules given above have the following implications when the
graph is a path.

Rule 1 implies that an equilibrium cannot have three or more consecutive
uncharged vertices. Rule 2 implies that an equilibrium cannot have two
consecutive uncharged vertices unless $\alpha\geq 1$. Rule 3 implies that no
equilibrium has uncharged vertices when $0\leq\alpha<\frac{1}{2}$.

Because such a game has at least one equilibrium by Theorem 3.1, we have that

  * •

either $det(M_{n,\alpha})\neq 0$: the unique solution to System (9) is
nonnegative;

  * •

or $det(M_{n,\alpha})=0$: among the solutions to System (9), at least one is
nonnegative.

From these three Rules and the above results on small values of $n$, we can
conjecture that:

###### Conjecture 1

For $n\geq 2$ and $\alpha<\frac{1}{2}$, we have $det(M_{n,\alpha})\neq 0$;
therefore, there is a unique equilibrium (which has a uniform cost) in
$P_{n}$.

###### Example 4.1

In path $P_{6}$ with $\alpha=\frac{1}{4}$, the unique equilibrium is
$\frac{1}{76}(15,11,12,12,11,15)$, with cost $\frac{71}{304}\approx.23$; for
$\alpha=\frac{1}{3}$, it is $\frac{1}{38}(8,5,6,6,5,8)$, with cost
$\frac{29}{114}\approx.25$. In $P_{7}$ with $\alpha=\frac{1}{4}$, it is
$\frac{1}{240}(41,30,33,32,33,30,41)$, with cost $\frac{97}{480}\approx.20$;
and for $\alpha=\frac{1}{3}$, it is $\frac{1}{71}(13,8,10,9,10,8,13)$, with
cost $\frac{47}{213}\approx.22$.

The above rules lead to a starting point for an algorithm finding an
equilibrium in a path with $n$ vertices, which, however, has too high a worst-
case complexity due to Step $2$:

  * •

Step $1$: compute $det(M_{n,\alpha})$.

(a) if $det(M_{n,\alpha})\neq 0$, there is a unique solution to System (9).

    * –

if the solution is nonnegative, we have a uniform equilibrium. We know that
this is always the case if $\alpha<\frac{1}{2}$.

    * –

if the solution is negative, we must search for non-uniform equilibria (see
Step 2).

(b) if $det(M_{n,\alpha})=0$, either there is no solution to System (9), or
infinitely many. In the latter case, if some of these solutions are
nonnegative, we have obtained uniform equilibria (see the example when $n=4$).
Otherwise, we are back to the search for non-uniform equilibria.

  * •

Step $2$: search for a non-uniform equilibrium: try with uncharged vertices,
respecting Rules 1 and 2 above (Rule 3 is respected because we are in a case
when no uniform equilibrium has been found).

This sketch of an algorithm can be adapted to general graphs, with
modification of the determinant. Note that uncharged vertices mean fewer
unknowns but induce inequalities on the costs instead of equalities.

Now, we restrict ourselves to the cases $\alpha=\frac{1}{2}$ and $\alpha=1$,
the study of general $\alpha$ being seemingly out of reach. We recall
Conjecture 1 when $\alpha<\frac{1}{2}$.

##### General case for $\alpha=\frac{1}{2}$.

Both ends of the path must be charged. Rule 3 above shows that if there is one
uncharged vertex $x_{i}=0$, then $x_{i-1}=x_{i+1}$, and either the vertex
$i-1$ or $i+1$ is an end, or $x_{i-2}=x_{i+2}=0$; similarly,
$x_{i-3}=x_{i+3}=x_{i-1}$, and so on. There are two cases.

If $n$ is odd, then
$(\frac{2}{n+1},0,\frac{2}{n+1},0,\frac{2}{n+1},\ldots,0,\frac{2}{n+1})$ is
the only equilibrium, with uniform cost equal to $\frac{2}{n+1}$.

If $n$ is even, $n=2q$, then all vertices are charged, and the only
equilibrium is given by

$\displaystyle x_{2k}=kx_{2},\;1\leq k\leq q$ $\displaystyle
x_{2k+1}=x_{1}-kx_{2},\;0\leq k\leq q-1$ $\displaystyle x_{1}=\frac{1}{q+1}$
$\displaystyle x_{2}=\frac{1}{q(q+1)},$

with uniform cost equal to $\frac{2q+1}{2q(q+1)}$. For instance, the
equilibrium for $n=10$ is

$(\frac{1}{6},\frac{1}{30},\frac{2}{15},\frac{1}{15},\frac{1}{10},\frac{1}{10},\frac{1}{15},\frac{2}{15},\frac{1}{30},\frac{1}{6})=\frac{1}{30}(5,1,4,2,3,3,2,4,1,5);$

its uniform cost is $\frac{11}{60}$. Observe that the odd positions are
$5,4,3,2,1$ and the even positions are $1,2,3,4,5$.

##### General case for $\alpha=1$.

###### Remark 4.2

Let ${\mathbf{x}}=(x_{1},\dots,x_{n})$ be an equilibrium. When $\alpha=1$, a
simple observation is that (in paths as well as in cycles) if $x_{i}=0$,
$x_{i+1}>0$ and $x_{i+2}>0$, then $x_{i+3}=0$.

The search for uniform-cost solutions is straightforward (no need to compute
the determinant) and divides into three cases.

  * •

If $n=3k+2$, there is a simple infinity of solutions
$(x_{1},x_{2},0,x_{1},x_{2},0,\ldots,x_{1},x_{2},0,x_{1},x_{2})$, with
$x_{1}\geq 0$, $x_{2}\geq 0$, and $x_{1}+x_{2}=\frac{3}{n+1}$. This includes
$(\frac{3}{n+1},0,0,\frac{3}{n+1},0,0,\ldots,\frac{3}{n+1},0)$ and its
symmetric $(0,\frac{3}{n+1},0,0,\frac{3}{n+1},0,\ldots,0,\frac{3}{n+1})$. The
cost for all vertices is $x_{1}+x_{2}=\frac{3}{n+1}$. We can see that this
means that $\alpha-1$ divides $det(M_{n,\alpha})$.

  * •

When $n=3k+1$ or $n=3k$, there is a unique solution, respectively
$(\frac{3}{n+2},0,0,\frac{3}{n+2},0,0,\ldots,\frac{3}{n+2})$ or
$(0,\frac{3}{n},0,0,\frac{3}{n},0,\ldots,0,\frac{3}{n},0)$, which means that
in both cases $det(M_{n,1})\neq 0$.

Still for $\alpha=1$, the study of non-uniform-cost equilibria is similar to
that for cycles. See below.

###  4.2 The Case When the Underlying Graph is a Cycle

We apply here the same argument as for paths: we build a new matrix

$M^{*}_{n,\alpha}=\begin{pmatrix}1&\alpha&&&&&\alpha&-1\\\
\alpha&1&\alpha&&&&&-1\\\ &\ddots&\ddots&\ddots&&&&-1\\\
&&\alpha&1&\alpha&&&-1\\\ &&&\ddots&\ddots&\ddots&&-1\\\
\alpha&&&&&\alpha&1&-1\\\ 1&1&\cdots&1&1&1&1&0\\\ \end{pmatrix}$

and its corresponding linear system (9${}^{*}).$

Cycles and their determinants are more regular than paths, but no general
pattern has been found for their determinants, roots, or solutions to
(9${}^{*})$.

Rules 1, 2 and 3, as well as the sketch of the algorithm above, can be adapted
to cycles. Conjecture 1 becomes:

###### Conjecture 2

For $n\geq 2$ and $\alpha<\frac{1}{2}$, we have $det(M^{*}_{n,\alpha})\neq 0$;
therefore there is a unique equilibrium (which has a uniform cost) in $C_{n}$.

Unlike what happens for paths, we can observe that in $C_{n}$, the mass
distribution described by $x_{i}=\frac{1}{n}$, $1\leq i\leq n$, is always a
uniform-cost equilibrium. We sketch some results for $\alpha=\frac{1}{2}$ and
$\alpha=1$.

##### General case for $\alpha=\frac{1}{2}$.

There is a simple infinity of equilibria with uniform cost when $n$ is even,
given by $(x_{1},x_{2},\ldots,x_{1},x_{2})$, with $x_{1}\geq 0$, $x_{2}\geq
0$, $x_{1}+x_{2}=\frac{2}{n}$. This includes
$(0,\frac{2}{n},\ldots,0,\frac{2}{n})$ and $(\frac{1}{n},\ldots,\frac{1}{n})$.
The cost of each vertex is $x_{1}+x_{2}=\frac{2}{n}$. When $n$ is odd, the
unique solution is with $x_{i}=\frac{1}{n}$.

##### General case for $\alpha=1$.

As for paths, it is straightforward to see that:

– If $n=3k$, there is a double infinity of solutions,
$(x_{1},x_{2},x_{3},\ldots,x_{1},x_{2},x_{3})$, with $x_{1}\geq 0$, $x_{2}\geq
0$, $x_{3}\geq 0$ and $x_{1}+x_{2}+x_{3}=\frac{3}{n}$. This means that
$(\alpha-1)^{2}$ divides $det(M^{*}_{n,\alpha})$.

– If $n=3k+1$ or $3k+2$, the only solution is with $x_{i}=\frac{1}{n}$.

Using Remark 4.2, one can see that non-uniform solutions are combinations of
configurations of the type

$(\ldots 0,x,0,0,x,0,x,0,ax,(1-a)x,0,bx,(1-b)x,0,\ldots),$

with $0<a<1$, $a\leq b<1$, and the sum of charges equal to $1$.

###  4.3 The Case When the Underlying Graph is a Complete Bipartite Graph

We consider the complete bipartite graph $K_{p,q}$ with $p+q=n$, $p\geq q$,
and a mass distribution
${\mathbf{x}}=(x_{1},\ldots,x_{p},x_{p+1},\dots,x_{p+q})$ with $r=1$.

Using Rule 4 given above, we have $x_{i}=x_{j}$ for $1\leq i<j\leq p$ and
$x_{k}=x_{\ell}$ for $p+1\leq k<\ell\leq p+q$. Let $a=x_{1}$ and $b=x_{p+1}$.

We start with the search for equilibria with uncharged vertices. We may assume
that either $a=0$ (and $b=\frac{1}{q}$) or $b=0$ (and $a=\frac{1}{p}$). We can
apply Rule 3 to determine when the equilibrium exists according to the value
$\alpha$. In the former case, the equilibrium with $a=0$ exists when
$\alpha\geq\frac{1}{q}$. Similarly in the latter case, the equilibrium with
$b=0$ exists when $\alpha\geq\frac{1}{p}$.

We see that if none of these two conditions on $\alpha$ is fulfilled, i.e.,
$\alpha<\frac{1}{p}$, then, since an equilibrium always exists, we must have a
uniform equilibrium with no uncharged vertices.

Now we search for a uniform equilibrium with no uncharged vertices. By
definition, we have $a+\alpha qb=b+\alpha pa$, i.e., $a(1-\alpha p)=b(1-\alpha
q)$, and $pa+qb=r=1$. Since $a\neq 0$ and $b\neq 0$, we can consider two
cases: (i) $1-\alpha p=1-\alpha q=0$, (ii) both $1-\alpha p$ and $1-\alpha q$
are nonzero.

(i) If $1-\alpha p=1-\alpha q=0$, then $p=q$ and the only condition remaining
is $a+b=\frac{1}{p}\,$: there is an infinity of equilibria, given by
$(a,b)=(a,\frac{1}{p}-a)$, $0\leq a\leq\frac{1}{p}$, and the common cost is
$\frac{1}{p}$.

(ii) If both $1-\alpha p$ and $1-\alpha q$ are nonzero, then
$a=b\frac{1-\alpha q}{1-\alpha p}$.

(1) $\frac{1}{p}<\alpha<\frac{1}{q}$. Then $a$ and $b$ have different signs,
and no uniform equilibrium with no uncharged vertices exists.

(2) $\alpha<\frac{1}{p}$ or $\alpha>\frac{1}{q}$. If $p+q-2\alpha pq$ has the
same sign as $1-\alpha p$ and $1-\alpha q$, then

$a=\frac{1-\alpha q}{p+q-2\alpha pq},\;b=\frac{1-\alpha p}{p+q-2\alpha pq}$

gives the only uniform equilibrium, with common cost
$\frac{1-\alpha^{2}pq}{p+q-2\alpha pq}$. Otherwise, we have to search for a
non-uniform equilibrium.

Note that the case $p=q=1$ gives the path $P_{2}$, $p=q=2$ gives the cycle
$C_{4}$, and $q=1$ gives the star, see below.

##### Particular case of the star.

The graph now is $K_{n-1,1}$.

(1) If $x_{n}=0$, i.e., only the center is uncharged, then
$x_{i}=\frac{1}{n-1}$, $1\leq i\leq n-1$, and necessarily
$\alpha\geq\frac{1}{n-1}$. In this case, we have an equilibrium, which is
uniform only for $\alpha=\frac{1}{n-1}$.

(2) If all leaves are uncharged, then $x_{n}=1$. This leads to an equilibrium
whenever $\alpha\geq 1$, and this equilibrium is uniform for $\alpha=1.$

(3) If there is no uncharged vertex, then $b(1-\alpha)=a(1-(n-1)\alpha)$ and
$b+(n-1)a=1$. If $\alpha=1$, then $a=0$ and $b=1$. If $\alpha=\frac{1}{n-1}$,
then $b=0$ and $a=\frac{1}{n-1}$. These are two uniform equilibria but with
uncharged vertices.

If $\alpha<1$ and $\alpha>\frac{1}{n-1}$, then $a$ and $b$ have opposite signs
and no uniform equilibrium exists.

If $\alpha>1$ or $\alpha<\frac{1}{n-1}$, then $a$ has the same sign as $b$. We
obtain $a=\frac{1-\alpha}{n-2\alpha(n-1)}$ and
$b=\frac{1-(n-1)\alpha}{n-2\alpha(n-1)}$. Both numbers are positive and yield
a uniform equilibrium.

Summarizing for the star: if $\alpha<\frac{1}{n-1}$, there is one uniform
equilibrium, with all vertices charged. For all $\alpha\geq\frac{1}{n-1}$,
there is one equilibrium with the centre uncharged, which is uniform for
$\alpha=\frac{1}{n-1}.$ If $\alpha=1$, there is one uniform equilibrium with
all uncharged leaves. If $\alpha>1$, there is one uniform equilibrium with all
charged vertices and one non-uniform equilibrium with all uncharged leaves.

## References

  * [1] Fidaa Abed, José R Correa, and Chien-Chung Huang.  Optimal coordination mechanisms for multi-job scheduling games.  In European Symposium on Algorithms, pages 13–24. Springer, 2014\.
  * [2] Ehsan Aryafar, Alireza Keshavarz-Haddad, Michael Wang, and Mung Chiang.  Rat selection games in hetnets.  In INFOCOM, 2013 Proceedings IEEE, pages 998–1006. IEEE, 2013.
  * [3] Baruch Awerbuch, Yossi Azar, Yossi Richter, and Dekel Tsur.  Tradeoffs in worst-case equilibria.  Theoretical Computer Science, 361(2-3):200–209, 2006.
  * [4] Sayan Bandyapadhyay, Aritra Banik, Sandip Das, and Hirak Sarkar.  Voronoi game on graphs.  Theoretical Computer Science, 562:270–282, 2015.
  * [5] Martin Beckmann, Charles B McGuire, and Christopher B Winsten.  Studies in the economics of transportation.  The Economic Journal, 67(265), 1957.
  * [6] Dietrich Braess.  Über ein paradoxon aus der verkehrsplanung.  Unternehmensforschung, 12:258–268, 1968.
  * [7] Ioannis Caragiannis, Michele Flammini, Christos Kaklamanis, Panagiotis Kanellopoulos, and Luca Moscardelli.  Tight bounds for selfish and greedy load balancing.  In Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I 33, pages 311–322. Springer, 2006.
  * [8] George Christodoulou and Martin Gairing.  Price of stability in polynomial congestion games.  ACM Transactions on Economics and Computation (TEAC), 4(2):1–17, 2015.
  * [9] George Christodoulou and Elias Koutsoupias.  On the price of anarchy and stability of correlated equilibria of linear congestion games.  In Algorithms–ESA 2005: 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings 13, pages 59–70. Springer, 2005.
  * [10] George Christodoulou, Elias Koutsoupias, and Akash Nanavati.  Coordination mechanisms.  In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP), pages 345–357, 2004.
  * [11] V Chvátal.  On the computational complexity of finding a kernel, report crm300.  Université de Montréal, Centre de Recherches Mathématiques, 1973.
  * [12] Riccardo Colini-Baldeschi, Roberto Cominetti, Panayotis Mertikopoulos, and Marco Scarsini.  When is selfish routing bad? the price of anarchy in light and heavy traffic.  Operations Research, 68(2):411–434, 2020.
  * [13] Riccardo Colini-Baldeschi, Roberto Cominetti, and Marco Scarsini.  On the price of anarchy of highly congested nonatomic network games.  In Algorithmic Game Theory: 9th International Symposium, SAGT 2016, Liverpool, UK, September 19–21, 2016, Proceedings 9, pages 117–128. Springer, 2016.
  * [14] José R Correa and Nicolás E Stier-Moses.  Wardrop equilibria.  Encyclopedia of Operations Research and Management Science. Wiley, 2011.
  * [15] Artur Czumaj and Berthold Vöcking.  Tight bounds for worst-case equilibria.  In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 413–420, 2002.
  * [16] Christoph Dürr and Nguyen Kim Thang.  Nash equilibria in voronoi games on graphs.  In European Symposium on Algorithms, pages 17–28. Springer, 2007\.
  * [17] Christoph Dürr and Nguyen Kim Thang.  Non-clairvoyant scheduling games.  In International Symposium on Algorithmic Game Theory, pages 135–146. Springer, 2009.
  * [18] Martin Gairing, Thomas Lücking, Marios Mavronicolas, and Burkhard Monien.  Computing Nash equilibria for scheduling on restricted parallel links.  In Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), pages 613–622, 2004.
  * [19] Michael R Garey and David S Johnson.  Computers and intractability, volume 174.  Freeman San Francisco, 1979.
  * [20] Nicole Immorlica, Li Li, Vahab S. Mirrokni, and Andreas Schulz.  Coordination mechanisms for selfish scheduling.  In Proceedings of the 1st International Workshop on Internet and Network Economics (WINE), pages 55–69, 2005.
  * [21] Elias Koutsoupias and Christos Papadimitriou.  Worst-case equilibria.  In Annual Symposium on Theoretical Aspects of Computer Science, pages 404–413. Springer, 1999.
  * [22] Samson Lasaulce and Hamidou Tembine.  Game theory and learning for wireless networks: fundamentals and applications.  Academic Press, 2011.
  * [23] John F Nash Jr.  Equilibrium points in n-person games.  Proceedings of the national academy of sciences, 36(1):48–49, 1950\.
  * [24] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani.  Algorithmic game theory, volume 1.  Cambridge University Press Cambridge, 2007.
  * [25] Robert W Rosenthal.  A class of games possessing pure-strategy nash equilibria.  International Journal of Game Theory, 2:65–67, 1973.
  * [26] Tim Roughgarden.  The price of anarchy is independent of the network topology.  In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 428–437, 2002.
  * [27] Tim Roughgarden.  Intrinsic robustness of the price of anarchy.  Journal of the ACM (JACM), 62(5):32, 2015.
  * [28] Tim Roughgarden and Éva Tardos.  How bad is selfish routing?  Journal of the ACM (JACM), 49(2):236–259, 2002.
  * [29] Andreas S Schulz and Nicolás E Stier Moses.  On the performance of user equilibria in traffic networks.  In SODA, volume 3, pages 86–87, 2003.
  * [30] Petra Schuurman and Tjark Vredeveld.  Performance guarantees of local search for multiprocessor scheduling.  Informs Journal on Computing, 361(1):52–63, 2007.
  * [31] Sachio Teramoto, Erik D Demaine, and Ryuhei Uehara.  Voronoi game on graphs and its complexity.  In 2006 IEEE Symposium on Computational Intelligence and Games, pages 265–271. IEEE, 2006.
  * [32] Nguyen Kim Thang.  $\mathcal{NP}$-hardness of pure Nash equilibrium in Scheduling and Connection Games.  In Proceedings of the 35th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), pages 413–424, 2009\.
  * [33] Adrian Vetta.  Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions.  In Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on, pages 416–425. IEEE, 2002.
  * [34] John Glen Wardrop.  Road paper. some theoretical aspects of road traffic research.  Proceedings of the institution of civil engineers, 1(3):325–362, 1952.
  * [35] Zijun Wu, Rolf H Möhring, Yanyan Chen, and Dachuan Xu.  Selfishness need not be bad.  Operations Research, 69(2):410–435, 2021.