Passively-Strictly Strong Nash Equilibrium in a Preference Revelation Game under the Student-Optimal Deferred Acceptance Algorithm

Chengyue Li^1*, Takehiro Inohara¹, Masahito Kitamura²

¹Department of Value and Decision Science, Tokyo Institute of Technology, Tokyo, Japan.
²Department of Risk Science in Finance and Management, Chiba Institute of Technology, Chiba, Japan.

DOI: 10.4236/tel.[phone]                

Abstract

We revisit a college admission market and a related preference revelation game under the student-optimal deferred acceptance algorithm (SODA). Previous research has demonstrated the existence of a strictly strong Nash equilibrium (SSN) based on either an iterative deferred acceptance algorithm (DA-SSN) or the core of a corresponding house allocation problem (Core-SSN). We propose a new equilibrium concept called passively-strictly strong Nash equilibrium (P-SSN). It rules out a kind of deviation called passively weak deviation which includes students who were threatened to deviate. Then we show two preliminary existence results about P-SSN. (i) If the DA-SSN and the Core-SSN are not equivalent, then neither of them is a P-SSN. (ii) If the matching determined by the DA-SSN satisfies a property called irrelevance of low-tier agents, then the DA-SSN is also a P-SSN.

Keywords

Student-Optimal Deferred Acceptance Algorithm, Preference Revelation Game, Passively-Strictly Strong Nash Equilibrium

1. Introduction

A college admission market is usually formulated as a many-to-one matching problem. In this problem, each college can admit multiple students but each student can attend at most one college. This model adopts a primary solution concept called stable matching. We can use the student-optimal deferred acceptance algorithm (SODA) which is proposed by Gale and Shapley [1] to find a stable matching that all students weakly prefer it to any other stable matching¹.

An important research topic on this problem is studying students’ strategic behavior. Specifically, a college admission market can be formulated as a strategic game in which each college’s true preferences over students are known publicly, but each student’s preferences over colleges are revealed strategically. This game adopts a primary solution concept called strong Nash equilibrium (SN). It is a strategy profile under which none of the student groups can make all its members strictly better off by changing their joint strategies. Dubins and Freedman [3] demonstrated that the truth-telling strategy profile is a SN. However, Bando [4] , Dubins and Freedman [3] and Sotomayor [5] all showed that it does not satisfy a stronger equilibrium concept, in the sense that none of the student groups can make all its members weakly better off and at least one member strictly better off by changing their joint strategies.

Bando [4] formally named this equilibrium concept as strictly strong Nash equilibrium (SSN). He then demonstrated the existence of two SSNs. The first one is obtained by iteratively applying the standard deferred acceptance algorithm (DA) so that we simply call it DA-SSN. This SSN has a very nice property that it always exists. Moreover, alternative algorithms can be found in Kesten [6] and Tang and Yu [7] . The other one is obtained by constructing a corresponding house allocation problem which is defined in Shapley and Scarf [8] and then identifying the strict core. We simply call it Core-SSN. We note that its existence depends on whether the strict core exists. Under SODA, both of DA-SSN and Core-SSN yield a matching that weakly Pareto dominates the matching determined by students’ true preferences.

In this research, we propose a new equilibrium concept called passively- strictly strong Nash equilibrium (P-SSN). It is stronger than both DA-SSN and Core-SSN. It rules out a deviation called passively weak deviation. Such a deviating coalition includes members who become strictly worse off, which means such a student was actually unwilling to deviate. But if not doing so, she will receive an even worse outcome caused by the unilateral deviation of the rest members. In this sense, there exist students who “passively’’ joined the deviating coalition.

Then we show two preliminary existence results about P-SSN. (i) If the DA-SSN and the Core-SSN are not equivalent, then neither of them is a P-SSN. (ii) If the matching determined by the DA-SSN under SODA satisfies a property called irrelevance of low-tier agents, then it is also a P-SSN. In general, P-SSN is a quite restrictive equilibrium concept. But nevertheless, we will discuss some extensions that possibly give inspiration to the refinement problem when multiple SSNs exist.

The rest of this paper is organized as follows. Section 2 introduces a college admission market and a related preference revelation game under SODA. Section 3 defines our equilibrium concept with an example, and shows two preliminary results about its existence problem. Section 4 concludes and discusses some possible directions for the future research.

2. Preliminaries

2.1. College Admission Market

Let $\left(I,C,{\succsim }_I,{\succsim }_C,q\right)$ be a college admission market. I is a finite set of students, and C is a finite set of colleges. Each student i has strict preferences ${\succsim }_i$ over $C\cup \left\{i\right\}$ , where $\left\{i\right\}$ means being unmatched. Let ${\succsim }_I={\left({\succsim }_i\right)}_{i\in I}$ be the students’ preference profile.

Each college c has strict preferences ${\succsim }_c$ over $2^I$ . Let ${\succsim }_C={\left({\succsim }_c\right)}_{c\in C}$ be the colleges’ preference profile. Particularly, let ${\succsim }_c^{*}$ be the restriction of ${\succsim }_c$ to singleton sets and the empty set. For each $i\in I$ and $c\in C$ , we say that i is acceptable for c if $i{\succ }_c^{*}\varnothing$ ( $i{\succ }_c\varnothing$ ). Let $q_c$ be the quota of college c. Let $q={\left(q_c\right)}_{c\in C}$ .

We assume that each college c’s preferences satisfy responsiveness with quota $q_c$ which is defined in Roth [9] ². That is, c is strictly better off by replacing any student with a more preferred acceptable student in ${\succsim }_c^{*}$ , and if c has a vacant seat, then it is strictly better off by adding an acceptable student and worse off by adding an unacceptable student. Then we identify ${\succsim }_c$ with ${\succsim }_c^{*}$ because only ${\succsim }_c^{*}$ is relevant to our analysis.

Given $S\subseteq I$ and $c\in C$ , each college c’s choice set $C{h}_c\left(S|{\succsim }_c\right)$ is defined as the set which satisfies (i) $C{h}_c\left(S|{\succsim }_c\right)\subseteq S$ and (ii) $C{h}_c\left(S|{\succsim }_c\right){\succsim }_c{S}^{\prime }$ for all $S^{\prime }\subseteq S$ .

A matching is defined as a function $\mu$ from $I$ into $C\cup I$ which satisfies (i) for each $c\in C$ , $\left|{\mu }^{-1}\left(c\right)\right|\le q_c$ and (ii) for each $i\in I$ , $\mu \left(i\right)\in i$ implies $\mu \left(i\right)=i$ .

We say that a matching $\mu$ is individually rational for students if $\mu \left(i\right){\succsim }_{i}i$ for all $i\in I$ , and is individually rational for colleges if $C{h}_c\left({\mu }^{-1}\left(c\right)|{\succsim }_c\right)={\mu }^{-1}\left(c\right)$ for all $c\in C$ . A matching is individually rational if it is individually rational for both students and colleges. We say that a matching $\mu$ is blocked by $\left(i,c\right)\in I\times C$ if (i) $c{\succ }_i\mu \left(i\right)$ and (ii) $i\in C{h}_c\left({\mu }^{-1}\left(c\right)\cup \left\{i\right\}|{\succsim }_c\right)$ . A matching is stable if it is individually rational and is not blocked.

2.2. Preference Revelation Game

Let $\left(I,{\left(D_i\left(C\right)\right)}_{i\in I},{\succsim }_I,DA\left(\cdot ,{\succsim }_c,q\right)\right)$ be a strategic game defined on a college admission market $\left(I,C,{\succsim }_I,{\succsim }_C,q\right)$ . $I$ is the set of players. Given a strategy profile ${{\succsim }^{\prime }}_I$ , the outcome of this game is determined by SODA and is denoted be $DA\left({{\succsim }^{\prime }}_I,{\succsim }_C,q\right)$ . Each student $i\in I$ evaluates the outcome according to her true preferences ${\succsim }_i$ .

For each $i\in I$ , define $D_i\left(C\right)$ as the set of her strict preferences over $C\cup \left\{i\right\}$ . A coalition $S\subseteq I$ is a nonempty subset of students. Define $D_S\left(C\right)={\times }_{i\in S}{D}_i\left(C\right)$ as coalition S’s joint strategies.

SN and SSN are two solution concepts that have been extensively studied in the previous research. Given a strategy profile ${\succsim }_I^{*}$ , we say that a coalition S has a weak deviation at ${\succsim }_I^{*}$ if there exists ${{\succsim }^{\prime }}_S\in D_S\left(C\right)$ such that (i) $\nu \left(i\right){\succsim }_i\mu \left(i\right)$ for all $i\in S$ and (ii) $\nu \left(i\right){\succ }_i\mu \left(i\right)$ for some $i\in S$ , where $\nu =DA\left({{\succsim }^{\prime }}_S,{\succsim }_{I\backslash S}^{*},{\succsim }_C,q\right)$ and $\mu =DA\left({\succsim }_I^{*},{\succsim }_C,q\right)$ . A strategy profile ${\succsim }_I^{*}$ is a SSN if each coalition does not have any weak deviation. When $\nu \left(i\right){\succ }_i\mu \left(i\right)$ holds for all $i\in S$ , we say that $S$ has a strong deviation at ${\succsim }_I^{*}$ , and ${\succsim }_I^{*}$ is a SN if each coalition does not have any strong deviation.

Dubins and Freedman [3] showed that the truth-telling strategy profile ${\succsim }_I$ is always a SN, but it may not be a SSN. Hence the existence problem of SSN becomes one of the focuses in the later research. Bando [4] demonstrated the existence of the following two SSNs.

DA-SSN

Given a market $M=\left(I,C,{\succsim }_I,{\succsim }_C,q\right)$ , for each $I^{\prime }\subseteq I$ and $c\in C$ , let ${\succsim }_c{|}^{I^{\prime }}$ be the restriction of ${\succsim }_c$ to $2^{I^{\prime }}$ . That is, ${\succsim }_c{|}^{I^{\prime }}$ is the strict preferences over $2^{I^{\prime }}$ such that for any $S,S^{\prime }\subseteq I^{\prime }$ , $S{\succsim }_c{|}^{I^{\prime }}{S}^{\prime }$ if and only if $S{\succsim }_c{S}^{\prime }$ . Let ${\succsim }_C{|}^{I^{\prime }}={\left({\succsim }_c{|}^{I^{\prime }}\right)}_{c\in C}$ be the profile of the restricted preferences. Then the iterative DA is defined as follows.

・ Step 0: Let $M_0=\left(I,C,{\succsim }_I,{\succsim }_C,q\right)$ and $DA\left(M_0\right)={\mu }_0$ . Let $L_0$ be the set of last proposers under $DA\left(M_0\right)$ . For each $i\in L_0$ , define: ${\succsim }_i^{*}:{\mu }_0\left(i\right),i$ . If $I\backslash L_0=\varnothing$ , then the alogrithm terminates. If $I\backslash L_0\ne \varnothing$ , then set $I_1=I\backslash L_0$ and proceed to the next step.

・ Step $k\left(k\ge 1\right)$ : Let $M_k=\left(I_k,C,{\succsim }_{I_k},{\succsim }_C{|}^{I_k},q\right)$ and $DA\left(M_k\right)={\mu }_k$ . Let $L_k$ be the set of last proposers under $DA\left(M_k\right)$ . For each $i\in L_k$ , define: ${\succsim }_i^{*}:{\mu }_k\left(i\right),{\mu }_{k-1}\left(i\right),\cdots ,{\mu }_0\left(i\right),i$ . If $I\backslash \left(L_0\cup \cdots \cup L_k\right)=\varnothing$ , then the algorithm terminates. If $I\backslash \left(L_0\cup \cdots \cup L_k\right)\ne \varnothing$ , then set $I_{k+1}=I\backslash \left(L_0\cup \cdots \cup L_k\right)$ and proceed to the next step.

This algorithm terminates in finite steps and yields a strategy profile ${\succsim }_I^{DA}={\left({\succsim }_i^{*}\right)}_{i\in I}$ , which is the DA-SSN.

Core-SSN

Given a market $M=\left(I,C,{\succsim }_I,{\succsim }_C,q\right)$ , let $\mu$ be a stable matching in this market. Then let $\left(I^{*},{\succcurlyeq }_{I^{*}},\mu \right)$ be a corresponding house allocation problem which is defined in Shapley and Scarf [8] . $I^{*}$ is the set of students such that $I^{*}=\left\{i\in I|\mu \left(i\right)\in C\right\}$ . Each i’s initial endowment is $\mu \left(i\right)$ . For each $i\in I^{*}$ , ${\succcurlyeq }_i$ is a preference relationship for $I^{*}$ satisfying: (i) for any $j\in I^{*}$ , if i is unacceptable for $\mu \left(j\right)$ , then $i{\succ }_{i}j$ , (ii) for any $j,j^{\prime }\in I^{*}$ where i is acceptable for $\mu \left(j\right)$ and $\mu \left(j^{\prime }\right)$ , $j{\succ }_i{j}^{\prime }$ if and only if $\mu \left(j\right){\succsim }_i\mu \left(j^{\prime }\right)$ .

An allocation is defined as a bijection $x:I^{*}\to I^{*}$ . Define a matching ${\mu }_x$ such that (i) if $i\in I^{*}$ , then ${\mu }_x\left(i\right)=\mu \left(x\left(i\right)\right)$ , and (ii) if $i\notin I^{*}$ , then ${\mu }_x\left(i\right)=i$ .

If x is a strict core allocation, then the strategy profile ${\succsim }_I^{Core}={\left({\succsim }_i^{Core}\right)}_{i\in I}$ such that ${\succsim }_i^{Core}:{\mu }_x\left(i\right),\mu \left(i\right),i$ is the Core-SSN. Particularly, we note that this result depends on whether the strict core exists.

Under SODA, both of the DA-SSN and the Core-SSN yield a matching which is Pareto efficient, and weakly Pareto dominates the matching determined by students’ true preferences.

3. Results

3.1. Equilibrium Concept

In this section, we propose a new equilibrium concept which is stronger than SSN (and thus it is stronger than both DA-SSN and Core-SSN). First of all, we use a simple example to show how it is defined.

Example 1. Let $I=\left\{i_1,i_2,i_3,i_4,i_5\right\}$ , $C=\left\{c_1,c_2,c_3,c_4\right\}$ and $q_{c_1}=q_{c_2}=q_{c_3}=q_{c_4}=1$ . The students’ preferences and the colleges’ preferences are given in the following table.

The student-optimal stable matching $\mu$ is:

$c_1{c}_2{c}_3{c}_4\varnothing$

$i_1{i}_4{i}_3{i}_2{i}_5$

Next we look into the DA-SSN and the Core-SSN for this example.

(DA-SSN) Applying the iterative DA which is introduced in Section 2.2, we obtain the following strategy profile ${\succsim }_I^{DA}$ :

${\succsim }_{i_1}^{DA}:c_4,c_1,i_1$

${\succsim }_{i_2}^{DA}:c_2,c_4,i_2$

${\succsim }_{i_3}^{DA}:c_1,c_3,i_3$

${\succsim }_{i_4}^{DA}:c_3,c_1,c_2,i_4$

${\succsim }_{i_5}^{DA}:i_5$

The corresponding matching ${\mu }^{*}=DA\left({\succsim }_I^{DA},{\succsim }_C,q\right)$ is:

$c_1{c}_2{c}_3{c}_4\varnothing$

$i_3{i}_2{i}_4{i}_1{i}_5$

Consider the following deviating strategies ${{\succsim }^{\prime }}_{i_1}$ for $i_1$ and ${{\succsim }^{\prime }}_{i_2}$ for $i_2$ :

${{\succsim }^{\prime }}_{i_1}:c_2,c_1,i_1$

${{\succsim }^{\prime }}_{i_2}:c_3,c_2,c_4,i_2$

We can check that $DA\left({{\succsim }^{\prime }}_{\left\{i_1,i_2\right\}},{\succsim }_{\left\{i_3,i_4,i_5\right\}}^{DA},{\succsim }_C,q\right)$ yields a matching $\nu$ which is equivalent to $\mu$ .

However, if $i_4$ agrees to deviate and play the following strategy:

${{\succsim }^{\prime }}_{i_4}:c_4,c_2,i_4$

then $DA\left({{\succsim }^{\prime }}_{\left\{i_1,i_2,i_4\right\}},{\succsim }_{\left\{i_3,i_5\right\}}^{DA},{\succsim }_C,q\right)$ yields the following matching ${\nu }^{\prime }$ :

$c_1{c}_2{c}_3{c}_4\varnothing$

$i_3{i}_1{i}_2{i}_4{i}_5$

We note that $i_4$ is strictly worse off in ${\nu }^{\prime }$ than in ${\mu }^{*}$ since ${\nu }^{\prime }\left(i_4\right)=c_4$ , ${\mu }^{*}\left(i_4\right)=c_3$ and $c_3{\succ }_{i_4}{c}_4$ . But nevertheless, she is strictly better off in ${\nu }^{\prime }$ than in $\nu$ since ${\nu }^{\prime }\left(i_4\right)=c_4$ , $\nu \left(i_4\right)=c_2$ and $c_4{\succ }_{i_4}{c}_2$ . On the other hand, we note that ${\nu }^{\prime }\left(i_1\right){\succ }_{i_1}{\mu }^{*}\left(i_1\right)$ and ${\nu }^{\prime }\left(i_2\right){\succ }_{i_2}{\mu }^{*}\left(i_2\right)$ . In this sense, we can regard ${{\succsim }^{\prime }}_{\left\{i_1,i_2\right\}}$ as $i_1$ ‘s and $i_2$ ‘s “threatening” strategy profile which forces $i_4$ to join the deviating coalition in order to avoid an even worse outcome caused by the unilateral deviation of them.

(Core-SSN) By constructing a house allocation problem as introduced in Section 2.2, we obtain the following strategy profile ${\succsim }_I^{Core}$ :

${\succsim }_{i_1}^{Core}:c_2,c_1,i_1$

${\succsim }_{i_2}^{Core}:c_4,i_2$

${\succsim }_{i_3}^{Core}:c_1,c_3,i_3$

${\succsim }_{i_4}^{Core}:c_3,c_2,i_4$

${\succsim }_{i_5}^{Core}:i_5$

The corresponding matching ${\mu }^{\prime }=DA\left({\succsim }_I^{Core},{\succsim }_C,q\right)$ is:

$c_1{c}_2{c}_3{c}_4\varnothing$

$i_3{i}_1{i}_4{i}_2{i}_5$

Consider the following deviating strategy ${{\succsim }^{″}}_{i_2}$ for $i_2$ :

${{\succsim }^{″}}_{i_2}:c_2,c_4,i_2$

We can check that $DA\left({{\succsim }^{″}}_{i_2},{\succsim }_{\left\{i_1,i_3,i_4,i_5\right\}}^{Core},{\succsim }_C,q\right)$ yields a matching ${\nu }^{″}$ which is equivalent to $\mu$ .

However, if $i_1$ agrees to join $i_2$ and play the following deviating strategy:

${{\succsim }^{″}}_{i_1}:c_4,c_1,i_1$

then $DA\left({{\succsim }^{″}}_{\left\{i_1,i_2\right\}},{\succsim }_{\left\{i_3,i_4,i_5\right\}}^{Core},{\succsim }_C,q\right)$ yields the following matching ${\nu }^{‴}$ :

$c_1{c}_2{c}_3{c}_4\varnothing$

$i_3{i}_2{i}_4{i}_1{i}_5$

Similarly, we observe that ${\nu }^{‴}\left(i_2\right){\succ }_{i_2}{\mu }^{\prime }\left(i_2\right)$ and ${\mu }^{\prime }\left(i_1\right){\succ }_{i_1}{\nu }^{‴}\left(i_1\right){\succ }_{i_1}{\nu }^{″}\left(i_1\right)$ . We can regard ${{\succsim }^{″}}_{i_2}$ as $i_2$ ’s threatening strategy which forces $i_1$ to deviate in order to avoid an even worse outcome caused by her unilateral deviation.

Example 1 presents a kind of deviating coalition in which some members were actually unwilling to deviate. They deviate not for achieving a better outcome, but for avoiding an even worse outcome which is caused by the unilateral deviation of the rest members. We name this deviation as passively weak deviation and give the formal definition as follows.

Definition 1. (Passively weak deviation) Given a strategy profile ${\succsim }_I^{*}\in D_I\left(C\right)$ and a coalition $S\subseteq I$ , we say that $S$ has a passively weak deviation at ${\succsim }_I^{*}$ if there exists ${{\succsim }^{\prime }}_S\in D_S\left(C\right)$ such that

1) $\nu \left(i\right){\succ }_i\mu \left(i\right),\exists i\in S$

2) $\nu \left(i\right){\succsim }_i{\nu }^{\prime }\left(i\right),\forall i\in S$

where $\mu =DA\left({\succsim }_I^{*},{\succsim }_C,q\right)$ , $\nu =DA\left({{\succsim }^{\prime }}_S,{\succsim }_{I\backslash S}^{*},{\succsim }_C,q\right)$ and ${\nu }^{\prime }=DA\left({{\succsim }^{\prime }}_T,{\succsim }_{I\backslash T}^{*},{\succsim }_C,q\right)$ such that $T=\left\{i\in S|\nu \left(i\right){\succsim }_i\mu \left(i\right)\right\}$ .

In a passively weak deviating coalition S, only a subgroup of members T are at least weakly better off. For each member in $S\backslash T$ , although joining S will bring her an outcome which is worse than that in a SSN, she has to do so because the outcome caused by T’s unilateral deviation is even worse for her. In this sense, each student in $S\backslash T$ “passively” chooses to deviate.

We say that a strategy profile ${\succsim }_I^{*}$ is a passively-strictly strong Nash equilibrium (P-SSN) if each coalition does not have any passively weak deviation.

We note that $T=S$ holds when $\nu \left(i\right){\succsim }_i\mu \left(i\right)$ holds for all $i\in S$ , and thus ${\nu }^{\prime }\left(i\right)=\nu \left(i\right)$ holds for all $i\in S$ in this case. This means a weak deviation must also be a passively weak deviation, and thus a P-SSN must be a SSN. However, Example 1 shows that the converse may not be true.

3.2. Existence

In this section, we study the existence problem of P-SSN. Particularly, we examine under which conditions a DA-SSN or a Core-SSN would become a P-SSN.

We first introduce two strategies that will support our next results. One is the c-bottom strategy proposed by Bando [4] . Given a market $\left(I,C,{\succsim }_I,{\succsim }_C,q\right)$ , for each ${{\succsim }^{\prime }}_i\in D_i\left(C\right)$ and $c\in C\cup \left\{i\right\}$ , define $U\left(c,{{\succsim }^{\prime }}_i\right)=\left\{c^{\prime }\in C\cup \left\{i\right\}|c^{\prime }{{\succsim }^{\prime }}_{i}c\right\}$ as the set of colleges that i weakly prefers to c under ${{\succsim }^{\prime }}_i$ . Then each i’s -bottom strategy ${\succsim }_i^c$ is defined as follows.

Definition 2. (c-bottom strategy, Bando [4] )

1) $c{{\succsim }^{\prime }}_{i}i$ and $c{\succsim }_i^{c}i$ ,

2) $U\left(c,{\succsim }_i^c\right)\subseteq U\left(c,{{\succsim }^{\prime }}_i\right)$ ,

3) There exists no $c^{\prime }\in C$ such that $c{\succsim }_i^c{c}^{\prime }{\succsim }_i^{c}i$ .

Let $\mu =DA\left({\succsim }_I,{\succsim }_C,q\right)$ . We are interested in $\mu \left(i\right)$ -bottom strategy related to the true preference ${\succsim }_i$ ( $\mu \left(i\right)$ -bottom strategy for short). Bando [4] further demonstrated the following results about $\mu \left(i\right)$ -bottom strategy.

Lemma 1. (Bando [4] ) Let $M=\left(I,C,{\succsim }_I,{\succsim }_C,q\right)$ be a market. Let $\mu$ be a stable matching in $M$ . For each $i\in I$ , let ${\succsim }_i^{*}$ be a $\mu \left(i\right)$ -bottom strategy related to ${\succsim }_i$ . Consider a coalition $S$ and ${{\succsim }^{\prime }}_S\in D_S\left(C\right)$ such that (i) $\nu \left(i\right){\succsim }_i{\mu }^{*}\left(i\right)$ for all $i\in S$ and (ii) ${{\succsim }^{\prime }}_i:\nu \left(i\right),i$ for all $i\in S$ , where $\nu =DA\left({{\succsim }^{\prime }}_S,{\succsim }_{I\backslash S}^{*},{\succsim }_C,q\right)$ and ${\mu }^{*}=DA\left({\succsim }_I^{*},{\succsim }_C,q\right)$ . Then we have that

1) ${\mu }^{*}\left(i\right){\succsim }_i\mu \left(i\right)$ for all $i\in I$ ,

2) $\nu \left(i\right){\succsim }_i\mu \left(i\right)$ for all $i\in I$ ,

3) $\left|\nu \left(i\right)\right|=\left|\mu \left(i\right)\right|$ for all $i\in I$ and $\left|{\nu }^{-1}\left(c\right)\right|=\left|{\mu }^{-1}\left(c\right)\right|$ for all $c\in C$ , where $\left|\mu \left(i\right)\right|=1$ if $\mu \left(i\right)\in C$ and $\left|\mu \left(i\right)\right|=0$ if $\mu \left(i\right)=i$ .

Here we note that the deviating coalition’s joint strategies have a quite simple structure. Roth [10] and Bando [4] demonstrated that if a coalition S has a successful deviation (either in a strong sense or in a weak sense), then it equals to using a simplified strategy that each student in S reports the deviating outcome as her first choice. Therefore, we also consider this kind of simple deviation in this research.

Based on the previous results, we are ready to introduce our first finding. We show that if the DA-SSN and the Core-SSN yield different matchings under SODA, then neither of them is a P-SSN. In other words, we can always construct a passively weak deviation at either the DA-SSN or the Core-SSN.

Proposition 1. Let $\left(I,C,{\succsim }_I,{\succsim }_C,q\right)$ be a market. Let $\mu =DA\left({\succsim }_I,{\succsim }_C,q\right)$ . Let ${\mu }^{*}=DA\left({\succsim }_I^{DA},{\succsim }_C,q\right)$ . Suppose that the Core-SSN exists, and let ${\mu }^{\prime }=DA\left({\succsim }_I^{Core},{\succsim }_C,q\right)$ . If ${\mu }^{*}\ne {\mu }^{\prime }$ , then neither ${\succsim }_I^{Core}$ nor ${\succsim }_I^{DA}$ is a P-SSN.

Proof. (i) We first show that we can construct a passively weak deviation at ${\succsim }_I^{Core}$ . By assumption, there exists $i\in I$ such that ${\mu }^{*}\left(i\right){\succ }_i{\mu }^{\prime }\left(i\right)$ . Otherwise, ${\mu }^{\prime }\left(i\right){\succsim }_i{\mu }^{*}\left(i\right)$ holds for all $i\in I$ . Since ${\mu }^{*}\ne {\mu }^{\prime }$ , a contradiction occurs with the Pareto efficiency of ${\mu }^{*}$ . Let $S^{+}=\left\{i\in I|{\mu }^{*}\left(i\right){\succ }_i{\mu }^{\prime }\left(i\right)\right\}$ , and let $S^{-}=\left\{i\in I|{\mu }^{\prime }\left(i\right){\succsim }_i{\mu }^{*}\left(i\right)\right\}$ . For each $c\in C$ , define $A_c\left(\mu ,{\succsim }_I\right)=\left\{i\in I|c{\succsim }_i\mu \left(i\right)\right\}$ as the set of students who weakly prefer $c$ to their assignments.

Consider the strategy ${{\succsim }^{\prime }}_i:{\mu }^{*}\left(i\right),\mu \left(i\right),i$ for all $i\in S^{+}$ . Let $\nu =DA\left({{\succsim }^{\prime }}_{S^{+}},{\succsim }_{S^{-}}^{Core},{\succsim }_C,q\right)$ . We will show that $\nu \left(i\right)=\mu \left(i\right)$ holds for all $i\in I$ . Suppose that there exists $i^{\prime }\in I$ such that $\nu \left(i^{\prime }\right)\ne \mu \left(i^{\prime }\right)$ . Note that $\left({{\succsim }^{\prime }}_{S^{+}},{\succsim }_{S^{-}}^{Core}\right)$ consists of $\mu \left(i\right)$ -bottom strategies. Hence by Lemma 1, $\nu \left(i\right){\succsim }_i\mu \left(i\right)$ holds for all $i\in I$ . This implies that $\nu \left(i^{\prime }\right){\succ }_{i^{\prime }}\mu \left(i^{\prime }\right)$ . Let $\nu \left(i^{\prime }\right)=c$ . By the stability of $\nu$ , we have that $i^{\prime }\in C{h}_c\left(A_c\left(\nu ,\left({{\succsim }^{\prime }}_{S^{+}},{\succsim }_{S^{-}}^{Core}\right)\right)|{\succsim }_c\right)$ . On the other hand, recall the construction of ${\succsim }_I^{Core}$ and ${\succsim }_I^{DA}$ . We note that $\nu \left(i\right)\in A_{\mu \left(i\right)}\left(\mu ,{\succsim }_I\right)$ for all $i\in S^{+}$ and $\nu \left(j\right)\in A_{\mu \left(j\right)}\left(\mu ,{\succsim }_I\right)$ for all $j\in S^{-}$ . This implies that $\nu$ is also stable in the market $\left(I,C,{\succsim }_I,{\succsim }_C,q\right)$ . However, $\mu$ is the student-optimal matching in this market, which implies that $\mu \left(i\right){\succsim }_i\nu \left(i\right)$ holds for all $i\in I$ . Hence the only possibility is that $\nu \left(i\right)=\mu \left(i\right)$ for all $i\in I$ .

Let $S^{\prime }=\left\{i\in I|{\mu }^{\prime }\left(i\right){\succ }_i{\mu }^{*}\left(i\right)\right\}$ . Then consider ${{\succsim }^{\prime }}_{i^{″}}:{\mu }^{*}\left(i^{″}\right),\mu \left(i^{″}\right),i^{″}$ for all $i^{″}\in S^{\prime }$ . Let ${\nu }^{\prime }=DA\left({{\succsim }^{\prime }}_{S^{+}},{{\succsim }^{\prime }}_{S^{\prime }},{\succsim }_{S^{-}\backslash S^{\prime }}^{Core},{\succsim }_C,q\right)$ . Then ${\nu }^{\prime }\left(i\right)={\mu }^{*}\left(i\right){\succsim }_i\mu \left(i\right)$ for all $i\in I$ . Therefore, $S^{+}\cup S^{\prime }$ constitutes a passively weak deviation where each $i^{‴}\in S^{+}\cup S^{\prime }$ plays strategy ${{\succsim }^{\prime }}_{i^{‴}}:{\mu }^{*}\left(i^{‴}\right),\mu \left(i^{‴}\right),i^{‴}$ .

(ii) Similarly, let $S^{+}=\left\{i\in I|{\mu }^{\prime }\left(i\right){\succ }_i{\mu }^{*}\left(i\right)\right\}$ , and let $S^{-}=\left\{i\in I|{\mu }^{*}\left(i\right){\succsim }_i{\mu }^{\prime }\left(i\right)\right\}$ . Then consider the strategy ${{\succsim }^{″}}_i:{\mu }^{\prime }\left(i\right),\mu \left(i\right),i$ for all $i\in S^{+}$ . The proof goes almost the same as that in (i), and thus we omit it here. □

However, the Core-SSN usually fails to exist since it depends on the existence of the strict core in the corresponding house allocation problem. Therefore, our second result focuses on the DA-SSN. We show that under SODA, if the DA- SSN yields a matching which satisfies a condition called irrelevance of low-tier agents, then it is also a P-SSN.

Definition 3. (Irrelevance of low-tier agents) Let $M=\left(I,C,{\succsim }_I,{\succsim }_C,q\right)$ be a market. Let ${\mu }^{*}=DA\left({\succsim }_I^{DA},{\succsim }_C,q\right)$ . Suppose that the iterative DA ends in $K$ steps such that $K\ge 1$ . Denote the set of last proposers in each step be $L_k$ such that $0\le k\le K$ . We say that ${\mu }^{*}$ satisfies irrelevance of low-tier agents if and only if pick any $i\in I$ such that $i\in L_k$ , we have that $\mu \left(i\right){\succ }_i{\mu }^{*}\left(i^{\prime }\right)$ for all $i^{\prime }$ such that $i^{\prime }\in L_{k^{\prime }}$ and $k^{\prime }<k$ .

This condition requires each student not to accept the assignment of any student who was identified as the last proposer in an earlier step than she was.

The next lemma is a direct application of Lemma 1.

Lemma 2. Let $M=\left(I,C,{\succsim }_I,{\succsim }_C,q\right)$ be a market. Let $\mu =DA\left({\succsim }_I,{\succsim }_C,q\right)$ . Denote ${\succsim }_I^{DA}$ be ${\succsim }_I^{*}$ and let ${\mu }^{*}=DA\left({\succsim }_I^{*},{\succsim }_C,q\right)$ . Consider a coalition $S$ and ${{\succsim }^{\prime }}_S\in D_S\left(C\right)$ such that (i) $\nu \left(i\right){\succsim }_i{\mu }^{*}\left(i\right)$ for some $i\in S$ , (ii) $\nu \left(i\right){\succsim }_i{\nu }^{\prime }\left(i\right)$ for all $i\in S$ , and (iii) ${{\succsim }^{\prime }}_i:\nu \left(i\right),\mu \left(i\right),i$ for all $i\in S$ , where $\nu =DA\left({{\succsim }^{\prime }}_S,{\succsim }_{I\backslash S}^{*},{\succsim }_C,q\right)$ and ${\nu }^{\prime }=DA\left({{\succsim }^{\prime }}_T,{\succsim }_{I\backslash T}^{*},{\succsim }_C,q\right)$ such that $T=\left\{i\in S|\nu \left(i\right){\succsim }_i{\mu }^{*}\left(i\right)\right\}$ . Then we have that

1) ${\nu }^{\prime }\left(i\right){\succsim }_i\mu \left(i\right)$ for all $i\in I$ ,

2) $\left|\nu \left(i\right)\right|=\left|\mu \left(i\right)\right|$ for all $i\in I$ and $\left|{\nu }^{-1}\left(c\right)\right|=\left|{\mu }^{-1}\left(c\right)\right|$ for all $c\in C$ , where $\left|\mu \left(i\right)\right|=1$ if $\mu \left(i\right)\in C$ and $\left|\mu \left(i\right)\right|=0$ if $\mu \left(i\right)=i$ .

Since $\left({{\succsim }^{\prime }}_T,{\succsim }_{I\backslash T}^{\text{*}}\right)$ consists of $\mu \left(i\right)$ -bottom strategies, Lemma 2 immediately follows from Lemma 1.

Then we have the following result.

Proposition 2. Let $\left(I,C,{\succsim }_I,{\succsim }_C,q\right)$ be a market. Let $\mu =DA\left({\succsim }_I,{\succsim }_C,q\right)$ . Let ${\mu }^{*}=DA\left({\succsim }_I^{DA},{\succsim }_C,q\right)$ . If ${\mu }^{*}$ satisfies irrelevance of lower-tier agents, then ${\succsim }_I^{DA}$ is a P-SSN.

Proof. Suppose that ${\succsim }_I^{DA}$ is not a P-SSN. Then there exists a coalition $S$ and ${{\succsim }^{\prime }}_S\in D_S\left(C\right)$ such that (i) $\nu \left(i\right){\succ }_i{\mu }^{*}\left(i\right)$ for some $i\in S$ , (ii) $\nu \left(i\right){\succsim }_i{\nu }^{\prime }\left(i\right)$ for all $i\in S$ , and (iii) ${{\succsim }^{\prime }}_i:\nu \left(i\right),\mu \left(i\right),i$ for all $i\in S$ , where $\nu =DA\left({{\succsim }^{\prime }}_S,{\succsim }_{I\backslash S}^{DA},{\succsim }_C,q\right)$ and ${\nu }^{\prime }=DA\left({{\succsim }^{\prime }}_T,{\succsim }_{I\backslash T}^{DA},{\succsim }_C,q\right)$ such that $T=\left\{i\in S|\nu \left(i\right){\succsim }_i{\mu }^{*}\left(i\right)\right\}$ . Moreover, $S\backslash T\ne \varnothing$ holds. Otherwise, $S$ has a weak deviation from ${\succsim }_I^{DA}$ and it cannot be a SSN.

Let $T^{+}=\left\{i\in S|\nu \left(i\right){\succ }_i{\mu }^{*}\left(i\right)\right\}$ . Suppose that the iterative DA ends in $K$ rounds such that $K\ge 0$ . Then it suffice to show that $L_k\cap T^{+}=\varnothing$ for each $k\in \left\{0,1,\cdots ,K\right\}$ .

Suppose that there exists $i\in L_k$ such that $\nu \left(i\right){\succ }_i{\mu }^{*}\left(i\right)$ . Since $\left|\nu \left(i\right)\right|=\left|{\mu }^{*}\left(i\right)\right|$ holds for all $i\in I$ according to Lemma 2, we know that $\nu \left(i\right)\in C$ and $\mu \left(i\right)\in C$ . Let $\nu \left(i\right)=c$ . Then $\left|{\mu }^{\ast -1}\left(c\right)\right|=q_c$ holds. Otherwise, we have that ${\mu }^{\ast -1}\left(c\right)\cup \left\{i\right\}{\succ }_c{\mu }^{\ast -1}\left(c\right)$ by responsiveness. This implies $i\in C{h}_c\left({\mu }^{*-1}\left(c\right)\cup \left\{i\right\}|{\succsim }_c\right)$ and hence a contradiction occurs with the stability of ${\mu }^{*}$ . On the other hand, since ${\mu }^{*}$ satisfies irrelevance of low-tier agents, we know that $c\in {\mu }^{*}\left(L_{k+1}\cup L_{k+2}\cup \cdots \cup L_K\right)$ . Then there exists $j$ such that ${\mu }^{*}\left(j\right)\in {\mu }^{*}\left(L_{k+1}\cup L_{k+2}\cup \cdots \cup L_K\right)$ and $\nu \left(j\right)\in {\mu }^{*}\left(L_0\cup L_1\cup \cdots \cup L_k\right)$ . However, we have that $\mu \left(j\right){\succ }_j\nu \left(j\right)$ again by the irrelevance of low-tier agents. Since $\nu \left(j\right){\succsim }_j\mu \left(j\right)$ by Lemma 2, a contradiction occurs. □

4. Conclusion and Discussion

In this research, we revisit a college admission market and a related preference revelation game under SODA. We propose a new equilibrium concept called passively-strictly strong Nash equilibrium (P-SSN). It rules out a deviating coalition called passively weak deviation that includes members who become strictly worse off. In other words, they were actually unwilling to deviate. But if not doing so, they will receive an even worse outcome which is caused by the unilateral deviation of the rest members. In this sense, some students were threatened to join the deviating coalition. Then we show two preliminary existence results about P-SSN.

In general, P-SSN is a quite restrictive equilibrium concept that easily fails to exist. But nevertheless, we plan to examine the following two extensions of Definition 1. (i) ${\nu }^{\prime }\left(i\right){\succsim }_i\mu \left(i\right)$ for all $i\in T$ . This condition requires students who have threatened others to join the deviating coalition not become worse off even if they deviate unilaterally. That is, their threatening strategy will not hurt themselves even if the target students do not cooperate. (ii) $\nu \left(j\right){\succ }_j{\nu }^{\prime }\left(j\right)$ for all $j\in S\backslash T$ . That is, each student who deviates passively should receive a strictly better outcome than that caused by the rest students’ unilateral deviation. With those assumptions, we can check that the SSNs in Example 1 would become P-SSN. Such equilibrium concepts give inspiration to the refinement problem when multiple equilibria exist, which we will study in the future research.

Cite this paper

Li, C.Y., Inohara, T. and Kitamura, M. (2017) Passively- Strictly Strong Nash Equilibrium in a Preference Revelation Game under the Student- Optimal Deferred Acceptance Algorithm. Theoretical Economics Letters, 7, 1244-1254. https://doi.org/10.4236/tel.[phone]

NOTES

¹See Roth and Sotomayor [2] for a comprehensive introduction.

²A college c’s preferences ${\succsim }_c$ satisfy responsiveness with quota q_c if (i) for any $i,i^{\prime }{\succ }_c\varnothing$ and any $S{\succ }_c\varnothing$ such that $i\in S$ , $i^{\prime }\notin S$ and $\left|S\right|<q_c$ , $S\backslash \left\{i\right\}\cup \left\{i^{\prime }\right\}{\succ }_{c}S$ if and only if $i^{\prime }{\succ }_{c}i$ , (ii) for any $i\in I$ and any $S{\succ }_i\varnothing$ with $i\notin S$ and $\left|S\right|<q_c$ , $S\cup \left\{i\right\}{\succ }_{c}S$ if and only if $i{\succ }_c\varnothing$ , and (iii) for any $S\subseteq I$ with $\left|S\right|>q_c$ , $\varnothing {\succ }_{c}S$ .

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Gale, D. and Shapley, L. (1962) College Admissions and Stability of Marriage. American Mathematicas Monthly, 69, 9-15. http://www.jstor.org/stable/2312726 https://doi.org/10.2307/2312726
[2]	Roth, A.E. and Sotomayor, M. (1990) Two-Sided Matching: A Study in Game Theoretical Modeling and Analysis. Cambridge University Press, Cambridge, UK. https://doi.org/10.1017/CCOL052139015X
[3]	Dubins, L. and Freedman, D. (1981) Machiavelli and the Gale-Shapley Algorithm. American Mathematics Monthly, 88, 485-494. http://www.jstor.org/stable/2321753 https://doi.org/10.2307/2321753
[4]	Bando, K. (2014) On the Existence of a Strictly Strong Nash Equilibrium under the Student-Optimal Deferred Acceptance Algorithm. Games and Economic Behavior, 87, 269-287. https://doi.org/10.1016/j.geb.2014.05.009
[5]	Sotomayor, M. (2008) The Stability of the Equilibrium Outcomes in the Admission Games Induced by Stable Matching Rules. International Journal of Game Theory, 36, 621-640. https://doi.org/10.1007/s00182-008-0115-8
[6]	Kesten, O. (2010) School Choice with Consent. Quarterly Journal of Economics, 125, 1297-1348. https://doi.org/10.1162/qjec.2010.125.3.1297
[7]	Tang, Q. and Yu, J. (2014) A New Perspective on Kesten’s School Choice with Consent Idea. Journal of Economic Theory, 154, 543-561. https://doi.org/10.1016/j.jet.2014.10.002
[8]	Shapley, L. and Scarf, H. (1974) On Cores and Indivisibility. Journal of Mathematical Economics, 1, 23-37. https://doi.org/10.1016/0304-4068(74)90033-0
[9]	Roth, A.E. (1985) The College Admissions Problem Is Not Equivalent to the Marriage Problem. Journal of Economic Theory, 36, 277-288. https://doi.org/10.1016/0022-0531(85)90106-1
[10]	Roth, A.E. (1982) The Economics of Matching: Stability and Incentives. Mathematics of Operations Research, 7, 617-628. http://www.jstor.org/stable/3689483 https://doi.org/10.1287/moor.7.4.617