## 3 Stability Concepts
### Score-Stability  
In this part, we describe the stability notion used in the Hungarian college admission scheme. For this reason, we shall call the agents colleges and applicants, and application is a synonym for contract. The mathematical model of the Hungarian college admissions system is close to stable matchings. Our  
Figure 3: Four-partition of the edge-set. model is a simplified version of the one that is used in practice. [PERSON], [PERSON] [9], [PERSON] and [PERSON] [5] also examined the math behind stable score limits. We shall generalize the model for loser-free choice functions, in particular for weighed scoring choice functions that have possible practical applications. Assume that we have \(n\) applicants \(A_{1},A_{2},\ldots,A_{n}\) and \(m\) colleges \(C_{1},C_{2},\ldots C_{m}\). Let \(E\) be the set of all contracts. It is convenient to think that \(E\) is the set of edges of the bipartite graph with color classes \(\{A_{1},\ldots,A_{n}\}\) and \(\{C_{1},\ldots,C_{m}\}\), where each edge, \(A_{i}C_{j}\), of the graph corresponds to a contract between applicant \(A_{i}\) and college \(C_{j}\). There, every applicant has a strict preference order over the colleges she applies to, and each college assigns some score \(s(A_{i}C_{j})\) (an integer between one and \(M\)) to each of its applicants. Moreover, each college, \(C\), has a quota, \(q(C)\), on admissible applicants. According to the law, no college can accept more applicants than its quota; moreover if an applicant, \(A_{i}\), with a certain score, \(s(A_{i}C_{j})\), is not acceptable to some college, \(C_{j}\), then any applicant with the same or lower score has to be unacceptable for \(C_{j}\). To determine the admissions after all information is known, each college has to declare a score limit. Let the score limits for colleges \(C_{1},C_{2},\ldots C_{m}\) be \(t_{1},t_{2},\ldots t_{m}\), respectively. Each applicant will become a student at her most preferred college where she has a high enough score. More precisely, applicant \(A_{i}\) is assigned to college \(C_{j}\) if \(s(A_{i}C_{j})\geq t_{j}\) (_i.e._, score \(s(A_{i}C_{j})\) of \(A_{i}\) at \(C_{j}\) is not less than threshold \(t_{j}\) for \(C_{j}\)) and \(s(A_{i}C_{j^{\prime}n})<t_{j^{\prime}}\) for \(j^{\prime}>_{i}j\) (_i.e._, score \(s(A_{i}C_{j^{\prime}})\) of \(A_{i}\) at \(C_{j^{\prime}}\) is less than the score limit, \(t_{j^{\prime}}\), if \(A_{i}\) likes \(C_{j^{\prime}}\) more than \(C_{j}\)). The vector of declared score limits \((t_{1},t_{2},\ldots,t_{m})\) is called a _score vector_. The stability notion below is defined according to the requirements of Hungarian law. **Definition 12**. : Score vector \((t_{1},t_{2},\ldots t_{m})\) is _valid_ if no college exceeds its quota with these score limits. Score vector \((t_{1},t_{2},\ldots t_{m})\) is _critical_ if for every college, \(C_{j}\), either \(t_{j}=0\) or score vector \((t_{1},t_{2},\ldots,t_{j-1},t_{j-1},t_{j+1},\ldots,t_{m})\) would assign more than \(q(C_{j})\) students to \(C_{j}\) (that is, no single college can decrease its score limit without exceeding its quota). A score vector, \(\underline{s}\), is _score-stable_ if \(\underline{s}\) is valid and critical. The above college admissions model determines a natural choice function for applicants and another one for the colleges. Therefore, for subset \(X\subseteq E\) of contracts, \(F_{i}(X)\) denotes the most preferred contract from \(X\) of applicant \(A_{i}\), and \(F(X)\) is the common choice function of all applicants. Therefore, \(F=F_{1}+F_{2}+\ldots F_{n}\). Similarly, \(G_{j}(X)\) denotes the set of contracts that college \(C_{j}\) would choose if it can select freely. More precisely, let \(X_{j}\) denote the set of contracts with \(C_{j}\) in \(X\), and let \(C_{j}\) declare a score limit, \(t_{j}\), such that no more than \(q(C_{j})\) contracts from \(X_{j}\) has score of at least \(t_{j}\), but either \(t_{j}=0\) or more than \(q(C_{j})\) contracts has a score of at least \(t_{j}-1\).