## 2 Preliminaries
### Examples for Choice Functions  
Here, we list some typical choice functions. Some of them are coming from practical applications, while some others are mostly theoretical, illustrating the flexibility of substitutable choice functions. Let \(v\) be an agent ( _i.e._, a vertex of \(G=(V,E)\)), and let \(E(v)\) be the set of possible contracts involving \(v\) ( _i.e._, the edges from \(v\)). 1. Agent \(v\)'s preferences are strict and always choose the best one: \(F(X)=\) the best member of \(X\). 2. Preferences are strict, and we allow polygamy ( _i.e._, a college can have more than one student). The choice function picks the best \(k\) contracts for some fixed \(k\): \(F(X)=\) the best \(k\) members of \(X\). If \(|X|\leq k\), then \(F(X)=X\). 3. We allow ties in the preference list. Here, \(v\) chooses the best partner if it is unique and chooses the empty set if there is more than one best partner. 4. We allow ties in the preference list. Agent \(v\) chooses the best partner if it is unique, and it chooses the set of best partners if there are two or more. 5. Let \(Q_{k}\) be the following choice function on \(E(v)\): for \(A\subseteq E(v)\), if \(|A|\leq k\), then \(Q_{k}(A)=A\), and if \(|A|>k\), then \(Q_{k}(A)=\emptyset\). 6. _Hungarian (H-scoring) choice function_: Every contract has a certain integral score: in the college admissions model, this is the number of points that the corresponding student reached at the particular college's entrance exam. There is also a quota, \(q\). If \(X\) is a given set of contracts, then \(v\) picks score \(t\), such that there are \(k\) contracts in \(X\) having a score of at least \(t\) and \(k\leq q\), and there are more than \(q\) contracts receiving a score of at least \(t-1\). If no such \(t\) exists, then \(v\) picks \(t=0\). The choice function selects the contracts from \(X\) having a score of at least \(t\). For example, if \(v\) is offered four contracts with scores of three, two, two and one and the quota is \(q=2\), then \(v\) chooses only the best contract with a score of three ( _i.e._, \(t=3\)). 7. _Permissive (L-scoring) choice function_: Agent \(v\) has a quota, \(q\), but it might choose more than \(q\) contracts. Namely, \(v\) chooses the best \(k_{2}\geq q\) contracts in a way that it chooses the best \(k\leq q\) using the previous H-scoring method (with score limit \(t\)), and if \(k<q\), then \(v\) adds the next group of applicants with score \(t-1\). If the H-scoring function chooses exactly \(k=q\) applicants, then \(v\) keeps them and does not add new students. Score-stability defined with this choice function was called _\(L\)-stable_ in [9]. In the previous example, \(v\) would set the score limit at two and pick three applicants with scores of three, two and two. 8. The _weighted scoring choice function_ is similar to the H-scoring choice function, except every contract also has a cost. Agent \(v\) has a budget, \(k\), instead of a quota, \(q\). For a given \(X\) set of contracts, \(v\) determines \(t\) in such a way that the total cost of contracts having a score of at least \(t\) is not more than \(k\), but the total cost of contracts having a score of at least \(t-1\) is more than \(k\). If no such \(t\) exists, then \(t=0\). Now, \(v\) chooses those contracts from \(X\) that have a score of at least \(t\). For example, if \(v\) has four applicants according to the table below:
and the budget is \(10\), then \(v\) chooses only \(a_{1}\). (Agent \(v\) cannot skip some applicants and choose a cost of \(9+1\).) 9. _Strict hierarchical choice function_: Agent \(v\) has a linear preference list over contracts, and there is a downward closed set system, \(\mathcal{I}\), of subsets of \(E(v)\) (that is, if \(A\in\mathcal{I},B\subseteq A\), then \(B\in\mathcal{I}\)). Let \(k\) be the greatest number, such that the set of \(k\) best contracts of set \(X\) belongs to \(\mathcal{I}\). Now, \(C(X)\) is the set of these \(k\) best applicants. 10.