# On testing substitutability

Cosmina Croitoru  Kurt Mehlhorn  Saarland University, Saarbrücken  Max Planck
Institut for Informatics, Saarbrücken

###### Abstract

The papers [1] and [2] propose algorithms for testing whether the choice
function induced by a (strict) preference list of length $N$ over a universe
$U$ is substitutable. The running time of these algorithms is $O(|U|^{3}\cdot
N^{3})$, respectively $O(|U|^{2}\cdot N^{3})$. In this note we present an
algorithm with running time $O(|U|^{2}\cdot N^{2})$. Note that $N$ may be
exponential in the size $|U|$ of the universe.

###### keywords:

Choice functions , Substitutability , Algorithm complexity

28

A _choice function_ on a finite set $U$ of alternatives is any function $f$
from subsets of $U$ to subsets of $U$ that maps any set $A$ to a subset of
itself, i.e., $f(A)\subseteq A$ for all $A\subseteq U$. A choice function $f$
is _substitutable_ if

$A\subseteq B$ implies $f(B)\cap A\subseteq f(A)$ for all $A,B\subseteq U$,

i.e. the additional alternatives provided by $B$ do not promote any $x\in
A-f(A)$ to the set of selected elements.

We are interested in choice functions induced by preference lists $\mathbb{Y}$
on subsets of $U$. A preference list $\mathbb{Y}$ is simply an ordered list of
subsets of $U$ and the associated choice function $f_{\mathbb{Y}}$ maps any
subset $A$ of $U$ to the first element on the list that is contained in $A$.
If $\mathbb{Y}$ is understood from the context, we write $f$ instead of
$f_{\mathbb{Y}}$. We use $N$ to denote the number of elements on $\mathbb{Y}$,
and, in order to make $f$ defined for all $A$, we assume that the empty set is
the last element of $\mathbb{Y}$. For elements $X$ and $Y$ in $\mathbb{Y}$, we
write $X\succ Y$ if $X$ properly precedes $Y$ on $\mathbb{Y}$ and we write
$X\succeq Y$ for $X\succ Y$ or $X=Y$.

For example, let $U=\\{a,b,c,d\\}$ and
$\mathbb{Y}=(\\{a,b\\},\\{a,c,d\\},\\{a,c\\},\\{a\\},\\{c\\},\emptyset)$. Then
$f_{\mathbb{Y}}(\\{a,b,c\\})=\\{a,b\\}$. The function $f_{\mathbb{Y}}$ is not
substitutable since
$d\in(f_{\mathbb{Y}}(\\{a,c,d\\})\cap\\{d\\})-f_{\mathbb{Y}}(\\{d\\})$. We
refer to [1] for a discussion of the role of substitutable choice functions in
economics.

$\mathbb{Y}$ is _coherent_ if $X\succ Y$ implies $X\not\subseteq Y$ for any
two elements on $\mathbb{Y}$. Assume $X\succ Y$ and $X\subseteq Y$. Then $Y$
does not lie in the range of $f_{\mathbb{Y}}$ and removing $Y$ from
$\mathbb{Y}$ does not change the function $f$. Thus we may assume that
$\mathbb{Y}$ is coherent.

From now on, $\mathbb{Y}$ denotes a coherent preference list and $f$ stands
for $f_{\mathbb{Y}}$. $\mathbb{Y}$ is substitutable if $f$ is a substitutable
choice function.

###### Lemma 1

Let $\mathbb{Y}$ be a coherent preference list on $U$. Then for any
$A\subseteq U$, $f(A)=A$ if and only if $A\in\mathbb{Y}$.

Proof. Since $f$ maps the powerset of $U$ to $\mathbb{Y}$, $f(A)=A$ implies
$A\in\mathbb{Y}$. Conversely, assume $A\in\mathbb{Y}$ and $f(A)\succ A$. Then
$f(A)$ and $A$ are members of $\mathbb{Y}$ with $f(A)\succ A$ and
$f(A)\subseteq A$, a contradiction to the coherence of $\mathbb{Y}$. $\Box$

An established condition of choice functions known as Aizerman’s outcast, or
Chernoff’s postulate $5^{*}$ , or $\hat{\alpha}$ (see Brandt and Harrenstein
[3]) is

$(outcast):\quad\quad\text{if $f(A)\subseteq B\subseteq A$ then $f(B)=f(A)$.}$

###### Lemma 2

If $Y$ is a coherent preference list on $U$, then $f$ satisfies _outcast_. ˚

Proof. $B\subseteq A$ implies $f(A)\succeq f(B)$ and $f(A)\subseteq B$ implies
$f(B)\succeq f(f(A))=f(A)$, where the last equality uses coherence. Thus
$f(A)=f(B)$. $\Box$

###### Lemma 3

Let $\mathbb{Y}$ be a coherent and substitutable preference list on $U$. If
$X$ is a member of $\mathbb{Y}$ then also every subset of $X$ is a member of
$\mathbb{Y}$.

Proof. Assume $X=f(X)$ and $A\subseteq X$. By substitutability, $f(X)\cap
A\subseteq f(A)$ and hence $A=X\cap A=f(X)\cap A\subseteq f(A)$. Thus
$f(A)=A$. $\Box$

A preference list $\mathbb{Y}$ is complete if it contains for each $X\in Y$
also all of its subsets. Note that complete preference lists are exponentially
long in the size of their largest member.

In order to demonstrate non-substitutability of a preference list, we need to
exhibit sets $A$ and $B$ with $A\subseteq B$ and
$f(B)\cap(A-f(A))\not=\emptyset$. We next show that we can restrict the search
to special subsets of $U$. A _witness (to non-substitutability)_ is a pair
$(X,Y)$ of members of $\mathbb{Y}$ such that $X\succ Y$, $f(X\cup Y)=X$ and
there is an $x\in X-Y$ such that $f(Y\cup\\{x\\})=Y$. Note that $x$ is
selected when the set of alternatives is $X\cup Y$ (this is the set $B$) but
is not selected when the set of alternatives is $Y\cup\\{x\\}$ (this is the
set $A$).

###### Theorem 4

$\mathbb{Y}$ is not substitutable if and only if there is a witness to non-
substitutability.

Proof. Assume first that $(X,Y)$ is a witness. Then $X\succ Y$, $f(X\cup Y)=X$
and there is an $x\in X-Y$ such that $f(Y\cup x)=Y$. Let $A=Y\cup\\{x\\}$ and
$B=X\cup Y$. Then $A\subseteq B$ and $x\in f(B)\cap(A-f(A))$. Thus $f$ is not
substitutable.

Conversely, assume that $f$ is not substitutable. Then there are subsets $A$
and $B$ of $U$ with $A\subseteq B$ and $f(B)\cap A\not\subseteq f(A)$. Since
$A\subseteq B$, we have $f(B)\succeq f(A)$. In fact, $f(B)\succ f(A)$ since
$f(B)=f(A)$ and $f(A)\subseteq A$ implies $f(B)\cap A=f(A)$. Since
$f(A)\subseteq A\subseteq B$, we have $f(A)\cup f(B)\subseteq B$ and hence
$f(B)\subseteq f(A)\cup f(B)\subseteq B$. Thus $f(f(A)\cup f(B))=f(B)$ by
property (outcast). Let $x\in(f(B)\cap A)-f(A)$. Then
$f(B)\cup\\{x\\}\subseteq A$ and $f(A)\subseteq f(A)\cup\\{x\\}\subseteq A$
and hence $f(f(A)\cup\\{x\\})=f(A)$ by (outcast). Thus $(f(B),f(A))$ is a
witness. $\Box$

Theorem 4 directly translates into an algorithm of running time
$O(N^{3}|U|+N^{2}|U|^{2})$. Note first that one can determine $f(A)$ in time
$O(N|U|)$ by simply scanning the list $\mathbb{Y}$ and checking each set for
containment. The algorithm has two phases. In the first phase, one determines
for each $Y\in\mathbb{Y}$ the set of $x$ for which $f(Y\cup\\{x\\})=Y$. This
requires $N|U|$ function evaluations and $O(N^{2}|U|^{2})$ time. Then one
checks for every pair $(X,Y)$ of elements of $\mathbb{Y}$, whether it is a
witness. This requires $N^{2}$ function evaluations and $N^{2}|U|$ look-ups of
precomputed values and hence takes time $O(N^{3}|U|)$.

We improve the running time to $O(N^{2}|U|^{2})$. The crucial insight is as
follows. We search for a witness pair $(X,Y)$ in increasing order of $X$. Of
course, we stop the search as soon as we have found a witness. So when we
consider a pair $(X,Y)$ we know that there is no witness $(Z,\cdot)$ with
$Z\succ X$. We then have $f(X\cup Y)=X$ if and only if $f(X\cup\\{x\\})=X$ for
all elements $x\in Y-X$. We stress that this equivalence does not hold in
general, it only holds under the assumption that there is no earlier witness.
So we can replace the function evaluation $f(X\cup Y)$ of cost $O(N|U|)$ by
$|U|$ look-ups of precomputed values. We next give the details.

We call $X\in\mathbb{Y}$ _insensitive_ to $x\in U$ if $f(X\cup\\{x\\})=X$ and
_sensitive_ otherwise.

###### Lemma 5

Let $X,Y\in\mathbb{Y}$ with $X\succ Y$. If $f(X\cup Y)=X$, then $X$ is
insensitive to all $x\in Y-X$. If $X$ is insensitive to all $x\in Y-X$ and
there is no witness $(Z,\cdot)$ with $Z\succ X$, then $f(X\cup Y)=X$.

Proof. Let $x\in Y-X$ be arbitrary. Then $X\subseteq X\cup\\{x\\}\subseteq
X\cup Y$ and hence $X=f(X\cup Y)\succeq f(X\cup\\{x\\})\succeq f(X)=X$. Thus
$f(X\cup\\{x\\})=X$ and $X$ is insensitive to $x$.

For the second part, assume $f(X\cup Y)=Z$ with $Z\succ X$. Then $Z\subseteq
X\cup Y$ and hence $Z\cup X\subseteq X\cup Y$. Thus $Z\succeq f(X\cup
Y)\succeq f(X\cup Z)\succeq Z$, where the last inequality follows from
$Z\subseteq X\cup Z$. Thus $f(X\cup Z)=Z$. Since $(Z,X)$ is not a witness, we
must have $f(X\cup\\{x\\})\not=X$ for every $x\in Z-X$. On the other hand,
$Z-X\subseteq Y-X$ (since $Z\subseteq X\cup Y$) and $f(X\cup\\{x\\})=X$ since
$X$ is insensitive to all $x\in Y-X$, a contradiction. $\Box$

Lemma 5 suggests a way to find the non-substitutability witness $(X,\cdot)$
with minimal first component.

⬇

——————————————————————–

$\mathbf{1.}\textbf{ Preprocessing}$

for all  $X\in\mathbb{Y}$ do $\\{\ d_{X}:=1;$ for all  $x\in U$ do
$\mathit{sens}(x,X):=\mathit{false}\ \\}$

for all  $X\in\mathbb{Y}$ do

for all  $Y\in\mathbb{Y}$ with  $X\succ Y$ $\textbf{do}\ \\{$

if $X\subseteq Y$ $\textbf{then \ return }\mathbb{Y}\text{ is NOT COHERENT}$;

if $Y\subseteq X$ then  $\text{increment }d_{X}\ $;

for all  $x\in U-Y\textbf{ do }$ if  $X\subseteq Y\cup\\{x\\}$ $\textbf{then
}\mathit{sens}(x,Y):=\mathit{true}$ $\\}$

for all  $X\in\mathbb{Y}$ do if $d_{X}\neq 2^{|X|}$ $\textbf{then return
}\mathbb{Y}\text{ is NOT COMPLETE}$;

$\mathbf{2.}\textbf{ Looking for the first witness to non-substitutability }$

for all  $X\in\mathbb{Y}$ do

for all  $Y\in\mathbb{Y}$ with  $X\succ Y$ do

if $(\exists x\in X-Y\,\text{s.t.
}\mathit{sens}(x,Y)=\mathit{true})\land(\forall y\in Y-X\
\mathit{sens}(y,X)=\mathit{false})$ then

$\textbf{return }\mathbb{Y}\text{ is NOT SUBSTITUTABLE: \text{ witness }
}(X,Y)$;

$\mathbf{3.}\textbf{ Success}$

$\textbf{return }\mathbb{Y}\text{ is SUBSTITUTABLE}$

———————————————————————

Figure 1:  $\textbf{Testing if the list }\mathbb{Y}\textbf{ is substitutable}$

###### Theorem 6

Let $X,Y\in\mathbb{Y}$ with $X\succ Y$ and assume that there is no witness
$(Z,\cdot)$ with $Z\succ X$. Then $(X,Y)$ is a witness if and only if $X$ is
insensitive to all $x\in Y-X$ and $Y$ is sensitive to some $x\in X-Y$.

Proof. Assume first that $(X,Y)$ is a witness pair. Then $Y$ is sensitive to
some $x\in X-Y$ and $f(X\cup Y)=X$. The latter implies that $X$ is insensitive
to all elements of $Y-X$.

Conversely, assume that $X$ is insensitive to all $x\in Y-X$ and $Y$ is
sensitive to some $x\in X-Y$. Then, $f(X\cup Y)=X$ by Lemma 5 and hence
$(X,Y)$ is a witness pair. $\Box$

We are now ready for the algorithm. The algorithm has two phases. In a
preprocessing phase, we determine whether $\mathbb{Y}$ is coherent, complete,
and, most importantly, compute the Boolean flags $\mathit{sens}(x,X)$ which is
true if $X\in\mathbb{Y}$ is sensitive to $x$.

In the main computation, we search for the first witness to non-
substitutability. We iterate over the elements of $X$ of $\mathbb{Y}$ in
increasing order. Assume that there is no witness $(Z,\cdot)$ with $Z\succ X$.
We then iterate over the $Y\in\mathbb{Y}$ with $X\succ Y$ and use Theorem 6 to
determine whether $(X,Y)$ is a witness pair.

The most expensive task of the first phase is the construction of the Boolean
matrix $\mathit{sens}$ of size $|U|\times N$. Since an inclusion test needs
$O(|U|)$ time, the overall time is therefore $O(|U|^{2}\cdot N^{2})$. The time
complexity of the second phase is $O(|U|\cdot N^{2})$ (the $|U|$ factor is
given by the inspection of the Boolean matrix $\mathit{sens}$ in order to
apply Theorem 6).

By Theorems 4 and 6 and the above discussion, the following corollary holds.

###### Corollary 1

The algorithm in Figure 1 tests in $O(|U|^{2}\cdot N^{2})$ time if a given
preference list of size $N$ over an universe $U$ is substitutable.

Remarks. The $O(N)$ speed-up over the existing algorithms is significant since
(as we noted after the definition of complete lists) $N$ is exponential in the
size of the largest member of $\mathbb{Y}$. The algorithm in [2] also applies
to weak preferences. We leave it as an open problem whether this also holds
for our algorithm.

## References

  * [1] J. W. Hatfield, N. Immorlica, S. D. Kominers, Testing substitutability, Games and Economic Behavior (2011) 639–645.
  * [2] H. Aziz, M. Brill, P. Harrenstein, Testing substitutability of weak preferences, Mathematical Social Sciences (2013) 91–94.
  * [3] F. Brandt, P. Harrenstein, Set-retionalizable choice functions and self- stability, Journal of Economic Theory 146 (2011) 233–273.