# Core and stability notions in many-to-one matching markets with
indifferences††thanks: We acknowledge financial support from UNSL through
grants 032016 and 030320, from Consejo Nacional de Investigaciones Científicas
y Técnicas (CONICET) through grant PIP 112-200801-00655, and from Agencia
Nacional de Promoción Científica y Tecnológica through grant PICT 2017-2355.

Agustín G. Bonifacio Instituto de Matemática Aplicada San Luis, Universidad
Nacional de San Luis and CONICET, San Luis, Argentina, and RedNIE. Emails:
<EMAIL_ADDRESS>(A. G. Bonifacio<EMAIL_ADDRESS>(N. Juarez),
<EMAIL_ADDRESS>(P. Neme) and<EMAIL_ADDRESS>(J. Oviedo). Noelia
Juarez22footnotemark: 2 Pablo Neme22footnotemark: 2 Jorge
Oviedo22footnotemark: 2

###### Abstract

In a many-to-one matching model with responsive preferences in which
indifferences are allowed, we study three notions of core, three notions of
stability, and their relationships. We show that (i) the core contains the
stable set, (ii) the strong core coincides with the strongly stable set, and
(iii) the super core coincides with the super stable set. We also show how the
core and the strong core in markets with indifferences relate to the stable
matchings of their associated tie-breaking strict markets.

_JEL classification:_ C78; D47.

_Keywords:_ Matching with indifferences; Stability; Strong Stability; Super
Stability; Core; Strong Core; Super Core.

##  1 Introduction

The core is one of the most important solution concepts in cooperative games.
Two-sided matching models can be seen as particular cooperative games. In
these models, a matching is “dominated” if there is a coalition of agents that
prefer another matching in which each agent of the coalition is matched to
agent(s) within the coalition; and a matching is in the “core” if it is
undominated. However, in these two-sided games, the most studied solution
concept is not the core but that of stability. Unlike in models with strict
preferences, where there is a unique concept of stability satisfied by pairs
of agents, in models with indifferences there are several concepts of
stability. Irving (1994) introduces the notions of strongly stable matching
and super stable matching. A matching is “blocked” if it can be dominated via
a coalition made of a single agent or a pair of agents (one from each side of
the market); and a matching is “stable” if it is not blocked. Notice that in
the definition of domination (and therefore in the definition of core) every
coalition plays a potential role, whereas in the definition of blocking (and
therefore in the definition of stability) only singletons and pairs of agents
are involved. In one-to-one matching model with strict preferences, nothing is
lost by ignoring coalitions other than singletons and pairs: the core
coincides with the set of stable matchings (see Roth, 1985). But in the more
general many-to-one model, a matching can be in the core and not be stable. In
our first theorem we show that this is also the case when indifferences are
allowed.

In a many-to-one matching market with responsive preferences and
indifferences, we study two weaker versions of domination (with their
corresponding stronger notions of core) and their associated weaker notions of
blocking (with their corresponding stronger notions of stability) and
investigate their relationships. A matching is “weakly dominated” if (i) there
is a coalition of agents that are at least as well-off in another matching,
(ii) one of them prefers this new matching, and (iii) agents of the coalition
are matched within the coalition in this new matching; and a matching is in
the “strong core” if it is not weakly dominated. A matching is “weakly
blocked” if it can be weakly dominated via a coalition made of a single agent
or a pair of agents (one from each side of the market); and a matching is
“strongly stable” if it is not weakly blocked. An even weaker notion of
domination, called “super weak domination” can be defined by losing condition
(ii) in the definition of weak domination. The associated definitions of
“super core”, “super weak blocking” and “super stable matching” are
straightforward. In this paper, we show that (i) the strong core coincides
with the set of strongly stable matchings, and (ii) the super core coincides
with the set of super stable matchings.

Gale and Shapley (1962) show that at least one stable matching always exists,
even when agents may have indifferences in their preferences. Usually, the
procedure to compute a stable matching consist of breaking ties and then
applying Gale and Shapley’s deferred acceptance algorithm. How these
indifferences may be ordered has both strategic and welfare consequences (see
Erdil and Ergin, 2017; Abdulkadiroğlu and Pathak, 2009). On the other hand,
strongly stable matchings and super stable matchings may not exist. In the
one-to-one model, Irving (1994) presents algorithms for determining whether a
strongly stable matching and/or a super stable matching exist. In each case,
if such a matching exists, the appropriate algorithm constructs one. Manlove
(2002) shows that the set of strongly stable matchings forms a distributive
lattice. Ghosal et al. (2016) present a polynomial-time algorithm for the
generation of all strongly stable matchings. They also give an alternative
prove that the set of strongly stable matching forms a distributive lattice.
In the many-to-one model, Irving et al. (2000) present the first linear-time
algorithm to compute super stable matchings when it exists. Linear programming
approaches to the study of stable and strongly stable matchings in models with
indifferences are also available (see Kwanashie and Manlove, 2014; Juarez et
al., 2021; Kunysz, 2018). Besides these three notions of stability, there are
other solution concepts for models with indifferences. Sotomayor (2011)
proposes Pareto-stability as a solution concept for the one-to-one model with
indifferences and the roommate model. A matching is Pareto-stable if it is
stable and Pareto optimal. She shows that every strongly stable matching is a
Pareto-stable matching and exhibits examples of markets in which there is a
Pareto-stable matching that is not strongly stable and there is a stable
matching that is not Pareto-stable.

The rest of the paper is organized as follows. Preliminaries are presented in
Section 2, where also the three notions of stability and the three notions of
core are introduced. Our results are shown is Section 3. After that, some
conclusions are gathered in Section 4.

##  2 Preliminaries

Let $F$ and $W$ denote disjoint finite sets of _firms_ and _workers_ ,
respectively. Each firm $f\in F$ has a _preference_ relation $R_{f}$ over
$2^{W}$ that is complete and transitive (i.e. a weak order). Each worker has a
_preference_ relation $R_{w}$ that is a weak order over
$F\cup\\{\emptyset\\},$ where $\emptyset$ represents the prospect of being
unemployed. Let $R=(R_{a})_{a\in F\cup W}$ denote the _profile of preferences_
of the agents. For each $a\in F\cup W,$ let $P_{a}$ and $I_{a}$ denote the
antisymmetric and symmetric part of $R_{a},$ respectively. Throughout, we
assume that there is no firm $f\in F$ such that $W^{\prime}I_{f}\emptyset$ for
some $W^{\prime}\subseteq W$ and there is no worker $w\in W$ such that
$fI_{w}\emptyset$ for some $f\in F.$ We call this the _no indifference to the
empty set_ assumption.111This assumption is commonly used in the literature;
see Erdil and Ergin (2008, 2017). For each $f\in F,$ let $q_{f}\geq 1$ denote
the number of positions that firm $f$ has (called $f$’s _quota_), and let
$q=(q_{f})_{f\in F}$ be the _profile of quotas_. We assume that each firm
gives its ranking of workers individually, and orders subsets of workers in a
responsive manner. That is to say, adding “good" workers to a set leads to a
better set, whereas adding “bad" workers to a set leads to a worse set. In
addition, for any two subsets that differ in only one worker, the firm prefers
the subset containing the most preferred worker. Formally,

###### Definition 1

Given $q_{f},$ preference relation $R_{f}$ over $2^{W}$ is responsive if it
satisfies the following conditions:222 Notice that when
$w^{\prime}=\emptyset,$ by _no indifference to the empty set,_ Conditions (i)
and (ii) in Definition 1 imply that for each $T\subseteq{W}$ such that
$|{T}|<q_{f}$ and each $w\in W\setminus T$,  $T\cup\\{w\\}R_{f}T\mbox{ if and
only if }wP_{f}\emptyset.$

  1. (i)

for each $T\subseteq{W}$ such that $|{T}|>q_{f}$, $\emptyset P_{f}T$.

  2. (ii)

for each $T\subseteq{W}$ such that $|T|\leq q_{f},$ each $w^{\prime}\in
T\cup\\{\emptyset\\}$, and each $w\in W\setminus T$,

$(T\setminus\\{w^{\prime}\\})\cup\\{w\\}R_{f}T\mbox{ if and only if
}wR_{f}w^{\prime}.$

A _many-to-one (matching) market_ is denoted by $(F,W,R,q).$ When $q_{f}=1$
for each $f\in F$, the market will be called a _one-to-one (matching) market_.
A matching $\mu$ is a mapping from $F\cup W$ into $2^{F\cup W}$ such that, for
each $w\in{W}$ and each $f\in{F}$:

  1. (i)

$\mu(w)\subseteq{F}$ and $|\mu(w)|\leq 1,$

  2. (ii)

$\mu(f)\subseteq W$ and $|\mu(f)|\leq q_{f},$

  3. (iii)

$\mu(w)=\\{f\\}$ if and only if $w\in\mu(f)$.

Furthermore, the set of all matchings is denoted by $\mathcal{M}.$ Since
workers are assigned to at most one firm, usually we will omit the curly
brackets. For instance, instead of condition (iii) we will write: “$\mu(w)=f$
if and only if $w\in\mu(f)$”. Throughout the paper we identify the market
$(F,W,R,q)$ with its corresponding preference profile $R.$

###  2.1 Stability, strong stability and super stability

In matching models, stability is considered the main property to be satisfied
by any matching. Unlike in models with strict preferences, where there is a
unique concept of stability satisfied by pairs of agents, in models with
indifferences there are several concepts of stability. In the one-to-one
model, a matching is stable if each agent is matched to an acceptable partner,
and there is no firm-worker pair such that they are not matched together and
strictly prefer each other to their current partners. Irving (1994) formulates
two other possible definitions of stability for the one-to-one model with
indifferences. A matching is strongly stable if each agent is matched to an
acceptable partner, and there is no firm-worker pair such that they are not
matched together, one of them strictly prefers the other one to their current
partner, and the other weakly prefers the other one to their current partner.
A matching is super stable if each agent is matched to an acceptable partner,
and there is no firm-worker pair such that they are not matched together and
weakly prefer each other to their current partners.

Now we present three types of blocking pairs, in order to formalize the
different definitions of stability for the many-to-one setting.

###### Definition 2

Let $\mu$ be a matching. We say that the pair $(f,w)\in F\times W$ with
$w\notin\mu(f)$

  1. (i)

blocks $\boldsymbol{\mu}$ whenever

    1. (i.a)

$\left|\mu(f)\right|=q_{f},$ and there is $w^{\prime}$ $\in\mu(f)$ such that
$wP_{f}w^{\prime}$ and $fP_{w}\mu(w)$; or

    2. (i.b)

$\left|\mu(f)\right|<q_{f},$ $wP_{f}\emptyset,$ and $fP_{w}\mu(w)$.

  2. (ii)

weakly blocks $\boldsymbol{\mu}$ whenever

    1. (ii.a)

$\left|\mu(f)\right|=q_{f},$ and there is $w^{\prime}$ $\in\mu(f)$ such that
either $wR_{f}w^{\prime}$ and $fP_{w}\mu(w)$, or $wP_{f}w^{\prime}$ and
$fR_{w}\mu(w)$; or

    2. (ii.b)

$\left|\mu(f)\right|<q_{f},$ $wP_{f}\emptyset,$ and $fR_{w}\mu(w)$.

  3. (iii)

super weakly blocks $\boldsymbol{\mu}$ whenever

    1. (iii.a)

$\left|\mu(f)\right|=q_{f},$ and there is $w^{\prime}\in\mu(f)$ such that
$wR_{f}w^{\prime}$ and $fR_{w}\mu(w)$; or

    2. (iii.b)

$\left|\mu(f)\right|<q_{f},$ $wP_{f}\emptyset,$ and $fR_{w}\mu(w).$

Now we are in a position to define the three notions of stability that we use
throughout the paper. First, we present a common condition that all stability
notion must satisfy. We say that a matching $\mu$ is individually rational if
it is not blocked by any individual agent, i.e., (i) for each $w\in W$,
$\mu(w)P_{w}\emptyset$; and (ii) for each $f\in F$, $wP_{f}\emptyset$ for each
$w\in\mu(f).$

###### Definition 3

We say that an individually rational matching is

  * (i)

stable if it has no blocking pair.

  * (ii)

strongly stable if it has no weakly blocking pair.

  * (iii)

super stable if it has no super weakly blocking pair.

Denote by $\mathcal{S}$, $\mathcal{SS}$ and $\mathcal{SSS}$ the set of all
stable, strongly stable, and super stable matchings, respectively.

The existence of stable matchings in models with indifferences is guaranteed:
by breaking ties arbitrarily, we obtain a model with strict preferences. A
stable matching in this strict model is a stable matching in the original
model with indifferences. Gale and Shapley (1962) show that each market with
strict preferences has at least one stable matching and compute it by the
deferred acceptance algorithm. On the other hand, strongly stable matchings
and super stable matchings could not exist. Irving (1994) presents algorithms
for determining whether a strongly stable matching and/or a super stable
matching exist. In each case, if such a matching exists, the appropriate
algorithm constructs one.

The following example shows that the super stable matching set can be a proper
subset of the strongly stable matching set and, in turn, the strongly stable
matching set can be a proper subset of the stable matchings set.

###### Example 1

Let $(F,W,R,q)$ be a matching market where
$F=\\{f_{1},f_{2},f_{3}\\},W=\\{w_{1},w_{2},w_{3},w_{4}\\},$ $q_{f_{1}}=2$,
$q_{f_{i}}=1$ for $i=2,3$ and the preference profile is given
by:444“$R_{f_{1}}:w_{1},w_{4},[w_{2},w_{3}]$” indicates that
$w_{1}P_{f_{1}}w_{4}P_{f_{1}}w_{2}I_{f_{1}}w_{3}.$

$R_{f_{1}}:w_{1},w_{4},\left[w_{2},w_{3}\right]$
---
$R_{f_{2}}:\left[w_{2},w_{3}\right],w_{1},w_{4}$
$R_{f_{3}}:\left[w_{2},w_{3}\right],w_{4},w_{1}$
$R_{w_{1}}:f_{3},f_{1},f_{2}$
---
$R_{w_{2}}:f_{1},\left[f_{2},f_{3}\right]$
$R_{w_{3}}:f_{1},\left[f_{2},f_{3}\right]$
$R_{w_{4}}:f_{2},f_{3},f_{1}$

Consider the following stable matchings:

$\mu_{1}=\begin{pmatrix}f_{1}&f_{2}&f_{3}\\\ w_{2}w_{3}&w_{4}&w_{1}\\\
\end{pmatrix},~{}$ $\mu_{2}=\begin{pmatrix}f_{1}&f_{2}&f_{3}\\\
w_{1}w_{4}&w_{2}&w_{3}\\\ \end{pmatrix},$ and
$\mu_{3}=\begin{pmatrix}f_{1}&f_{2}&f_{3}\\\ w_{1}w_{2}&w_{4}&w_{3}\\\
\end{pmatrix}.$

Notice that $\mu_{1}$ matches each worker to her most preferred firm. Since
each worker does not have indifference in the top of her preference, there are
no super weakly blocking pairs for $\mu_{1}$. Therefore,
$\mu_{1}\in\mathcal{SSS}$. Since $(f_{2},w_{3})$ is a super weakly blocking
pair for $\mu_{2}$, $\mu_{2}\notin\mathcal{SSS}.$ It can be checked that
$\mu_{2}$ does not have any strongly blocking pair, thus
$\mu_{2}\in\mathcal{SS}$. Furthermore, since $(f_{1},w_{3})$ is a weakly
blocking pair for $\mu_{3}$, $\mu_{3}\notin\mathcal{SS}$. $\Diamond$

###  2.2 Core, strong core, and super core

A cooperative game consists of a set of players; a set of feasible outcomes;
preferences of the players over outcomes; and the “rules of the game”, that
specify which coalitions of players are empowered to enforce which outcomes
(see Chapter 3 in Roth and Sotomayor, 1990). Every many-to-one matching market
with indifferences $(F,W,R,q)$ induces a cooperative game as follows: the set
of players is, of course, $F\cup W;$ the feasible outcomes are equal to the
set of all possible matchings $\mathcal{M};$ the preferences over outcomes
(matchings) are induced from the profile $R$ of preferences over (subsets) of
agents in the straightforward way; and the rules of game specify that a
coalition $C\subseteq F\cup W$ is empowered to enforce matching
$\mu^{\prime}\in\mathcal{M}$ if and only if $\mu^{\prime}(C)=C.$ This implies
that every worker in coalition $C$ is assigned to some firm in $C$ by
$\mu^{\prime}$ and that every firm in coalition $C$ is assigned to some subset
of workers in $C$ by $\mu^{\prime}.$

The rules of the game and the preferences of the agents allow us to define
three domination relations on the outcomes of the game:

###### Definition 4

Let $\mu,\mu^{\prime}\in\mathcal{M}$ and let $C\subseteq F\cup W$ be a non-
empty coalition such that $\mu^{\prime}(C)=C.$

  * (i)

$\boldsymbol{\mu^{\prime}$\textbf{dominates $\mu$ via}$C}$ if
$\mu^{\prime}(c)P_{c}\mu(c)$ for each $c\in C.$

  * (ii)

$\boldsymbol{\mu^{\prime}$\textbf{weakly dominates $\mu$ via}$C}$ if
$\mu^{\prime}(c)R_{c}\mu(c)$ for each $c\in C,$ and there is $c^{\prime}\in C$
such that $\mu^{\prime}(c^{\prime})P_{c^{\prime}}\mu(c^{\prime}).$

  * (iii)

$\boldsymbol{\mu^{\prime}$\textbf{super weakly dominates $\mu$ via}$C}$ if
there is $c\in C$ such that $\mu(c)\neq\mu^{\prime}(c)$, and
$\mu^{\prime}(c^{\prime})R_{c^{\prime}}\mu(c^{\prime})$ for each
$c^{\prime}\in C.$

###### Definition 5

The set of all matchings that are not

  * (i)

dominated is the core.

  * (ii)

weakly dominated is the strong core.

  * (iii)

super weakly dominated is the super core.

Denote by $\mathcal{C},$ $\mathcal{C}_{S},$ and $\mathcal{C}_{SS}$ the core,
the strong core, and the super core, respectively.

By definition, the core includes the strong core and the strong core includes
the super core.

##  3 Results

In this section, unless otherwise specified, all the results apply to the
many-to-one model with indifferences. In the one-to-one setting with strict
preferences, the core coincides with the strong core (Roth, 1985). Next, we
show that this result holds even when indifferences are allowed.

###### Proposition 1

For any one-to-one market with indifferences, $\mathcal{C}=\mathcal{S}$.

_Proof._ First, we prove that $\mathcal{C}\subseteq\mathcal{S}.$ Assume that
$\mu\notin\mathcal{S}$. If $\mu$ is not an individually rational matching,
then there is $c\in F\cup W$ such that $\emptyset P_{c}\mu(c).$ Let
$\mu^{\prime}$ be a matching such that $\mu^{\prime}(c)=\emptyset$. Thus,
$\mu^{\prime}$ dominates $\mu$ via $C=\\{c\\}.$ Now, assume that there is a
blocking pair $(f,w)$ of $\mu$. That is, $wP_{f}\mu(f)$ and $fP_{w}\mu(w).$
Let matching $\mu^{\prime}$ be such that $\mu^{\prime}(w)=f$. Let
$C=\\{f,w\\}$. Obviously, $\mu^{\prime}(C)=C$ and it is straightforward that
$\mu^{\prime}$ dominates $\mu$ via $C.$ Therefore, $\mu\notin\mathcal{C}.$
Next, we prove that $\mathcal{S}\subseteq\mathcal{C}.$ Assume that
$\mu\in\mathcal{S}$ and $\mu\notin\mathcal{C}.$ Then, there are a matching
$\mu^{\prime}$ and a non-empty coalition $C\subseteq F\cup W$ such that
$\mu^{\prime}$ dominates $\mu$ via $C$. Take any $c\in C.$ If
$\mu^{\prime}(c)=\emptyset,$ since $\mu^{\prime}$ dominates $\mu,$ we have
$\emptyset=\mu^{\prime}(c)P_{c}\mu(c),$ contradicting the individual
rationality of $\mu.$ Hence, $\mu^{\prime}(c)\neq\emptyset$ for each $c\in C,$
implying $W\cap C\neq\emptyset.$ Let $w\in W\cap C$ and let
$f=\mu^{\prime}(w).$ Since $\mu^{\prime}(C)=C$, $f\in C$. Since $\mu^{\prime}$
dominates $\mu$, it follows that $f=\mu^{\prime}(w)P_{w}\mu(w)$ and
$w=\mu^{\prime}(f)P_{f}\mu(f)$. Thus, $(f,w)$ blocks $\mu,$ contradicting the
stability of $\mu.$ Therefore, $\mu\in\mathcal{C}.$ $\square$

In the many-to-one setting, the core is no longer equal to the stable matching
set, only one inclusion holds:

###### Theorem 1

$\mathcal{S}\subseteq\mathcal{C}$.

_Proof._ Let $\mu\in\mathcal{S}$ and assume $\mu\notin\mathcal{C}.$ Then,
there are a non-empty coalition $C\subseteq F\cup W$ and a matching
$\mu^{\prime}\in\mathcal{M}$ such that $\mu^{\prime}(C)=C$ and
$\mu^{\prime}(c)P_{c}\mu(c)$ for each $c\in C.$ First, we claim that $C\cap
F\neq\emptyset.$ Otherwise, $C\cap F=\emptyset$ implies, for each $w\in C,$
that $\mu^{\prime}(w)=\emptyset$ (since $\mu^{\prime}(C)=C$), and therefore
$\emptyset=\mu^{\prime}(w)P_{w}\mu(w),$ contradicting the individual
rationality of $\mu.$ So take any $f\in C$. Since $\mu^{\prime}$ dominated
$\mu$ via $C$, $\mu^{\prime}(f)P_{f}\mu(f).$ Now we claim that
$\mu^{\prime}(f)\setminus\mu(f)\neq\emptyset.$ Otherwise,
$\mu^{\prime}(f)\setminus\mu(f)=\emptyset$, $\mu^{\prime}(f)P_{f}\mu(f)$ imply
$\mu^{\prime}(f)\subset\mu(f).$ Let
$\mu(f)\setminus\mu^{\prime}(f):=\\{w_{1},\ldots,w_{\ell}\\}$. By individual
rationality of $\mu$, $w_{i}P_{f}\emptyset$ for each $i=1,\ldots,\ell.$ By
responsiveness of $R_{f}$,

$\mu(f)=\mu^{\prime}(f)\cup\\{w_{1},\ldots,w_{\ell}\\}P_{f}\mu^{\prime}(f)\cup\\{w_{1},\ldots,w_{\ell-1}\\}P_{f}\cdots
P_{f}\mu^{\prime}(f)\cup\\{w_{1}\\}P_{f}\mu^{\prime}(f).$

Thus $\mu(f)P_{f}\mu^{\prime}(f),$ contradicting $\mu^{\prime}(f)P_{f}\mu(f)$.
Therefore, $\mu^{\prime}(f)\setminus\mu(f)\neq\emptyset.$ Define

$\mu^{\prime}(f)\setminus\mu(f):=\\{w^{\prime}_{1},\ldots,w^{\prime}_{k}\\}$

where subscripts are chosen so that $w^{\prime}_{i}R_{f}w^{\prime}_{i+1}$ for
each $i=1\ldots,k-1,$ and

$\mu(f)\setminus\mu^{\prime}(f):=\\{w_{1},\ldots,w_{\ell}\\}$

where subscripts are chosen so that $w_{i}R_{f}w_{i+1}$ for each
$i=1\ldots,\ell-1.$ Now, there are two cases to consider:

  * $\boldsymbol{1}.$

$\boldsymbol{|\mu^{\prime}(f)|\leq|\mu(f)|}$. Then,
$|\mu^{\prime}(f)\setminus\mu(f)|\leq|\mu(f)\setminus\mu^{\prime}(f)|.$ First,
we claim that

$w^{\prime}_{1}P_{f}w_{\ell}.$ (1)

Otherwise,

$w_{1}R_{f}\cdots R_{f}w_{\ell}R_{f}w^{\prime}_{1}R_{f}\cdots
R_{f}w^{\prime}_{k}$

and, by responsiveness of $R_{f}$ and the individual rationality of $\mu$,
since $\ell\geq k$

$\mu(f)P_{f}\mu(f)\setminus\\{w_{\ell}\\}P_{f}\cdots
P_{f}\mu(f)\setminus\\{w_{k+1},\ldots,w_{\ell}\\}.$ (2)

Define $\widetilde{W}:=\mu^{\prime}(f)\cap\mu(f).$ Notice that
$\mu(f)\setminus\\{w_{k+1},\ldots,w_{\ell}\\}=\widetilde{W}\cup\\{w_{1},\ldots,w_{k}\\}.$
Again, by responsiveness of $R_{f}$,

$\widetilde{W}\cup\\{w_{1},\ldots,w_{k}\\}R_{f}\widetilde{W}\cup\\{w_{1},\ldots,w^{\prime}_{k}\\}R_{f}\cdots
R_{f}\widetilde{W}\cup\\{w^{\prime}_{1}\ldots,w^{\prime}_{k}\\}.$ (3)

Notice that
$\widetilde{W}\cup\\{w^{\prime}_{1},\ldots,w^{\prime}_{k}\\}=\mu^{\prime}(f).$
Thus, by (2) and (3), $\mu(f)R_{f}\mu^{\prime}(f)$. This contradicts that
$\mu^{\prime}(f)P_{f}\mu(f)$ and, therefore, (1) holds and the claim is
proven. Since $f\in C$ and $\mu^{\prime}(C)=C$, $w^{\prime}_{1}\in C$. As
$\mu^{\prime}$ dominates $\mu$ via $C$,

$f=\mu^{\prime}(w^{\prime}_{1})P_{w^{\prime}_{1}}\mu(w^{\prime}_{1}).$ (4)

If $|\mu(f)|=q_{f}$, by (1) and (4), $(f,w^{\prime}_{1})$ is a blocking pair
for $\mu$. If $|\mu(f)|<q_{f}$, by (1) we have $w^{\prime}_{1}P_{f}w_{\ell}$,
and by the individual rationality of $\mu$, $w_{\ell}P_{f}\emptyset.$ Hence,
$w^{\prime}_{1}P_{f}\emptyset$ and, therefore, together with (4),
$(f,w^{\prime}_{1})$ is a blocking pair for $\mu$.

  * $\boldsymbol{2}.$

$\boldsymbol{|\mu^{\prime}(f)|>|\mu(f)|}$. First, we claim that

$w^{\prime}_{1}P_{f}\emptyset.$ (5)

Otherwise,

$\emptyset P_{f}w^{\prime}_{1}R_{f}\cdots R_{f}w^{\prime}_{k}.$

Define $\widetilde{W}:=\mu^{\prime}(f)\cap\mu(f).$ By responsiveness of
$R_{f}$, since $\ell<k$

$\mu(f)P_{f}(\mu(f)\setminus\\{w_{1}\\})\cup\\{w_{1}^{\prime}\\}P_{f}\cdots
P_{f}\widetilde{W}\cup\\{w_{1}^{\prime},\ldots,w_{\ell}^{\prime}\\}.$ (6)

Again, by responsiveness of $R_{f}$,

$\widetilde{W}\cup\\{w_{1}^{\prime},\ldots,w_{\ell}^{\prime}\\}P_{f}\widetilde{W}\cup\\{w_{1}^{\prime},\ldots,w^{\prime}_{\ell}\
,w_{\ell+1}^{\prime}\\}P_{f}\cdots
P_{f}\widetilde{W}\cup\\{w^{\prime}_{1}\ldots,w^{\prime}_{k}\\}.$ (7)

Notice that
$\widetilde{W}\cup\\{w^{\prime}_{1},\ldots,w^{\prime}_{k}\\}=\mu^{\prime}(f).$
Thus, by (6) and (7), $\mu(f)P_{f}\mu^{\prime}(f)$. This contradicts that
$\mu^{\prime}$ dominates $\mu$ via $C$ and, therefore, (5) holds and the claim
is proven.

Notice that since $\mu^{\prime}$ is a matching,
$q_{f}\geq|\mu^{\prime}(f)|>|\mu(f)|$. Since $f\in C$ and $\mu^{\prime}(C)=C$,
$w^{\prime}_{1}\in C$. As $\mu^{\prime}$ dominates $\mu$ via $C$, (4) holds,
and together with (5) imply that $(f,w^{\prime}_{1})$ is a blocking pair for
$\mu$.

Given that in each case we find a blocking pair for $\mu$, we contradict the
fact that $\mu\in\mathcal{S}.$ Therefore, $\mu\in\mathcal{C}.$ $\square$

Since the stable matching set is always non-empty, the following holds:

###### Remark 1

$\mathcal{C}\neq\emptyset.$

Next, using Example 1, we show that the inclusion stated in Theorem 1 can be a
proper inclusion.

Example 1 (continued) _Consider matching
$\mu_{4}=\begin{pmatrix}f_{1}&f_{2}&f_{3}\\\ w_{2}w_{3}&w_{1}&w_{4}\\\
\end{pmatrix}$. The pair $(f_{1},w_{1})$ blocks $\mu_{4}$ and, therefore,
$\mu_{4}\notin\mathcal{S}$. However, we will show that
$\mu_{4}\in\mathcal{C}$. Assume that this is not the case. Then, there are a
coalition of agents $C$ and a matching $\mu^{\prime}$ such that
$\mu^{\prime}(C)=C$ and $\mu^{\prime}$ dominates $\mu_{4}$ via $C$. Since
$w_{2}$ and $w_{3}$ are matched to their most preferred firm in $\mu_{4}$,
then $w_{2}$ and $w_{3}$ cannot be part of coalition $C$. Assume that
$w_{4}\in C$. Since $\mu_{4}(w_{4})=f_{3}$ and $f_{2}$ is the only firm
preferred by $w_{4}$ to $f_{3}$, $f_{2}$ must belong to coalition $C$ and
$\mu^{\prime}(w_{4})=f_{2}.$ However,
$\mu_{4}(f_{2})=w_{1}P_{f_{2}}w_{4}=\mu^{\prime}(f_{2})$ contradincting that
$\mu^{\prime}$ dominates $\mu_{4}$ via $C$. Lastly, assume that $w_{1}\in C$.
Thus, either $f_{1}$ or $f_{3}$ belong to $C$. If $f_{1}\in C$ and
$\mu^{\prime}(w_{1})=f_{1}$, in order that $\mu^{\prime}$ dominates $\mu_{4}$
via $C$ we need that $|\mu^{\prime}(f_{1})|=2$. Then, some other worker
besides $w_{1}$ must belong to $C$, contradicting the previous arguments. If
$f_{3}\in C$ and $\mu^{\prime}(w_{1})=f_{3}$, then
$\mu_{4}(f_{3})=w_{4}P_{f_{3}}w_{1}=\mu^{\prime}(f_{3})$. This contradicts
that $\mu^{\prime}$ dominates $\mu_{4}$ via $C$. Therefore, $\mu_{4}$ is
undominated implying that $\mu_{4}\in\mathcal{C}\setminus\mathcal{S}.$_
$\Diamond$

In a many-to-one setting with strict and responsive preferences, the strong
core coincides with the set of stable matchings (Roth, 1985). However, if we
allow indifferences, the following result shows that the strong core coincides
with the set of strongly stable matchings.

###### Theorem 2

$\mathcal{C}_{S}=\mathcal{SS}.$

_Proof._ First, we prove that $\mathcal{C}_{S}\subseteq\mathcal{SS}.$ Assume
that $\mu\notin\mathcal{SS}$. We want to see that $\mu\notin\mathcal{C}_{S}.$
There are two cases to consider:

  * $\boldsymbol{1}$.

$\boldsymbol{\mu}$ is not individually rational. Thus, there are $f\in F$ and
$w\in\mu(f)$ such that either $\emptyset P_{w}f$ or $\emptyset P_{f}w.$ If
$\emptyset P_{w}f$, let $\mu^{\prime}$ be a matching such that
$\mu^{\prime}(w)=\emptyset$. Thus, $\mu^{\prime}$ weakly dominates $\mu$ via
coalition $\left\\{w\right\\}.$ Therefore $\mu\notin\mathcal{C}_{S}.$ If there
is $w\in\mu(f)$ such that $\emptyset P_{f}w,$ let $\mu^{\prime}$ be a matching
such that $\mu^{\prime}(f)=\mu(f)\setminus\\{w\\}$. Thus, $\mu^{\prime}$
weakly dominates $\mu$ via coalition
$C=\\{f\\}\cup\left(\mu(f)\setminus\\{w\\}\right).$ Therefore
$\mu\notin\mathcal{C}_{S}.$

  * $\boldsymbol{2}$.

$\boldsymbol{\mu}$ is individually rational. Then, since
$\mu\notin\mathcal{SS},$ there is a weakly blocking pair $(f,w^{\prime})$ of
$\mu.$ There are two subcases to consider:

    1. $\boldsymbol{2.1}$.

$\boldsymbol{|\mu(f)|=q_{f}}.$ Since $(f,w^{\prime})$ is a weakly blocking
pair for $\mu$, there is $\overline{w}$ $\in\mu(f)$ such that either
$w^{\prime}P_{f}\overline{w}\text{ and }fR_{w^{\prime}}\mu(w^{\prime})$ or
$w^{\prime}R_{f}\overline{w}\text{ and }fP_{w^{\prime}}\mu(w^{\prime}).$
Consider coalition
$C=\\{f,w^{\prime}\\}\cup\left(\mu(f)\setminus\\{\overline{w}\\}\right)$. Let
matching $\mu^{\prime}$ be such that $\mu^{\prime}(w^{\prime})=f$ and
$\mu^{\prime}(w)=f$ for each $w\in\mu(f)\setminus\\{\overline{w}\\}.$ This
implies that
$\mu^{\prime}(f)=\left(\mu(f)\setminus\\{\overline{w}\\}\right)\cup\\{w^{\prime}\\}$.
By definition of $\mu^{\prime}$, $\mu^{\prime}(C)=C.$ We claim that
$\mu^{\prime}$ dominates $\mu$ via $C.$ Since $w^{\prime}P_{f}\overline{w}$,
by responsiveness,

$\mu^{\prime}(f)=\left(\mu(f)\setminus\\{\overline{w}\\}\right)\cup\\{w^{\prime}\\}P_{f}\mu(f).$
(8)

By definition of $\mu^{\prime}$, $\mu^{\prime}(w)=\mu(w)$ and, therefore,
$\mu^{\prime}(w)I_{w}\mu(w)$ for each $w\in C\setminus\\{w^{\prime}\\}$.
Finally, since $(f,w^{\prime})$ is a weakly blocking pair for $\mu$,

$f=\mu^{\prime}(w^{\prime})P_{w^{\prime}}\mu(w^{\prime}).$ (9)

Hence, $\mu^{\prime}$ weakly dominates $\mu$ via $C$.

    2. $\boldsymbol{2.2}$.

$\boldsymbol{|\mu(f)|<q_{f}}.$ Consider coalition
$C=\\{f,w^{\prime}\\}\cup\mu(f)$. Let matching $\mu^{\prime}$ be such that
$\mu^{\prime}(w^{\prime})=f$ and $\mu^{\prime}(w)=f$ for each $w\in\mu(f).$
This implies that $\mu^{\prime}(f)=\mu(f)\cup\\{w^{\prime}\\}$. By definition
of $\mu^{\prime}$, $\mu^{\prime}(C)=C.$ We claim that $\mu^{\prime}$ weakly
dominates $\mu$ via $C.$ First consider $w\in\mu(f)\setminus\\{w^{\prime}\\}$.
By definition of $\mu^{\prime},$ $\mu^{\prime}(w)=\mu(w)$ and then
$\mu^{\prime}(w)R_{w}\mu(w)$. Since $(f,w^{\prime})$ is a weakly blocking pair
for $\mu$, we have that $fR_{w^{\prime}}\mu(w^{\prime})$ and
$w^{\prime}P_{f}\emptyset$. Definition of $\mu^{\prime}$,
$w^{\prime}P_{f}\emptyset$, and responsiveness imply
$\mu^{\prime}(f)P_{f}\mu(f)$. Furthermore, $\mu^{\prime}(w^{\prime})=f$ and
$fR_{w^{\prime}}\mu(w^{\prime})$ imply
$\mu^{\prime}(w^{\prime})R_{w^{\prime}}\mu(w^{\prime}).$ Thus, $\mu^{\prime}$
weakly dominates $\mu$ via $C$. Therefore $\mu\notin\mathcal{C}_{S}.$

Next, we prove that $\mathcal{SS}\subseteq\mathcal{C}_{S}.$ Assume that
$\mu\in\mathcal{SS}$ and $\mu\notin\mathcal{C}_{S}.$ Thus, there are a non-
empty coalition $C$ and a matching $\mu^{\prime}$ such that $\mu^{\prime}$
weakly dominates $\mu$ via $C.$ There are two cases to consider:

  1. $\boldsymbol{1}.$

There is $\boldsymbol{f\in C$suchthat$\mu^{\prime}(f)P_{f}\mu(f)}$. Now,
following similar reasonings to the ones in the proof of Theorem 1, and
replacing (4) by

$f=\mu^{\prime}(w^{\prime}_{1})R_{w^{\prime}_{1}}\mu(w^{\prime}_{1}),$

we can prove that $(f,w^{\prime}_{1})$ is a weakly blocking pair for $\mu$.

  2. $\boldsymbol{2}.$

There is $\boldsymbol{\widehat{w}\in
C$suchthat$\mu^{\prime}(\widehat{w})P_{\widehat{w}}\mu(\widehat{w})}$. Let
$f=\mu^{\prime}(\widehat{w})$. Thus, $f\in C$. Since $\mu^{\prime}$ weakly
dominates $\mu$ via $C$, $\mu^{\prime}(f)R_{f}\mu(f).$ Assume w.l.o.g. that
$wP_{f}\emptyset$ for each $w\in\mu^{\prime}(f)$.555Otherwise, if
$w^{\prime}\in\mu^{\prime}(f)$ is such that $\emptyset P_{f}w^{\prime}$ we
have, by responsiveness,
$\mu^{\prime}(f)\setminus\\{w^{\prime}\\}P_{f}\mu^{\prime}(f)$. Let
$\mu^{\prime\prime}(f)=\mu^{\prime}(f)\setminus\\{w^{\prime}\\}$ and
$\mu^{\prime\prime}(a)=\mu^{\prime}(a)$ for each $a\in
C\setminus\\{f,w^{\prime}\\}.$ Then, $\mu^{\prime\prime}$ dominates $\mu$ via
$C\setminus\\{w^{\prime}\\}.$ There are two subcases to consider:

     * $\boldsymbol{2.1}.$

$\boldsymbol{\mu^{\prime}(f)P_{f}\mu(f)}$. Following the arguments of Case 1,
the pair $(f,\widehat{w})$ is a weakly blocking pair for $\mu.$

     * $\boldsymbol{2.2}.$

$\boldsymbol{\mu^{\prime}(f)I_{f}\mu(f)}$. First consider the case
$|\mu^{\prime}(f)|>|\mu(f)|$. Since $\mu^{\prime}$ is a matching,
$q_{f}\geq|\mu^{\prime}(f)|>|\mu(f)|$. Also $\widehat{w}\in C$ such that
$f=\mu^{\prime}(\widehat{w})P_{\widehat{w}}\mu(\widehat{w})$ together with the
fact that $\widehat{w}P_{f}\emptyset$ imply that $(f,\widehat{w})$ is a weakly
blocking pair for $\mu.$

Now consider the case $|\mu^{\prime}(f)|\leq|\mu(f)|$. Then,
$|\mu^{\prime}(f)\setminus\mu(f)|\leq|\mu(f)\setminus\mu^{\prime}(f)|.$ By
hypothesis, $\widehat{w}\in\mu^{\prime}(f)\setminus\mu(f).$

Let

$\mathcal{X}=\\{w\in\mu^{\prime}(f)\setminus\mu(f):wR_{f}w_{\ell}\\},$

and

$\mathcal{Y}=\\{w\in\mu^{\prime}(f)\setminus\mu(f):f=\mu^{\prime}(w)P_{w}\mu(w)\\}.$

Note that $\mathcal{Y}\neq\emptyset$, since $\widehat{w}\in\mathcal{Y}$.

First, consider $\mathcal{X}\cap\mathcal{Y}\neq\emptyset$. Let
$\overline{w}\in\mathcal{X}\cap\mathcal{Y}.$ Then, the pair $(f,\overline{w})$
is a weakly blocking pair for $\mu.$

Second, consider $\mathcal{X}\cap\mathcal{Y}=\emptyset$. Then,
$\mathcal{Y}\subseteq\mathcal{X}^{c}$ and since
$\mathcal{Y}\neq\emptyset,~{}\mathcal{X}^{c}\neq\emptyset.$666By
$\mathcal{X}^{c}$ we denote the complement of $\mathcal{X}.$ We claim that

there is $\overline{w}\in\mathcal{X}$ such that $\overline{w}P_{f}w_{\ell}$.
(9)

Otherwise, $w_{\ell}R_{f}w$ for each $w\in\mathcal{X}$. Moreover, by
definition of $\mathcal{X}$, $wR_{f}w_{\ell}$ for each $w\in\mathcal{X}$.
Thus, $wI_{f}w_{\ell}$ for each $w\in\mathcal{X}.$ Let
$\mathcal{X}=\\{w^{\prime}_{1},\ldots,w^{\prime}_{m}\\}.$ Notice that $m<k$.
Hence, since $wI_{f}w_{\ell}$ for each $w\in\mathcal{X}$,

$\mu(f)R_{f}\mu(f)\setminus\\{w_{1}\\}\cup\\{w^{\prime}_{1}\\}R_{f}\cdots
R_{f}\mu(f)\setminus\\{w_{1},\ldots,w_{m}\\}\cup\\{w^{\prime}_{1},\ldots,w^{\prime}_{m}\\}.$
(10)

Now, since $w_{\ell}P_{f}w$ for each $w\in\mathcal{X}^{c}$, we have

$\begin{split}\mu(f)\setminus\\{w_{1},\ldots,w_{m}\\}\cup\\{w^{\prime}_{1},\ldots,w^{\prime}_{m}\\}P_{f}&\\\
\mu(f)\setminus\\{w_{1},\ldots,w_{m},w_{m+1}\\}\cup\\{&w^{\prime}_{1},\ldots,w^{\prime}_{m},w^{\prime}_{m+1}\\}P_{f}\cdots
P_{f}\\\
&\mu(f)\setminus\\{w_{1},\ldots,w_{k}\\}\cup\\{w^{\prime}_{1},\ldots,w^{\prime}_{k}\\}.\end{split}$
(11)

Lastly, by the individual rationality of $\mu$, $wP_{f}\emptyset$ for each
$w\in\mu$

$\begin{split}\mu(f)\setminus\\{w_{1},\ldots,w_{k}\\}\cup\\{w^{\prime}_{1},\ldots,w^{\prime}_{k}\\}P_{f}&\\\
\mu(f)\setminus\\{w_{1},\ldots,w_{k},w_{k+1}\\}\cup&\\{w^{\prime}_{1},\ldots,w^{\prime}_{k}\\}P_{f}\cdots
P_{f}\\\
\mu(f)\setminus\\{w_{1},&\ldots,w_{\ell}\\}\cup\\{w^{\prime}_{1},\ldots,w^{\prime}_{k}\\}=\mu^{\prime}(f).\end{split}$
(12)

By (10), (11) and (12), $\mu(f)P_{f}\mu^{\prime}(f)$. This contradicts this
subcase’s hypothesis. Then, (9) holds. Since $f\in C$ and
$\overline{w}\in\mu^{\prime}(f)$, $\overline{w}\in C$. Then,
$\mu^{\prime}(\overline{w})R_{\overline{w}}\mu(\overline{w})$. This fact
together with (9) imply that $(f,\overline{w})$ is a weakly blocking pair for
$\mu.$

Given that in each case we find a weakly blocking pair for $\mu$, we
contradict the fact that $\mu\in\mathcal{SS}.$ Therefore,
$\mu\in\mathcal{C}_{S}.$ $\square$

Note, however, that the strong core may be empty. To see this, consider the
following example due to Roth and Sotomayor (1990) (p. 167). There are two
workers and one firm, with quota equal to one, that is acceptable to but
indifferent between both workers. Then both individually rational matchings
are weakly dominated (by one another) even though both are stable. This
example, together with Theorem 2 confirms the fact that, as we previously
mentioned, the set $\mathcal{SS}$ may be empty.

The previous theorem shows that nothing is lost by ignoring coalitions other
than singletons and pairs when studying weak domination: the strong core
coincides with the set of strongly stable matchings. The following result
shows that the same is true for super weak domination:

###### Theorem 3

$\mathcal{C}_{SS}=\mathcal{SSS}.$

_Proof._ First, we prove that $\mathcal{C}_{SS}\subseteq\mathcal{SSS}.$ Assume
that $\mu\notin\mathcal{SSS}$. We want to see that
$\mu\notin\mathcal{C}_{SS}.$ There are two cases to consider:

  * $\boldsymbol{1}$.

$\boldsymbol{\mu}$ is not individually rational. To prove this case, we can
construct matchings $\mu^{\prime}$ that super weakly dominates $\mu$ in an
analogous way to Case 1 in the proof of Theorem 2.

  * $\boldsymbol{2}$.

$\boldsymbol{\mu}$ is individually rational. Then, since
$\mu\notin\mathcal{SSS},$ there is a super weakly blocking pair
$(f,w^{\prime})$ of $\mu.$ There are two subcases to consider:

    1. $\boldsymbol{2.1}$.

$\boldsymbol{|\mu(f)|=q_{f}}.$ Since $(f,w^{\prime})$ is a super weakly
blocking pair for $\mu$, there is $\overline{w}$ $\in\mu(f)$ such that
$w^{\prime}R_{f}\overline{w}\text{ and }fR_{w^{\prime}}\mu(w^{\prime}).$ Now,
following similar reasonings to the ones in Case 2.1 in the proof of Theorem
2, and replacing (8) and (9) by

$\mu^{\prime}(f)=\left(\mu(f)\setminus\\{\overline{w}\\}\right)\cup\\{w^{\prime}\\}R_{f}\mu(f),$

and

$f=\mu^{\prime}(w^{\prime})R_{w^{\prime}}\mu(w^{\prime}),$

we can construct coalition $C$ and matching $\mu^{\prime}$ such that
$\mu^{\prime}$ super weakly dominates $\mu$ via $C$.

    2. $\boldsymbol{2.2}$.

$\boldsymbol{|\mu(f)|<q_{f}}.$ To prove this case, we can construct matchings
$\mu^{\prime}$ that super weakly dominates $\mu$ in an analogous way to Case
2.2. in the proof of Theorem 2.

By subcases 2.1 and 2.2, $\mu\notin\mathcal{C}_{SS}.$

Next, we prove that $\mathcal{SSS}\subseteq\mathcal{C}_{SS}.$ Assume that
$\mu\in\mathcal{SSS}$ and $\mu\notin\mathcal{C}_{SS}.$ Thus, there are a non-
empty coalition $C$ and a matching $\mu^{\prime}$ such that $\mu^{\prime}$
super weakly dominates $\mu$ via $C.$ First, we claim that $C\cap
F\neq\emptyset.$ Otherwise, $C\cap F=\emptyset$ implies, for each $w\in C,$
that $\mu^{\prime}(w)=\emptyset$ (since $\mu^{\prime}(C)=C$), and therefore
$\emptyset=\mu^{\prime}(w)R_{w}\mu(w),$ contradicting the individual
rationality of $\mu.$ So take any $f\in C$. Since $\mu^{\prime}$ super weakly
dominated $\mu$ via $C$, $\mu^{\prime}(f)R_{f}\mu(f).$ Now we claim that
$\mu^{\prime}(f)\setminus\mu(f)\neq\emptyset.$ Otherwise,
$\mu^{\prime}(f)\setminus\mu(f)=\emptyset$, $\mu^{\prime}(f)R_{f}\mu(f)$, and
$\mu^{\prime}\neq\mu$ imply $\mu^{\prime}(f)\subset\mu(f).$ Let
$\mu(f)\setminus\mu^{\prime}(f):=\\{w_{1},\ldots,w_{\ell}\\}$. By individual
rationality of $\mu$, $w_{i}P_{f}\emptyset$ for each $i=1,\ldots,\ell.$ By
responsiveness of $R_{f}$,

$\mu(f)=\mu^{\prime}(f)\cup\\{w_{1},\ldots,w_{\ell}\\}P_{f}\mu^{\prime}(f)\cup\\{w_{1},\ldots,w_{\ell-1}\\}P_{f}\cdots
P_{f}\mu^{\prime}(f)\cup\\{w_{1}\\}P_{f}\mu^{\prime}(f).$

Thus $\mu(f)P_{f}\mu^{\prime}(f),$ contradicting $\mu^{\prime}(f)R_{f}\mu(f)$.
Therefore, $\mu^{\prime}(f)\setminus\mu(f)\neq\emptyset.$ Define

$\mu^{\prime}(f)\setminus\mu(f):=\\{w^{\prime}_{1},\ldots,w^{\prime}_{k}\\}$

where subscripts are chosen so that $w^{\prime}_{i}R_{f}w^{\prime}_{i+1}$ for
each $i=1\ldots,k-1,$ and

$\mu(f)\setminus\mu^{\prime}(f):=\\{w_{1},\ldots,w_{\ell}\\}$

where subscripts are chosen so that $w_{i}R_{f}w_{i+1}$ for each
$i=1\ldots,\ell-1.$ Now, there are two cases to consider:

  * $\boldsymbol{1}.$

$\boldsymbol{|\mu^{\prime}(f)|\leq|\mu(f)|}$. Then,
$|\mu^{\prime}(f)\setminus\mu(f)|\leq|\mu(f)\setminus\mu^{\prime}(f)|.$ First,
we claim that

$w^{\prime}_{1}R_{f}w_{\ell}.$ (12)

Otherwise,

$w_{1}R_{f}\cdots R_{f}w_{\ell}P_{f}w^{\prime}_{1}R_{f}\cdots
R_{f}w^{\prime}_{k}$

and, by responsiveness of $R_{f}$ and the individual rationality of $\mu$,
since $\ell\geq k$

$\mu(f)P_{f}\mu(f)\setminus\\{w_{\ell}\\}P_{f}\cdots
P_{f}\mu(f)\setminus\\{w_{k+1},\ldots,w_{\ell}\\}.$ (13)

Define $\widetilde{W}:=\mu^{\prime}(f)\cap\mu(f).$ Notice that
$\mu(f)\setminus\\{w_{k+1},\ldots,w_{\ell}\\}=\widetilde{W}\cup\\{w_{1},\ldots,w_{k}\\}.$
Again, by responsiveness of $R_{f}$,

$\widetilde{W}\cup\\{w_{1},\ldots,w_{k}\\}P_{f}\widetilde{W}\cup\\{w_{1},\ldots,w^{\prime}_{k}\\}P_{f}\cdots
P_{f}\widetilde{W}\cup\\{w^{\prime}_{1}\ldots,w^{\prime}_{k}\\}.$ (14)

Notice that
$\widetilde{W}\cup\\{w^{\prime}_{1},\ldots,w^{\prime}_{k}\\}=\mu^{\prime}(f).$
Thus, by (13) and (14), $\mu(f)P_{f}\mu^{\prime}(f)$. This contradicts that
$\mu^{\prime}(f)R_{f}\mu(f)$ and, therefore, (12) holds and the claim is
proven. Since $f\in C$ and $\mu^{\prime}(C)=C$, $w^{\prime}_{1}\in C$. As
$\mu^{\prime}$ super weakly dominates $\mu$ via $C$,

$f=\mu^{\prime}(w^{\prime}_{1})R_{w^{\prime}_{1}}\mu(w^{\prime}_{1}).$ (15)

If $|\mu(f)|=q_{f}$, by (12) and (15), $(f,w^{\prime}_{1})$ is a super weakly
blocking pair for $\mu$. If $|\mu(f)|<q_{f}$, by (12) we have
$w^{\prime}_{1}R_{f}w_{\ell}$, and by the individual rationality of $\mu$,
$w_{\ell}P_{f}\emptyset.$ Hence, $w^{\prime}_{1}P_{f}\emptyset$ and,
therefore, together with (15), $(f,w^{\prime}_{1})$ is a super weakly blocking
pair for $\mu$.

  * $\boldsymbol{2}.$

$\boldsymbol{|\mu^{\prime}(f)|>|\mu(f)|}$. Following a similar reasoning as in
Case 2 of the proof of Theorem 1, we can prove that

$w^{\prime}_{1}P_{f}\emptyset.$ (16)

Notice that since $\mu^{\prime}$ is a matching,
$q_{f}\geq|\mu^{\prime}(f)|>|\mu(f)|$. Since $f\in C$ and $\mu^{\prime}(C)=C$,
$w^{\prime}_{1}\in C$. As $\mu^{\prime}$ super weakly dominates $\mu$ via $C$,
$f=\mu^{\prime}(w^{\prime}_{1})R_{w^{\prime}_{1}}\mu(w^{\prime}_{1})$ and,
together with (16), $(f,w^{\prime}_{1})$ is a super weakly blocking pair for
$\mu$.

Given that in each case we find a super weakly blocking pair for $\mu$, we
contradict the fact that $\mu\in\mathcal{SSS}.$ Therefore,
$\mu\in\mathcal{C}_{SS}.$ $\square$

In order to compute solution concepts in matching models with indifferences,
it is usual to study their relationship with solution concepts in matching
models with strict preferences, for which several algorithms are already
available in the literature. Given a market $R,$ denote the set of all strict
tie-breakings of $R$ by $\mathcal{L}(R).$ The following result provides a way
to compute the super core of a market with indifferences in terms of the
stable matchings of all its associated strict markets.

###### Proposition 2

For any market $R,$
$\mathcal{C}_{SS}(R)=\bigcap_{P\in\mathcal{L}(R)}\mathcal{S}(P).$

_Proof._ Let $R$ be a many-to-one market. By Theorem 3,
$\mathcal{C}_{SS}(R)=\mathcal{SSS}(R).$ By Proposition 2 in Irving et al.
(2000), $\mathcal{SSS}(R)=\bigcap_{P\in\mathcal{L}(R)}\mathcal{S}(P),$ and the
result follows. $\square$

Our last result applies to the one-to-one model with indifferences, and
provides a way to compute the core of a market with indifferences in terms of
the stable matchings of all its associated strict markets.

###### Proposition 3

For any one-to-one market $R$,
$\mathcal{C}(R)=\bigcup_{P\in\mathcal{L}(R)}\mathcal{S}(P)$.

_Proof._ Let $R$ be a one-to-one market. By Proposition 1,
$\mathcal{C}(R)=\mathcal{S}(R).$ By Proposition 1 in Irving et al. (2000),
$\mathcal{S}(R)=\bigcup_{P\in\mathcal{L}(R)}\mathcal{S}(P),$ and the result
follows. $\square$

$\mathcal{C}_{SS}=\mathcal{SSS}$$\mathcal{C}_{S}=\mathcal{SS}$$\mathcal{S}$$\mathcal{C}$
Figure 1: Inclusions among different cores and stability notions in the many-
to-one setting.

##  4 Concluding remarks

This paper presents, for a many-to-one model with indifferences, three notion
of cores and its relationships with the three already known notions of
stability. All the results and relations are summarized in Figure 1.

An interesting avenue for future research is to investigate whether our
results are still valid in a many-to-one model with indifferences in which
firms’ preferences are substitutable instead of responsive.

## References

  * Abdulkadiroğlu and Pathak (2009) Abdulkadiroğlu, A. and A. Pathak, P.and Roth (2009): “Strategy-Proofness versus Efficiency in Matching With Indifferences: Redesigning the NYC high school match,” _American Economic Review_ , 99, 1954–1978.
  * Erdil and Ergin (2017) Erdil, A. and H. Ergin (2017): “Two-sided matching with indifferences,” _Journal of Economic Theory_ , 171, 268–292.
  * Gale and Shapley (1962) Gale, D. and L. Shapley (1962): “College admissions and the stability of marriage,” _The American Mathematical Monthly_ , 69, 9–15.
  * Ghosal et al. (2016) Ghosal, P., A. Kunysz, and K. Paluch (2016): “Characterisation of strongly stable matchings,” in _Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms_ , SIAM, 107–119.
  * Irving (1994) Irving, R. W. (1994): “Stable marriage and indifference,” _Discrete Applied Mathematics_ , 48, 261–272.
  * Irving et al. (2000) Irving, R. W., D. F. Manlove, and S. Scott (2000): “The hospitals/residents problem with ties,” in _Scandinavian Workshop on Algorithm Theory_ , Springer, 259–271.
  * Juarez et al. (2021) Juarez, N., P. A. Neme, and J. Oviedo (2021): “Marriage market with indifferences: A linear programming approach,” _Journal of the Operations Research Society of China_ , 1–24.
  * Kunysz (2018) Kunysz, A. (2018): “An Algorithm for the Maximum Weight Strongly Stable Matching Problem,” in _29th International Symposium on Algorithms and Computation (ISAAC 2018)_ , Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
  * Kwanashie and Manlove (2014) Kwanashie, A. and D. F. Manlove (2014): “An integer programming approach to the hospitals/residents problem with ties,” in _Operations Research Proceedings 2013_ , Springer, 263–269.
  * Manlove (2002) Manlove, D. F. (2002): “The structure of stable marriage with indifference,” _Discrete Applied Mathematics_ , 122, 167–181.
  * Roth and Sotomayor (1990) Roth, A. and M. Sotomayor (1990): _Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis_ , Cambidge University Press, Cambridge.
  * Roth (1985) Roth, A. E. (1985): “Common and conflicting interests in two-sided matching markets,” _European Economic Review_ , 27, 75–96.
  * Sotomayor (2011) Sotomayor, M. (2011): “The Pareto-stability concept is a natural solution concept for discrete matching markets with indifferences,” _International Journal of Game Theory_ , 40, 631–644.


Each replicate of the experiment draws a new sample of errors from a Gaussian distribution (Section <ref>) and hence of new traffic counts. For each replicate, we compute the bias of the utility function coefficients and of the value of time, the normalized root mean squared error () and the amount of false negatives. The  is defined as the ratio between the root mean squared error () and the mean of the observed traffic counts. Because the standard deviation $\sigma$ of the random error is defined as a proportion of the mean of true traffic counts (Section <ref>), the  is expected to be close to $\sigma = 0.1$. Since the ground truth coefficients of the utility function are all set to values different than zero, a false negative equates a non-rejection of the null hypothesis $H_{0} = 0$. The initial values for optimization of the utility function coefficients are set with a uniform distribution centered at the true values of the coefficients and with a width of two. Thus, the initial value of the travel time coefficient $\theta_t$ is randomly chosen within the interval $[-3,1]$.

Exogenous travel times

Endogenous travel times

Consistency in coefficients recovery

The experiment results show that the estimates were roughly unbiased in all optimization setups and under exogenous and endogenous travel times. This result is interesting because the assumptions prove only consistency but not unbiasedness of the estimators in large samples. A potential explanation is related to the pseudo-convexity of the outer level objective and to the existence of a unique global optima in the neighborhood around the initial values for optimization. Furthermore, our evidence strongly supports the use of +over the standalone application of first or second order optimization methods. The higher standard error of the estimates obtained with unveils the problems of numerical stability of second order methods when the initial values for optimization are in regions where the objective function is not convex. The latter is also associated with the large proportion of false negatives reported by in both experimental scenarios. In contrast, the standalone application of reports less than 5% of false negatives in both scenarios, which equates to a statistical power of 95%. This is a encouraging result given the reference threshold of 80% typically used for experimental studies.

In the endogenous case, we observe an increase of the difference between the and its expected value, given by the dashed bar shown in the bottom right plots of Figures <ref> and <ref>. Similarly, the bias of the estimated coefficients and of the value of time increase consistently in the three setup of optimization methods compared to the exogenous case. The computation of equilibria in the endogenous case may result into inaccurate approximations of the travel times at equilibria. From an econometric standpoint, this introduce measurement error in the travel time attribute and it can add bias in the parameter estimates. Another problem in the endogenous case is the significant increase of computational burden due to solving traffic equilibria at each replicate of the experiment.

To ensure good convergence over replicates and that the assumptions for consistency of the estimator are satisfied, the following experiments in this section are performed under the scenario of exogenous travel times only. The initial values for optimization of the utility function coefficients are also set with a uniform distribution centered at the true values of the coefficients and with a width of two. This choice of width allows to start the optimization in a region close of the ground truth values of the utility function coefficients and where the objective function is at best convex or at worst pseudo-convex. A tighter width makes difficult to assess the reduction of the objective function with different setups of optimization method. The significance level for all hypotheses tests is also set at $\alpha = 0.1$.

§.§.§ Irrelevant attributes

The theory suggests that the estimator is asymptotically consistent. Therefore, the coefficients associated to irrelevant attributes included in the utility function should converge to zero and they should not impact the statistical inference on coefficients weighting relevant attributes. However, with finite samples, the inclusion of irrelevant attributes in the utility function can reduce the efficiency of coefficients of relevant attributes. As a consequence, the t-tests of other coefficients may decrease and this could artificially increase the number of false negatives, i.e. lower rejections of the null hypothesis for coefficients different than zero.

Figure <ref> shows the impact of the inclusion of irrelevant attributes on the bias of the estimated coefficients and of the value of time, and on hypothesis testing. In contrast to the Monte Carlo experiments conducted in Section <ref>, the utility function used to generate synthetic traffic counts includes six irrelevant attributes. Each irrelevant attribute is generated as a standard Gaussian random variable and it is weighted by a coefficient equal to zero in the utility function. Hence, the hypothesis tests are expected to not reject the null for these coefficients. To quantify the power of the hypothesis tests to detect irrelevant attributes, we compute the proportion of false positives, namely, the proportion of times that the null hypotheses for coefficients weighting the set of irrelevant attributes are rejected. By classic statistical theory, p-values are uniformly distributed under the null hypothesis, hence, a significance level of $\alpha = 0.1$ should result into a 10% of false positives. To analyze the impact of the inclusion of irrelevant attributes on the statistical inference of relevant attributes, we also report the proportion of false negatives.

Impact of irrelevant attributes on statistical inference

Similar to the results obtained in Section <ref>, the integration of and significantly reduces the amount of false negatives and the bias of the estimated coefficients and of the value of time. The inclusion of irrelevant attributes in the utility function increases the amount of false negative but only in the case of . Notably, the integration of and perfectly matches the theoretical 10% level of false positives that is expected at a significance level of $\alpha = 0.1$. Overall, these results reaffirm that the statistical inference is more reliable with the integration of first order and second order optimization methods. Given this evidence, the following experiments are conducted using +only.

§.§.§ Sensor coverage

A lower sensor coverage reduces the sample size and this is expected to increase the standard error in the estimates of the utility function coefficients. As a consequence, t-tests may be overestimated and thus, the amount of false negative may increase. Figure <ref> shows the impact on hypothesis testing when varying the link coverage at three levels; 25%, 50% and 75%. As expected, the amount of false negatives and the standard error of the coefficients decrease with the level of sensor coverage. Notably, for coverages of only 50% (N = 38), the statistical power already surpasses the desired threshold of 80%. For all coverage levels, the proportion of false positives does not surpass the theoretical level of 10% and the closely matches its expected value at 10%.

Impact of sensor coverage on statistical inference

§.§.§ Error in traffic count measurements

The standard error of the estimators is expected to increase when the variance of the random perturbation is higher. Thus, hypothesis testing should tend to reject less frequently the null for coefficients associated to relevant attributes and hence, the amount of false negatives could artificially increase. Figure <ref> shows the impact of increasing the standard deviation of the Gaussian perturbation on statistical inference. The standard deviation is defined as a percentage of the average value of the synthetic traffic counts (see Section <ref>). As expected, the amount of false negatives and the standard error of the estimated coefficients increases with the level of variability in the random perturbation. The values of the closely match the error levels and the proportion of false positives does not surpass the theoretical level of 10%. In real applications and in line with the sensor coverage experiment (Figure <ref>), a larger sample size should compensate for an increase in the variance of the random perturbation.

Impact of noise in traffic counts on statistical inference

§.§.§ Non-deterministic O-D matrix

Our methodology assumes that the O-D matrix is exogenous and deterministic (Assumption <ref>, Section <ref>). While it is feasible to have an accurate reference O-D matrix available, its cells may be subject to random perturbations. Any gap between the true and reference O-D matrix may add measurement error in the model and this could bias or distort the t-tests of the coefficients. Figure <ref> shows the impact of introducing different level of noise in the O-D matrix. The reference O-D matrix is assumed to be a Gaussian random variable with expected value $\vmu_{\mQ} \in \mathbb{R}^{V \times V}_{\geq 0}$ equal to the values of the true O-D matrix $\mQ$ and with standard deviation $\sigma_{\mQ} \in \mathbb{R}_+$ defined as a percentage of the average value of $\mQ$. To compare the impact of adding noise in either the traffic counts (Section <ref>) or the O-D matrix, we set the same levels of the standard deviation of the random perturbation in both experiments. Surprisingly, our results show that the noise in the O-D matrix does not significantly impact statistical inference. Therefore, the standard error of the estimated coefficients and the remains invariant for all levels of random noise.

Impact of noise in O-D matrix on statistical inference

§.§.§ Ill scaled O-D matrix

An ill scaled O-D matrix is expected to increase the gap between predicted and observed traffic counts and this may induce an overestimation of the variance of the random error. As a consequence, the t-tests and the false negatives could increase. Figure <ref> shows the impact of a ill-scaled the O-D matrix. The level represents the true value of the scale or factor that should multiply the reference O-D matrix to recover the true O-D matrix. Therefore, values lower or higher than 1 represent cases of overestimation or underestimation of the true O-D matrix, respectively. Compared to the previous experiments that assume a well-scaled O-D matrix, we observe that the is far from its expected value, which suggest that there is no a good convergence toward the ground truth values of the utility function coefficients. The estimated coefficients are biased upwards and downwards when the true O-D matrix is overestimated or underestimated, respectively. The latter is directly associated with the underestimation and overestimation of the false positives respect to the theoretical level of 10%. The false negatives surpasses the 20% when the true O-D matrix is underestimated, which significantly reduce the statistical power to detect the effect of relevant attributes in the utility function.

Impact of a bad scaled O-D matrix on statistical inference

§ A LARGE-SCALE NETWORK WITH MULTIPLE ATTRIBUTES: CALIFORNIA SR-41 CORRIDOR

The proposed methodology was also applied to a large scale transportation network located in the City of Fresno, California. This network primarily covers major roads and highways around the SR-41 corridor and it comprises 1789 nodes and 2413 links <cit.>. The following sections describe the use of various data sources to estimate our model in the Fresno network. Subsequently, we describe the attributes of the utility function, the models' specifications, the estimation procedure and the results.

SR-R1 corridor in Fresno, CA

§.§ Traffic counts

The Caltrans Performance Measurement System <cit.> provides open source data with georeferenced stations that record information on traffic counts, speeds and travel times in major highways in California. Using geoprocessing tools, a total of 141 links of the Fresno network were matched to PeMS stations, which equates to a 5.8% of sensor coverage. We only use traffic count data collected during the first Tuesday of October 2019 and October 2020 between 4pm and 5pm and which correspond to periods before and during COVID-19. The average traffic counts for the selected periods in 2019 and 2020 are 2213.6 and 2113.3 vehicles per hour, respectively.

§.§ Travel demand

A dynamic O-D demand matrix calibrated with support of the PARAMICS estimator tool for the SR-R1 corridor is adopted in our study <cit.>. This O-D demand is provided with a 15 minutes resolution and for the period between 4PM and 6PM on a typical weekday. To have consistency in the temporal resolutions of the O-D demand and the traffic counts data, both data sources are aggregated in a one hour window starting at 4pm. The aggregation in vehicles per hour is also consistent with the temporal resolution of the link performance functions.

Figures <ref> show the cumulative demand respect to the number of O-D pairs. There are 6970 O-D pairs that reported trips, which gives a total 66,266.3 trips. The dashed bars in the figures suggest that approximately the 30% of the O-D pairs with the highest demand covers a 85% of all trips. To account for the reduction in travel demand in the selected periods of 2019 and 2020, we scale the O-D matrix in 2019 by a uniform factor of 0.9546, which is equal to ratio between the average traffic counts in each year (2113.3/2213.6). Note that this factor is similar but more conservative than the ratio between the traffic volumes of October 2020 and October 2019 in all roads and streets in the United States <cit.>.

Cumulative travel demand in Fresno, CA

§.§ System level data

Below are the sources of system level data used to compute the attributes of the travelers' utility function in every link of the Fresno network:

* Speed and travel times

INRIX traffic time and traffic speed data have been successfully used in previous transportation studies an it is considered a reliable data source for our analyses <cit.>. Our raw data includes a shapefile with a collection of georeferenced line segments representing the major roads in Fresno, CA. It also includes  files with traffic speeds for every line segment and with a 5 minutes resolution. Attributes in the dataset include a unique identifier for each line segment, a time stamp, observed speed, average speed and reference speed. Using the length of each line segment, the speed attributes were transformed into travel time attributes in minute units. The line segments of the INRIX shapefile and the links of the Fresno network are matched according to the orientation and proximity of the streets. For the 15.5% links that were not successfully matched, we imputed the mean value of the attributes that were matched in the remaining links.

* Traffic incidents

The Statewide Integrated Traffic Records System (SWITRS) is one of the two official sources of traffic incidents data in California <cit.>. SWITRS is managed by the California Highway Patrol (CHP) and includes post-processed and georeferenced data on incidents causing human injury or death. A codebook of the dataset and the incidents reported between 2016 and 2021 are publicly available in <cit.> and <cit.>. A buffer of 50 feet is used to match the links in the Fresno network with the location of the incidents. In 2019 and 2020, 1601 and 2020 incidents are matched to 276 and 382 links of the Fresno network, respectively.

* Streets characteristics

Street characteristics are hypothesized to be a predictor of travelers' route choices. Using an open repository maintained by the <cit.>, we processed shapefiles with the georeferenced positions of bus stops and streets intersections in Fresno. A buffer of 50 feet is used to match the links in the Fresno network with the location of the stops and intersections. 362 and 2115 bus stops and streets intersections are matched to 300 and 1139 links, respectively.

* Socio-demographics from Census data

A shapefile with the most recent selected sociodemographic data at the block level was retrieved from <cit.>. We only use the layers with data about the proportions of population by gender, age and income level at each block. There are other layers with relevant features to explain route choice preference, such as one related to commuting patterns, but this data is not available for the city of Fresno or it is only available at the tract and county levels.

§.§ Attributes of the utility function

Travel time is the only endogenous attribute in the utility function and it is equal to the output of the links' performance functions. The free flow travel times defined in the link performance functions is obtained from INRIX data. The speed attribute used to compute free flow travel times corresponds to the speed driven on a road when it is wide open and it does not necessarily match the legal speed limit. Using the system level data described in Section <ref>, we also compute the following set of exogenous attributes for every link of the Fresno network:

* Std. Speed: Standard deviation of speed [miles/hour]

* Incidents: Total incidents in the current year

* Intersections: Number of streets intersections

* Bus stops: Number of bus stops

* Median income: Median household income in the U.S. Census block [USD/year]

Std. Speed is computed using historical data provided by INRIX for the period between 4pm and 5pm on a weekday and it is assumed to negatively impact the utility of choosing a path. There are alternative ways to capture the effect of travel time variability on travelers' route choices, such as the standard deviation or coefficient of variation of travel time. The main advantage of the standard deviation of speed is that it provides a measure of time variability that is independent of the length of the link segments. The rationale to aggregate the number of incidents in the current year is to have a proxy of the drivers' perception on the road safety of a link segment. Median income is used as a proxy of the perception of the level of crime in surrounding neighborhoods and it is hypothesized to be positively associated with the utility of choosing a path. A larger number of bus stops or streets intersections in a link segment should encourage drivers to use alternative paths. Thus, all attributes, except for Median income, are expected to have a negative coefficient in the utility function.

To test non-linear effects of the attributes on the utility function, we also binarized the exogenous attributes as follows. Reliable speed and Low income take the value 1 if the values of Std. speed and Median income are below the 25th percentile of their distributions, respectively, and 0 otherwise. Bus stop, Intersection and Incident take the value 1 if Bus stops, Intersections and Incidents are greater than zero, respectively, and 0 otherwise. Under this new specification of the attributes, all coefficients of the utility function, except for the coefficient weighting Reliable speed, are expected to be negative.

Note that the network contains 656 links (38.8%) that are centroid connectors. These connectors usually do not have physical counterparts in the real network <cit.> and they should not impact travelers' route choices. Thus, we set the values of the attributes in these links to zero, regardless if the attributes are continuous or binary. The path size correction factor is set to its default value of one in all model specifications.

§.§ Descriptive statistics

Figure <ref> shows the correlations among traffic counts and system level attributes of the Fresno network during the first Tuesdays of October 2019 and 2020. We include free flow speed instead of free flow travel times which normalize the attribute by the link length. The Pearson correlations shown in the top row of the plots indicate that the free flow speed is negatively correlated with the number of intersections and bus stops in the two selected periods. Also, as expected, the number of incidents is positively associated with the free flow speed. An interesting result is the negative correlation between median income and free flow speed. The latter is probably explained by the higher rate of motorization in high income areas and which should be associated to lower speeds. The standard deviation of speed shows a positive correlation with free flow speed but only during 2020. The sign of the correlation between traffic flows and free flow speed is unclear. Overall, the correlational analysis shows sensitive associations between the attributes of the utility function and it suggests that the spatial matching of attributes conducted in <ref> was reasonably accurate.

Correlations among system level attributes in Fresno, CA

§.§ Model specifications

We estimate three model specifications using the data collected in each time period. Following the state of the practice in previous literature, we first estimate a Baseline model including travel time only. We also estimate a Full model including the exogenous attributes in a continuous scale; Std. Speed, Median income, Incidents, Intersections, Bus stops. Finally, a Binarized model includes the exogenous attributes in a binary scale; Reliable speed, Low income, Incident, Intersection, Bus stop (Section <ref>). To assess the gain in explanatory and predictive power of the Full model and Binarized model compared the Baseline model, these models also include Travel time. By assumption, the utility function is defined as a linear weight between attributes and their respective coefficients. Travel time, the only endogenous attribute in all models, is iteratively updated during the bilevel optimization.

§.§ Estimation

To prevent that numerical issues associated to the scale of the attributes impact the quality of the statistical inference, we normalize each exogenous attribute, including the free flow travel time defined in the link performance functions, by their maximum values. Because all these attributes are non-negative, their new ranges are between 0 and 1. Section <ref> includes figures with descriptive statistics of the attributes after this normalization and that exclude links that are centroid connectors.

The models are estimated on Amazon Web Services on two  instances equipped with Intel Xeon CPU 3.3GHz x 8, 32 GB RAM <cit.>. The three model specifications are run in parallel using the data collected in either 2019 or 2020. Because -is path-based, the computational and memory complexity is a function of the number of paths. The CPU processor and RAM memory of the  instance allow to handle 33,430 of paths. In contrast, a  instance with Intel Xeon CPU 3.3GHz x 4, 16 GB RAM, handles 22,015 paths without reporting memory overflow. The memory bottleneck of the algorithm is on the computation of the analytical gradients performed to update the utility function coefficients during the outer level optimization. The computation time of each notebook is about 6 hours.

All models are estimated using in the no-refined stage with a learning rate of $\eta_1 = 0.5$, and in the refined stage, respectively. Each stage performs 10 iterations of the optimization methods. The starting points for optimization in the non-refined stage are set to zero for the three model specifications. The best estimate of the utility function coefficients in the non-refined stage is chosen as the starting point for optimization in the refined-stage. The coefficients are projected to zero during the iterations of the bilevel optimization if their sign is not consistent with our expectation  (Section <ref>). If the coefficients of the attributes are zero at the end of the non-refined stage, they are excluded for the refined stage. This strategy is used to reduce computational burden and to accelerate the convergence of the optimization algorithm to a local optimal solution.

§.§ Path generation

We generate an initial set of 13,905 paths using the two shortest paths between the 6970 O-D pairs that report trips (Figure <ref>, Section <ref>). The initial path set of the three model specifications are the same. The total number of paths is odd because some O-D pairs are only connected by a single path. The column generation method described in Step 1, Algorithm <ref>, <ref> is used to update the path sets during the bilevel optimization. To guide the paths exploration, new paths are generated in the 30% of O-D pairs with the highest demand  only, which covers approximately 85% of the total trips in the Fresno network (Figure <ref>, Section <ref>). Based on the current estimate of the utility function coefficients and the link attributes, the column generation step generates the 40 shortest paths among 3% of the OD pairs at each iteration of the bilevel optimization. The selected O-D pairs at each iteration changes sequentially according to their level of demand and the process continue until the target of 30% of OD-pairs is reached in the last iteration. The sequential selection of O-D pairs reduces the computational burden of generating new paths in all O-D pairs and at every iteration, without compromising significantly path exploration. Subsequently, the inner level optimization algorithm solves -and the paths utilities are updated according to the new travel times at equilibria. Finally, it selects the 10 paths with the highest utility for every O-D pair.

§.§ Indicators for model comparison

For each model specification and time period, we compute the value of the objective function (i.e. sum of squared errors), the root mean squared error (RMSE), the normalized RMSE (NRMSE), the F-test (Section <ref>) and the adjusted pseudo $R^2$. The F-test compares the sum of squared errors of the model with its null version where all coefficients of the utility function were set to zero and that represents an scenario where travelers' make equilikely choices among paths. F-tests with p-values lower than $\alpha$ in rejects the null hypothesis that two models are statistically equivalent at the $1-\alpha$ % level of confidence and hence, this is evidence that supports the selection of the augmented model.

Our adjusted pseudo $R^2$ is analogous of the McFadden Pseudo-$R^2$ <cit.> and it is adjusted by the number of coefficients of the model <cit.>. It is defined as 1 minus the ratio between the SSE of a model minus the number of coefficients and the SSE of the model with all coefficients set to zero. Since traffic counts are an aggregate of individual path choices, the adjusted pseudo $R^2$ of our model is directly comparable with those values obtained from discrete choice models. This indicator is an absolute measure of the predictive ability of discrete choice models and it is useful to generate benchmark values against which researchers can evaluate <cit.>. It tends to be considerably lower than the $R^2$ index used in ordinary regression analysis, and values of 0.2 to 0.4 represent an excellent fit <cit.>.

§.§ Results

Table <ref> shows the estimation results obtained with traffic count data collected during the first Tuesday of October 2019 (before COVID-19) and October 2020 (during COVID-19) and for three model specifications (Section <ref>). Besides the point estimates and t-tests of each coefficient of the utility function, the table also includes multiple indicators for model comparison (Section <ref>). Figure <ref> shows histograms with the distribution of errors obtained after performing the non-refined and refined stages of the optimization. Figures <ref> and <ref>, <ref> show a comparison of the convergence of the full and binarized models against the baseline model. The top plots of the figures shows the number of paths that are generated during column generation and that are added after performing the paths selection step during the inner level optimization. The significant decrease in the number of paths added in the bilevel iterations of the refined stage suggests that the path exploration over the selected set of O-D pairs in the non-refined stage was reasonably exhaustive.

Point estimates and summary statistics of models fitted with data collected between 4pm and 5pm during the first Tuesdays of October 2019 and October 2020 in Fresno, CA

3c First Tuesday of October 2019 (Before COVID-19)
3c First Tuesday of October 2020 (During COVID-19)

Attribute  (t-test)
Baseline model     Full model     Binarized model     Baseline model     Full model     Binarized model

Travel time  $(\theta_{t})$
$-$2.000$^{**}$ ($-$2.5)     $-$1.904$^{**}$ ($-$2.3)      $-$0.760$^{***}$ ($-$3.1)
$-$2.500$^{**}$ ($-$2.1)     $-$1.889$^{*}$ ($-$1.9)      $-$0.458$^{*}$ ($-$1.8)

Std. speed      $\minus$     0.000 (0.0)      $\minus$     $\minus$     0.000 (0.0)     $\minus$

Incidents      $\minus$     $-$2.409$^{**}$ ($-$2.2)     $\minus$      $\minus$     $-$2.597 ($-$1.3)     $\minus$

Median income      $\minus$      0.864$^{**}$ (2.0)     $\minus$     $\minus$     $-$0.447 ($-$0.8)      $\minus$

Intersections       $\minus$     0.000 (0.0)     $\minus$      $\minus$     $-$0.708 ($-$0.7)     $\minus$

Bus stops     $\minus$       0.000 (0.0)      $\minus$     $\minus$       0.000 (0.0)      $\minus$

Reliable speed      $\minus$     $\minus$      0.000 (0.0)     $\minus$     $\minus$       0.000 (0.0)

Incident      $\minus$     $\minus$     $-$0.118 ($-$0.7)      $\minus$     $\minus$     $-$0.249 ($-$1.5)

Low income      $\minus$      $\minus$     0.000 (0.0)     $\minus$     $\minus$       0.000 (0.0)

Intersection      $\minus$     $\minus$      0.000 (0.0)     $\minus$     $\minus$     0.000 (0.0)

Bus stop     $\minus$     $\minus$      0.000 (0.0)     $\minus$       $\minus$       0.000 (0.0)

Obs. (coverage)     141 (5.8%)      141 (5.8%)     141 (5.8%)     141 (5.8%)      141 (5.8%)     141 (5.8%)

Initial objective     278,924,807     278,924,807     278,924,807      273,069,736      273,069,736     273,069,736

Objective function     192,568,627     168,917,573     186,985,714      188,694,982      158,156,498     178,166,886

RMSE     1168.6     1094.5     1151.6      1094.5      1059.1     1124.1

NRMSE     0.528     0.494     0.520      0.547      0.501     0.532

Adjusted pseudo $R^2$     0.311     0.395     0.331      0.316      0.422     0.345

F-test (p-value)     71.954$^{***}$ (0.000)     11.224$^{**}$ (0.000)     8.047$^{***}$ (0.000)     99.482$^{***}$ (0.000)     4.157$^{***}$ (0.002)     9.166$^{***}$ (0.000)

* Note: Significance levels: $^{*}$p$<$0.1; $^{**}$p$<$0.05; $^{***}$p$<$0.01

Baseline model 2019

Full model 2019

Binarized model 2019

Baseline model 2020

Full model 2020

Binarized model 2020

Distribution of errors in non-refined and refined stages of the optimization of the baseline, full and binarized models

Notably, our results shows that the adjusted pseudo $R^2$ obtained in all models are in the order of 0.3-0.56, which are considered an excellent fit in travel behavior studies <cit.>. The F-tests included in the table suggest that all models are statistically different than the null model at the 99% confidence level. The F-tests comparing the Full model with the Baseline model are equal to 3.7804 and 4.3697 when using data collected before and during COVID, respectively. Because they are lower than their critical value of $F_{6-1,141-6 3.1557, 99\%}$, we conclude that the Full model is not statistically equivalent to the Baseline model. The indicators for model comparison of the Binarized model were lower than the Full model in all cases, thus, the latter is preferred over the former.

The NRMSE of the Full model is in the order of 0.5, meaning that the standard deviation of the traffic counts is approximately a 50% of their sample mean. The experiments conducted in the Sioux Falls network find that a NRMSE of 0.25 results into more than 20% false negatives. Although the sample size in the Fresno network is two times higher than the number of links in the Sioux Falls network, it is unlikely to compensate for the difference in NRMSE. Other factors that could contribute to the decrease of the t-test of the coefficients in the Full model are associated to the high correlation of travel time with some exogenous attributes and also to numerical issues arising from the estimation of a richer utility function. Overall, this evidence anticipates a low statistical power to detect of the effect of attributes that significantly impact travelers' utility in the Fresno network.

As expected, the travel time coefficient is significant at the 90% confidence level in all the models. Note that the estimated coefficients of travel times in the baseline models are exact multiples of the learning rate of because there was no improvement of the objective function in the refined stage. In contrast, the estimations of the full and binarized models report improvements during the refined stage. The estimation of the Full model with the data collected before COVID-19 suggests that the total incidents during the year and the monthly household income of the neighborhoods nearby the link segments has a positive and negative effect on the travelers' utility, respectively. Both effects were significant at the 95% level of confidence. The estimation results of the Full model with the data collected during COVID-19 also found a negative effect of the number of streets intersection but the coefficients of all attributes, except for travel time, were not significant at the 90% confidence level. As discussed earlier, the high level of noise in the Fresno network can explain the difficulty to detect significant effect of these attributes. Although it is not required in non-linear regression models, the distribution errors of the models resemble Gaussian distributions with zero mean (Figure <ref>). Finally, regarding the impact of COVID-19, we conclude that there are no significant differences on the attributes that determine travellers' route choices.

§ CONCLUSIONS

The network modeling community has studied the problem of estimating the travelers' utility function coefficients using traffic counts and travel time measurements. However, research has been limited to utility functions dependent on travel time only and methods have been tested on networks of relatively small size. Under the assumption of a known exogenous O-D demand matrix, we enhance existing methods to estimate the coefficients of utility functions with multiple attributes and using traffic counts consistent with stochastic user equilibrium with assignment (-). We refer to this problem as Logit Utility Estimation (). To perform attributes' selection, we conduct hypothesis tests on the coefficients of a multi-attribute utility function . Furthermore, a rigorous analysis of the non-convexity and mathematical properties of the problem is conducted to inform the design of our solution algorithm and to derive some theoretical guarantees about convergence toward local optima.

The realization of the pseudo-convexity of the optimization problem motivates the use of normalized gradient descent (), a first order method developed in the machine learning community that is suitable for pseudo-convex optimization. The integration of with Levenberg–Marquardt () algorithm outperforms the standalone application of second order optimization methods used in previous literature in many ways. First, the estimates of the utility function coefficients become less sensitive to the starting points for optimization, which is a common issue in non-convex problems. Second, improves the convergence toward global optima and this makes the statistical inference more reliable. Third, the use of first order methods reduces computational cost because it only requires to compute the gradient of the objective function respect to the utility function coefficients. To our knowledge, this is the first time that a paper presented vectorized expressions to perform the gradient computation and this is key to accelerate the optimization and to scale up our methodology to the largest transportation network studied to date within the literature.

The analysis of mathematical properties of the problem identifies the coordinate-wise monotonicity of the traffic flow functions as a main driver of the coordinate-wise pseudo-convexity of the objective function. Experiments in networks used in previous studies show that the traffic flow functions are generally monotonic and that the objective function of the problem is pseudo-convex respect to the coefficient of a utility function dependent on travel time only. Results in the Sioux Falls network support the coordinate-wise pseudo-convexity of the objective function respect to the coefficients of a multi-attribute utility function. A series of Monte Carlo experiments show that statistical inference on the utility function coefficients is robust to traffic congestion and also to different levels of sensor coverage and noises in the O-D matrix and in the traffic counts. The amount of false negatives and false positives obtained in these experiments are generally well-aligned with statistical theory. For instance, the amount of false positives perfectly matches the value expected for an arbitrary significance level. A higher amount of noise in the traffic counts increase false negatives and hence it reduces the statistical power to identify effect of relevant attributes in the utility function. Surprisingly, the statistical inference is resilient to high level of noise in the cells of t he reference O-D matrix.

Our solution algorithm is deployed on a large scale network in Fresno, CA and it gave reasonable results in terms of both the estimates and hypothesis tests of the utility function coefficients. Based on standard metrics of model comparison used in travel behavior research, the models report an excellent goodness of fit. As expected, travel time is identified as a main determinant of travelers' route choices in all model specifications, which partially supports the standard practice in the network modelling community of assuming utility functions dependent on travel time only. However, the incorporation of additional system level attributes in the utility function significantly increases the goodness of fit of the baseline model that uses travel time only. These conclusions are robust when using data collected before and during COVID-19. Among the exogenous attributes, the total incidents during the year and the median income are the most relevant predictors of travellers' route choices. The coefficients of these attributes are significant at the 95% level of confidence but only when using data collected before COVID-19.

The implementation of our methodology in a large scale network is challenging mainly due to the high computational cost and level of noise of real world data. On one hand, accounting for the interdependence between travelers' choices in transportation networks and for the endogeneity of travel times requires to compute traffic equilibria. On the other hand, estimating the coefficients of the travelers' utility function requires to solve a regression problem. The computational complexity of the inner and outer level problems is a function of the number of paths and thus, the alternating optimization of the problems become intractable with a large number of O-D pairs. We learned that the use of column generation methods for updating path sets in -provides a good compromise between computational cost and prediction error. The strategy of selecting the O-D pairs according to their demand level is also key to control the exploration of new paths over iterations of the bilevel optimization and to also identify the paths that most decrease the prediction error. To our knowledge, this strategy is not integrated in previous column generation algorithms and we strongly encourage its use in further application of our methodology. To control for the effect of path correlation/overlapping, we correct path utilities according to the Path Size Logit model.

§ FURTHER RESEARCH

Further research could enhance our methodology to incorporate multi-day data and to perform a joint estimation of the utility function coefficients and the O-D matrix. The increase in sample size should help to identify all parameters of interest and to improve the quality of the statistical inference. The use of cloud computing is important to handle a larger number of paths and thus, to achieve a larger reduction of prediction error. However, the cost of estimating a model with data from multiple time period can become high. We expect that use of deep learning models, computational graphs and automatic differentiation tools will help to handle large amounts of multi-day data while keeping computational cost reasonable. Regarding statistical inference, our study is lacking a more careful treatment of the endogeneity that arises from the computation of travel time over the iterations of the bilevel optimization. Therefore, the use of Two-Stage Least Squares (2SLS) and instrumental variables may contribute to correct bias and inconsistency in the coefficient estimates caused by the presence of endogeneity <cit.>.

We are also interested in relaxing the assumption of a homogeneous and linear-in-parameters utility function. The use of a non-homogeneous utility function and fixed effects may contribute to capture heterogeneity of preferences among individuals traveling between different O-D pairs. Besides, the effect of time variability may be better captured with a non-linear specification of the utility function as the one used in prospect theory route choice models. We will also look at estimating the coefficient weighting the utility term associated to the path size correction. We would also like to leverage the use of GPS data to have a better prior of the path sets among O-D pairs and to improve the estimation of the utility function coefficients. Here the integration of our methodology with the nested recursive logit model <cit.> seems a promising avenue for further research.

This study chooses traffic flows for the response function of the non-linear least objective functions. However, there are other choice of response functions that are also admissible such as link travel times or traffic densities. In static traffic assignment, both quantities are monotonic functions of the traffic counts and thus, they are suitable quantities to estimate the utility function coefficients. Finally, system level data is less subject to sampling bias than data collected from individual surveys but it is also more subject to measurement errors. Thus, we expect the joint use of travel surveys and system-level data can help leverage the strengths and weaknesses of each data source.

§ MODEL IMPLEMENTATION AND DATA

The Python package developed to implement our methodology and the system level data from the Fresno, CA network can be found at the following url: <https://github.com/pabloguarda/isuelogit>. The folder  contains Jupyter notebooks that reproduce all the results presented in this paper.

§ ACKNOWLEDGMENTS

This research is supported by a National Science Foundation grant CMMI-1751448

§ AUTHOR CONTRIBUTIONS

The authors confirm contribution to the paper as follows: study conception and design: Pablo Guarda, Sean Qian; data collection: Pablo Guarda, Sean Qian; programming and experiments: Pablo Guarda; analysis and interpretation of results: Pablo Guarda, Sean Qian; draft manuscript preparation: Pablo Guarda, Sean Qian. All authors reviewed the results and approved the final version of the manuscript.

§ REFERENCES