We consider a job market in which preferences of players are represented by linearly increasing valuations. The set of players is divided into two disjoint subsets: A set of workers and a set of firms. The set of workers is further divided into subsets, which represent different categories or classes in everyday life. | Turk J Math (2015) 39: 427 – 438 ¨ ITAK ˙ c TUB ⃝ Turkish Journal of Mathematics doi: Research Article Stability in a job market with linearly increasing valuations and quota system Yasir ALI∗ College of Electrical and Mechanical Engineering, National University of Sciences and Technology Rawalpindi, Pakistan Received: • Accepted/Published Online: • Printed: Abstract: We consider a job market in which preferences of players are represented by linearly increasing valuations. The set of players is divided into two disjoint subsets: a set of workers and a set of firms. The set of workers is further divided into subsets, which represent different categories or classes in everyday life. We consider that firms have vacant posts for all such categories. Each worker wants a job for a category to which he/she belongs. Firms have freedom to hire more than one worker from any category. A worker can work in only one category for at most one firm. We prove the existence of a stable outcome for such a market. The college admission problem by Gale and Shapley is a special case of our model. Key words: Stable marriage, pairwise stability, job allocation, linear valuation, quota system 1. Introduction Most theoretical work on bipartite matching traces its history to the papers of Gale and Shapley [6] and Shapley and Shubik [11]. In bipartite matching, we have two disjoint sets, F and W . The main purpose is to match the elements of F to the elements of W . Matching between elements of the same set is forbidden in bipartite matching markets. For convenience, we use the term “player” for an element in F ∪ W . If we match exactly one player of set F to exactly one player of the set W , then the matching is called “one-to-one” matching. If a group of players of one set is matched to one player of the other set, such a matching is called “many-to-one” matching. If there is freedom for .
