Theoretical Economics Letters
Vol.07 No.05(2017), Article ID:78077,11 pages
10.4236/tel.2017.75084
Passively-Strictly Strong Nash Equilibrium in a Preference Revelation Game under the Student-Optimal Deferred Acceptance Algorithm
Chengyue Li1*, Takehiro Inohara1, Masahito Kitamura2
1Department of Value and Decision Science, Tokyo Institute of Technology, Tokyo, Japan
2Department of Risk Science in Finance and Management, Chiba Institute of Technology, Chiba, Japan
Copyright © 2017 by authors and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: June 16, 2017; Accepted: July 28, 2017; Published: July 31, 2017
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 matching1.
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 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 over , where means being unmatched. Let be the students’ preference profile.
Each college c has strict preferences over . Let be the colleges’ preference profile. Particularly, let be the restriction of to singleton sets and the empty set. For each and , we say that i is acceptable for c if ( ). Let be the quota of college c. Let .
We assume that each college c’s preferences satisfy responsiveness with quota which is defined in Roth [9] 2. That is, c is strictly better off by replacing any student with a more preferred acceptable student in , 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 with because only is relevant to our analysis.
Given and , each college c’s choice set is defined as the set which satisfies (i) and (ii) for all .
A matching is defined as a function from into which satisfies (i) for each , and (ii) for each , implies .
We say that a matching is individually rational for students if for all , and is individually rational for colleges if for all . A matching is individually rational if it is individually rational for both students and colleges. We say that a matching is blocked by if (i) and (ii) . A matching is stable if it is individually rational and is not blocked.
2.2. Preference Revelation Game
Let be a strategic game defined on a college admission market . is the set of players. Given a strategy profile , the outcome of this game is determined by SODA and is denoted be . Each student evaluates the outcome according to her true preferences .
For each , define as the set of her strict preferences over . A coalition is a nonempty subset of students. Define 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 , we say that a coalition S has a weak deviation at if there exists such that (i) for all and (ii) for some , where and . A strategy profile is a SSN if each coalition does not have any weak deviation. When holds for all , we say that has a strong deviation at , and is a SN if each coalition does not have any strong deviation.
Dubins and Freedman [3] showed that the truth-telling strategy profile 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 , for each and , let be the restriction of to . That is, is the strict preferences over such that for any , if and only if . Let be the profile of the restricted preferences. Then the iterative DA is defined as follows.
・ Step 0: Let and . Let be the set of last proposers under . For each , define: . If , then the alogrithm terminates. If , then set and proceed to the next step.
・ Step : Let and . Let be the set of last proposers under . For each , define: . If , then the algorithm terminates. If , then set and proceed to the next step.
This algorithm terminates in finite steps and yields a strategy profile , which is the DA-SSN.
Core-SSN
Given a market , let be a stable matching in this market. Then let be a corresponding house allocation problem which is defined in Shapley and Scarf [8] . is the set of students such that . Each i’s initial endowment is . For each , is a preference relationship for satisfying: (i) for any , if i is unacceptable for , then , (ii) for any where i is acceptable for and , if and only if .
An allocation is defined as a bijection . Define a matching such that (i) if , then , and (ii) if , then .
If x is a strict core allocation, then the strategy profile such that 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 , and . The students’ preferences and the colleges’ preferences are given in the following table.
The student-optimal stable matching is:
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 :
The corresponding matching is:
Consider the following deviating strategies for and for :
We can check that yields a matching which is equivalent to .
However, if agrees to deviate and play the following strategy:
then yields the following matching :
We note that is strictly worse off in than in since , and . But nevertheless, she is strictly better off in than in since , and . On the other hand, we note that and . In this sense, we can regard as ‘s and ‘s “threatening” strategy profile which forces 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 :
The corresponding matching is:
Consider the following deviating strategy for :
We can check that yields a matching which is equivalent to .
However, if agrees to join and play the following deviating strategy:
then yields the following matching :
Similarly, we observe that and . We can regard as ’s threatening strategy which forces 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 and a coalition , we say that has a passively weak deviation at if there exists such that
1)
2)
where , and such that .
In a passively weak deviating coalition S, only a subgroup of members T are at least weakly better off. For each member in , 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 “passively” chooses to deviate.
We say that a strategy profile is a passively-strictly strong Nash equilibrium (P-SSN) if each coalition does not have any passively weak deviation.
We note that holds when holds for all , and thus holds for all 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
, for each
and
, define
as the set of colleges that i weakly prefers to c under
. Then each i’s
Definition 2. (c-bottom strategy, Bando [4] )
1) and ,
2) ,
3) There exists no such that .
Let . We are interested in -bottom strategy related to the true preference ( -bottom strategy for short). Bando [4] further demonstrated the following results about -bottom strategy.
Lemma 1. (Bando [4] ) Let be a market. Let be a stable matching in . For each , let be a -bottom strategy related to . Consider a coalition and such that (i) for all and (ii) for all , where and . Then we have that
1) for all ,
2) for all ,
3) for all and for all , where if and if .
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 be a market. Let . Let . Suppose that the Core-SSN exists, and let . If , then neither nor is a P-SSN.
Proof. (i) We first show that we can construct a passively weak deviation at . By assumption, there exists such that . Otherwise, holds for all . Since , a contradiction occurs with the Pareto efficiency of . Let , and let . For each , define as the set of students who weakly prefer to their assignments.
Consider the strategy for all . Let . We will show that holds for all . Suppose that there exists such that . Note that consists of -bottom strategies. Hence by Lemma 1, holds for all . This implies that . Let . By the stability of , we have that . On the other hand, recall the construction of and . We note that for all and for all . This implies that is also stable in the market . However, is the student-optimal matching in this market, which implies that holds for all . Hence the only possibility is that for all .
Let . Then consider for all . Let . Then for all . Therefore, constitutes a passively weak deviation where each plays strategy .
(ii) Similarly, let , and let . Then consider the strategy for all . 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 be a market. Let . Suppose that the iterative DA ends in steps such that . Denote the set of last proposers in each step be such that . We say that satisfies irrelevance of low-tier agents if and only if pick any such that , we have that for all such that and .
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 be a market. Let . Denote be and let . Consider a coalition and such that (i) for some , (ii) for all , and (iii) for all , where and such that . Then we have that
1) for all ,
2) for all and for all , where if and if .
Since consists of -bottom strategies, Lemma 2 immediately follows from Lemma 1.
Then we have the following result.
Proposition 2. Let be a market. Let . Let . If satisfies irrelevance of lower-tier agents, then is a P-SSN.
Proof. Suppose that is not a P-SSN. Then there exists a coalition and such that (i) for some , (ii) for all , and (iii) for all , where and such that . Moreover, holds. Otherwise, has a weak deviation from and it cannot be a SSN.
Let . Suppose that the iterative DA ends in rounds such that . Then it suffice to show that for each .
Suppose that there exists such that . Since holds for all according to Lemma 2, we know that and . Let . Then holds. Otherwise, we have that by responsiveness. This implies and hence a contradiction occurs with the stability of . On the other hand, since satisfies irrelevance of low-tier agents, we know that . Then there exists such that and . However, we have that again by the irrelevance of low-tier agents. Since 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) for all . 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) for all . 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.2017.75084
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
NOTES
1See Roth and Sotomayor [2] for a comprehensive introduction.
2A college c’s preferences satisfy responsiveness with quota qc if (i) for any and any such that , and , if and only if , (ii) for any and any with and , if and only if , and (iii) for any with , .