# A Unified Model of Congestion Games with Priorities: Two-Sided Markets with
Ties, Finite and Non-Affine Delay Functions, and Pure Nash Equilibria

Kenjiro Takazawa Department of Industrial and Systems Engineering, Faculty of
Science and Engineering, Hosei University, Tokyo 184-8584, Japan.
<EMAIL_ADDRESS>Supported by JSPS KAKENHI Grant Numbers JP20K11699,
24K02901, JP24K14828, Japan.

(July 2024)

###### Abstract

The study of equilibrium concepts in congestion games and two-sided markets
with ties has been a primary topic in game theory, economics, and computer
science. Ackermann, Goldberg, Mirrokni, Röglin, Vöcking (2008) gave a common
generalization of these two models, in which a player more prioritized by a
resource produces an infinite delay on less prioritized players. While
presenting several theorems on pure Nash equilibria in this model, Ackermann
et al. posed an open problem of how to design a model in which more
prioritized players produce a large but finite delay on less prioritized
players. In this paper, we present a positive solution to this open problem by
combining the model of Ackermann et al. with a generalized model of congestion
games due to Bilò and Vinci (2023). In the model of Bilò and Vinci, the more
prioritized players produce a finite delay on the less prioritized players,
while the delay functions are of a specific kind of affine function, and all
resources have the same priorities. By unifying these two models, we achieve a
model in which the delay functions may be finite and non-affine, and the
priorities of the resources may be distinct. We prove some positive results on
the existence and computability of pure Nash equilibria in our model, which
extend those for the previous models and support the validity of our model.

##  1 Introduction

The study of equilibrium concepts in noncooperative games is a primary topic
in the fields of game theory, economics, and computer science. In particular,
the models of _congestion games_ and _two-sided markets with ties_ have played
important roles in the literature.

_Congestion games_ , introduced by Rosenthal [35] in 1973, represent the human
behaviour of avoiding congestion. Each _player_ chooses a strategy, which is a
set of _resources_. If a resource is shared by many players, then much delay
is imposed on those players. The objective of a player is to minimize the
total delay of the resources in her strategy. Rosenthal [35] proved that every
congestion game is a _potential game_. A noncooperative game is called a
potential game if it admits a _potential function_ , the existence of which
guarantees the existence of a pure Nash equilibrium. Moreover, Monderer and
Shapley [32] proved the converse: every potential game can be represented as a
congestion game. On the basis of these results, congestion games are
recognized as a fundamental model in the study of pure Nash equilibria in
noncooperative games (see, e.g., [7, 36]).

A _two-sided market_ consists of _agents_ and _markets_ , which have
preferences over the other side. Each agent chooses a set of markets. On the
basis of the choices of the agents, the markets determine an assignment of the
players to the markets according to their preferences over the agents. The
objective of a player is to maximize her payoff, which is determined by the
assignment. Typical special cases of a two-sided market are the stable
matching problem and the Hospitals/Residents problem. Since the pioneering
work of Gale and Shapley [14], analyses on equilibria have been a primary
topic in the study of two-sided markets, and a large number of generalized
models have been proposed. In particular, a typical generalization of allowing
_ties_ in the preferences [24] critically changes the difficulty of the
analyses (see [16, 29]), and attracts intensive interests [15, 17, 21, 22, 25,
26, 27, 30, 42].

In 2008, Ackermann, Goldberg, Mirrokni, Röglin, and Vöking [1] introduced a
model which commonly generalizes congestion games and two-sided markets with
ties, and is referred to as _congestion games with priorities_. This model is
briefly described as follows. Each resource $e$ has priorities (preferences)
with ties over the players. Among the players choosing $e$ in their
strategies, only the players most prioritized by $e$ receive a finite delay
from $e$, and the other players receive an infinite delay. In other words,
only the most prioritized players are accepted. It is clear that this model
generalizes congestion games, and it also generalizes a certain model of two-
sided markets with ties, _correlated two-sided markets with ties_.

For several classes of their model, Ackermann et al. [1] presented some
positive results on the existence and computability of pure Nash equilibria.
These results are summarized in Table 1 and will be formally described in
Section 2.2. In _player-specific congestion games_ , each resource $e$ has a
specific delay function $d_{i,e}$ for each player $i$. In a _singleton
congestion game_ , every strategy of every player consists of a single
resource. In a _matroid congestion game_ , the strategies of each player are
the bases of a _matroid_.

Table 1: Results of Ackermann et al. [1]. “NPS” stands for “Non-Player-Specific,” while “PS” stands for “Player-Specific.” “Polynomial BR Dynamics” means that there exists a sequence of a polynomial number of best responses reaching a pure Nash equilibrium.  | Consistent Priorities | Inconsistent Priorities
---|---|---
NPS |  | Polynomial BR Dynamics
---
\- Singleton Game (Theorem 2.6)
\- Matroid Game (Theorem 2.10)
| Potential Function
---
\- Singleton Game (Theorem 2.7)
\- Matroid Game (Theorem 2.11)
PS | — |  | Potential Function
---
\- Two-Sided Singleton Market (Theorem 2.9)
\- Two-Sided Matroid Market (Theorem 2.13)
Polynomial Algorithm
\- Singleton Game (Theorem 2.8)
\- Matroid Game (Theorem 2.12)

Meanwhile, Ackermann et al. [1] posed an open question of how to design a
model in which the less prioritized players receive a finite delay caused by
the more prioritized players. We appreciate the importance of this question
because such a model can include the many-to-many models of the stable
matching problem [4, 5, 9, 12, 38, 39] (see also [29]). In congestion games,
the fact that each resource accepts multiple players is essential, since the
number of those players determine the cost of the resource. In the models of
stables matchings in which each market accepts multiple agents, the
preferences of the markets indeed affect the stability of the matchings, but
it is not the case that only the most preferred agents are accepted. Thus,
such a generalization of congestion games with priorities suggested in [1] is
crucial to attain a more reasonable generalization of the stable matching
problem.

The contributions of the paper are described as follows. We first point out
that a generalized model of congestion games by Bilò and Vinci [6] partially
answers to the question posed by Ackermann et al. [1]. In their model, the
players more prioritized by a resource indeed produce a finite delay on the
less prioritized players. Meanwhile, this model only covers a special case of
the model of Ackermann et al. [1] in which the delay functions are of a
specific kind of affine functions and all resources have the same priorities
over the players. We refer to the model of [6] as a _priority-based affine
congestion game with consistent priorities_.

A main contribution of this paper is to design a model which gives a positive
and full answer to the open problem of Ackermann et al. [1]. By unifying the
models of Ackermann et al. [1] and Bilò and Vinci [6], we present a model of
congestion games with priorities in which the more prioritized players produce
a finite delay on the less prioritized players, the delay function may be non-
affine, and the priorities of the resources may be inconsistent. We refer to
our model as a _priority-based congestion games with (in)consistent
priprities_. We then prove some positive results on the existence and
computability of pure Nash equilibria in our model, which extend those for the
previous models [1, 6] and support the validity of our model. Our technical
results are summarized in Table 2.

Table 2: Summary of Our Results. “NPS” stands for “Non-Player-Specific,” while “PS” stands for “Player-Specific.” “Polynomial BR Dynamics” means that there exists a sequence of a polynomial number of better responses reaching a pure Nash equilibrium. “PNE” stands for “Pure Nash Equilibrium.”  | Consistent Priorities | Inconsistent Priorities
---|---|---
NPS |  | Polynomial BR Dynamics
---
\- Singleton Game (Theorem 4.1)
\- Matroid Game (Theorem 6.2)
Existence of a PNE
\- General Game (Theorem 6.7)
| Potential Function
---
\- Singleton Game (Theorem 4.4)
\- Matroid Game (Theorem 6.3)
PS |  | Polynomial BR Dynamics
---
\- Singleton Game (Theorem 4.1)
\- Matroid Game (Theorem 6.2)
| Potential Function
---
\- Two-Sided Singleton Market (Theorem 5.3)
\- Two-Sided Matroid Market (Theorem 6.5)
Existence of a PNE
\- Singleton Game (Theorem 4.5)
\- Matroid Game (Theorem 6.4)

The rest of the paper is organized as follows. We review previous results in
Section 2. Emphases are put on a formal description of the model and results
of congestion games with priorities [1]. In Section 3, we describe our model
of priority-based congestion games. In Section 4, we present some positive
results on pure Nash equilibria in priority-based singleton congestion games.
Section 5 is devoted to a description of how correlated two-sided markets with
ties are generalized in our model. Finally, in Section 6, we deal with
priority-based congestion games which are not singleton games.

##  2 Preliminaries

Let ${\mathbb{Z}}$ denote the set of the integers, and ${\mathbb{R}}$ that of
the real numbers. Subscripts $+$ and ${++}$ represent that the set consists of
nonnegative numbers and positive numbers, respectively. For instance,
${\mathbb{R}}_{+}$ denotes the set of the nonnegative real numbers and
${\mathbb{Z}}_{++}$ that of the positive integers.

###  2.1 Congestion Games

A congestion game is described by a tuple

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

Here, $N=\\{1,\ldots,n\\}$ denotes the set of the players and $E$ that of the
resources. Each player $i\in N$ has her _strategy space_
$\mathcal{S}_{i}\subseteq 2^{E}$, and chooses a _strategy_
$S_{i}\in\mathcal{S}_{i}$. The collection $(S_{1},\ldots,S_{n})$ of the chosen
strategies is called a _strategy profile_. For a resource $e\in E$ and a
strategy profile $S=(S_{1},\ldots,S_{n})$, let $N_{e}(S)\subseteq N$ denote
the set of players whose strategy includes $e$, and let
$n_{e}(S)\in{\mathbb{Z}}_{+}$ denote the size of $N_{e}(S)$, i.e.,

$N_{e}(S)=\\{i\in N\colon e\in S_{i}\\},\quad n_{e}(S)=|N_{e}(S)|.$

Each resource $e\in E$ has its _delay function_
$d_{e}\colon{\mathbb{Z}}_{++}\to{\mathbb{R}}_{+}$. In a strategy profile $S$,
the function value $d_{e}(n_{e}(S))$ represents the delay of a resource $e\in
E$. The objective of each player is to minimize her cost, which is the sum of
the delays of the resources in her strategy. Namely, the cost $\gamma_{i}(S)$
imposed on a player $i\in N$ in a strategy profile $S$ is defined as
$\gamma_{i}(S)=\sum_{e\in S_{i}}d_{e}(n_{e}(S))$, which is to be minimized.

For a strategy profile $S=(S_{1},\ldots,S_{n})$ and a player $i\in N$, Let
$S_{-i}$ denote a collection of the strategies in $S$ other than $S_{i}$,
namely $S_{-i}=(S_{1},\ldots,S_{i-1},S_{i+1},\ldots,S_{n})$. A _better
response_ of a player in a strategy profile is a change of her strategy so
that her cost strictly decreases. Namely, when $i\in N$ changes her strategy
from $S_{i}$ to $S_{i}^{\prime}$ in a strategy profile $S$, it is a better
response if $\gamma_{i}(S_{-i},S_{i}^{\prime})<\gamma_{i}(S)$. In particular,
a better response from $S_{i}$ to $S_{i}^{\prime}$ is a _best response_ if
$S_{i}^{\prime}$ minimizes $\gamma_{i}(S_{-i},S_{i}^{\prime})$. A _pure Nash
equilibrium_ is a strategy profile in which no player has a better response.
Namely, a strategy profile $S$ is a pure Nash equilibrium if

$\displaystyle\gamma_{i}(S)\leq\gamma_{i}(S_{-i},S_{i}^{\prime})\quad\mbox{for
each player $i\in N$ and each of her strategy
$S_{i}^{\prime}\in\mathcal{S}_{i}$}.$

A _potential function_ $\Phi$ is one which is defined on the set of the
strategy profiles and satisfies

$\Phi(S_{-i},S_{i}^{\prime})-\Phi(S)=\gamma_{i}(S_{-i},S_{i}^{\prime})-\gamma_{i}(S)$

for each strategy profile $S$, each player $i\in N$, and each strategy
$S_{i}^{\prime}\in\mathcal{S}$. The existence of a potential function implies
the existence of a pure Nash equilibrium, because a strategy profile
minimizing the potential function must be a pure Nash equilibrium. A game
admitting a potential function is referred to as a _potential game_. The
following theorem is a primary result on congestion games, stating that each
congestion game is a potential game and vice versa.

######  Theorem 2.1 ([32, 35]).

A congestion game is a potential game, and hence possesses a pure Nash
equilibrium. Moreover, every potential game is represented as a congestion
game.

Hereafter, we assume that each delay function $d_{e}$ ($e\in E$) is
monotonically nondecreasing, i.e., $d_{e}(x)\leq d_{e}(x^{\prime})$ if
$x<x^{\prime}$.

Study on congestion games from the viewpoint of _algorithmic game theory_ [7,
34, 36] has appeared since around 2000. For singleton congestion games, Ieong,
McGrew, Nudelman, Shoham, and Sun [23] proved that a pure Nash equilibrium in
a singleton congestion game can be attained after a polynomial number of
better responses.

######  Theorem 2.2 ([23]).

In a singleton congestion game, starting from an arbitrary strategy profile, a
pure Nash equilibrium is attained after a polynomial number of better (hence,
best)responses.

This theorem is followed by a large number of extensions. Recall that a
_player-specific congestion game_ is one in which each resource $e\in E$ has a
delay function $d_{i,e}\colon{\mathbb{Z}}_{++}\to{\mathbb{R}}_{+}$ specific to
each player $i\in N$. Milchtaich [31] proved the following theorem for player-
specific singleton congestion games.

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

In a player-specific singleton congestion game, there exists a sequences of
polynomial number of best responses starting from an arbitrary strategy
profile and reaching a pure Nash equilibrium.

Note that Theorem 2.3 differs from Theorem 2.2 in that not any sequence of
best responses reaches to a pure Nash equilibrium.

A significant work along this line is due to Ackermann, Röglin, and Vöking [2,
3], who employed the discrete structure of _matroids_ into congestion games.
For a finite set $E$ and its subset family $\mathcal{S}\subseteq 2^{E}$, the
pair $(E,\mathcal{S})$ is a _matroid_ if $\mathcal{S}\neq\emptyset$ and

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

A set in $\mathcal{S}$ is referred to as a _base_. It follows from (1) that
all bases in $\mathcal{S}$ has the same cardinality, which is referred to as
the _rank_ of the matroid $(E,\mathcal{S})$.

A congestion game $(N,E,(\mathcal{S}_{i})_{i\in N},(d_{e})_{e\in E})$ is
referred to as a _matroid congestion game_ if $(E,\mathcal{S}_{i})$ is a
matroid for every player $i\in N$. It is straightforward to see that a
singleton congestion game is a spacial case of a matroid congestion game.
Ackermann, Röglin, and Vöking [2, 3] proved the following extensions of
Theorems 2.2 and 2.3 to matroid congestion games.

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

In a matroid congestion game, starting from an arbitrary strategy profile, a
pure Nash equilibrium is attained after a polynomial number of best responses.

######  Theorem 2.5 ([3]).

In a player-specific matroid congestion game, there exists a sequence of
polynomial number of better responses starting from an arbitrary strategy
profile and reaching a pure Nash equilibrium.

Since these works, matroid congestion games have been recognized as a well-
behaved class of congestion games, and study on more generalized and related
models followed. In the models of _congestion games with mixed objectives_
[11] and _congestion games with complementarities_ [10, 41], the cost on a
player is not necessarily the sum of the delays in her strategy. A _budget
game_ [8] is a variant of a congestion game, and their common generalization
is proposed in [28]. A _resource buying game_ [19, 40] is another kind of a
noncooperative game in which the players share the resources. In all of the
above models, the fact that $(E,\mathcal{S}_{i})$ is a matroid for each player
$i$ plays a key role to guaranteeing the existence of a pure Nash equilibrium.
A further generalized model in which the strategy space is represented by a
_polymatroid_ is studied in [18, 20]. A different kind of relation between
matroids and congestion games is investigated in [13].

###  2.2 Congestion Games with Priorities

Ackermann et al. [1] offered a model which commonly generalizes congestion
games and a certain class of two-sided markets with ties. This model is
described by a tuple

$(N,E,(\mathcal{S}_{i})_{i\in N},(p_{e})_{e\in E},(d_{e})_{e\in E}),$

in which the player set $N$, the resource set $E$, the strategy spaces
$\mathcal{S}_{i}\subseteq 2^{E}$ ($i\in N$), and the delay functions
$d_{e}\colon{\mathbb{Z}}_{++}\to{\mathbb{R}}_{+}$ ($e\in E$) are the same as
those in the classical model in Section 2.1. What is specific to this model is
that each resource $e\in E$ has a _priority function_ $p_{e}\colon
N\to{\mathbb{Z}}_{++}$. If $p_{e}(i)<p_{e}(j)$ for players $i,j\in N$, then
the resource $e$ prefers $i$ to $j$.

In a strategy profile $S=(S_{1},\ldots,S_{n})$, the delay of $e$ imposed on
each player in $N_{e}(S)$ is determined in the following way. Define
$p^{*}_{e}(S)\in{\mathbb{Z}}_{++}\cup\\{+\infty\\}$ by

$\displaystyle p^{*}_{e}(S)=\begin{cases}\min\\{p_{e}(i)\colon i\in
N_{e}(S)\\}&\mbox{if $N_{e}(S)\neq\emptyset$},\\\ +\infty&\mbox{if
$N_{e}(S)=\emptyset$}.\end{cases}$

For a positive integer $q$, define $n_{e}^{q}(S)\in{\mathbb{Z}}_{+}$ by

$\displaystyle n_{e}^{q}(S)=\left|\\{i\in N_{e}(S)\colon
p_{e}(i)=q\\}\right|.$ (2)

Now the delay imposed on a player $i\in N_{e}(S)$ by the resource $e$ is
defined as

$\displaystyle\begin{cases}d_{e}\left(n_{e}^{p_{e}^{*}(S)}(S)\right)&\mbox{if
$p_{e}(i)=p_{e}^{*}(S)$},\\\ +\infty&\mbox{if
$p_{e}(i)>p_{e}^{*}(S)$}.\end{cases}$

This model is referred to as a _congestion game with priorities_. A special
case in which all resources have the same priority function is called a
_congestion game with consistent priorities_. The general model is often
referred to as a _congestion game with inconsistent priorities_.

It is straightforward to see that the model of congestion games with
priorities includes congestion games. An instance
$(N,E,(\mathcal{S}_{i})_{i\in N},(d_{e})_{e\in E})$ of a congestion game
reduces to a congestion game $(N,E,(\mathcal{S}_{i})_{i\in N},(d_{e})_{e\in
E})$ reduces to a congestion game $(N,E,(\mathcal{S}_{i})_{i\in
N},(p_{e})_{e\in E},(d_{e})_{e\in E})$ with priorities in which all resources
have the same constant priority function. As mentioned above, the model of
congestion games with priorities also includes _correlated two-sided markets
with ties_. See Section 2.2.2 for details.

####  2.2.1 Singleton Games

For singleton congestion games with consistent priorities, Ackermann et al.
[1] proved the following theorem on the basis of Theorem 2.2.

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

In a singleton congestion game with consistent priorities, there exists a
sequence of a polynomial number of best responses starting from an arbitrary
strategy profile and reaching a pure Nash equilibrium.

To the best of our knowledge, an extension of Theorem 2.3 to player-specific
delay functions is missing in the literature, and will be discussed in a more
generalized form in Section 4.1.

Ackermann et al. [1] further proved that every singleton congestion game with
inconsistent priorities is a potential game.

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

A singleton congestion game with inconsistent priorities is a potential game,
and hence possesses a pure Nash equilibrium.

We remark that the potential function establishing Theorem 2.7 obeys a
generalized definition of potential functions. It maps a strategy profile to a
sequence of vectors, which lexicographically decreases by a better response.
The details will appear in our proof of Theorem 4.4, which extends Theorem 2.7
to priority-based singleton congestion games.

For player-specific congestion games with inconsistent priorities, Ackermann
et al. [1] designed a polynomial-time algorithm for constructing a pure Nash
equilibrium. Let $n$ denote the number of the players and $m$ that of the
resources.

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

A player-specific singleton congestion game with inconsistent priorities
possesses a pure Nash equilibrium, which can be computed in polynomial time
with $O(n^{3}m)$ strategy changes.

####  2.2.2 Correlated Two-Sided Markets with Ties

Here we describe a _correlated to two-sided market with ties_ [1], and see
that it can be represented as a player-specific congestion game with
inconsistent priorities. For unity, we apply the terminology of congestion
games to two-sided markets. For example, we use the terms players and
resources instead of agents and markets. We also assume that the objective of
a player is to minimize her delay, instead of to maximize her payoff.

A _correlated two-sided market with ties_ is represented by a tuple

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

For each pair $(i,e)$ of a player $i\in N$ and a resource $e\in E$, a _cost_
$c_{i,e}\in{\mathbb{R}}_{+}$ is associated. The costs implicitly determine the
preferences of the players, since the objective of a player is to minimize her
cost. Moreover, each resource $e$ also prefer players with smaller costs, and
in particular only accepts the players with smallest cost, which is formally
described in the following way.

Let $S=(S_{1},\ldots,S_{n})$ be a strategy profile, and let $e\in E$ be a
resource. Let $c^{*}_{e}(S)\in{\mathbb{R}}_{+}$ be the minimum cost associated
with a player in $N_{e}(S)$ and $e$, i.e., $c_{e}^{*}(S)=\min\\{c_{i,e}\colon
i\in N_{e}(S)\\}$. Let $N_{e}^{*}(S)\subseteq N_{e}(S)$ denote the set of the
players in $N_{e}(S)$ with cost $c_{e}^{*}(S)$, and let
$|N_{e}^{*}(S)|=n_{e}^{*}(S)$. Namely,

$\displaystyle c^{*}_{e}(S)=\min\\{c_{i,e}\colon i\in N_{e}(S)\\},\quad
N_{e}^{*}(S)=\\{i\in N_{e}(S)\colon c_{i,e}=c^{*}_{e}(S)\\},\quad
n_{e}^{*}(S)=|N_{e}^{*}(S)|.$

Each player in $N_{e}(S)\setminus N_{e}^{*}(S)$ receives an infinite cost from
$e$. The cost on a player $i\in N_{e}^{*}(S)$ satisfies that it is
nonincreasing with respect to $n_{e}^{*}(S)$ and is equal to $c^{*}_{e}(S)$ if
$n_{e}^{*}(S)=1$, i.e., $i$ is the only player in $N_{e}^{*}(S)$. This is
represented by a bivariate delay function
$d_{e}:{\mathbb{R}}_{+}\times{\mathbb{Z}}_{++}\to{\mathbb{R}}_{+}$ such that,
for each $x\in{\mathbb{R}}_{+}$, $d_{e}(x,1)=x$ and $d_{e}(x,y)$ is
nondecreasing with respect to $y$. In summary, the cost imposed on a player
$i\in N_{e}(S)$ by $e$ is equal to

$\displaystyle\begin{cases}d_{e}(c_{e}^{*}(S),n_{e}^{*}(S))&(i\in
N_{e}^{*}(S)),\\\ +\infty&(i\in N_{e}(S)\setminus N_{e}^{*}(S)).\end{cases}$
(3)

A correlated two-sided market $(N,E,(\mathcal{S}_{i}),(c_{i,e}),(d_{e}))$ with
ties reduces to a player-specific congestion game with inconsistent
priorities. For a resource $e\in E$, construct a priority function
$p_{e}\colon N\to{\mathbb{Z}}_{++}$ satisfying that

$\displaystyle\mbox{$p_{e}(i)<p_{e}(j)$ if and only if $c_{i,e}<c_{j,e}$ for
each $i,j\in N$}.$ (4)

Then, for each pair $(i,e)$ of a player $i\in N$ and a resource $e\in E$,
define a player-specific delay function
$d^{\prime}_{i,e}\colon{\mathbb{Z}}_{++}\to{\mathbb{R}}_{+}$ by

$\displaystyle
d^{\prime}_{i,e}(y)=d_{e}(c_{i,e},y)\quad(y\in{\mathbb{Z}}_{++}).$

We refer to a correlated two-sided markets with ties in which each strategy of
each player is a singleton as a _correlated two-sided singleton markets with
ties_. It follows from the above reduction that Theorem 2.8 applies to a
correlated two-sided singleton markets with ties. Ackermann et al. [1] proved
a stronger result that a correlated two-sided singleton markets with ties has
a potential function.

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

A correlated two-sided singleton market with ties is a potential game, and
hence possesses a pure Nash equilibrium.

####  2.2.3 Extension to Matroid Games

Finally, Ackermann et al. [1] provided the following extensions of Theorems
2.6–2.9 from singleton games to matroid games. For a matroid game, define its
_rank_ $r$ as the the maximum rank of the matroids forming the strategy spaces
of all players.

A better response of a player $i\in N$ in a strategy profile $S$ from a
strategy $S_{i}$ to another strategy $S_{i}^{\prime}$ is referred to as a
_lazy better response_ if if there exists a sequence
$(S^{0}_{i},S^{1}_{i},...,S^{k}_{i})$ of strategies of $i$ such that
$S^{0}_{i}=S_{i}$, $S^{k}_{i}=S_{i}^{\prime}$, $|S^{k^{\prime}+1}_{i}\setminus
S^{k^{\prime}}_{i}|=1$ and the cost on $i$ in a strategy profile
$(S_{-i},S^{k^{\prime}+1}_{i})$ is strictly smaller than that in
$(S_{-i},S^{k^{\prime}}_{i})$ for each $k^{\prime}=0,1,\ldots,k-1$. A
_potential game with respect to lazy better responses_ is a game admitting a
potential function which strictly decreases by a lazy better response.

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

In a matroid congestion game with consistent priorities, there exists a
sequence of a polynomial number of best responses starting from an arbitrary
strategy profile and reaching a pure Nash equilibrium.

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

A matroid congestion game with inconsistent priorities is a potential game
with respect to lazy better responses, and hence possesses a pure Nash
equilibrium.

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

A player-specific matroid congestion game with inconsistent priorities
possesses a pure Nash equilibrium, which can be computed in polynomial time
with $O(n^{3}mr)$ strategy changes.

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

A correlated two-sided matroid market with ties is a potential game with
respect to lazy better responses, and hence possesses a pure Nash equilibrium.

###  2.3 Priority-Based Affine Congestion Games

In this subsection, we describe the model of priority-based affine congestion
games with consistent priorities [6], by using the terminology of congestion
games with priorities. A priority-based affine congestion game with consistent
priorities is described by a tuple

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

Again, $N$ and $E$ denote the set of the players and that of the resources,
respectively, and $\mathcal{S}_{i}\subseteq 2^{E}$ is the strategy space of a
player $i\in N$. Note that all resources have the same priority function
$p\colon N\to{\mathbb{Z}}_{++}$. Each resource $e\in E$ is associated with two
nonnegative real numbers $\alpha_{e},\beta_{e}\in{\mathbb{R}}_{+}$, which
determine the delay function of $e$ in the following manner.

Let $S$ be a strategy profile, $e\in E$ be a resource, and
$q\in{\mathbb{Z}}_{+}$ a positive integer. Define
$n_{e}^{q}(S)\in{\mathbb{Z}}_{+}$ as in (2), in which $p_{e}$ is replaced by
$p$. Similarly, define $n_{e}^{<q}(S)\in{\mathbb{Z}}_{+}$ by

$\displaystyle n_{e}^{<q}(S)\ {}$ $\displaystyle{}=\ \left|\\{i\in
N_{e}(S)\colon p(i)<q\\}\right|.$ (5)

Now the delay imposed on a player $i\in N_{e}(S)$ by $e$ is defined as

$\displaystyle\alpha_{e}\cdot\left(n_{e}^{<p(i)}(S)+\frac{n_{e}^{p(i)}(S)+1}{2}\right)+\beta_{e},$
(6)

which is interpreted in the following way. The delay imposed on player $i\in
N_{e}(S)$ by $e\in E$ is affected by the $n_{e}^{<p(i)}(S)$ players in
$N_{e}(S)$ more prioritized than $i$. It is also affected by the
$n_{e}^{p(i)}(S)$ players with the same priority as $i$, which is reflected to
$(n_{e}^{p(i)}(S)+1)/2$ in (6). This value is the expected number of the
players more or equally prioritized than $i$ when the ties of the
$n_{e}^{p(i)}(S)$ players are broken uniformly at random.

Bilò and Vinci [6] proved that every priority-based affine congestion game
with consistent priorities has a pure Nash equilibrium, and that it can be
constructed by finding a pure Nash equilibrium of the most prioritized
players, and then inductively extending the pure Nash equilibrium of the
players with up to the $k$-th priority to those with up to the $(k+1)$-st
priority. In each step, the game restricted to the players with the $(k+1)$-st
priority is a potential game.

######  Theorem 2.14 ([6]).

A priority-based affine congestion game with consistent priorities possesses a
pure Nash equilibrium.

We should remark that Bilò and Vinci [6] further conducted an elaborated
analysis on the price of anarchy and the price of stability of the pure Nash
equilibria of this model, which might be a main contribution of their paper.

##  3 Our Model

We first point out that the model of Bilò and Vinci [6] described in Section
2.3 partially answers to the open question of Ackermann et al. [1]. Indeed,
the delay (6) of a player $i\in N_{e}(S)$ is finitely affected by the more
prioritized players in $N_{e}(S)$. Meanwhile, compared to the model of
Ackermann et al. [1], the delay (6) is specific in that it is a particular
affine function of $n_{e}^{<p(i)}(S)$ and $n_{e}^{p(i)}(S)$, and the
priorities of the resources are consistent. Below we resolve these points by
providing a common generalization of the two models, which provides a full
answer to the open question in [1].

Our model is represented by a tuple

$(N,E,(\mathcal{S}_{i})_{i\in N},(p_{e})_{e\in E},(d_{e})_{e\in E}),$

which is often abbreviated as $(N,E,(\mathcal{S}_{i}),(p_{e}),(d_{e}))$.
Again, $N$ and $E$ denote the sets of players and resources, respectively,
each player $i\in N$ has her strategy space $\mathcal{S}_{i}\subseteq 2^{E}$,
and each resource $e\in E$ has a priority function $p_{e}\colon
N\to{\mathbb{Z}}_{++}$.

Let $S=(S_{1},\ldots,S_{n})$ be a strategy profile, $i\in N$, and $e\in
S_{i}$. Reflecting the delay function (6), our delay function
$d_{e}\colon{\mathbb{Z}}_{+}\times{\mathbb{Z}}_{++}\to{\mathbb{R}}_{+}$ ($e\in
E$) is a bivariate function with variables $n_{e}^{<p_{e}(i)}(S)$ and
$n_{e}^{p_{e}(i)}(S)$. Namely, the delay imposed on $i$ by $e$ is described as

$\displaystyle d_{e}\left(n_{e}^{<p_{e}(i)}(S),n_{e}^{p_{e}(i)}(S)\right).$
(7)

We assume that each delay function $d_{e}$ ($e\in E$) has the following
properties:

$\displaystyle d_{e}(x,y)\leq d_{e}(x^{\prime},y)$ $\displaystyle(\mbox{if
$x<x^{\prime}$}),$ (8) $\displaystyle d_{e}(x,y)\leq d_{e}(x,y^{\prime})$
$\displaystyle(\mbox{if $y<y^{\prime}$}),$ (9) $\displaystyle d_{e}(x,y)\leq
d_{e}(x+y-1,1)$ $\displaystyle(\mbox{for each $x\in{\mathbb{Z}}_{+}$ and
$y\in{\mathbb{Z}}_{++}$}).$ (10)

Property (8) and (9) mean that the delay function $d_{e}$ is nondecreasing
with respect to $n_{e}^{<p_{e}(i)}(S)$ and $n_{e}^{p_{e}(i)}(S)$,
respectively. These properties reflect the monotonicity of the delay functions
in the previous models. Property (10) means that the cost on $i$ increases if
the $n_{e}^{p_{e}(i)}(S)-1$ players in $N_{e}(S)$ with the same priority as
$i$ are replaced by the same number of more prioritized players. This property
captures the characteristic of the models of [1, 6] that prioritized players
produce more delays than those with the same priority.

We refer to our model as a _priority-based congestion game with inconsistent
priorities_ , or _priority-based congestion game_ for short. If the resources
have the same priority function, then the game is referred to as a _priority-
based congestion game with consistent priorities_.

A priority-based affine congestion game $(N,E,(\mathcal{S}_{i})_{i\in
N},p,(\alpha_{e},\beta_{e})_{e\in E})$ with consistent priority [6] is
represented as a priority-based congestion game with consistent priorities $p$
and delay function
$d_{e}\colon{\mathbb{Z}}_{+}\times{\mathbb{Z}}_{++}\to{\mathbb{R}}_{+}$ ($e\in
E$) defined as in (6), namely

$\displaystyle
d_{e}\left(n_{e}^{<p_{e}(i)}(S),n_{e}^{p_{e}(i)}(S)\right)=\alpha_{e}\left(n_{e}^{<p(i)}(S)+\frac{n_{e}^{p(i)}(S)+1}{2}\right)+\beta_{e}.$
(11)

It is not difficult to see that the delay function $d_{e}$ in (11) satisfies
the properties (8)–(10).

A congestion game with inconsistent priorities [1] is also a special case of a
priority-based congestion game. Given a congestion game
$(N,E,(\mathcal{S}_{i})_{i\in N},(p_{e})_{e\in E},(d_{e})_{e\in E})$ with
priorities, define a delay function
$d_{e}^{\prime}\colon{\mathbb{Z}}_{+}\times{\mathbb{Z}}_{++}\to{\mathbb{R}}$
of a priority-based congestion game by

$\displaystyle d_{e}^{\prime}(x,y)=\begin{cases}+\infty&(x\geq 1),\\\
d_{e}(y)&(x=0).\end{cases}$ (12)

Again, the delay function $d_{e}^{\prime}$ in (12) satisfies the properties
(8)–(10) if $d_{e}$ is a nondecreasing function. The properties (8) and (9)
are directly derived. The property (10) follows from the fact that
$d_{e}^{\prime}(x+y-1,1)\neq+\infty$ only if $(x,y)=(0,1)$, and in that case
both $d_{e}^{\prime}(x,y)$ and $d_{e}^{\prime}(x+y-1,1)$ is equal to
$d_{e}^{\prime}(0,1)=d_{e}(1)$.

##  4 Priority-Based Singleton Congestion Games

In this section, we present some theorems on pure Nash equilibria in singleton
games in our model.

###  4.1 Consistent Priorities

In this subsection, we present a theorem on pure Nash equilibria in priority-
based player-specific singleton congestion games with consistent priorities
(Theorem 4.1). This theorem is not only an extension of Theorems 2.2 and 2.6,
which concern pure Nash equilibria in non-player-specific singleton congestion
games, but also implies the existence of pure Nash equilibria in player-
specific congestion games with consistent priorities (Corollary 4.2), which is
missing in the literature.

Hereafter, some theorems are marked with $(\star)$, meaning that their proofs
appear in Appendix.

######  Theorem 4.1 ($\star$).

In a priority-based player-specific singleton congestion game
$G=(N,E,(\mathcal{S}_{i}),p,(d_{i,e}))$ with consistent priorities, there
exists a sequence of polynomial number of better responses starting from an
arbitrary strategy profile and reaching a pure Nash equilibrium.

The following corollary is a direct consequence of Theorem 4.1.

######  Corollary 4.2.

In a player-specific singleton congestion game with consistent priorities,
there exists a sequences of polynomial number of better responses starting
from an arbitrary strategy profile and reaching a pure Nash equilibrium.

######  Remark 4.3.

Corollary 4.2 does not imply that a pure Nash equilibrium in a priority-based
singleton congestion games which is not player-specific is obtained from an
_arbitrary_ sequence of best responses. This is because, as described in the
proof for Theorem 4.1, the order of the players in the sequence is specified
by the priority function.

###  4.2 Inconsistent Priorities

In this subsection, we investigate priority-based singleton congestion games
with inconsistent priorities. We first prove the following extension of
Theorem 2.7.

######  Theorem 4.4.

A priority-based singleton congestion game
$(N,E,(\mathcal{S}_{i}),(p_{e}),(d_{e}))$ with inconsistent priorities is a
potential game, and hence possesses a pure Nash equilibrium.

###### Proof.

For each strategy profile $S=(e_{1},\ldots,e_{n})$, define its potential
$\Phi(S)\in({\mathbb{R}}_{+}\times{\mathbb{Z}}_{++})^{n}$ as follows. Let
$e\in E$ be a resource, and let $Q_{e}(S)=\\{q_{1},...,q_{k^{*}}\\}$ be a set
of integers such that $Q_{e}(S)=\\{q\colon n_{e}^{q}(S)>0\\}$ and
$q_{1}<\cdots<q_{k^{*}}$. The resource $e\in E$ contributes the following
$n_{e}(S)$ vectors in ${\mathbb{R}}_{+}\times{\mathbb{Z}}_{++}$ to $\Phi(S)$:

$\displaystyle{}(d_{e}(0,1),\,q_{1}),\ldots,(d_{e}(0,n_{e}^{q_{1}}(S)),\,q_{1}),$
$\displaystyle{}(d_{e}(n_{e}^{q_{1}}(S),1),\,q_{2}),\ldots,(d_{e}(n_{e}^{q_{1}}(S),n_{e}^{q_{2}}(S)),\,q_{2}),$
$\displaystyle{}\ldots,$
$\displaystyle{}\left(d_{e}\left(n_{e}^{<q_{k}}(S),1\right),\,q_{k}\right),\ldots,\left(d_{e}\left(n_{e}^{<q_{k}}(S),n_{e}^{q_{k}}(S)\right),\,q_{k}\right),$
$\displaystyle{}\ldots,$
$\displaystyle{}\left(d_{e}\left(n_{e}^{<q_{k^{*}}}(S),1\right),\,q_{k^{*}}\right),\ldots,\left(d_{e}\left(n_{e}^{<{q_{k^{*}}}}(S),n_{e}^{q_{k^{*}}}(S)\right),\,q_{k^{*}}\right).$
(13)

For two vectors
$(x,y),(x^{\prime},y^{\prime})\in{\mathbb{R}}_{+}\times{\mathbb{Z}}_{++}$, we
define a lexicographic order
$(x,y)\operatorname{\preceq_{lex}}(x^{\prime},y^{\prime})$ if

$\displaystyle{}x<x^{\prime},\quad\mbox{or}\quad x=x^{\prime}\mbox{ and }y\leq
y^{\prime}.$

The strict relation $(x,y)\operatorname{\prec_{lex}}(x^{\prime},y^{\prime})$
means that $(x,y)\operatorname{\preceq_{lex}}(x^{\prime},y^{\prime})$ and
$(x,y)\neq(x^{\prime},y^{\prime})$ hold.

The potential $\Phi(S)$ is obtained by ordering the $n$ vectors contributed by
all resources in the lexicographically nondecreasing order. We remark that the
order in (13) is lexicographically nondecreasing, which can be derived from
(8)–(10) as follows. It follows from (9) that

$\displaystyle d_{e}(n_{e}^{<q_{k}}(S),y)\leq
d_{e}(n_{e}^{<q_{k}}(S),y+1)\quad\mbox{($k=1,\ldots,k^{*}$,
$y=1,\ldots,q_{k-1}$)},$ (14)

and from (8) and (10) that

$\displaystyle d_{e}\left(n_{e}^{<q_{k}}(S),n_{e}^{q_{k}}(S)\right)\leq
d_{e}\left(n_{e}^{<q_{k+1}}(S)-1,1\right)\leq
d_{e}\left(n_{e}^{<q_{k+1}}(S),1\right)\quad\mbox{($k=1,\ldots,k^{*}-1$)}.$
(15)

We then define a lexicographic order over the potentials. For strategy
profiles $S$ and $S^{\prime}$, where

$\displaystyle\Phi(S)=((x_{1},y_{1}),\ldots,(x_{n},y_{n})),\quad\Phi(S^{\prime})=((x^{\prime}_{1},y^{\prime}_{1}),\ldots,(x^{\prime}_{n},y^{\prime}_{n})),$

define $\Phi(S^{\prime})\operatorname{\preceq_{lex}}\Phi(S)$ if there exists
an integer $\ell$ with $1\leq\ell\leq n$ such that

$\displaystyle{}\mbox{$(x^{\prime}_{\ell^{\prime}},y^{\prime}_{\ell^{\prime}})=(x_{\ell^{\prime}},y_{\ell^{\prime}})$
for each $\ell^{\prime}<\ell$, and
$(x^{\prime}_{\ell},y^{\prime}_{\ell})\operatorname{\prec_{lex}}(x_{\ell},y_{\ell})$}.$

The strict relation $\Phi(S^{\prime})\operatorname{\prec_{lex}}\Phi(S)$ means
that $\Phi(S^{\prime})\operatorname{\preceq_{lex}}\Phi(S)$ and
$\Phi(S^{\prime})\neq\Phi(S)$ hold.

Suppose that a player $i$ has a better response in a strategy profile $S$,
which changes her strategy from $e$ to $e^{\prime}$. Let
$S^{\prime}=(S_{-i},e^{\prime})$. Below we show that
$\Phi(S^{\prime})\operatorname{\prec_{lex}}\Phi(S)$, which completes the
proof.

Let $p_{e}(i)=q$ and $p_{e^{\prime}}(i)=q^{\prime}$. Since the delay imposed
on $i$ becomes smaller due to the better response, it holds that

$\displaystyle
d_{e^{\prime}}(n_{e^{\prime}}^{<q^{\prime}}(S),n_{e^{\prime}}^{q^{\prime}}(S)+1)<d_{e}(n_{e}^{<q}(S),n_{e}^{q}(S)).$
(16)

Note that $e^{\prime}$ contributes a vector

$\displaystyle(d_{e^{\prime}}(n_{e^{\prime}}^{<q^{\prime}}(S),n_{e^{\prime}}^{q^{\prime}}(S)+1),\,q^{\prime})$
(17)

to $\Phi(S^{\prime})$ but not to $\Phi(S)$. To prove
$\Phi(S^{\prime})\operatorname{\prec_{lex}}\Phi(S)$, it suffices to show that
a vector belonging to $\Phi(S)$ but not to $\Phi(S^{\prime})$ is
lexcographically larger than the vector (17).

First, consider the vectors in $\Phi(S)$ contributed by $e$. Let
$Q_{e}(S)=\\{q_{1},\ldots,q_{k^{*}}\\}$, where $q_{1}<\cdots<q_{k^{*}}$. The
better response of $i$ changes the vectors in $\Phi(S)$ whose second component
is larger than $q$, because the first argument of the delay function $d_{e}$
decreases by one. If $q=q_{k^{*}}$, then those vectors do not exist and thus
we are done. Suppose that $q=q_{k}$ for some $k<k^{*}$. Among those vectors,
the lexicographically smallest one is

$\left(d_{e}\left(n_{e}^{<q_{k+1}}(S),1\right),\,q_{k+1}\right).$

Recall (15), saying that

$d_{e}\left(n_{e}^{<q_{k}}(S),n_{e}^{q_{k}}(S)\right)\leq
d_{e}\left(n_{e}^{<q_{k+1}}(S),1\right),$

and thus

$d_{e^{\prime}}\left(n_{e^{\prime}}^{<q^{\prime}}(S),n_{e^{\prime}}^{q^{\prime}}(S)+1\right)<d_{e}\left(n_{e}^{<q_{k+1}}(S),1\right)$

follows from (16). Hence, we conclude that

$\left(d_{e^{\prime}}\left(n_{e^{\prime}}^{<q^{\prime}}(S),n_{e^{\prime}}^{q^{\prime}}(S)+1\right),\,q^{\prime}\right)\operatorname{\prec_{lex}}\left(d_{e}\left(n_{e}^{<q_{k+1}}(S),1\right),\,q_{k+1}\right).$

Next, consider the vectors in $\Phi(S)$ contributed by $e^{\prime}$. Without
loss of generality, suppose that there exists a positive integer
$q^{\prime\prime}$ such that $q^{\prime\prime}\in Q_{e^{\prime}}(S)$ and
$q^{\prime\prime}>q^{\prime}$. Let $q^{\prime\prime}$ be the smallest integer
satisfying these conditions. The lexicographically smallest vector in
$\Phi(S)$ contributed by $e^{\prime}$ and changed by the better response of
$i$ is

$\left(d_{e^{\prime}}\left(n_{e^{\prime}}^{<q^{\prime\prime}}(S),1\right),\,q^{\prime\prime}\right).$

It follows from the property (10) that

$d_{e^{\prime}}\left(n_{e^{\prime}}^{<q^{\prime}}(S),n_{e^{\prime}}^{q^{\prime}}(S)+1\right)\leq
d_{e^{\prime}}\left(n_{e^{\prime}}^{<q^{\prime\prime}}(S),1\right),$

and thus

$\left(d_{e^{\prime}}\left(n_{e^{\prime}}^{<q^{\prime}}(S),n_{e^{\prime}}^{q^{\prime}}(S)+1\right),\,q^{\prime}\right)\operatorname{\prec_{lex}}\left(d_{e^{\prime}}\left(n_{e^{\prime}}^{<q^{\prime\prime}}(S),1\right),\,q^{\prime\prime}\right),$

completing the proof. ∎

We next show the following theorem, which corresponds to Theorem 2.8 but does
not include a polynomial bound on the number of strategy changes.

######  Theorem 4.5 ($\star$).

A priority-based player-specific singleton congestion game with inconsistent
priorities possesses a pure Nash equilibrium, which can be computed with a
finite number of strategy changes.

##  5 Generalized Correlated Two-Sided Markets with Ties

In this section, we introduce the model of _generalized correlated two-sided
markets with ties_ , which generalizes correlated two-sided markets with ties
described in Section 2.2.2. We show that this model is a special class of
priority-based player-specific congestion games with inconsistent priorities,
and it includes priority-based congestion games with inconsistent priorities.
This is in contrast to the situation of correlated two-sided markets with
ties, in which it is unclear whether correlated two-sided markets with ties
include congestion games with inconsistent priorities. We then prove that a
generalized correlated two-sided market with ties is a potential game, which
extends Theorem 2.9.

###  5.1 Model

A generalized correlated two-sided market with ties is described by a tuple

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

Again, $N$ and $E$ denote the sets of the players and resources, respectively.
For each player $i\in N$ and each resource $e\in E$, a nonnegative real number
$c_{i,e}\in{\mathbb{R}}_{+}$ is associated, which implies the preferences of
$i$ and $e$, and are reflected in the delay function $d_{e}$ of $e$ in the
following way.

Let $S=(S_{1},\ldots,S_{n})$ be a strategy profile and $e\in E$ be a resource.
In the same way as (2) and (5), for a nonnegative number
$q\in{\mathbb{R}}_{+}$, define $n_{e}^{q}(S),n_{e}^{<q}(S)\in{\mathbb{Z}}_{+}$
by

$\displaystyle n_{e}^{q}(S)\ {}$ $\displaystyle{}=\ \left|\\{i\in
N_{e}(S)\colon c_{i,e}=q\\}\right|,$ $\displaystyle n_{e}^{<q}(S)\ {}$
$\displaystyle{}=\ \left|\\{i\in N_{e}(S)\colon c_{i,e}<q\\}\right|.$

Note that $n_{e}^{c_{i,e}}(S)>0$ if $e\in S_{i}$. The delay function $d_{e}$
is a trivariate function
$d_{e}\colon{\mathbb{R}}_{+}\times{\mathbb{Z}}_{+}\times{\mathbb{Z}}_{++}\to{\mathbb{R}}_{+}$.
The cost imposed by $e$ on a player $i\in N_{e}(S)$ is

$d_{e}\left(c_{i,e},\,n_{e}^{<c_{i,e}}(S),\,n_{e}^{c_{i,e}}(S)\right).$

Here, the delay functions $d_{e}$ ($e\in E$) have the following properties:

$\displaystyle d_{e}(c,x,y)\leq d_{e}(c^{\prime},x,y)$ $\displaystyle(\mbox{if
$c<c^{\prime}$}),$ (18) $\displaystyle d_{e}(c,x,y)\leq d_{e}(c,x^{\prime},y)$
$\displaystyle(\mbox{if $x<x^{\prime}$}),$ (19) $\displaystyle
d_{e}(c,x,y)\leq d_{e}(c,x,y^{\prime})$ $\displaystyle(\mbox{if
$y<y^{\prime}$}),$ (20) $\displaystyle d_{e}(c,x,y)\leq d(c,x+y-1,1)$
$\displaystyle(\mbox{for each $x\in{\mathbb{Z}}_{+}$ and
$y\in{\mathbb{Z}}_{++}$}).$ (21)

The properties (18)–(20) represent the monotonicity of $d_{e}$, while
(19)–(21) corresponds to the properties (8)–(10) of the delay functions in
priority-based congestion games. We also remark that $d_{e}(c,0,1)$ is not
necessarily equal to $c$, whereas $d_{e}(c,1)=c$ in correlated two-sided
markets with ties.

###  5.2 Relation to Other Models

A correlated two-sided market with ties
$(N,E,(\mathcal{S}_{i}),(c_{i,e}),(d_{e}))$ is represented as a generalized
correlated two-sided market with ties
$(N,E,(\mathcal{S}_{i}),(c_{i,e}),(d_{e}^{\prime}))$ by defining the
trivariate function
$d_{e}^{\prime}\colon{\mathbb{R}}_{+}\times{\mathbb{Z}}_{+}\times{\mathbb{Z}}_{++}\to{\mathbb{R}}_{+}$
by

$\displaystyle d_{e}^{\prime}(c,x,y)=\begin{cases}d_{e}(c,y)&\mbox{if
$x=0$},\\\ +\infty&\mbox{if $x\geq 1$}\end{cases}$

for each resource $e\in E$.

The following propositions show that generalized correlated two-sided markets
with ties lie between priority-based congestion games with inconsistent
priorities and priority-based player-specific congestion games with
inconsistent priorities.

######  Proposition 5.1 ($\star$).

A priority-based congestion games with inconsistent priorities is represented
as a generalized correlated two-sided market with ties.

######  Proposition 5.2 ($\star$).

A generalized correlated two-sided market with ties is represented as a
priority-based player-specific congestion games with inconsistent priorities.

###  5.3 Pure Nash Equilibria and Potential

From Proposition 5.2 and Theorem 4.5, it follows that a generalized correlated
singleton two-sided market has a pure Nash equilibrium and it can be computed
with a finite number of strategy changes. What is more, the proof for Theorem
4.4 applies to a generalized correlated singleton two-sided market, and hence
it is indeed a potential game.

######  Theorem 5.3 ($\star$).

A generalized correlated two-sided singleton market
$(N,E,(\mathcal{S}_{i}),(c_{i,e}),(d_{e}))$ with ties is a potential game, and
hence possesses a pure Nash equilibrium.

##  6 Extension Beyond Singleton Games

In this section, we discuss extensions of the above results on priority-based
singleton congestion games into larger classes with respect to the strategy
spaces. We present extensions of Theorems 4.1, 4.4, 4.5, and 5.3 into matroid
games, followed by an investigation of priority-based congestion games with
consistent priorities without any assumption on the strategy spaces of the
players.

###  6.1 Matroid Games

The following is a fundamental property of matroids, which is essential to the
extension of our arguments for singleton games to matroid games.

######  Lemma 6.1 (see, e.g., [33, 37]).

Let $(E,\mathcal{S})$ be a matroid, $S\in\mathcal{S}$ be a base, and
$w_{e}\in{\mathbb{R}}$ be a weight for each $e\in E$. If there exists a base
$S^{\prime}\in\mathcal{S}$ such that $\sum_{e\in S^{\prime}}w_{e}<\sum_{e\in
S}w_{e}$, then there exists an element $e\in S$ and $e^{\prime}\in E\setminus
S$ such that $(S\setminus\\{e\\})\cup\\{e^{\prime}\\}\in\mathcal{S}$ and
$w_{e^{\prime}}<w_{e}$.

It follows from Lemma 6.1 that we can implement an arbitrary better response
of a player in a matroid game as a lazy better response. On the basis of this
fact, the proofs for Theorems 4.1, 4.4, 4.5, and 5.3 can be adapted to matroid
games.

######  Theorem 6.2.

In a priority-based player-specific matroid congestion game with consistent
priorities, there exists a sequences of polynomial number of better responses
starting from an arbitrary strategy profile and reaching a pure Nash
equilibrium.

######  Theorem 6.3.

A priority-based matroid congestion game with inconsistent priorities is a
potential game, and hence possesses a pure Nash equilibrium.

######  Theorem 6.4.

A priority-based player-specific matroid congestion game with inconsistent
priority possesses a pure Nash equilibrium, which can be computed with a
finite number of strategy changes.

######  Theorem 6.5.

A generalized correlated two-sided matroid market with ties is a potential
game, and hence possesses a pure Nash equilibrium.

###  6.2 Arbitrary Strategy Spaces

For a priority-based congestion game $(N,E,(\mathcal{S}_{i})_{i\in
N},p,(d_{e})_{e\in E})$ with consistent priorities, let $N^{q}$ denote the set
of the players with priority-function value $q$, namely $N^{q}=\\{i\in N\colon
p(i)=q\\}$.

######  Lemma 6.6 ($\star$).

Let $G=(N,E,(\mathcal{S}_{i})_{i\in N},p,(d_{e})_{e\in E})$ be a priority-
based congestion game with consistent priorities. Let $S=(S_{1},\ldots,S_{n})$
be its strategy profile and let $q\in{\mathbb{Z}}_{+}$. Fix the strategy of
each player $j\in N\setminus N^{q}$ to $S_{j}$, and let $G^{q}$ denote the
game restricted to the players in $N^{q}$. Then, the game $G^{q}$ is a
potential game with potential function

$\displaystyle\Phi(S^{q})=\sum_{e\in
E}\sum_{k=1}^{n_{e}(S^{q})}d_{e}(n_{e}^{<q}(S),k)\quad(S^{q}=(S_{i})_{i\in
N^{q}}).$

It directly follows from Lemma 6.6 that a pure Nash equilibrium of a priority-
based congestion game $G$ with consistent priorities can be constructed by
combining pure Nash equilibria $S^{q}$ of a game $G^{q}$ for each priority-
function value $q$, where $G^{q}$ is defined by fixing the strategies of the
players in $N^{q^{\prime}}$ to form a pure Nash equilibrium of
$G^{q^{\prime}}$ for each $q^{\prime}<q$.

######  Theorem 6.7.

A priority-based congestion game with consistent priorities possesses a pure
Nash equilibrium.

##  7 Conclusion

We have presented a common generalization of the models of congestion games by
Ackermann et al. [1] and Bilò and Vinci [6]. This generalization gives a
positive and full answer to the open question posed by Ackermann et al. [1].
We then proved some theorems on the existence of pure Nash equilibria,
extending those in [1] and [6].

Once the existence of pure Nash equilibria is established, a possible
direction of future work is to design an efficient algorithm for finding a
pure Nash equilibrium in our model. Analyses on the price of anarchy and the
price of stability in our model is also of interest, as is intensively done
for the model of Bilò and Vinci [6].

## References

  * [1] H. Ackermann, P. W. Goldberg, V. S. Mirrokni, H. Röglin, and B. Vöcking.  A unified approach to congestion games and two-sided markets.  Internet Math., 5(4):439–457, 2008.
  * [2] H. Ackermann, H. Röglin, and B. Vöcking.  On the impact of combinatorial structure on congestion games.  J. ACM, 55(6):25:1–25:22, 2008.
  * [3] 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.
  * [4] M. Baïou and M. Balinski.  Many-to-many matching: stable polyandrous polygamy (or polygamous polyandry).  Discret. Appl. Math., 101(1-3):1–12, 2000.
  * [5] V. Bansal, A. Agrawal, and V. S. Malhotra.  Polynomial time algorithm for an optimal stable assignment with multiple partners.  Theor. Comput. Sci., 379(3):317–328, 2007.
  * [6] V. Bilò and C. Vinci.  Congestion games with priority-based scheduling.  Theor. Comput. Sci., 974:114094, 2023.
  * [7] 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.
  * [8] M. Drees, M. Feldotto, S. Riechers, and A. Skopalik.  Pure Nash equilibria in restricted budget games.  J. Comb. Optim., 37(2):620–638, 2019.
  * [9] P. Eirinakis, D. Magos, I. Mourtos, and P. Miliotis.  Finding all stable pairs and solutions to the many-to-many stable matching problem.  INFORMS J. Comput., 24(2):245–259, 2012.
  * [10] 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.
  * [11] M. Feldotto, L. Leder, and A. Skopalik.  Congestion games with mixed objectives.  J. Comb. Optim., 36(4):1145–1167, 2018.
  * [12] T. Fleiner.  On the stable $b$-matching polytope.  Math. Soc. Sci., 46(2):149–158, 2003.
  * [13] S. Fujishige, M. X. Goemans, T. Harks, B. Peis, and R. Zenklusen.  Congestion games viewed from M-convexity.  Oper. Res. Lett., 43(3):329–333, 2015.
  * [14] D. Gale and L. Shapley.  College admissions and the stability of marriage.  Am. Math. Mon., 69:9–15, 1962.
  * [15] H. Goko, K. Makino, S. Miyazaki, and Y. Yokoi.  Maximally satisfying lower quotas in the hospitals/residents problem with ties.  In P. Berenbrink and B. Monmege, editors, 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, volume 219 of LIPIcs, pages 31:1–31:20, 2022.
  * [16] D. Gusfield and R. W. Irving.  The Stable Marriage Problem—Structure and Algorithms.  Foundations of computing series. MIT Press, 1989.
  * [17] K. Hamada, S. Miyazaki, and H. Yanagisawa.  Strategy-proof approximation algorithms for the stable marriage problem with ties and incomplete lists.  In P. Lu and G. Zhang, editors, 30th International Symposium on Algorithms and Computation, ISAAC 2019, volume 149 of LIPIcs, pages 9:1–9:14, 2019.
  * [18] T. Harks, M. Klimm, and B. Peis.  Sensitivity analysis for convex separable optimization over integral polymatroids.  SIAM J. Optim., 28(3):2222–2245, 2018.
  * [19] T. Harks and B. Peis.  Resource buying games.  In A. S. Schulz, M. Skutella, S. Stiller, and D. Wagner, editors, Gems of Combinatorial Optimization and Graph Algorithms, pages 103–111. Springer, 2015.
  * [20] T. Harks and V. Timmermans.  Uniqueness of equilibria in atomic splittable polymatroid congestion games.  J. Comb. Optim., 36(3):812–830, 2018.
  * [21] C.-C. Huang, K. Iwama, S. Miyazaki, and H. Yanagisawa.  A tight approximation bound for the stable marriage problem with restricted ties.  In N. Garg, K. Jansen, A. Rao, and J. D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, volume 40 of LIPIcs, pages 361–380, 2015\.
  * [22] C.-C. Huang and T. Kavitha.  Improved approximation algorithms for two variants of the stable marriage problem with ties.  Math. Program., 154(1-2):353–380, 2015.
  * [23] S. Ieong, R. McGrew, E. Nudelman, Y. Shoham, and Q. Sun.  Fast and compact: A simple class of congestion games.  In M. M. Veloso and S. Kambhampati, editors, 20th Annual AAAI Conference on Artificial Intelligence, AAAI 2005, pages 489–494, 2005.
  * [24] R. W. Irving.  Stable marriage and indifference.  Discret. Appl. Math., 48(3):261–272, 1994.
  * [25] N. Kamiyama.  Stable matchings with ties, master preference lists, and matroid constraints.  In M. Hoefer, editor, 8th International Symposium, SAGT 2015, volume 9347 of Lecture Notes in Computer Science, pages 3–14. Springer, 2015.
  * [26] N. Kamiyama.  Many-to-many stable matchings with ties, master preference lists, and matroid constraints.  In E. Elkind, M. Veloso, N. Agmon, and M. E. Taylor, editors, 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2019, pages 583–591. IFAAMAS, 2019.
  * [27] T. Kavitha.  Stable matchings with one-sided ties and approximate popularity.  In A. Dawar and V. Guruswami, editors, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022, volume 250 of LIPIcs, pages 22:1–22:17, 2022.
  * [28] 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.
  * [29] D. F. Manlove.  Algorithmics of Matching Under Preferences, volume 2 of Series on Theoretical Computer Science.  WorldScientific, 2013.
  * [30] D. Marx and I. Schlotter.  Parameterized complexity and local search approaches for the stable marriage problem with ties.  Algorithmica, 58(1):170–187, 2010.
  * [31] I. Milchtaich.  Congestion games with player-specific payoff functions.  Game. Econ. Behav., 13:111–124, 1996.
  * [32] D. Monderer and L. S. Shapley.  Potential games.  Games Econ. Behav., 14:124–143, 1996.
  * [33] K. Murota.  Discrete Convex Analysis.  Society for Industrial and Applied Mathematics, Philadelphia, 2003.
  * [34] N. Nisan, T. Roughgarden, É. Tardos, and V. V. Vazirani, editors.  Algorithmic Game Theory.  Cambridge University Press, 2007.
  * [35] R. W. Rosenthal.  A class of games possessing pure-strategy Nash equilibria.  Int. J. Game Theory, 2:65–67, 1973.
  * [36] T. Roughgarden.  Twenty Lectures on Algorithmic Game Theory.  Cambridge University Press, 2016.
  * [37] A. Schrijver.  Combinatorial Optimization—Polyhedra and Efficiency.  Springer, 2003.
  * [38] M. Sotomayor.  The lattice structure of the set of stable outcomes of the multiple partners assignment game.  Int. J. Game Theory, 28(4):567–583, 1999.
  * [39] M. Sotomayor.  Three remarks on the many-to-many stable matching prblem.  Math. Soc. Sci., 38(1):55–70, 1999.
  * [40] 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.
  * [41] K. Takazawa.  Pure Nash equilibria in weighted congestion games with complementarities and beyond.  In M. Dastani, J. S. Sichman, N. Alechina, and V. Dignum, editors, Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2024, pages 2495–2497. ACM, 2024.
  * [42] Y. Yokoi.  An approximation algorithm for maximum stable matching with ties and constraints.  In H. Ahn and K. Sadakane, editors, 32nd International Symposium on Algorithms and Computation, ISAAC 2021, volume 212 of LIPIcs, pages 71:1–71:16, 2021.

##  Appendix A Omitted Proof

###  A.1 Proofs from Section 4

In a singleton game, a strategy $\\{e\\}$ is simply denoted by $e$. We use a
term _state_ to refer to a collection of the strategies of some of the players
in $N$, and let $N(S)$ denote the set of the players contributing a state $S$.
In other words, a strategy profile is a special case of a state $S$ for which
$N(S)=N$. For a state $S$ and a resource $e\in E$, let $N_{e}(S)$ denote the
set of players choosing $e$ as the strategy, and let $|N_{e}(S)|=n_{e}(S)$.

###### Proof of Theorem 4.1.

Let $\\{q_{1},q_{2},\ldots,q_{k}\\}$ denote the set of the priority-function
values of all players, i.e.,

$\\{q_{1},q_{2},\ldots,q_{k}\\}=\\{p(i)\colon i\in N\\}$, where
$q_{1}<q_{2}<\cdots<q_{k}$.

For each $k^{\prime}=1,2,\ldots,{k}$, define $N^{k^{\prime}}\subseteq N$ by
$N^{k^{\prime}}=\\{i\in N\colon p(i)=q_{k^{\prime}}\\}$.

Let $S=(e_{1},\ldots,e_{n})$ be an arbitrary strategy profile of $G$, and let
$S^{k^{\prime}}$ be a state of $G$ consisting of the strategies of the players
in $N^{k^{\prime}}$ in $S$ for each ${k^{\prime}}=1,2,\ldots,{k}$. We prove
the theorem by induction on $k^{\prime}$. First, define a player-specific
singleton congestion game

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

in which the delay function
$d^{\prime}_{i,e}\colon{\mathbb{Z}}_{++}\to{\mathbb{R}}_{+}$ ($i\in N^{1}$,
$e\in E$) is defined by

$\displaystyle d_{i,e}^{\prime}(y)=d_{i,e}(0,y)\quad(y\in{\mathbb{Z}}_{++}).$

It then follows from Theorem 2.3 that $G^{1}$ has a pure Nash equilibrium
$\hat{S}^{1}$, which is attained by a polynomial number of best responses from
$S^{1}$.

Now let $k^{\prime}\in\\{1,\ldots,k-1\\}$ and suppose that we have a state
$\hat{S}^{k^{\prime}}$ of the players in
$\bigcup_{\ell=1}^{k^{\prime}}N^{\ell}$ in which no player has an incentive to
change her strategy. Then construct a player-specific singleton congestion
game

$G^{{k^{\prime}}+1}=(N^{{k^{\prime}}+1},E,(\mathcal{S}_{i})_{i\in
N^{{k^{\prime}}+1}},(d^{\prime}_{i,e})_{i\in N^{k^{\prime}+1},e\in E})$

in which

$\displaystyle
d_{i,e}^{\prime}(y)=d_{i,e}(n_{e}(\hat{S}^{k^{\prime}}),y)\quad(y\in{\mathbb{Z}}_{++})$

for each $e\in E$. It again follows from Theorem 2.3 that the game
$G^{{k^{\prime}}+1}$ has a pure Nash equilibrium and it is attained by a
polynomial number of best responses from an arbitrary strategy profile.

By induction, we have proved that a pure Nash equilibrium of a player-specific
priority-based singleton congestion game can be attained through a polynomial
number of best responses from an arbitrary strategy profile. ∎

###### Proof of Theorem 4.5.

We prove this theorem by presenting an algorithm for computing a pure Nash
equilibrium of a priority-based player-specific singleton congestion game
$(N,E,(\mathcal{S}_{i}),(p_{e}),(d_{i,e}))$. The algorithm constructs a
sequence $S_{0},S_{1},\ldots,S_{k}$ of states in which $N(S_{0})=\emptyset$,
$N(S_{k})=N$, and

each player in $N(S_{k^{\prime}})$ has no incentive to change her strategy
(22)

for each ${k^{\prime}}=0,1,\ldots,k$, implying that $S_{k}$ is a pure Nash
equilibrium.

It is clear that (22) is satisfied for ${k^{\prime}}=0$. Below we show how to
construct $S_{{k^{\prime}}+1}$ from $S_{k^{\prime}}$ under an assumption that
$S_{k^{\prime}}$ satisfies (22) and $N(S_{k^{\prime}})\subsetneq N$.

Take a player $i\in N\setminus N(S_{k^{\prime}})$, and let $i$ choose a
resource $e\in E$ imposing the minimum cost on $i$ if $i$ is added to
$N_{e}(S_{k^{\prime}})$. We construct the new state $S_{{k^{\prime}}+1}$ by
changing the strategy of each player $j\in N_{e}(S_{k^{\prime}})$ in the
following way. The other players do not change their strategies.

For the players in $N_{e}(S_{k^{\prime}})$, we have the following cases A and
B.

Case A.

No player in $N_{e}(S_{k^{\prime}})$ comes to have a better response when $i$
is added to $N_{e}(S_{k^{\prime}})$.

Case B.

Some players in $N_{e}(S_{k^{\prime}})$ comes to have a better response when
$i$ is added to $N_{e}(S_{k^{\prime}})$.

In Case A, we do not change the strategies of the players in
$N_{e}(S_{k^{\prime}})$. In Case B, if a player $j\in N_{e}(S_{k^{\prime}})$
comes to have a better response, it must hold that $p_{e}(j)\geq p_{e}(i)$. We
further separate Case B into the following two cases.

Case B1.

There exists a player $j\in N_{e}(S_{k^{\prime}})$ having a better response
and satisfying $p_{e}(j)=p_{e}(i)$.

Case B2.

Every player $j\in N_{e}(S_{k^{\prime}})$ having a better response satisfies
$p_{e}(j)>p_{e}(i)$.

In each case, the strategies are changed as follows.

Case B1.

Only one player $j\in N_{e}(S_{k^{\prime}})$ having a better response and
$p_{e}(j)=p_{e}(i)$ changes her strategy by discarding her strategy. Namely,
$j\not\in N(S_{k^{\prime}+1})$. The other players do not change their
strategies.

Case B2.

Every player $j\in N_{e}(S_{k^{\prime}})$ having a better response discards
her strategy.

We have now constructed the new state $S_{k^{\prime}+1}$. It is
straightforward to see that the state $S_{k^{\prime}+1}$ satisfies (22). We
complete the proof by showing that this algorithm terminates within a finite
number of strategy changes.

For a resource $e\in E$, let $q^{*}_{e}=\max\\{p_{e}(i)\colon i\in N\\}$. For
each state $S_{k^{\prime}}$ appearing in the algorithm, define its potential
$\Phi(S_{k^{\prime}})\in\left(\bigtimes_{e\in
E}{\mathbb{Z}}_{+}^{q_{e}^{*}}\right)\times{\mathbb{Z}}_{++}$ in the following
manner. For each resource $e\in E$, define a vector
$\phi_{e}\in{\mathbb{Z}}_{+}^{q_{e}^{*}}$ by

$\displaystyle\phi_{e}(q)=n_{e}^{q}(S_{k^{\prime}})\quad(q=1,2,\ldots,q_{e}^{*}),$

which is a contribution of $e$ to the first component of
$\Phi(S_{k^{\prime}})$. The first component of $\Phi(S_{k^{\prime}})$ is
constructed by ordering the vectors $\phi_{e}$ ($e\in E$) in the
lexicographically nondecreasing order.

For a resource $e\in E$ and a player $i\in N_{e}(S_{k^{\prime}})$, define
$\operatorname{tol}(i,S_{k^{\prime}})\in{\mathbb{Z}}_{++}$ as the maximum
number $y\in{\mathbb{Z}}_{++}$ such that $e$ is an optimal strategy for $i$ if
$i$ shares $e$ with $y$ players having the same priority as $e$, i.e.,

$\displaystyle d_{i,e}(n_{e}^{<p_{e}(i)}(S_{k^{\prime}}),y)\leq
d_{i,e^{\prime}}(n_{e^{\prime}}^{<p_{e^{\prime}}(i)}(S_{k^{\prime}}),n_{e^{\prime}}^{p_{e^{\prime}}(i)}(S_{k^{\prime}})+1)$

for each $e^{\prime}$ with $e^{\prime}\neq e$ and
$\\{e^{\prime}\\}\in\mathcal{S}_{i}$. Note that $i$ herself is counted in $y$,
and hence $\operatorname{tol}(i,S_{k^{\prime}})\geq 1$ for each $i\in
N(S_{k^{\prime}})$. Now the second component of the potential
$\Phi(S_{k^{\prime}})$ is defined as $\sum_{i\in
N(S_{k^{\prime}})}\operatorname{tol}(i,S_{k^{\prime}})$.

We prove that the potential $\Phi(S_{k^{\prime}})$ increases lexicographically
monotonically during the algorithm. Let a state $S_{k^{\prime}+1}$ is
constructed from $S_{k^{\prime}}$ and the involvement of a player $i\in
N\setminus N(S_{k^{\prime}})$ choosing a resource $e\in E$. It is
straightforward to see that $\phi_{e^{\prime}}$ is unchanged for each
$e^{\prime}\in E\setminus\\{e\\}$. Consider how the vector $\phi_{e}$ changes.

##### Case A.

The unique change of $\phi_{e}$ is that $\phi_{e}(p_{e}(i))$ increases by one,
implying that the first component of $\Phi(S_{k^{\prime}+1})$ is
lexicographically larger than that of $\Phi(S_{k^{\prime}})$.

##### Case B1.

Let $j^{*}\in N_{e}(S_{k^{\prime}})$ denote the unique player who discard her
strategy. Recall that $p_{e}(j^{*})=p_{e}(i)$. It follows that $\phi_{e}$ is
unchanged, and hence the first component of $\Phi(S_{k^{\prime}+1})$ is the
same as that of $\Phi(S_{k^{\prime}})$. The second component of
$\Phi(S_{{k^{\prime}}+1})$ is strictly larger than that of
$\Phi(S_{k^{\prime}})$, because

$\displaystyle{}N(S_{{k^{\prime}}+1})=(N(S_{k^{\prime}})\cup\\{i\\})\setminus\\{j^{*}\\},$
$\displaystyle{}\operatorname{tol}(j,S_{{k^{\prime}}+1})=\operatorname{tol}(j,S_{{k^{\prime}}})\quad\mbox{for
each $j\in N(S_{k^{\prime}})\setminus\\{i,j^{*}\\}$},$
$\displaystyle{}\operatorname{tol}(i,S_{{k^{\prime}}+1})\geq
n_{e}^{p_{e}(i)}(S_{k^{\prime}})+1,$
$\displaystyle{}\operatorname{tol}(j^{*},S_{{k^{\prime}}})=n_{e}^{p_{e}(i)}(S_{k^{\prime}}).$

##### Case B2.

It holds that $n_{e}^{q}(S_{{k^{\prime}}+1})=n_{e}^{q}(S_{k^{\prime}})$ for
each $q<p_{e}(i)$ and
$n_{e}^{p_{e}(i)}(S_{{k^{\prime}}+1})=n_{e}^{p_{e}(i)}(S_{k^{\prime}})+1$.
Thus, the first component of $\Phi$ lexicographically increases. ∎

###  A.2 Proofs from Section 5

###### Proof of Proposition 5.1.

Given a priority-based congestion game
$(N,E,(\mathcal{S}_{i}),(p_{e}),(d_{e}))$ with inconsistent priorities,
construct a generalized correlated two-sided market
$(N,E,(\mathcal{S}_{i}),(c_{i,e}),(d_{e}^{\prime}))$ with ties by defining

$\displaystyle{}c_{i,e}=p_{e}(i)$ $\displaystyle(i\in N,e\in E),$
$\displaystyle{}d_{e}^{\prime}(c,x,y)=d_{e}(x,y).$ $\displaystyle(e\in
E,c\in{\mathbb{R}}_{+},x\in{\mathbb{Z}}_{+},y\in{\mathbb{Z}}_{++}).$

It is straightforward to see that the delay function $d_{e}^{\prime}$ ($e\in
E$) satisfy (18)–(21) in which $d_{e}$ is replaced by $d_{e}^{\prime}$, if the
original delay function $d_{e}$ satisfies (8)–(10). ∎

###### Proof of Proposition 5.2.

Given a generalized correlated two-sided market
$(N,E,(\mathcal{S}_{i}),(c_{i,e}),(d_{e}))$ with ties, construct a priority-
based player-specific congestion game
$(N,E,(\mathcal{S}_{i}),(p_{e}),(d_{i,e}^{\prime}))$ with inconsistent
priorities as follows. For each resource $e\in E$, construct its priority
function $p_{e}\colon N\to{\mathbb{Z}}_{+}$ in the same way as in (4), and
define its delay function
$d_{i,e}^{\prime}\colon{\mathbb{Z}}_{+}\times{\mathbb{Z}}_{++}\to{\mathbb{R}}_{+}$
specific to a player $i\in N$ by

$\displaystyle{}d_{i,e}^{\prime}(x,y)=d_{e}(p_{e}(i),x,y)\quad(x\in{\mathbb{Z}}_{+},y\in{\mathbb{Z}}_{++}).$

It is straightforward to see that the delay function $d_{i,e}^{\prime}$ ($i\in
N$, $e\in E$) satisfies (8)–(10) in which $d_{e}$ is replaced by
$d_{i,e}^{\prime}$, if the original delay function $d_{e}$ satisfies
(18)–(21). ∎

###### Proof of Theorem 5.3.

For each strategy profile $S=(e_{1},\ldots,e_{n})$, define its potential
$\Phi(S)\in({\mathbb{R}}_{+}\times{\mathbb{Z}}_{++})^{n}$ as follows. Let
$e\in E$ be a resource, and let $Q_{e}(S)=\\{q_{1},...,q_{k^{*}}\\}$ be a set
of integers such that $Q_{e}(S)=\\{q\colon n_{e}^{q}(S)>0\\}$ and
$q_{1}<\cdots<q_{k^{*}}$. The resource $e\in E$ contributes the following
$n_{e}(S)$ vectors in ${\mathbb{R}}_{+}\times{\mathbb{Z}}_{++}$ to $\Phi(S)$:

$\displaystyle{}(d_{e}(q_{1},0,1),\,q_{1}),\ldots,(d_{e}(q_{1},0,n_{e}(S,q_{1})),\,q_{1}),$
$\displaystyle{}(d_{e}(q_{2},n_{e}^{q_{1}}(S),1),\,q_{2}),\ldots,(d_{e}(q_{2},n_{e}^{q_{1}}(S),n_{e}^{q_{2}}(S)),\,q_{2}),$
$\displaystyle{}\ldots,$
$\displaystyle{}(d_{e}(q_{k},n_{e}^{<q_{k}}(S),1),\,q_{k}),\ldots,(d_{e}(q_{k},n_{e}^{<q_{k}}(S),n_{e}^{q_{k}}(S)),\,q_{k}),$
$\displaystyle{}\ldots,$
$\displaystyle{}(d_{e}(q_{k^{*}},n_{e}^{<q_{k^{*}}}(S),1),\,q_{k^{*}}),\ldots,(d_{e}(q_{k^{*}},n_{e}^{<q_{k^{*}}}(S),n_{e}^{q_{k^{*}}}(S)),\,q_{k^{*}}).$

The potential $\Phi(S)$ is obtained by ordering the $n$ vectors contributed by
all resources in the lexicographically nondecreasing order. We can observe
that the order of the $n_{e}(S)$ vectors shown above is lexicographically
nondecreasing in the following way. It follows from the property (20) that

$\displaystyle{}d_{e}(q_{k},n_{e}^{<q_{k}}(S),y)\leq
d_{e}(q_{k},n_{e}^{<q_{k}}(S),y+1)$

for each $k=1,\ldots,k^{*}$ and for each $y=q_{1},\ldots,q_{k^{-}1}$. It
further follows from the properties (18), (19) and (21) that

$\displaystyle d_{e}(c,x,y)\leq d_{e}(c,x+y-1,1)\leq d_{e}(c^{\prime},x+y,1)$
(23)

if $c<c^{\prime}$, and in particular

$\displaystyle d_{e}(q_{k},n_{e}^{<q_{k}}(S),n_{e}^{q_{k}}(S))\leq
d_{e}(q_{k+1},n_{e}^{<q_{k+1}}(S),1)\quad\mbox{for each
$k=1,\ldots,k^{*}-1$.}$ (24)

Suppose that a player $i$ has a better response in a strategy profile $S$,
which changes her strategy from $e$ to $e^{\prime}$, and let
$S^{\prime}=(S_{-i},e^{\prime})$. Below we show that
$\Phi(S^{\prime})\operatorname{\prec_{lex}}\Phi(S)$, which completes the
proof.

Let $c_{i,e}=q$ and $c_{i,e^{\prime}}=q^{\prime}$. Since the delay imposed on
$i$ becomes smaller due to the better response, it holds that

$\displaystyle
d_{e^{\prime}}(q^{\prime},n_{e^{\prime}}^{<q^{\prime}}(S),n_{e^{\prime}}^{q^{\prime}}(S)+1)<d_{e}(q,n_{e}^{<q}(S),n_{e}^{q}(S)).$
(25)

Note that $e^{\prime}$ contributes a vector

$\displaystyle(d_{e^{\prime}}(q^{\prime},n_{e^{\prime}}^{<q^{\prime}}(S),n_{e^{\prime}}^{q^{\prime}}(S)+1),q^{\prime})$
(26)

to $\Phi(S^{\prime})$ but not to $\Phi(S)$. To prove
$\Phi(S^{\prime})\operatorname{\prec_{lex}}\Phi(S)$, it suffices to show that
a vector belonging to $\Phi(S)$ but not to $\Phi(S^{\prime})$ is
lexcographically larger than the vector (26).

First, consider the vectors in $\Phi(S)$ contributed by $e$. Let
$Q_{e}(S)=\\{q_{1},\ldots,q_{k^{*}}\\}$, where $q_{1}<\cdots<q_{k^{*}}$. Due
to the better response of $i$, the vectors in $\Phi(S)$ whose second component
is larger than $q$ changes, because the second argument of the delay function
$d_{e}$ decreases by one. If $q=q_{k^{*}}$, then those vectors do not exist
and thus we are done. Suppose that $q=q_{k}$ for some $k<k^{*}$. Among those
vectors, the lexicographically smallest one is

$(d_{e}(q_{k+1},n_{e}^{<q_{k+1}}(S),1),q_{k+1}).$

It follows from (24) and (25) that

$d_{e^{\prime}}(q^{\prime},n_{e^{\prime}}^{<q^{\prime}}(S),n_{e^{\prime}}^{q^{\prime}}(S)+1)<d_{e}(q,n_{e}^{<q}(S),n_{e}^{q}(S))\leq
d_{e}(q_{k+1},n_{e}^{<q_{k+1}}(S),1).$

Hence, it holds that

$(d_{e^{\prime}}(q^{\prime},n_{e^{\prime}}^{<q^{\prime}}(S),n_{e^{\prime}}^{q^{\prime}}(S)+1),q^{\prime})\operatorname{\prec_{lex}}(d_{e}(q_{k+1},n_{e}^{<q_{k+1}}(S),1),q_{k+1}).$

Next, consider the vectors in $\Phi(S)$ contributed by $e^{\prime}$. Without
loss of generality, suppose that there exists a positive integer
$q^{\prime\prime}$ such that $q^{\prime\prime}\in Q_{e^{\prime}}(S)$ and
$q^{\prime\prime}>q^{\prime}$. Let $q^{\prime\prime}$ be the smallest integer
satisfying these conditions. The lexicographically smallest vector in
$\Phi(S)$ contributed by $e^{\prime}$ and changed by the better response of
$i$ is

$(d_{e^{\prime}}(q^{\prime\prime},n_{e^{\prime}}^{<q^{\prime\prime}}(S),1),q^{\prime\prime}).$

It then follows from the properties (18) and (21) that

$d_{e^{\prime}}(q^{\prime},n_{e^{\prime}}^{<q^{\prime}}(S),n_{e^{\prime}}^{q^{\prime}}(S)+1)\leq
d_{e^{\prime}}(q^{\prime\prime},n_{e^{\prime}}^{<q^{\prime}}(S),n_{e^{\prime}}^{q^{\prime}}(S)+1)\leq
d_{e^{\prime}}(q^{\prime\prime},n_{e^{\prime}}^{<q^{\prime\prime}}(S),1)$

and thus

$(d_{e^{\prime}}(q^{\prime},n_{e^{\prime}}^{<q^{\prime}}(S),n_{e^{\prime}}^{q^{\prime}}(S)+1),q^{\prime})\operatorname{\prec_{lex}}(d_{e^{\prime}}(q^{\prime\prime},n_{e^{\prime}}^{<q^{\prime\prime}}(S),1),q^{\prime\prime}),$

completing the proof. ∎

###  A.3 Proof from Section 6

###### Proof of Lemma 6.6.

Let $i$ be a player in $N^{q}$, and $S_{i}\in\mathcal{S}_{i}$ be an arbitrary
strategy of $i$. For each $S_{i}^{\prime}\in\mathcal{S}_{i}$, it holds that

$\displaystyle\Phi(S^{q}_{-i},S_{i}^{\prime})-\Phi(S^{q}){}$
$\displaystyle{}=\sum_{e\in S_{i}^{\prime}\setminus
S_{i}}d_{e}(n_{e}^{<q}(S),n_{e}(S^{q})+1)-\sum_{e\in S_{i}\setminus
S_{i}^{\prime}}d_{e}(n_{e}^{<q}(S),n_{e}(S^{q}))$
$\displaystyle{}=\gamma_{i}(S^{q}_{-i},S_{i}^{\prime})-\gamma_{i}(S^{q}),$

and hence the function $\Phi$ is a potential function of $G^{q}$. ∎


* Augustin et al., (2014) Augustin, T., Walter, G., and Coolen, F. P. A. (2014).  Statistical inference.  In Introduction to Imprecise Probabilities, Wiley Ser. Probab. Stat., pages 135–189. Wiley, Chichester.
  * Balch et al., (2019) Balch, M. S., Martin, R., and Ferson, S. (2019).  Satellite conjunction analysis and the false confidence theorem.  Proc. Royal Soc. A, 475(2227):2018.0565.
  * Barndorff-Nielsen, (1977) Barndorff-Nielsen, O. (1977).  Exponentially decreasing distributions for the logarithm of particle size.  Proc. R. Soc. Lond. A., 353(1674):401–419.
  * Barndorff-Nielsen, (1983) Barndorff-Nielsen, O. (1983).  On a formula for the distribution of the maximum likelihood estimator.  Biometrika, 70(2):343–365.
  * Barndorff-Nielsen and Cox, (1994) Barndorff-Nielsen, O. E. and Cox, D. R. (1994).  Inference and Asymptotics, volume 52 of Monographs on Statistics and Applied Probability.  Chapman & Hall, London.
  * Baroni, (2004) Baroni, P. (2004).  Extending consonant approximations to capacities.  In Proceedings of Information Processing with Management of Uncertainty in Knowledge-based Systems (IPMU’04), pages 1127–1134.
  * Berger, (1984) Berger, J. O. (1984).  The robust Bayesian viewpoint.  In Robustness of Bayesian Analyses, volume 4 of Stud. Bayesian Econometrics, pages 63–144. North-Holland, Amsterdam.  With comments and with a reply by the author.
  * Berger and Wolpert, (1984) Berger, J. O. and Wolpert, R. L. (1984).  The Likelihood Principle.  Institute of Mathematical Statistics Lecture Notes—Monograph Series, 6. Institute of Mathematical Statistics, Hayward, CA.
  * Bernardo and Smith, (1994) Bernardo, J.-M. and Smith, A. F. M. (1994).  Bayesian Theory.  Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. John Wiley & Sons, Ltd., Chichester.
  * Birnbaum, (1962) Birnbaum, A. (1962).  On the foundations of statistical inference.  J. Amer. Statist. Assoc., 57:269–326.
  * (12) Cella, L. and Martin, R. (2022a).  Direct and approximately valid probabilistic inference on a class of statistical functionals.  Internat. J. Approx. Reason., 151:205–224.
  * (13) Cella, L. and Martin, R. (2022b).  Valid inferential models for prediction in supervised learning problems.  Internat. J. Approx. Reason., 150:1–18.
  * (14) Cella, L. and Martin, R. (2022c).  Validity, consonant plausibility measures, and conformal prediction.  Internat. J. Approx. Reason., 141:110–130.
  * Couso and Dubois, (2018) Couso, I. and Dubois, D. (2018).  A general framework for maximizing likelihood under incomplete data.  Internat. J. Approx. Reason., 93:238–260.
  * Couso et al., (2001) Couso, I., Montes, S., and Gil, P. (2001).  The necessity of the strong $\alpha$-cuts of a fuzzy set.  Internat. J. Uncertain. Fuzziness Knowledge-Based Systems, 9(2):249–262.
  * Cox and Reid, (1987) Cox, D. R. and Reid, N. (1987).  Parameter orthogonality and approximate conditional inference (with discussion).  J. Roy. Statist. Soc. Ser. B, 49(1):1–39.
  * Cui and Hannig, (2022) Cui, Y. and Hannig, J. (2022).  Demystifying inferential moels: A fiducial approach.  arXiv:2205.05612.
  * Dawid, (1991) Dawid, A. P. (1991).  Fisherian inference in likelihood and prequential frames of reference.  J. Roy. Statist. Soc. Ser. B, 53(1):79–109.  With discussion and a reply by the author.
  * De Cooman, (1997) De Cooman, G. (1997).  Possibility theory. II. Conditional possibility.  Internat. J. Gen. Systems, 25(4):325–351.
  * de Finetti, (1937) de Finetti, B. (1937).  La prévision : ses lois logiques, ses sources subjectives.  Ann. Inst. H. Poincaré, 7(1):1–68.
  * Dempster, (1967) Dempster, A. P. (1967).  Upper and lower probabilities induced by a multivalued mapping.  Ann. Math. Statist., 38:325–339.
  * (23) Dempster, A. P. (1968a).  A generalization of Bayesian inference. (With discussion).  J. Roy. Statist. Soc. Ser. B, 30:205–247.
  * (24) Dempster, A. P. (1968b).  Upper and lower probabilities generated by a random closed interval.  Ann. Math. Statist., 39:957–966.
  * Dempster, (2008) Dempster, A. P. (2008).  The Dempster–Shafer calculus for statisticians.  Internat. J. Approx. Reason., 48(2):365–377.
  * Denœux, (2006) Denœux, T. (2006).  Constructing belief functions from sample data using multinomial confidence regions.  Internat. J. of Approx. Reason., 42(3):228–252.
  * Denœux, (2014) Denœux, T. (2014).  Likelihood-based belief function: justification and some extensions to low-quality data.  Internat. J. Approx. Reason., 55(7):1535–1547.
  * Denœux, (2022) Denœux, T. (2022).  Reasoning with fuzzy and uncertain evidence using epistemic random fuzzy sets: general framework and practical models.  Fuzzy Sets Syst., to appear.
  * Denœux and Li, (2018) Denœux, T. and Li, S. (2018).  Frequency-calibrated belief functions: review and new insights.  Internat. J. Approx. Reason., 92:232–254.
  * Destercke et al., (2009) Destercke, S., Dubois, D., and Chojnacki, E. (2009).  A consonant approximation of the product of independent consonant random sets.  Internat. J. Uncertain. Fuzziness Knowledge-Based Systems, 17(6):773–792.
  * Dubois et al., (2004) Dubois, D., Foulloy, L., Mauris, G., and Prade, H. (2004).  Probability-possibility transformations, triangular fuzzy sets, and probabilistic inequalities.  Reliab. Comput., 10(4):273–297.
  * Dubois and Prade, (1984) Dubois, D. and Prade, H. (1984).  Fuzzy logics and the generalized modus ponens revisited.  Cybernet. Systems, 15(3-4):293–331.
  * (33) Dubois, D. and Prade, H. (1986a).  The principle of minimum specificity as a basis for evidential reasoning.  In Proceedings of International Conference on Information Processing and Management of Uncertainty in Knowledge-based Systems, pages 75–84. Springer.
  * (34) Dubois, D. and Prade, H. (1986b).  A set-theoretic view of belief functions. Logical operations and approximations by fuzzy sets.  Internat. J. Gen. Systems, 12(3):193–226.
  * (35) Dubois, D. and Prade, H. (1988a).  Possibility Theory.  Plenum Press, New York.
  * (36) Dubois, D. and Prade, H. (1988b).  Representation and combination of uncertainty with belief functions and possibility measures.  Comput. Intell., 4(3):244–264.
  * (37) Dubois, D. and Prade, H. (1990a).  Consonant approximations of belief functions.  Internat. J. Approx. Reason., 4(5-6):419–449.
  * (38) Dubois, D. and Prade, H. (1990b).  The logical view of conditioning and its application to possibility and evidence theories.  Internat. J. Approx. Reason., 4(1):23–46.
  * Efron, (1979) Efron, B. (1979).  Bootstrap methods: Another look at the jackknife.  Ann. Statist., 7(1):1–26.
  * Efron, (1998) Efron, B. (1998).  R. A. Fisher in the 21st century.  Statist. Sci., 13(2):95–122.
  * Efron and Hinkley, (1978) Efron, B. and Hinkley, D. V. (1978).  Assessing the accuracy of the maximum likelihood estimator: observed versus expected Fisher information.  Biometrika, 65(3):457–487.  With comments by Ole Barndorff-Nielsen, A. T. James, G. K. Robinson and D. A. Sprott and a reply by the authors.
  * Efron and Tibshirani, (1993) Efron, B. and Tibshirani, R. J. (1993).  An Introduction to the Bootstrap.  Chapman & Hall, New York.
  * Ferguson, (1973) Ferguson, T. S. (1973).  A Bayesian analysis of some nonparametric problems.  Ann. Statist., 1:209–230.
  * Fisher, (1935) Fisher, R. A. (1935).  The fiducial argument in statistical inference.  Ann. Eugenics, 6:391–398.
  * (45) Fisher, R. A. (1973a).  Statistical Methods and Scientific Inference.  Hafner Press, New York, 3rd edition.
  * (46) Fisher, R. A. (1973b).  Statistical Methods for Research Workers.  Hafner Publishing Co., New York.  Fourteenth edition—revised and enlarged.
  * Fraser, (2004) Fraser, D. A. S. (2004).  Ancillaries and conditional inference.  Statist. Sci., 19(2):333–369.  With comments and a rejoinder by the author.
  * Fraser, (2014) Fraser, D. A. S. (2014).  Why does statistics have two theories?  In Lin, X., Genest, C., Banks, D. L., Molenberghs, G., Scott, D. W., and Wang, J.-L., editors, Past, Present, and Future of Statistical Science, chapter 22. Chapman & Hall/CRC Press.
  * Fraser et al., (1997) Fraser, D. A. S., Reid, N., and Wong, A. (1997).  Simple and accurate inference for the mean of a gamma model.  Canad. J. Statist., 25(1):91–99.
  * Ghosal and van der Vaart, (2017) Ghosal, S. and van der Vaart, A. (2017).  Fundamentals of Nonparametric Bayesian Inference, volume 44 of Cambridge Series in Statistical and Probabilistic Mathematics.  Cambridge University Press, Cambridge.
  * Ghosh et al., (2006) Ghosh, J. K., Delampady, M., and Samanta, T. (2006).  An Introduction to Bayesian Analysis.  Springer, New York.
  * Ghosh et al., (2010) Ghosh, M., Reid, N., and Fraser, D. A. S. (2010).  Ancillary statistics: A review.  Statist. Sinica, 20:1309–1332.
  * Godambe, (1960) Godambe, V. P. (1960).  An optimum property of regular maximum likelihood estimation.  Ann. Math. Statist., 31:1208–1211.
  * Gong and Meng, (2021) Gong, R. and Meng, X.-L. (2021).  Judicious judgment meets unsettling updating: dilation, sure loss and Simpson’s paradox.  Statist. Sci., 36(2):169–190.
  * Goodman, (1965) Goodman, L. A. (1965).  On simultaneous confidence intervals for multinomial proportions.  Technometrics, 7(2):247–254.
  * Guillaume and Dubois, (2020) Guillaume, R. and Dubois, D. (2020).  A min-max regret approach to maximum likelihood inference under incomplete data.  Internat. J. Approx. Reason., 121:135–149.
  * Hamada et al., (2004) Hamada, M., Johnson, V., Moore, L. M., and Wendelberger, J. (2004).  Bayesian prediction intervals and their relationship to tolerance intervals.  Technometrics, 46(4):452–459.
  * Hannig et al., (2016) Hannig, J., Iyer, H., Lai, R. C. S., and Lee, T. C. M. (2016).  Generalized fiducial inference: a review and new results.  J. Amer. Statist. Assoc., 111(515):1346–1361.
  * Hannig and Xie, (2012) Hannig, J. and Xie, M.-g. (2012).  A note on Dempster–Shafer recombination of confidence distributions.  Electron. J. Stat., 6:1943–1966.
  * Heitjan and Rubin, (1991) Heitjan, D. F. and Rubin, D. B. (1991).  Ignorability and coarse data.  Ann. Statist., 19(4):2244–2253.
  * Hisdal, (1978) Hisdal, E. (1978).  Conditional possibilities, independence, and noninteraction.  Fuzzy Sets and Systems, 1:283–297.
  * Hose, (2022) Hose, D. (2022).  Possibilistic Reasoning with Imprecise Probabilities: Statistical Inference and Dynamic Filtering.  PhD thesis, University of Stuttgart.
  * Hose and Hanss, (2020) Hose, D. and Hanss, M. (2020).  On data-based estimation of possibility distributions.  Fuzzy Sets and Systems, 399:77–94.
  * Hose and Hanss, (2021) Hose, D. and Hanss, M. (2021).  A universal approach to imprecise probabilities in possibility theory.  Internat. J. Approx. Reason., 133:133–158.
  * Hose et al., (2022) Hose, D., Hanss, M., and Martin, R. (2022).  A practical strategy for valid partial prior-dependent possibilistic inference.  In Le Hégarat-Mascle, S., Bloch, I., and Aldea, E., editors, Belief Functions: Theory and Applications (BELIEF 2022), volume 13506 of Lecture Notes in Artificial Intelligence, pages 197–206. Springer.
  * Huber, (1981) Huber, P. J. (1981).  Robust Statistics.  John Wiley & Sons Inc., New York.  Wiley Series in Probability and Mathematical Statistics.
  * Imbens and Rubin, (2015) Imbens, G. W. and Rubin, D. B. (2015).  Causal Inference—for Statistics, Social, and Biomedical Sciences.  Cambridge University Press, New York.
  * (68) Jacob, P. E., Gong, R., Edlefsen, P. T., and Dempster, A. P. (2021a).  A Gibbs sampler for a class of random convex polytopes.  J. Amer. Statist. Assoc., 116(535):1181–1192.
  * (69) Jacob, P. E., Gong, R., Edlefsen, P. T., and Dempster, A. P. (2021b).  Rejoinder—A Gibbs sampler for a class of random convex polytopes.  J. Amer. Statist. Assoc., 116(535):1211–1214.
  * Jaynes, (2003) Jaynes, E. T. (2003).  Probability Theory.  Cambridge University Press, Cambridge.
  * Kalbfleisch and Sprott, (1970) Kalbfleisch, J. D. and Sprott, D. A. (1970).  Application of likelihood methods to models involving large numbers of parameters.  J. Roy. Statist. Soc. Ser. B, 32:175–208.
  * Klein and Moeschberger, (2003) Klein, J. P. and Moeschberger, M. L. (2003).  Survival Analysis.  Springer-Verlag, New York, 2nd edition.
  * Lash, (2017) Lash, T. L. (2017).  The harm done to reproducibility by the culture of null hypothesis significance testing.  Am. J. Epidemiol., 186(6):627–635.
  * Lawrence et al., (2009) Lawrence, E., Liu, C., Vander Weil, S., and Zhang, J. (2009).  A new method for multinomial inference using Dempster–Shafer theory.  https://www.osti.gov/biblio/956387.
  * Little and Rubin, (2002) Little, R. J. A. and Rubin, D. B. (2002).  Statistical Analysis with Missing Data.  Wiley Series in Probability and Statistics. Wiley-Interscience [John Wiley & Sons], Hoboken, NJ, second edition.
  * Liu and Martin, (2021) Liu, C. and Martin, R. (2021).  Inferential models and possibility measures.  Handbook of Bayesian, Fiducial, and Frequentist Inference, to appear; arXiv:2008.06874.
  * Manski, (2003) Manski, C. F. (2003).  Partial Identification of Probability Distributions.  Springer Series in Statistics. Springer-Verlag, New York.
  * Martin, (2018) Martin, R. (2018).  On an inferential model construction using generalized associations.  J. Statist. Plann. Inference, 195:105–115.
  * (79) Martin, R. (2019a).  False confidence, non-additive beliefs, and valid statistical inference.  Internat. J. Approx. Reason., 113:39–73.
  * (80) Martin, R. (2019b).  On valid uncertainty quantification about a model.  In De Bock, J., de Campos, C. P., de Cooman, G., Quaeghebeur, E., and Wheeler, G., editors, Proceedings of the Eleventh International Symposium on Imprecise Probabilities: Theories and Applications, volume 103 of Proceedings of Machine Learning Research, pages 295–303, Thagaste, Ghent, Belgium. PMLR.
  * (81) Martin, R. (2021a).  An imprecise-probabilistic characterization of frequentist statistical inference.  https://researchers.one/articles/21.01.00002.
  * (82) Martin, R. (2021b).  Inferential models and the decision-theoretic implications of the validity property.  https://researchers.one/articles/21.12.00005.
  * Martin, (2022) Martin, R. (2022).  Valid and efficient imprecise-probabilistic inference under partial priors, I. First results.  https://researchers.one/articles/21.05.00001.
  * Martin et al., (2021) Martin, R., Balch, M., and Ferson, S. (2021).  Response to the comment ‘Confidence in confidence distributions!’.  Proc. R. Soc. A., 477:20200579.
  * Martin and Lingham, (2016) Martin, R. and Lingham, R. T. (2016).  Prior-free probabilistic prediction of future observations.  Technometrics, 58(2):225–235.
  * Martin and Liu, (2013) Martin, R. and Liu, C. (2013).  Inferential models: a framework for prior-free posterior probabilistic inference.  J. Amer. Statist. Assoc., 108(501):301–313.
  * (87) Martin, R. and Liu, C. (2014a).  Discussion: Foundations of statistical inference, revisited.  Statist. Sci., 29:247–251.
  * (88) Martin, R. and Liu, C. (2014b).  A note on p-values interpreted as plausibilities.  Statist. Sinica, 24(4):1703–1716.
  * (89) Martin, R. and Liu, C. (2015a).  Conditional inferential models: combining information for prior-free probabilistic inference.  J. R. Stat. Soc. Ser. B. Stat. Methodol., 77(1):195–217.
  * (90) Martin, R. and Liu, C. (2015b).  Inferential Models, volume 147 of Monographs on Statistics and Applied Probability.  CRC Press, Boca Raton, FL.
  * (91) Martin, R. and Liu, C. (2015c).  Marginal inferential models: prior-free probabilistic inference on interest parameters.  J. Amer. Statist. Assoc., 110(512):1621–1631.
  * Martin and Syring, (2022) Martin, R. and Syring, N. (2022).  Direct Gibbs posterior inference on risk minimizers: construction, concentration, and calibration.  In Srinivasa Rao, A. S. R., Young, G. A., and Rao, C. R., editors, Handbook of Statistics: Advancements in Bayesian Methods and Implementation, volume 47, pages 1–41. Elsevier.
  * Mayo, (2018) Mayo, D. G. (2018).  Statistical Inference as Severe Testing.  Cambridge University Press, Cambridge.
  * Murph et al., (2021) Murph, A., Hannig, J., and Williams, J. (2021).  Introduction to generalized fiducial inference.  Handbook on Bayesian, Fiducial, and Frequentist Inference, to appear.
  * Murphy and van der Vaart, (2000) Murphy, S. A. and van der Vaart, A. W. (2000).  On profile likelihood.  J. Amer. Statist. Assoc., 95(450):449–485.  With discussion.
  * Nguyen, (1978) Nguyen, H. T. (1978).  On conditional possibility distributions.  Fuzzy Sets and Systems, 1(4):299–309.
  * Nguyen, (2006) Nguyen, H. T. (2006).  An Introduction to Random Sets.  Chapman & Hall/CRC, Boca Raton, FL.
  * Normand, (1999) Normand, S. (1999).  Meta-analysis: formulating, evaluating, combining, and reporting.  Stat. Med., 18(3):321–359.
  * Owen, (1990) Owen, A. (1990).  Empirical likelihood ratio confidence regions.  Ann. Statist., 18(1):90–120.
  * Owen, (1988) Owen, A. B. (1988).  Empirical likelihood ratio confidence intervals for a single functional.  Biometrika, 75(2):237–249.
  * Owen, (2001) Owen, A. B. (2001).  Empirical Likelihood, volume 92 of Monographs on Statistics and Applied Probability.  Chapman & Hall/CRC Press, Boca Raton, FL.
  * Pearson, (1920) Pearson, K. (1920).  The fundamental problem of practical statistics.  Biometrika, 13:1–16.
  * Pereira and Stern, (2022) Pereira, C. A. B. and Stern, J. M. (2022).  The $e$-value: a fully Bayesian significance measure for precise statistical hypotheses and its research program.  São Paulo J. Math. Sci., 16(1):566–584.
  * Pereira et al., (2008) Pereira, C. A. d. B., Stern, J. M., and Wechsler, S. (2008).  Can a significance test be genuinely Bayesian?  Bayesian Anal., 3(1):79–100.
  * Qin and Lawless, (1994) Qin, J. and Lawless, J. (1994).  Empirical likelihood and general estimating equations.  Ann. Statist., 22(1):300–325.
  * Rao, (1973) Rao, C. R. (1973).  Linear statistical inference and its applications.  Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, New York-London-Sydney, second edition.
  * Reid, (2003) Reid, N. (2003).  Asymptotics and the theory of inference.  Ann. Statist., 31(6):1695–1731.
  * Royall, (1997) Royall, R. M. (1997).  Statistical Evidence, volume 71 of Monographs on Statistics and Applied Probability.  Chapman & Hall, London.
  * Schervish, (1996) Schervish, M. J. (1996).  $P$ values: what they are and what they are not.  Amer. Statist., 50(3):203–206.
  * Schreiber, (2000) Schreiber, T. (2000).  Statistical inference from set-valued observations.  Probab. Math. Statist., 20(2, Acta Univ. Wratislav. No. 2256):223–235.
  * Schweder and Hjort, (2016) Schweder, T. and Hjort, N. L. (2016).  Confidence, Likelihood, Probability, volume 41 of Cambridge Series in Statistical and Probabilistic Mathematics.  Cambridge University Press, New York.
  * Seidenfeld, (1992) Seidenfeld, T. (1992).  R. A. Fisher’s fiducial argument and Bayes’ theorem.  Statist. Sci., 7(3):358–368.
  * Shackle, (1961) Shackle, G. L. S. (1961).  Decision Order and Time in Human Affairs.  Cambridge University Press, Cambridge.
  * Shafer, (1976) Shafer, G. (1976).  A Mathematical Theory of Evidence.  Princeton University Press, Princeton, N.J.
  * Shafer, (1982) Shafer, G. (1982).  Belief functions and parametric models.  J. Roy. Statist. Soc. Ser. B, 44(3):322–352.  With discussion.
  * Shafer and Vovk, (2008) Shafer, G. and Vovk, V. (2008).  A tutorial on conformal prediction.  J. Mach. Learn. Res., 9:371–421.
  * Stern and Pereira, (2014) Stern, J. M. and Pereira, C. A. D. B. (2014).  Bayesian epistemic values: focus on surprise, measure probability!  Log. J. IGPL, 22(2):236–254.
  * Stigler, (1977) Stigler, S. M. (1977).  Do robust estimators work with real data?  Ann. Statist., 5(6):1055–1098.  With discussion and a reply by the author.
  * Swihart and Lindsey, (2022) Swihart, B. and Lindsey, J. (2022).  rmutil: Utilities for nonlinear regression and repeated measurements models.  R package version 1.1.10.
  * Syring and Martin, (2017) Syring, N. and Martin, R. (2017).  Gibbs posterior inference on the minimum clinically important difference.  J. Statist. Plann. Inference, 187:67–77.
  * Syring and Martin, (2019) Syring, N. and Martin, R. (2019).  Calibrating general posterior credible regions.  Biometrika, 106(2):479–486.
  * Syring and Martin, (2022) Syring, N. and Martin, R. (2022).  Gibbs posterior concentration rates under sub-exponential type losses.  Bernoulli, to appear, arXiv:2012.04505.
  * Tang and Leng, (2010) Tang, C. Y. and Leng, C. (2010).  Penalized high-dimensional empirical likelihood.  Biometrika, 97(4):905–919.
  * Thornton and Xie, (2020) Thornton, S. and Xie, M.-g. (2020).  Bridging Bayesian, frequentist and fiducial (BFF) inferences using confidence distribution.  arXiv:2012.04464.
  * Trafimow and Marks, (2015) Trafimow, D. and Marks, M. (2015).  Editorial.  Basic Appl. Soc. Psych., 37(1):1–2.
  * Troffaes and de Cooman, (2014) Troffaes, M. C. M. and de Cooman, G. (2014).  Lower Previsions.  Wiley Series in Probability and Statistics. John Wiley & Sons, Ltd., Chichester.
  * Troffaes et al., (2013) Troffaes, M. C. M., Miranda, E., and Destercke, S. (2013).  On the connection between probability boxes and possibility measures.  Inform. Sci., 224:88–108.
  * Tsybakov, (2009) Tsybakov, A. B. (2009).  Introduction to Nonparametric Estimation.  Springer, New York.
  * Vovk et al., (2005) Vovk, V., Gammerman, A., and Shafer, G. (2005).  Algorithmic Learning in a Random World.  Springer, New York.
  * Walley, (1991) Walley, P. (1991).  Statistical Reasoning with Imprecise Probabilities, volume 42 of Monographs on Statistics and Applied Probability.  Chapman & Hall Ltd., London.
  * Walley, (2002) Walley, P. (2002).  Reconciling frequentist properties with the likelihood principle.  J. Statist. Plann. Inference, 105(1):35–65.
  * Wang et al., (2012) Wang, C. M., Hannig, J., and Iyer, H. K. (2012).  Fiducial prediction intervals.  J. Statist. Plann. Inference, 142(7):1980–1990.
  * Wang and Martin, (2021) Wang, Z. and Martin, R. (2021).  Gibbs posterior inference on a Lévy density under discrete sampling.  arXiv:2109.06567.
  * Wasserman, (2008) Wasserman, L. (2008).  Why isn’t everyone a Bayesian?  In Morris, C. and Tibshirani, R., editors, The Science of Bradley Efron, pages 260–261. Springer, New York.
  * Wasserman et al., (2020) Wasserman, L., Ramdas, A., and Balakrishnan, S. (2020).  Universal inference.  Proceedings of the National Academy of Sciences, 117(29):16880–16890.
  * (136) Wasserman, L. A. (1990a).  Belief functions and statistical inference.  Canad. J. Statist., 18(3):183–196.
  * (137) Wasserman, L. A. (1990b).  Prior envelopes based on belief functions.  Ann. Statist., 18(1):454–464.
  * Wu and Martin, (2022) Wu, P.-S. and Martin, R. (2022).  Generalized Bayes inference on a linear personalized minimum clinically important difference.  arXiv:2208.12565.
  * Xie and Singh, (2013) Xie, M. and Singh, K. (2013).  Confidence distribution, the frequentist distribution estimator of a parameter: a review.  Int. Stat. Rev., 81(1):3–39.
  * Zabell, (1992) Zabell, S. L. (1992).  R. A. Fisher and the fiducial argument.  Statist. Sci., 7(3):369–387.
  * Zadeh, (1975) Zadeh, L. A. (1975).  The concept of a linguistic variable and its application to approximate reasoning. I.  Information Sci., 8:199–249.
  * Zadeh, (1978) Zadeh, L. A. (1978).  Fuzzy sets as a basis for a theory of possibility.  Fuzzy Sets and Systems, 1(1):3–28.
  * Zhang, (2010) Zhang, Z. (2010).  Profile likelihood and incomplete data.  Int. Stat. Rev., 78:102–116.
  * Zhou, (2022) Zhou, M. (2022).  emplik: Empirical Likelihood Ratio for Censored/Truncated Data.  R package version 1.2.