___

• Proof
• Consider the case when La= Ea=∅, for all a ∈ I . By Lemma3.7(i), pijdecreases for each
• (i, j)∈ Ua\{La, Ea}, for all a ∈ I . However, p is discrete and pij≥ max{π,
• βji} for each (i, j) ∈ Ua
• αji} for each (i, j) ∈ U , a∈ I .
• 0}, for all a ∈ I . However, p is discrete and pij
• Therefore, pijcan be decreased only by a finite number of times.
• Next we consider the case when La̸= ∅, or Ea̸= ∅. In either case, E reduces at Step 3. By Lemma
• 0̸= ∅. In either case, E reduces at Step 3. By Lemma
• 7(iv), in each iteration of the Job Allocation, E decreases or remains the same, and therefore this case is
• possible at most|E| times. This completes the proof. ✷
• Concluding remarks
• We have presented a job market in which we have taken different categories of the workers into account. Each
• firm employs worker according to its eligibility criteria. The preferences of players are represented by increasing
• utility functions. Here we list some important points about the model and Job Allocation: 1. The existence of a pairwise stable outcome is guaranteed in our model. The salary in this model is a
• discrete variable. The marriage model [6] and the Ali and Farooq model [1] are special cases of this
• model. A possible extension of the model is to consider salary as a continuous variable.
• By Lemma3.8, we have that p
• is the maximum integer in [πij, πij] for which νji(−p) > ra, a∈ I , for j, a∈ I , for
• some (i, j)∈ E . Since valuations are linearly increasing, the matching will be worker-optimal. It is possible
• to define an algorithm by starting from the lowest possible salary and then increasing it accordingly. This
• type of algorithm will yield firm-optimal stable outcomes.
• The complexity of the Job Allocation is not polynomial as it depends on the length of [πij, πij] for each (i, j)∈ E .
• Ali Y, Farooq R. Pairwise stability in a two-sided matching market with indivisible goods and money. J Oper Res Soc Jpn 2011; 54: 1–11.
• Ali Y, Farooq R. Existence of stable outcome for a job market with linear valuations and possibly bounded salaries. Pac J Optim 2011; 7: 531–550.
• Eriksson K, Karlander J. Stable matching in a common generalization of the marriage and assignment models.
• Discrete Math 2000; 217: 135–156.
• Farooq R. A polynomial-time algorithm for a stable matching problem with linear valuations and bounded side
• payments. Jpn J Ind Appl Math 2008; 25: 83–98.
• Femenia D, Mari M, Neme A, Oviedo J. Stable solutions on matching models with quota restriction. Int Game
• Theor Rev 2011; 13: 159–179.
• Gale D, Shapley LS. College admissions and the stability of marriage. Amer Math Monthly 1962; 69: 9–15.
• Karakaya M. Graduate admission problem with quota and budget constraints. MSc, Bilkent University, Ankara, Turkey, 2003.
• Karakaya M. On stability and efficiency in different economic environments. PhD, Bilkent University, Ankara, Turkey, 2011.
• Kelso JAS, Crawford VP. Job matching coalition formation, and gross substitution. Econometrica 1982; 50: 1483– 1504.
• Roth AE. Stability and polarization of interests in job matching. Econometrica 1984; 52: 47–57.
• Shapley LS, Shubik M. The assignment game I: The core. Internat J Game Theory 1972; 1: 111–130.
• Sotomayor M. Three remarks on the many-to-many stable matching problem. Math Social Sci 1999; 38: 55–70.
• Sotomayor M. Existence of stable outcomes and the lattice property for a unified matching market. Math Social
• Sci 2000; 39: 119–132.