## 5 The Lattice Property
### The Lattice of Stable Score Vectors  
A graph, \(G\), is simple if \(G\) has neither parallel edges nor loops. Therefore, between a given student and college, only one contract is permitted. In some applications, for example in the college enrollment system, the underlying graph is simple: one cannot apply to the same department, in the same year, twice. For the sake of generalizations that involve for example loser-free choice functions, the underlying graph in our model may not be simple. Assume that \(F\) and \(G\) are substitutable choice functions and \(G\) is also loser-free. Define the following function \(f:\mathbb{N}^{E}\rightarrow\mathbb{N}^{E}\):  
\[f(\underline{t})=P_{G}(E\setminus\mathcal{D}_{F}(P(\underline{t})))\]  
Therefore, we take all contracts above score limit \(\underline{t}\) (this is \(P(\underline{t})\)) and add those contracts that are not dominated by \(P(\underline{t})\). Then, \(f(\underline{t})\) is the score limit that the colleges choose for this set. If \(\underline{t}_{1}\leq\underline{t}_{2}\), then \(P(\underline{t}_{1})\supseteq P(\underline{t}_{2})\). Since \(\mathcal{D}_{F}\) is monotone, \(E\setminus\mathcal{D}_{F}(P(\underline{t}_{1})))\subseteq E\setminus \mathcal{D}_{F}(P(\underline{t}_{2})))\). For a greater set, \(P_{G}\) gives a higher score limit; so, \(P_{G}(E\setminus\mathcal{D}_{F}(P(\underline{t}_{1})))\leq P_{G}(E\setminus \mathcal{D}_{F}(P(\underline{t}_{2})))\). Therefore, \(f\) is a monotone function, indeed. **Statement 5**. : _If the underlying graph, \(\mathcal{G}\), is simple, and choice functions \(F\) and \(G\) are substitutable, \(G\) is loser-free; then, score vector \(\underline{t}\) is stable if and only if \(\underline{t}=P_{G}(E\setminus\mathcal{D}_{F}(P(\underline{t}))).\)_  
[PERSON]'s fixed point theorem implies the following corollary:  
**Theorem 12**. : _If graph \(\mathcal{G}\) is simple, choice functions \(F\) and \(G\) are substitutable and \(G\) is loser-free, then the score-stable sets form a non-empty lattice._  
Moreover, we can achieve a connection with four-stability for every bipartite graph. **Statement 6**. : _If choice functions \(F\) and \(G\) are substitutable, \(G\) is loser-free and \(F\) is path independent, then the following two statements are equivalent: (i) \(S=F(P(\underline{t}))\) for some score vector \(\underline{t}\), such that \(f(\underline{t})=\underline{t}\), (ii) The contract set \(S\) is four-stable._  
As a corollary of Statements 5 and 6, we get the following theorem:  
**Theorem 13**. : _If choice functions \(F\) and \(G\) are substitutable, \(G\) is loser-free and the applicants' choice function \(F\) is path independent, then every score-stable set is also four-stable. Furthermore, if we require that graph \(\mathcal{G}\) is simple, then score-stability is equivalent with four-stability._  
**Example 10**. : _Figure 4 illustrates a counterexample for Theorem 13 if the underlying graph is not simple._  
**Figure 4**. A counterexample. _There is one college and one student, and the student applies both for math and physics, but prefers math. She achieved a zero score on both. The college has a common quota of one for these two faculties. If the score limit is one, the college accepts nobody._  
_If the score limit is zero, the college accepts both contracts \(a\) and \(b\), and the applicant prefers \(a\), so only \(a\) realizes. This is valid and stable. Therefore, the only score-stable solution is \(\underline{t}=0\), \(S=F(P(\underline{t}))=\{a\}\). There are two four-stable sets: \(S=\emptyset\) with \(A=\emptyset,B=\{a,b\}\)_  
Stable score vectors form a lattice, even if the graph is not simple; so, a stronger version of Theorem 12 is also true:  
**Theorem 14**. : _If choice functions \(F\) and \(G\) are substitutable and \(G\) is loser-free, then the score-stable sets form a non-empty lattice._  
In the Appendix, we prove Theorem 14 by taking a pointwise minimum of \(\underline{t}^{1}\) and \(\underline{t}^{2}\) and starting from there.