# Pure Nash Equilibria in Weighted Congestion Games with Complementarities and
Beyond††thanks: An extended abstract of this paper [25] appears in the
Proceedings of the 23rd International Conference on Autonomous Agents and
Multiagent Systems (AAMAS 2024).

Kenjiro Takazawa Department of Industrial and Systems Engineering, Faculty of
Science and Engineering, Hosei University, Tokyo 184-8584, Japan.
<EMAIL_ADDRESS>Partially supported by JSPS KAKENHI Grant Number
JP20K11699, Japan.

(January 2024)

###### Abstract

Congestion games offer a primary model in the study of pure Nash equilibria in
non-cooperative games, and a number of generalized models have been proposed
in the literature. One line of generalization includes weighted congestion
games, in which the cost of a resource is a function of the total weight of
the players choosing that resource. Another line includes congestion games
with mixed costs, in which the cost imposed on a player is a convex
combination of the total cost and the maximum cost of the resources in her
strategy. This model is further generalized to that of congestion games with
complementarities. For the above models, the existence of a pure Nash
equilibrium is proved under some assumptions, including that the strategy
space of each player is the base family of a matroid and that the cost
functions have a certain kind of monotonicity. In this paper, we deal with
common generalizations of these two lines, namely weighted matroid congestion
games with complementarities, and its further generalization. Our main
technical contribution is a proof of the existence of pure Nash equilibria in
these generalized models under a simplified assumption on the monotonicity,
which provide a common extension of the previous results. We also present some
extensions on the existence of pure Nash equilibria in player-specific and
weighted matroid congestion games with mixed costs.

Keywords

Non-Cooperative Game Theory; Pure Nash Equilibrium; Congestion Game; Matroid

##  1 Introduction

The analysis of the existence of pure Nash equilibria in non-cooperative games
is a central topic in algorithmic game theory [19, 22], and the model of
_congestion games_ [4] play an important role in this topic. A congestion game
models the human behavior of selecting the best strategy in a situation where
congestion results in a larger cost. In a congestion game, each strategy is a
set of _resources_. The cost of a resource is represented by a function of the
number of the players using it. The entire cost imposed on a player is the sum
of the costs of the resources in her strategy. For a formal description of
congestion games, see Section 2.2.

The most important feature of congestion games is that every congestion game
is a _potential game_ , which implies that every congestion game has a pure
Nash equilibrium [21]. Further, the converse is also true: every potential
game is represented by a congestion game [17]. Since those primary results, a
number of generalized models of congestion games have been proposed. As is
mentioned below, however, a pure Nash equilibrium may not exist in those
generalized models, and its existence is proved under certain assumptions. The
purpose of this paper is to provide a model commonly generalizing previous
models, while preserving the existence of a pure Nash equilibrium.

###  1.1 Previous Work

In this section, we describe two major directions of generalizations of
congestion games.

####  1.1.1 Weighted and Player-Specific Congestion Games

In a main direction of the study of congestion games, the cost functions of
the resources are generalized. One model in this direction is a _weighted
congestion game_ : each player has a nonnegative weight; and the cost of a
resource is a function of the total weight of the players using it. Another
model is a _player-specific congestion game_ , in which the resources have a
cost function specific to each player.

Both of the weighted and player-specific congestion games do not have a pure
Nash equilibrium in general, but are guaranteed to possess one under certain
assumptions. A congestion game is referred to as a _singleton game_ if every
strategy of every player consists of a single resource, and as a _matroid
game_ if the strategy space of each player is a base family of a matroid; see
Section 2.1 for the definition of matroids. Milchtaich [16] proved that every
singleton player-specific congestion game has a pure Nash equilibrium.
Ackermann, Röglin, and Vöcking [1] extended this result to matroid congestion
games, i.e., every player-specific matroid congestion game has a pure Nash
equilibrium. A further generalized model on polymatroids is studied by Harks,
Klimm, and Peis [12]. Ackermann, Röglin, and Vöcking [1] also proved that
every weighted matroid congestion game have a pure Nash equilibrium, and this
result is extended to a further generalized model of a _matroid congestion
game with set-functional costs_ by Takazawa [24]. Some of these results are
explained in detail in Section 2.3.

####  1.1.2 Congestion Games with Bottleneck Costs, Mixed Costs, and
Complementarities

In another major direction of generalization, the cost imposed on a player is
not simply defined as the sum of the costs of the resources in the strategy. A
typical model is a _bottleneck congestion game_ , in which the cost on a
player is defined as the maximum cost of the resources in her strategy. Banner
and Orda [3] proved the existence of pure Nash equilibria and analyzed the
price of anarchy in certain kinds of network bottleneck congestion games, in
which a strategy of a player is a flow in a given network.

Harks, Klimm, and Möhring [11] introduced a generalized class of _congestion
games with lexicographical improvement property_. They proved that every
bottleneck congestion game belongs to this class, and that every congestion
game in this class possesses a _strong equilibrium_ [2], a stronger concept of
a pure Nash equilibrium. Harks, Hoefer, Klimm, and Skopalik [10] analyzed the
complexity of finding a strong equilibrium in bottleneck congestion games. In
particular, they presented polynomial-time algorithms for several classes of
bottleneck congestion games, including matroid bottleneck congestion games.

Feldotto, Leder, and Skopalik [9] proposed a common generalization of
classical congestion games and bottleneck congestion games, called _congestion
games with mixed costs_. In this model, the cost imposed on a player is a
convex combination of the total cost and the maximum cost of the resources in
her strategy; see Section 2.4 for detailed description. For this model, a
matroid game may fail to possess a pure Nash equilibrium. Feldotto, Leder, and
Skopalik [9] proved the existence of pure Nash equilibria in certain classes
of this model, including singleton games, and matroid games with some more
property (Theorem 2.7 below).

Feldotto, Leder, Skopalik [8] introduced a further generalized model,
_congestion games with complementarities_. In this model, the cost imposed on
a player is determined by an _aggregation function_ , which a general function
of the costs of the resources in the strategy. A typical example of an
aggregation function is the $L^{p}$ norm of the costs of the resources. A
detailed description of this model appears in Section 2.4. For this model,
Feldotto, Leder, Skopalik [8] proved the existence of a pure Nash equilibrium
in matroid games under an assumption on the monotonicity of the aggregation
function, which is defined in a sophisticated manner (Theorem 2.8 below).
Related work dealing with aggregation cost functions also appears in [14, 15].

###  1.2 Our Contribution

The aim of this paper is to offer a model of congestion games which commonly
generalizes the previous models in the two directions mentioned in Section
1.1. In particular, we provide a generalized model preserving the existence of
pure Nash equilibria in matroid games.

Our main contribution is a common extension of the existence of pure Nash
equilibria in weighted congestion games and congestion games with
complementarities. Namely, our model is _weighted congestion games with
complementarities_ , and its further generalization of _congestion games with
set-functional costs and complementarities_. On the basis of the previous
results [1, 8, 24], we prove that every game in this model has a pure Nash
equilibrium if it is a matroid game and the aggregation function has a certain
monotonicity (see Theorem 3.3 below). This class includes weighted matroid
bottleneck congestion games and weighted congestion games with
$L^{p}$-aggregation functions. Thus, our result implies the guaranteed
existence of pure Nash equilibria in these models (Corollaries 3.4 and 3.5
below). We remark here that the definition of the monotonicity of the
aggregation functions in our model is simpler than that in the previous work
[8], which provides a simpler proof for the existence of pure Nash equilibria
and a clearer comprehension of the model.

We also generalize the model of congestion games with mixed costs to those
with player-specific cost functions and set-functional cost functions. For
these models, we extend the result of Feldotto, Leder, and Skopalik [9] to
prove the existence of pure Nash equilibria under the same assumptions.

###  1.3 Organization of the Paper

The rest of the paper is organized as follows. In Section 2, we give a
detailed description of the previous models. In Section 3, we present our main
contribution: the generalized model of congestion games with set-functional
costs and complementarities; a simplified definition of the monotonicity of
the aggregation functions; and a proof of the existence of pure Nash
equilibria in matroid games with a monotone aggregation function. Finally, in
Section 4, we deal with generalizations of congestion games with mixed costs.

##  2 Preliminaries

In this section, we present some basic properties of matroids, followed by
descriptions of classical and recent generalized models of congestion games.

###  2.1 Matroids

Let $E$ be a finite set and $\mathcal{S}\subseteq 2^{E}$ its subset family.
The pair $(E,\mathcal{S})$ is a _matroid_ if $\mathcal{S}\neq\emptyset$ and it
satisfies the following exchange axiom:

(EX)

for $S,S^{\prime}\in\mathcal{S}$ and for $e\in S\setminus S^{\prime}$, there
exists $f\in S^{\prime}\setminus S$ such that
$(S\setminus\\{e\\})\cup\\{f\\}\in\mathcal{S}$.

The subset family $\mathcal{S}$ is called the _base family_ , and a set
$S\subseteq E$ belonging to $\mathcal{S}$ is called a _base_ of the matroid
$(E,\mathcal{S})$. It is noteworthy that all bases have the same cardinality,
i.e., $|S|=|S^{\prime}|$ for each $S,S^{\prime}\in\mathcal{S}$ for every
matroid $(E,\mathcal{S})$.

Optimization over matroids has formed an extensive research field in
combinatorial optimization, due to its nice structure and wide range of
application (see, e.g., [18, 20, 23]). Below we show some properties of
matroids, which will be used in subsequent sections.

First, the one-sided exchange axiom (EX) is equivalent to the following
stronger two-sided exchange property.

######  Lemma 2.1 ([5]).

Every matroid $(E,\mathcal{S})$ has the following simultaneous exchange
property:

($\mbox{EX}\pm$)

for $S,S^{\prime}\in\mathcal{S}$ and for $e\in S\setminus S^{\prime}$, there
exists $f\in S^{\prime}\setminus S$ such that
$(S\setminus\\{e\\})\cup\\{f\\}\in\mathcal{S}$ and
$(S^{\prime}\setminus\\{f\\})\cup\\{e\\}\in\mathcal{S}$.

The next lemma is derived from the exchange axiom (EX) and will be used in the
analysis of congestion games with mixed costs.

######  Lemma 2.2.

Let $(E,\mathcal{S})$ be a matroid and let $c_{e}\in{\mathbb{R}}$ denote the
cost of an element $e\in E$. Then, a base $S\in\mathcal{S}$ minimizing the
total cost $\sum_{e\in S}c_{e}$ among all bases in $\mathcal{S}$ also
minimizes the maximum cost $\max_{e\in S}\\{c_{e}\\}$ among all bases in
$\mathcal{S}$.

###### Proof.

Let a base $S_{1}\in\mathcal{S}$ minimize $\sum_{e\in S}c_{e}$ among all
bases. Suppose to the contrary that $S_{1}$ does not minimize $\max_{e\in
S}\\{c_{e}\\}$, i.e., there exists another base $S_{2}\in\mathcal{S}$ such
that an element $e^{*}\in S_{1}\setminus S_{2}$ satisfies

$\displaystyle c_{e^{*}}>c_{f}\quad\mbox{for each element $f\in S_{2}$}.$

Then, it follows from the exchange axiom (EX) that there exists an element
$f^{*}\in S_{2}\setminus S_{1}$ such that
$S_{1}^{\prime}=(S_{1}\setminus\\{e^{*}\\})\cup\\{f\\}\in\mathcal{S}$. We now
obtain

$\sum_{e\in S_{1}^{\prime}}c_{e}=\sum_{e\in
S_{1}}c_{e}-c_{e^{*}}+c_{f^{*}}<\sum_{e\in S_{1}}c_{e},$

contradicting that $S_{1}$ is a base minimizing $\sum_{e\in S}c_{e}$. ∎

###  2.2 Classical Model of Congestion Games

Let ${\mathbb{Z}}_{+}$ and ${\mathbb{R}}_{+}$ denote the sets of the
nonnegative integers and the nonnegative real numbers, respectively. The
classical model of congestion games is represented as

$\displaystyle(N,E,(\mathcal{S}_{i})_{i\in N},(c_{e})_{e\in E}).$

Here, $N=\\{1,\ldots,n\\}$ and $E$ denote the sets of the players and the
resources, respectively. For each player $i\in N$, the resource subset family
$\mathcal{S}_{i}\subseteq 2^{E}$ denotes the strategy space of $i$. For each
resource $e\in E$, a cost function
$c_{e}\colon{\mathbb{Z}}_{+}\to{\mathbb{R}}_{+}$ is associated.

In a congestion game $(N,E,(\mathcal{S}_{i})_{i\in N},(c_{e})_{e\in E})$, the
cost imposed on a player is determined in the following way. A _strategy
profile_ $\mathbf{S}=(S_{1},\ldots,S_{n})$ is a collection of the strategies
of all players, i.e., $S_{i}\in\mathcal{S}_{i}$ for each $i\in N$. For a
strategy profile $\mathbf{S}=(S_{1},\ldots,S_{n})$ and a resource $e\in E$,
let $N_{e}(\mathbf{S})$ denote the set of the players choosing $e$ in her
strategy, and $n_{e}(\mathbf{S})$ its cardinality. Namely,

$N_{e}(\mathbf{S})=\\{i\in N\mid e\in S_{i}\\},\quad
n_{e}(\mathbf{S})=\left|\\{i\in N\mid e\in S_{i}\\}\right|.$

Now $c_{e}(n_{e}(\mathbf{S}))\in{\mathbb{R}}_{+}$ represents the cost of using
a resource $e$ in a strategy profile $\mathbf{S}$. The cost
$\gamma_{i}(\mathbf{S})$ imposed on a player $i\in N$ in a strategy profile
$\mathbf{S}$ is defined as the total cost of the resources in her strategy
$S_{i}$, that is,

$\displaystyle\gamma_{i}(\mathbf{S})=\sum_{e\in
S_{i}}c_{e}(n_{e}(\mathbf{S})).$

For a strategy profile $\mathbf{S}=(S_{1},\ldots,S_{n})$ and a player $i\in
N$, let $\mathbf{S}_{-i}$ denote the collection of the strategies in
$\mathbf{S}$ other than $S_{i}$, i.e.,
$\mathbf{S}_{-i}=(S_{1},\ldots,S_{i-1},S_{i+1},\ldots,S_{n})$. A _pure Nash
equilibrium_ is a strategy profile in which no player has an incentive to
change her strategy. Namely, a strategy profile
$\mathbf{S}=(S_{1},\ldots,S_{n})$ is a pure Nash equilibrium if

$\displaystyle\gamma_{i}(\mathbf{S})\leq\gamma_{i}(\mathbf{S}_{-i},S_{i}^{\prime})$

holds for each player $i\in N$ and each strategy
$S_{i}^{\prime}\in\mathcal{S}_{i}$. As mentioned in Section 1, every
congestion game has a pure Nash equilibrium [21].

###  2.3 Weighted and Player-Specific Congestion Games

The model of _weighted congestion games_ is described as

$\displaystyle(N,E,(\mathcal{S}_{i})_{i\in N},(c_{e})_{e\in E},(w_{i})_{i\in
N}).$

The difference from the classical model is the presence of the nonnegative
weight $w_{i}\in{\mathbb{R}}_{+}$ of each player $i\in N$. For each resource
$e\in E$, the argument of the cost function $c_{e}$ is not the cardinality of
the players using $e$, but the sum of the weights of those players. For a
subset $N^{\prime}\subseteq N$ of players, let $w(N^{\prime})$ denote the
total weight of the players in $N^{\prime}$, i.e., $w(N^{\prime})=\sum_{i\in
N^{\prime}}w_{i}$. In a strategy profile $\mathbf{S}=(S_{1},\ldots,S_{n})$,
the cost $\gamma_{i}(\mathbf{S})$ imposed on a player $i\in N$ is described as

$\displaystyle\gamma_{i}(\mathbf{S})=\sum_{e\in
S_{i}}c_{e}(w(N_{e}(\mathbf{S}))).$

Hereafter, we assume that $c_{e}$ is monotonically nondecreasing for each
resource $e\in E$, i.e.,

$\displaystyle\mbox{$x<y$ implies $c_{e}(x)\leq
c_{e}(y)$}\quad(x,y\in{\mathbb{Z}}_{+}).$

In contrast to the classical model, weighted congestion games do not
necessarily have pure Nash equilibria. Ackermann, Röglin, and Vöcking [1]
proved that a weighted congestion game has a pure Nash equilibrium if it is a
_matroid game_. Recall that a congestion game is a matroid game if the
strategy space of each player is a base family of a matroid.

######  Theorem 2.3 ([1]).

Every weighted matroid congestion game possesses a pure Nash equilibrium.

Ackermann, Röglin, and Vöcking [1] also proved that the matroid property is
the maximal assumption in a certain sense ensuring the existence of a pure
Nash equilibrium.

A further generalized model of weighted congestion games is proposed by
Takazawa [24]. A distinctive feature of this model is that the cost function
$c_{e}$ of each resource $e\in E$ is a set function defined on the power set
$2^{N}$ of the players: $c_{e}\colon 2^{N}\to{\mathbb{R}}_{+}$. Similarly to
the cost functions in weighted congestion games, this cost function $c_{e}$ is
assumed to be monotonically nondecreasing, that is,

$\mbox{$X\subseteq Y$ implies $c_{e}(X)\leq c_{e}(Y)$ \quad($X,Y\subseteq
N$)}.$

In a strategy profile $\mathbf{S}=(S_{1},\ldots,S_{n})$, the cost
$\gamma_{i}(\mathbf{S})$ imposed on a player $i\in N$ is described as

$\displaystyle\gamma_{i}(\mathbf{S})=\sum_{e\in
S_{i}}c_{e}(N_{e}(\mathbf{S})).$

We refer to this model as a _congestion game with set-functional costs_.

It is straightforward to see that this model generalizes weighted congestion
games. To see this fact, for an instance of a weighted congestion game
$(N,E,(\mathcal{S}_{i})_{i\in N},(c_{e})_{e\in E},(w_{i})_{i\in N})$, it
suffices to define a set function $c^{\prime}_{e}\colon
2^{N}\to{\mathbb{R}}_{+}$ by

$\displaystyle
c^{\prime}_{e}(N^{\prime})=c_{e}(w(N^{\prime}))\quad(N^{\prime}\subseteq N)$
(1)

for each resource $e\in E$. Takazawa [24] extended Theorem 2.3 as follows.

######  Theorem 2.4 ([24]).

Every matroid congestion game with set-functional costs has a pure Nash
equilibrium.

######  Remark 2.5.

The same kind of generalization with set-functional costs is proposed by
Kiyosue and Takazawa [13] for _budget games_ [6, 7]. A budget game is a
variant of congestion game in which the players share the budgets, or
utilities, of the resources. In the original model [6, 7], the utility of a
resource is simply divided by the number of the players using that resource
and allocated to those players. In the generalized model [13], the allocated
utility is represented by a monotonically nondecreasing set function.
Similarly to the situation of congestion games described in Theorems 2.3 and
2.4, the fact that the strategy space of each player is a base family of a
matroid plays an essential role in guaranteeing the existence of a pure Nash
equilibrium in both of the original and generalized models of budget games.

In a _player-specific congestion game_ , a cost function is defined for each
pair of a player and a resource. Namely, a player-specific congestion game
represented by

$\displaystyle(N,E,(\mathcal{S}_{i})_{i\in N},(c_{i,e})_{i\in N,e\in E}),$

where $c_{i,e}\colon{\mathbb{Z}}_{+}\to{\mathbb{R}}_{+}$ is a monotonically
nondecreasing function for each $i\in N$ and $e\in E$. The cost
$\gamma_{i}(\mathbf{S})$ imposed on a player $i\in N$ in a strategy profile
$\mathbf{S}=(S_{1},\ldots,S_{n})$ is defined as

$\gamma_{i}(\mathbf{S})=\sum_{e\in S_{i}}c_{i,e}(n_{e}(\mathbf{S})).$

As mentioned in Section 1, every player-specific singleton congestion game has
a pure Nash equilibrium [16]. Ackermann, Röglin, and Vöcking [1] extended the
existence of pure Nash equilibria in player-specific matroid congestion games.

######  Theorem 2.6 ([1]).

Every player-specific matroid congestion game possesses a pure Nash
equilibrium.

###  2.4 Congestion Games with Mixed Costs and with Complementarities

Feldotto, Leder, and Skopalik [9] proposed a common generalization of
classical congestion games and bottleneck congestion games, called _congestion
games with mixed costs_. A congestion game with mixed costs is represented by
a tuple

$\displaystyle(N,E,(\mathcal{S}_{i})_{i\in N},(\ell_{e})_{e\in
E},(b_{e})_{e\in E},(\alpha_{i})_{i\in N}).$

For each resource $e\in E$, let
$\ell_{e}\colon{\mathbb{Z}}_{+}\to{\mathbb{R}}_{+}$ and
$b_{e}\colon{\mathbb{Z}}_{+}\to{\mathbb{R}}_{+}$ denote its _latency cost
function_ and _bottleneck cost function_ , respectively. We assume that both
$\ell_{e}$ and $b_{e}$ are monotonically nondecreasing. For each player $i\in
N$, a real number $\alpha_{i}\in[0,1]$ denotes her _preference value_. In a
strategy profile $\mathbf{S}=(S_{1},\ldots,S_{n})$, the cost
$\gamma_{i}(\mathbf{S})$ imposed on a player $i\in N$ is defined as

$\displaystyle\gamma_{i}(\mathbf{S})=\alpha_{i}\cdot\sum_{e\in
S_{i}}\ell_{e}(n_{e}(\mathbf{S}))+(1-\alpha_{i})\cdot\max_{e\in
S_{i}}\\{b_{e}(n_{e}(\mathbf{S}))\\}.$

It is straightforward to see that a congestion game with mixed costs is
exactly a classical congestion game if $\alpha_{i}=1$ for each player $i\in
N$, and a bottleneck congestion game if $\alpha_{i}=0$ for each player $i\in
N$.

On the existence of pure Nash equilibria in congestion games with mixed costs,
Feldotto, Leder, and Skopalik [9] proved the following theorem. For a
congestion game with mixed costs, the cost functions $\ell_{e}$ and $b_{e}$
$(e\in E)$ have _monotone dependence_ if there exists a monotonically
nondecreasing function $d\colon{\mathbb{R}}_{+}\to{\mathbb{R}}_{+}$ satisfying
that

$\displaystyle b_{e}(x)=d(\ell_{e}(x))\qquad(x\in{\mathbb{Z}}_{+})$

for each resource $e\in E$.

######  Theorem 2.7 ([9]).

A congestion game with mixed costs has a pure Nash equilibrium in the
following three cases.

  1. (i)

It is a singleton game.

  2. (ii)

It is a matroid game and $\alpha_{i}\in\\{0,1\\}$ for each player $i\in N$.

  3. (iii)

It is a matroid game and the cost functions have monotone dependence.

Feldotto, Leder, and Skopalik [8] proposed a further generalized model of a
_congestion game with complementarities_ , which is represented by a tuple

$\displaystyle(N,E,(\mathcal{S}_{i})_{i\in N},(c_{e})_{e\in E},g).$

In this model, $g\colon{\mathbb{R}}_{+}^{r}\to{\mathbb{R}}$ denotes the
aggregation function, which is defined on ${\mathbb{R}}_{+}^{r}$ for a
positive integer $r$, and we assume that the sizes of the strategies of all
players are equal to $r$, i.e., $|S_{i}|=r$ for each player $i\in N$ and each
strategy $S_{i}\in\mathcal{S}_{i}$. For a player $i\in N$ and a strategy
profile $\mathbf{S}=(S_{1},\ldots,S_{n})$, where
$S_{i}=\\{e_{1},\ldots,e_{r}\\}$, the cost $\gamma_{i}(\mathbf{S})$ on $i$ in
$\mathbf{S}$ is described as

$\displaystyle\gamma_{i}(\mathbf{S})=g(c_{e_{1}}(n_{e_{1}}(\mathbf{S})),\ldots,c_{e_{r}}(n_{e_{r}}(\mathbf{S}))).$

It is straightforward to see that congestion games with complementarities
generalize classical congestion games and bottleneck congestion games. An
important special case analyzed in detail in [8] is _congestion games with
$L^{p}$-aggregation functions_, i.e.,

$\displaystyle
g(x_{1},\ldots,x_{r})=\left(\sum_{j=1}^{r}{x_{j}}^{p}\right)^{\frac{1}{p}}.$
(2)

for some value $p\geq 1$. It is also noteworthy that, if the aggregation
function is player-specific, then this model includes congestion games with
mixed costs.

Feldotto, Leder, Skopalik [8] proved the existence of a pure Nash equilibrium
under the assumption that it is a matroid game and the aggregation function
$g$ is _weakly monotone_. Weak monotone functions generalize the monotonically
nondecreasing functions, and are defined in a sophisticated manner. The
readers are referred to their original paper [8] for the definition of weakly
monotone functions.

######  Theorem 2.8 ([8]).

Every matroid congestion game with complementarities has a pure Nash
equilibrium if the aggregation function is weakly monotone.

##  3 Weighted Congestion Games with Complementarities and Beyond

The central subject of this paper is described in this section. We deal with a
common generalization of weighted congestion games and congestion games with
complementarities, referred to as _weighted congestion games with
complementarities_ , and a further generalized model of _congestion games with
set-functional costs and complementarities_. Below we investigate the latter
model, because the former model can be represented as the latter model with
cost function $c_{e}$ defined by (1) for each resource $e\in E$.

###  3.1 Our Model

A _congestion game with set-functional costs and complementarities_ is
described by a tuple

$\displaystyle(N,E,(\mathcal{S}_{i})_{i\in N},(c_{e})_{e\in E},g).$

Again we assume that the aggregation function
$g\colon{\mathbb{R}}_{+}^{r}\to{\mathbb{R}}$ is defined on
${\mathbb{R}}_{+}^{r}$ for some positive integer $r$ and $|S_{i}|=r$ for each
player $i\in N$ and each strategy $S_{i}\in\mathcal{S}_{i}$. The difference
from congestion games with complementarities described in Section 2.4 is that
the cost function $c_{e}\colon 2^{N}\to{\mathbb{R}}_{+}$ is a set function for
each resource $e\in E$. Consequently, for a player $i\in N$ and a strategy
profile $\mathbf{S}=(S_{1},\ldots,S_{n})$, where
$S_{i}=\\{e_{1},\ldots,e_{r}\\}$, the cost $\gamma_{i}(\mathbf{S})$ on $i$ in
$\mathbf{S}$ is described as

$\displaystyle\gamma_{i}(\mathbf{S})=g(c_{e_{1}}(N_{e_{1}}(\mathbf{S})),\ldots,c_{e_{r}}(N_{e_{r}}(\mathbf{S}))).$

The monotonicity of the cost functions $c_{e}$ ($e\in E$) and the aggregation
function $g$ in the previous models is represented in the following manner.
First, in the aggregation of the costs of the resources in a strategy of a
player, we take no account of the order of the resources. Formally, we assume
that

$g({\mbox{\boldmath$v$}})=g(\sigma({\mbox{\boldmath$v$}}))$

for each cost vector ${\mbox{\boldmath$v$}}\in{\mathbb{R}}_{+}^{r}$ and each
permutation $\sigma$ of a set of $r$ elements. Then, we adopt the following
definition of weakly monotone functions, which is simpler than that in [8].

######  Definition 3.1.

Let $r$ be a positive integer. A function
$g\colon{\mathbb{R}}_{+}^{r}\to{\mathbb{R}}$ is _weakly monotone_ if, for each
$x,y\in{\mathbb{R}}_{+}$, it holds that

$g({\mbox{\boldmath$v$}}^{\prime},x)\leq
g({\mbox{\boldmath$v$}}^{\prime},y)\quad\mbox{for each
${\mbox{\boldmath$v$}}^{\prime}\in{\mathbb{R}}^{r-1}_{+}$}$

or

$g({\mbox{\boldmath$v$}}^{\prime},x)\geq
g({\mbox{\boldmath$v$}}^{\prime},y)\quad\mbox{for each
${\mbox{\boldmath$v$}}^{\prime}\in{\mathbb{R}}^{r-1}_{+}$}.$

It is straightforward to see that a function
$g\colon{\mathbb{R}}_{+}^{r}\to{\mathbb{R}}$ such that

${\mbox{\boldmath$u$}}\leq{\mbox{\boldmath$v$}}$ implies
$g({\mbox{\boldmath$u$}})\leq g({\mbox{\boldmath$v$}})$
(${\mbox{\boldmath$u$}},{\mbox{\boldmath$v$}}\in{\mathbb{R}}^{r}$)

is weakly monotone, where ${\mbox{\boldmath$u$}}\leq{\mbox{\boldmath$v$}}$
means $u_{j}\leq v_{j}$ for each $j=1,\ldots,r$. For instance, the
$L^{p}$-aggregation function (2) is weakly monotone.

Associated with Definition 3.1 of the weak monotonicity of the aggregation
function $g$, the monotonicity of the cost function $c_{e}\colon
2^{N}\to{\mathbb{R}}$ ($e\in E$) is adjusted in the following way.

######  Definition 3.2.

For a weakly monotone aggregation function
$g\colon{\mathbb{R}}^{r}_{+}\to{\mathbb{R}}$, a cost function $c\colon
2^{N}\to{\mathbb{R}}_{+}$ is _monotonically nondecreasing_ with respect to $g$
if, for each $X,Y\subseteq N$ with $X\subseteq Y$, it holds that

$g({\mbox{\boldmath$v$}}^{\prime},c(X))\leq
g({\mbox{\boldmath$v$}}^{\prime},c(Y))\quad\mbox{for each
${\mbox{\boldmath$v$}}^{\prime}\in{\mathbb{R}}^{r-1}_{+}$}.$

Definition 3.2 means that more players on one resource result in larger cost,
even in the weak monotonicity of the aggregation function.

###  3.2 Pure Nash Equilibria in Matroid Games

Our main technical contribution is the following theorem, which guarantees the
existence of a pure Nash equilibrium in a matroid congestion game with set-
functional costs and complementarities. This theorem amounts to a common
extension of Theorems 2.3, 2.4, and 2.8.

######  Theorem 3.3.

A matroid congestion game $(N,E,(\mathcal{S}_{i})_{i\in N},(c_{e})_{e\in
E},g)$ with set-functional costs and complementarities has a pure Nash
equilibrium if the aggregation function
$g\colon{\mathbb{R}}_{+}^{r}\to{\mathbb{R}}$ is weakly monotone and the cost
function $c_{e}\colon 2^{N}\to{\mathbb{R}}_{+}$ is monotonically nondecreasing
with respect to $g$ for each resource $e\in E$.

Before a proof, we present the following corollaries of Theorem 3.3. These
corollaries are immediately derived from Theorem 3.3, and guarantee the
existence of pure Nash equilibria in some generalized models of congestion
games.

######  Corollary 3.4.

Every weighted matroid bottleneck congestion game in which the strategies of
all players have the same cardinality has a pure Nash equilibrium.

######  Corollary 3.5.

Every weighted matroid congestion game with $L^{p}$-aggregation functions in
which the strategies of all players have the same cardinality has a pure Nash
equilibrium.

Our proof for Theorem 3.3 is obtained by extending the arguments in [1, 24]
and [8]. In preparation for the proof, we first define a total preorder
$\preceq_{g}$ on ${\mathbb{R}}_{+}$, on the basis of the weak monotonicity of
the aggregation function $g$. Recall that a relation $\preceq$ on a set $X$ is
a _preorder_ if $x\preceq x$ for each $x\in X$, and $x\preceq y$ and $y\preceq
z$ implies $x\preceq z$ for each $x,y,z\in X$. A preorder is _total_ if
$x\preceq y$ or $y\preceq x$ holds for each $x,y\in X$.

######  Definition 3.6 (Total preorder $\preceq_{g}$ on ${\mathbb{R}}_{+}$).

Let $g\colon{\mathbb{R}}_{+}^{r}\to{\mathbb{R}}$ be a weakly monotone
function. For two nonnegative values $x,y\in{\mathbb{R}}_{+}$, we define
$x\preceq_{g}y$ if

$\mbox{$g({\mbox{\boldmath$v$}}^{\prime},x)\leq
g({\mbox{\boldmath$v$}}^{\prime},y)$ for each
${\mbox{\boldmath$v$}}^{\prime}\in{\mathbb{R}}_{+}^{r-1}$}.$

Further, we define $x\sim_{g}y$ if both $x\preceq_{g}y$ and $y\preceq_{g}x$
hold, and $x\prec_{g}y$ if $x\preceq_{g}y$ but $y\not\preceq_{g}x$.

It directly follows from Definition 3.1 that the relation $\preceq_{g}$ is a
total preorder. By employing this total preorder $\preceq_{g}$ and the
simultaneous exchange property of matroids (Lemma 2.1), we then show that, if
a strategy profile is not a pure Nash equilibrium, a player has an _improving
local move_. For a strategy profile $\mathbf{S}=(S_{1},\ldots,S_{n})$ and a
player $i\in N$, a strategy $S_{i}^{\prime}\in\mathcal{S}_{i}$ of $i$ is an
_improving move_ in $\mathbf{S}$ if the cost imposed on $i$ becomes smaller by
choosing $S_{i}^{\prime}$ instead of $S_{i}$, i.e.,
$\gamma_{i}(\mathbf{S}_{-i},S_{i}^{\prime})<\gamma_{i}(\mathbf{S})$. An
improving move $S_{i}^{\prime}$ is called an _improving local move_ if
$|S_{i}^{\prime}\setminus S_{i}|=1$.

######  Lemma 3.7.

Let $\mathbf{S}=(S_{1},\ldots,S_{n})$ be a strategy profile in a matroid
congestion game $(N,E,(\mathcal{S}_{i})_{i\in N},(c_{e})_{e\in E},g)$ with
set-functional costs and complementarities. If $\mathbf{S}$ is not a pure Nash
equilibrium, then there exists a player $i\in N$ having an improving local
move in $\mathbf{S}$.

###### Proof.

Since the strategy profile $\mathbf{S}$ is not a pure Nash equilibrium, there
exists a player $i\in N$ having an improving move
$S_{i}^{\prime}\in\mathcal{S}_{i}$. Among the improving moves, choose
$S_{i}^{\prime}$ which minimizes $|S_{i}^{\prime}\setminus S_{i}|$, and let
$\mathbf{S}^{\prime}$ denote the strategy profile
$(\mathbf{S}_{-i},S_{i}^{\prime})$. Since $S_{i}^{\prime}$ is an improving
move, it holds that

$\displaystyle\gamma_{i}(\mathbf{S}^{\prime})<\gamma_{i}(\mathbf{S}).$ (3)

We show $|S_{i}^{\prime}\setminus S_{i}|=1$ to prove that $S_{i}^{\prime}$ is
an improving local move.

Suppose to the contrary that $|S_{i}^{\prime}\setminus S_{i}|\geq 2$. It
follows from Lemma 2.1 that there exist two resources $e^{*}\in S_{i}\setminus
S_{i}^{\prime}$ and $f^{*}\in S_{i}^{\prime}\setminus S_{i}$ satisfying that

$T_{i}=(S_{i}\setminus\\{e^{*}\\})\cup\\{f^{*}\\}\in\mathcal{S}_{i}\quad\mbox{and}\quad
T_{i}^{\prime}=(S_{i}^{\prime}\setminus\\{f^{*}\\})\cup\\{e^{*}\\}\in\mathcal{S}_{i}.$

It then follows from $|S_{i}^{\prime}\setminus S_{i}|\geq 2$ and the
minimality of $|S_{i}^{\prime}\setminus S_{i}|$ that neither $T_{i}$ nor
$T_{i}^{\prime}$ is an improving move, i.e.,

$\displaystyle{}\gamma_{i}(\mathbf{S}_{-i},T_{i})\geq\gamma_{i}(\mathbf{S}),$
(4)
$\displaystyle{}\gamma_{i}(\mathbf{S}_{-i},T_{i}^{\prime})\geq\gamma_{i}(\mathbf{S}).$
(5)

We have that

$\displaystyle\gamma_{i}(\mathbf{S}){}$
$\displaystyle{}=g((c_{e}(N_{e}(\mathbf{S})))_{e\in S_{i}}),$
$\displaystyle\gamma_{i}(\mathbf{S}_{-i},T_{i}){}$
$\displaystyle{}=g((c_{e}(N_{e}(\mathbf{S}_{-i},T_{i})))_{e\in T_{i}})$
$\displaystyle{}=g((c_{e}(N_{e}(\mathbf{S})))_{e\in
S_{i}\setminus\\{e^{*}\\}},c_{f^{*}}(N_{f^{*}}(\mathbf{S}_{-i},T_{i})))$
$\displaystyle{}=g((c_{e}(N_{e}(\mathbf{S})))_{e\in
S_{i}\setminus\\{e^{*}\\}},c_{f^{*}}(N_{f^{*}}(\mathbf{S})\cup\\{i\\})),$

and hence it follows from (4) that

$\displaystyle
c_{e^{*}}(N_{e^{*}}(\mathbf{S}))\preceq_{g}c_{f^{*}}(N_{f^{*}}(\mathbf{S})\cup\\{i\\})=c_{f^{*}}(N_{f^{*}}(\mathbf{S}^{\prime})).$
(6)

Further, it follows from (3) and (5) that
$\gamma_{i}(\mathbf{S}^{\prime})<\gamma_{i}(\mathbf{S}_{-i},T_{i}^{\prime})$.
We have that

$\displaystyle{}\gamma_{i}(\mathbf{S}^{\prime})=g(c_{e}(N_{e}(\mathbf{S}^{\prime}))_{e\in
S_{i}^{\prime}}),$
$\displaystyle{}\gamma_{i}(\mathbf{S}_{-i},T_{i}^{\prime})=\gamma_{i}(\mathbf{S}_{-i},(S_{i}^{\prime}\setminus\\{f^{*}\\})\cup\\{e^{*}\\})=g((c_{e}(N_{e}(\mathbf{S}^{\prime})))_{e\in
S_{i}^{\prime}\setminus\\{f^{*}\\}},c_{e^{*}}(N_{e^{*}}(\mathbf{S}))),$

and hence

$\displaystyle
c_{f^{*}}(N_{f^{*}}(\mathbf{S}^{\prime}))\prec_{g}c_{e^{*}}(N_{e^{*}}(\mathbf{S})).$
(7)

We now have both (6) and (7), a contradiction. ∎

On the basis of Lemma 3.7, we prove Theorem 3.3 by showing that an improving
local move strictly decreases a lexicographic order on the potential of the
strategy profile. For this purpose, below we define the potential
$\Phi(\mathbf{S})$ of a strategy profile $\mathbf{S}$ and a lexicographic
order on the potentials.

Let $|E|=m$. For a resource $e\in E$, define a two-dimensional vector
$\phi_{e}(\mathbf{S})\in{\mathbb{R}}_{+}\times{\mathbb{Z}}_{+}$ by

$\phi_{e}(\mathbf{S})=(c_{e}(N_{e}(\mathbf{S})),n_{e}(\mathbf{S})).$

######  Definition 3.8.

For two resources $e,e^{\prime}\in E$, we define
$\phi_{e}(\mathbf{S})\preceq_{\mathrm{lex}}\phi_{e^{\prime}}(\mathbf{S})$ if
either

$c_{e}(\mathbf{S})\prec_{g}c_{e^{\prime}}(\mathbf{S})$

or

$c_{e}(\mathbf{S})\sim_{g}c_{e^{\prime}}(\mathbf{S})$ and
$n_{e}(\mathbf{S})\leq n_{e^{\prime}}(\mathbf{S^{\prime}})$

holds. Further, we define
$\phi_{e}(\mathbf{S})\sim_{\mathrm{lex}}\phi_{e^{\prime}}(\mathbf{S})$ if

$\phi_{e}(\mathbf{S})\preceq_{\mathrm{lex}}\phi_{e^{\prime}}(\mathbf{S})$ and
$\phi_{e^{\prime}}(\mathbf{S})\preceq_{\mathrm{lex}}\phi_{e}(\mathbf{S})$

hold, and
$\phi_{e}(\mathbf{S})\prec_{\mathrm{lex}}\phi_{e^{\prime}}(\mathbf{S})$ if

$\phi_{e}(\mathbf{S})\preceq_{\mathrm{lex}}\phi_{e^{\prime}}(\mathbf{S})$ and
$\phi_{e^{\prime}}(\mathbf{S})\not\preceq_{\mathrm{lex}}\phi_{e}(\mathbf{S})$

hold.

Now the potential $\Phi(\mathbf{S})$ is a sequence
$(\phi_{e}(\mathbf{S}))_{e\in E}$ of all resources in the lexicographically
nonincreasing order. Namely,

$\mbox{$\Phi(\mathbf{S})=(\phi_{e_{1}}(\mathbf{S}),\ldots,\phi_{e_{m}}(\mathbf{S}))$,
where
$\phi_{e_{1}}(\mathbf{S})\succeq_{\mathrm{lex}}\cdots\succeq_{\mathrm{lex}}\phi_{e_{m}}(\mathbf{S})$}.$

######  Definition 3.9 (Lexicographic order on the potentials).

For two strategy profiles $\mathbf{S}$ and $\mathbf{S}^{\prime}$, where
$\Phi(\mathbf{S})=(\phi_{e_{1}}(\mathbf{S}),\ldots,\phi_{e_{m}}(\mathbf{S}))$
and
$\Phi(\mathbf{S}^{\prime})=(\phi_{e^{\prime}_{1}}(\mathbf{S}),\ldots,\phi_{e^{\prime}_{m}}(\mathbf{S}))$,
we define $\Phi(\mathbf{S})\preceq_{\mathrm{lex}}\Phi(\mathbf{S^{\prime}})$ if
there exists an integer $k$ with $1\leq k\leq m$ such that

$\displaystyle\mbox{$\phi_{e_{j}}(\mathbf{S})\sim_{\mathrm{lex}}\phi_{e^{\prime}_{j}}(\mathbf{S})$
for every $j<k$},$
$\displaystyle\phi_{e_{k}}(\mathbf{S})\prec_{\mathrm{lex}}\phi_{e^{\prime}_{k}}(\mathbf{S}).$

A strict relation
$\Phi(\mathbf{S})\prec_{\mathrm{lex}}\Phi(\mathbf{S^{\prime}})$ means that
$\Phi(\mathbf{S})\preceq_{\mathrm{lex}}\Phi(\mathbf{S^{\prime}})$ and
$\Phi(\mathbf{S}^{\prime})\not\preceq_{\mathrm{lex}}\Phi(\mathbf{S})$ hold.

We are now ready to prove Theorem 3.3.

###### Proof of Theorem 3.3.

Let $\mathbf{S}=(S_{1},\ldots,S_{n})$ be a strategy profile, and suppose that
it is not a pure Nash equilibrium. It then follows from Lemma 3.7 that there
exists a player $i\in N$ having a local improving move
$S_{i}^{\prime}=(S_{i}\setminus\\{e^{*}\\})\cup\\{f^{*}\\}$. Denote
$\mathbf{S}^{\prime}=(\mathbf{S}_{-i},S_{i}^{\prime})$. Recall that
$\gamma_{i}(\mathbf{S}^{\prime})<\gamma_{i}(\mathbf{S})$ holds.

We analyze the lexicographic order of the potentials of $\Phi(\mathbf{S})$ and
$\Phi(\mathbf{S}^{\prime})$. First, for each resource $e\in
E\setminus\\{e^{*},f^{*}\\}$, it holds that
$N_{e}(\mathbf{S})=N_{e}(\mathbf{S}^{\prime})$ and hence

$\displaystyle\phi_{e}(\mathbf{S})=\phi_{e}(\mathbf{S}^{\prime})\quad(e\in
E\setminus\\{e^{*},f^{*}\\}).$ (8)

We then investigate the two resources $e^{*}$ and $f^{*}$. First, it follows
from $\gamma_{i}(\mathbf{S}^{\prime})<\gamma_{i}(\mathbf{S})$ that

$\displaystyle g\left((c_{e}(N_{e}(\mathbf{S})))_{e\in
S_{i}\setminus\\{e^{*}\\}},c_{f^{*}}(N_{f^{*}}(\mathbf{S}^{\prime}))\right)<g\left((c_{e}(N_{e}(\mathbf{S})))_{e\in
S_{i}\setminus\\{e^{*}\\}},c_{e^{*}}(N_{e^{*}}(\mathbf{S}))\right),$

and hence

$\displaystyle
c_{f^{*}}(N_{f^{*}}(\mathbf{S}^{\prime}))\prec_{g}c_{e^{*}}(N_{e^{*}}(\mathbf{S})).$
(9)

Further, it is straightforward to see that $i\in N_{e^{*}}(\mathbf{S})$ and
$N_{e^{*}}(\mathbf{S}^{\prime})=N_{e^{*}}(\mathbf{S})\setminus\\{i\\}$, and
thus

$\displaystyle{}n_{e^{*}}(\mathbf{S}^{\prime})<n_{e^{*}}(\mathbf{S}),$ (10)
$\displaystyle{}c_{e^{*}}(N_{e^{*}}(\mathbf{S}^{\prime}))\preceq_{g}c_{e^{*}}(N_{e^{*}}(\mathbf{S})),$
(11)

where the latter relation (11) follows from the monotonicity of the cost
function $c_{e^{*}}$ (Definition 3.2).

Now it follows from (9) that

$\displaystyle\phi_{f^{*}}(\mathbf{S}^{\prime})=(c_{f^{*}}(N_{f^{*}}(\mathbf{S}^{\prime})),n_{f^{*}}(\mathbf{S^{\prime}}))\prec_{\mathrm{lex}}(c_{e^{*}}(N_{e^{*}}(\mathbf{S})),n_{e^{*}}(\mathbf{S}))=\phi_{e^{*}}(\mathbf{S}).$
(12)

We also obtain from (10) and (11) that

$\displaystyle\phi_{e^{*}}(\mathbf{S^{\prime}})=\left(c_{e^{*}}(N_{e^{*}}(\mathbf{S}^{\prime})),n_{e^{*}}(\mathbf{S^{\prime}})\right)\prec_{\mathrm{lex}}\left(c_{e^{*}}(N_{e^{*}}(\mathbf{S})),n_{e^{*}}(\mathbf{S})\right)=\phi_{e^{*}}(\mathbf{S}).$
(13)

From (8), (12), and (13), we derive that
$\Phi(\mathbf{S}^{\prime})\prec_{\mathrm{lex}}\Phi(\mathbf{S})$.

Therefore, an improving local move strictly decreases the lexicographic order
of the potential $\Phi(\mathbf{S})$. On the basis of the finiteness of the
game, after a finite number of improving local moves, a strategy profile in
which no player has an improving local move is attained. It now follows from
Lemma 3.7 that this strategy profile is a pure Nash equilibrium. ∎

##  4 Generalizations of Congestion Games with Mixed Costs

In this section, we deal with generalizations of congestion games with mixed
costs, and provide some extensions of Theorem 2.7.

###  4.1 Player-Specific Congestion Games with Mixed Costs

One model is a _player-specific congestion game with mixed costs_ , which is
represented by a tuple

$\displaystyle(N,R,(\mathcal{S}_{i})_{i\in N},(\ell_{i,e})_{i\in N,e\in
E},(b_{i,e})_{i\in N,e\in E},(\alpha_{i})_{i\in N}).$

The difference from the model of congestion games with mixed costs in Section
2.4 is that the latency and bottleneck cost functions are player-specific.
Namely, each player $i\in N$ has her own latency cost function
$\ell_{i,e}\colon{\mathbb{Z}}_{+}\to{\mathbb{R}}_{+}$ and bottleneck cost
function $b_{i,e}\colon{\mathbb{Z}}_{+}\to{\mathbb{R}}_{+}$ for each resource
$e\in E$. Hence, the cost $\gamma_{i}(\mathbf{S})$ imposed on a player $i\in
N$ in a strategy profile $\mathbf{S}=(S_{1},\ldots,S_{n})$ is described as

$\displaystyle\gamma_{i}(\mathbf{S})=\alpha_{i}\cdot\sum_{e\in
S_{i}}\ell_{i,e}(n_{e}(\mathbf{S}))+(1-\alpha_{i})\cdot\max_{e\in
S_{i}}\\{b_{i,e}(n_{e}(\mathbf{S}))\\}.$

We assume that the cost functions $\ell_{i,e}$ and $b_{i,e}$ are monotonically
nondecreasing for each $i\in N$ and $e\in E$.

The following theorem extends Theorem 2.7(i)(ii). The proof below is a modest
extension of that in [9].

######  Theorem 4.1.

A player-specific congestion game $G$ with mixed costs has a pure Nash
equilibrium in the following two cases.

  1. (i)

$G$ is a singleton game.

  2. (ii)

$G$ is a matroid game and $\alpha_{i}\in\\{0,1\\}$ for each player $i\in N$.

###### Proof.

We first investigate Case (i). Let $\mathbf{S}=(S_{1},\ldots,S_{n})$ be a
strategy profile and let $i\in N$ be a player. Since $G$ is a singleton game,
it holds that $S_{i}=\\{e\\}$ for some resource $e\in E$, and

$\displaystyle\gamma_{i}(\mathbf{S})=\alpha_{i}\cdot\ell_{i,e}(n_{e}(\mathbf{S}))+(1-\alpha_{i})\cdot
b_{i,e}(n_{e}(\mathbf{S})).$

Now define a new player-specific cost function
$c^{\prime}_{i,e}\colon{\mathbb{Z}}_{+}\to{\mathbb{R}}_{+}$ by

$c^{\prime}_{i,e}(x)=\alpha_{i}\cdot\ell_{i,e}(x)+(1-\alpha_{i})\cdot
b_{i,e}(x)\quad(x\in{\mathbb{Z}}_{+})$

for each player $i\in N$ and each resource $e\in E$, and construct a player-
specific singleton congestion game

$G^{\prime}=(N,E,(\mathcal{S}_{i})_{i\in N},(c^{\prime}_{i,e})_{i\in N,e\in
E}),$

in which the existence of a pure Nash equilibrium is proved in [16] (see also
Theorem 2.6). Clearly, a pure Nash equilibrium in $G^{\prime}$ is also a pure
Nash equilibrium in $G$.

We next consider Case (ii). Let $\mathbf{S}=(S_{1},\ldots,S_{n})$ be a
strategy profile. For a player $i\in N$, her cost $\gamma_{i}(\mathbf{S})$ is
described as

$\displaystyle\gamma_{i}(\mathbf{S}){}$
$\displaystyle{}=\alpha_{i}\cdot\sum_{e\in
S_{i}}\ell_{i,e}(n_{e}(\mathbf{S}))+(1-\alpha_{i})\cdot\max_{e\in
S_{i}}\\{b_{i,e}(n_{e}(\mathbf{S}))\\}$
$\displaystyle{}=\begin{cases}\displaystyle\sum_{e\in
S_{i}}\ell_{i,e}(n_{e}(\mathbf{S}))&\mbox{if $\alpha_{i}=1$},\\\
\displaystyle\max_{e\in S_{i}}\\{b_{i,e}(n_{e}(\mathbf{S}))\\}&\mbox{if
$\alpha_{i}=0$}.\end{cases}$

Similarly to the above proof, define a new player-specific cost function
$c^{\prime\prime}_{i,e}\colon{\mathbb{Z}}_{+}\to{\mathbb{R}}_{+}$ by

$\displaystyle
c^{\prime\prime}_{i,e}(x)=\begin{cases}\displaystyle\ell_{i,e}(x)&\mbox{if
$\alpha_{i}=1$},\\\ \displaystyle b_{i,e}(x)&\mbox{if
$\alpha_{i}=0$}\end{cases}\quad(x\in{\mathbb{Z}}_{+})$

for each player $i\in N$ and each resource $e\in E$ to construct a player-
specific matroid congestion game

$G^{\prime\prime}=(N,E,(\mathcal{S}_{i})_{i\in
N},(c^{\prime\prime}_{i,e})_{i\in N,e\in E}),$

which is guaranteed to possess a pure Nash equilibrium in [1] (Theorem 2.6).
Since $G$ is a matroid game, it follows from Lemma 2.2 that a strategy
$S_{i}\in\mathcal{S}_{i}$ minimizing $\sum_{e\in
S_{i}}b_{i,e}(n_{e}(\mathbf{S}_{-i},S_{i}))$ also minimizes $\max_{e\in
S_{i}}\\{b_{i,e}(n_{e}(\mathbf{S}_{-i},S_{i}))\\}$. Now it is straightforward
to see that a pure Nash equilibrium in $G^{\prime\prime}$ is also a pure Nash
equilibrium in $G$. ∎

###  4.2 Weighted Congestion Games with Mixed Costs and Beyond

Another model is a _congestion game with mixed and set-functional costs_ ,
which includes a _weighted congestion game with mixed costs_. A congestion
game with mixed and set-functional costs is represented by a tuple

$(N,E,(\mathcal{S}_{i})_{i\in N},(\ell_{e})_{e\in E},(b_{e})_{e\in
E},(\alpha_{i})_{i\in N}).$

A new feature of this model is that the latency cost function $\ell_{e}\colon
2^{N}\to{\mathbb{R}}_{+}$ and the bottleneck cost function $b_{e}\colon
2^{N}\to{\mathbb{R}}_{+}$ are set functions for each resource $e\in E$. Again,
these cost functions are assumed to be monotonically nondecreasing. Moreover,
we generalize the definition of the monotone dependence of the cost functions
$\ell_{e}$ and $b_{e}$ as the existence of a monotonically nondecreasing
function $d\colon{\mathbb{R}}_{+}\to{\mathbb{R}}_{+}$ satisfying that

$b_{e}(N^{\prime})=d(\ell_{e}(N^{\prime}))\quad(N^{\prime}\subseteq N)$

for each resource $e\in E$.

For this model, we extend Theorem 2.7(iii) to obtain the following theorem.

######  Theorem 4.2.

A congestion game $G$ with mixed and set-functional costs has a pure Nash
equilibrium if $G$ is a matroid game and the cost functions have monotone
dependence.

###### Proof.

Let $\mathbf{S}$ be a strategy profile of $G$ and $i\in N$ be a player. Since
the cost functions have monotone dependence, it holds that

$\displaystyle\gamma_{i}(\mathbf{S}){}$
$\displaystyle{}=\alpha_{i}\cdot\sum_{e\in
S_{i}}\ell_{e}(N_{e}(\mathbf{S}))+(1-\alpha_{i})\cdot\max_{e\in
S_{i}}\\{b_{e}(N_{e}(\mathbf{S}))\\}$
$\displaystyle{}=\alpha_{i}\cdot\sum_{e\in
S_{i}}\ell_{e}(N_{e}(\mathbf{S}))+(1-\alpha_{i})\cdot\max_{e\in
S_{i}}\\{d(\ell_{e}(N_{e}(\mathbf{S})))\\}$

for a monotonically nondecreasing function
$d\colon{\mathbb{R}}_{+}\to{\mathbb{R}}_{+}$.

Now construct a congestion game $G^{\prime}=(N,E,(\mathcal{S}_{i})_{i\in
N},(c_{e})_{e\in E})$ with set-functional costs $c_{e}\colon
2^{N}\to{\mathbb{R}}_{+}$ ($e\in E$) defined by

$\displaystyle c_{e}(N^{\prime})=\ell_{e}(N^{\prime})\quad(N^{\prime}\subseteq
N).$

It follows from Theorem 2.4 that $G^{\prime}$ has a pure Nash equilibrium
$\mathbf{S}=(S_{1},\ldots,S_{n})$.

We have that $S_{i}$ minimizes $\sum_{e\in
S_{i}}\ell_{e}(N_{e}(\mathbf{S}_{-i},S_{i}))$ among all the strategies in
$\mathcal{S}_{i}$. Since $G$ is a matroid game, it follows from Lemma 2.2 that
$S_{i}$ also minimizes $\max_{e\in
S_{i}}\\{\ell_{e}(N_{e}(\mathbf{S}_{-i},S_{i}))\\}$. From the monotonicity of
$d$, it follows that

$\max_{e\in S_{i}}\\{d(\ell_{e}(N_{e}(\mathbf{S})))\\}=d\left(\max_{e\in
S_{i}}\\{\ell_{e}(N_{e}(\mathbf{S}))\\}\right),$

and hence $S_{i}$ further minimizes $\max_{e\in
S_{i}}\\{d(\ell_{e}(N_{e}(\mathbf{S}_{-i},S_{i})))\\}$. Consequently, $S_{i}$
minimizes $\gamma_{i}(\mathbf{S}_{-i},S_{i})$, and therefore we conclude that
$\mathbf{S}$ is also a pure Nash equilibrium in $G$. ∎

##  5 Conclusion

We have presented a model of congestion games with set-functional costs and
complementarities, which commonly generalizes previous models such as weighted
congestion games, congestion games with set-functional costs, congestion games
with bottleneck costs, and congestion games with complementarities. Main
technical contributions of this paper are a simplification of the monotonicity
of the aggregation functions and a proof of the existence of pure Nash
equilibria for matroid games under the simplified definition of the monotone
aggregation functions. We have also extended the existence of pure Nash
equilibria in congestion games with mixed costs to player-specific and
weighted congestion games.

A possible direction of future research is to analyze the algorithmic aspects
and the efficiency of the pure Nash equilibria, such as the convergence time,
the price of anarchy, and the price of stability. It is also of interest to
investigate a relation between our model and congestion games with
lexicographical improvement property [11].

## References

  * [1] H. Ackermann, H. Röglin, and B. Vöcking.  Pure Nash equilibria in player-specific and weighted congestion games.  Theor. Comput. Sci., 410(17):1552–1563, 2009.
  * [2] R. J. Aumann.  Acceptable points in general cooperative $n$-person games.  In R. D. Luce and A. W. Tucker, editors, Contribution to the Theory of Games IV, pages 287–324. Princeton University Press, 1959.
  * [3] R. Banner and A. Orda.  Bottleneck routing games in communication networks.  IEEE J. Sel. Areas Commun., 25(6):1173–1179, 2007.
  * [4] V. Bilò and C. Vinci.  Coping with Selfishness in Congestion Games—Analysis and Design via LP Duality.  Monographs in Theoretical Computer Science. An EATCS Series. Springer, 2023.
  * [5] R. A. Brualdi.  Comments on bases in dependence structures.  Bull. Austral. Math. Soc., 1:161–167, 1969.
  * [6] M. Drees, M. Feldotto, S. Riechers, and A. Skopalik.  On existence and properties of approximate pure Nash equilibria in bandwidth allocation games.  In M. Hoefer, editor, 8th International Symposium on Algorithmic Game Theory, SAGT 2015, volume 9347 of Lecture Notes in Computer Science, pages 178–189. Springer, 2015.
  * [7] M. Drees, M. Feldotto, S. Riechers, and A. Skopalik.  Pure Nash equilibria in restricted budget games.  J. Comb. Optim., 37(2):620–638, 2019.
  * [8] M. Feldotto, L. Leder, and A. Skopalik.  Congestion games with complementarities.  In D. Fotakis, A. Pagourtzis, and V. T. Paschos, editors, 10th International Conference on Algorithms and Complexity, CIAC 2017, volume 10236 of Lecture Notes in Computer Science, pages 222–233, 2017.
  * [9] M. Feldotto, L. Leder, and A. Skopalik.  Congestion games with mixed objectives.  J. Comb. Optim., 36(4):1145–1167, 2018.
  * [10] T. Harks, M. Hoefer, M. Klimm, and A. Skopalik.  Computing pure Nash and strong equilibria in bottleneck congestion games.  Math. Program., 141(1-2):193–215, 2013.
  * [11] T. Harks, M. Klimm, and R. H. Möhring.  Strong equilibria in games with the lexicographical improvement property.  Int. J. Game Theory, 42(2):461–482, 2013.
  * [12] T. Harks, M. Klimm, and B. Peis.  Sensitivity analysis for convex separable optimization over integral polymatroids.  SIAM J. Optim., 28(3):2222–2245, 2018.
  * [13] F. Kiyosue and K. Takazawa.  A common generalization of budget games and congestion games.  In P. Kanellopoulos, M. Kyropoulou, and A. A. Voudouris, editors, 15th International Symposium on Algorithmic Game Theory, SAGT 2022, volume 13584 of Lecture Notes in Computer Science, pages 258–274. Springer, 2022.
  * [14] N. S. Kukushkin.  Congestion games revisited.  Int. J. Game Theory, 36(1):57–83, 2007.
  * [15] N. S. Kukushkin.  Rosenthal’s potential and a discrete version of the Debreu-Gorman theorem.  Autom. Remote. Control., 76(6):1101–1110, 2015.
  * [16] I. Milchtaich.  Congestion games with player-specific payoff functions.  Game. Econ. Behav., 13:111–124, 1996.
  * [17] D. Monderer and L. S. Shapley.  Potential games.  Games Econ. Behav., 14:124–143, 1996.
  * [18] K. Murota.  Matrices and Matroids for Systems Analysis.  Springer, 2010.
  * [19] N. Nisan, T. Roughgarden, É. Tardos, and V. V. Vazirani, editors.  Algorithmic Game Theory.  Cambridge University Press, 2007.
  * [20] A. Recski.  Matroid Theory and Its Application in Electric Network Theory and in Statics.  Springer, 1989.
  * [21] R. W. Rosenthal.  A class of games possessing pure-strategy Nash equilibria.  Int. J. Game Theory, 2:65–67, 1973.
  * [22] T. Roughgarden.  Twenty Lectures on Algorithmic Game Theory.  Cambridge University Press, 2016.
  * [23] A. Schrijver.  Combinatorial Optimization—Polyhedra and Efficiency.  Springer, 2003.
  * [24] K. Takazawa.  Generalizations of weighted matroid congestion games: pure Nash equilibrium, sensitivity analysis, and discrete convex function.  J. Comb. Optim., 38(4):1043–1065, 2019.
  * [25] K. Takazawa.  Pure nash equilibria in weighted congestion games with complementarities and beyond.  In N. Alechina, V. Dignum, M. Dastani, and J. Sichman, editors, 23rd International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2024. IFAAMAS, 2024.  to appear.