Project topics and materials
Get Complete Project Material File(s) Now! »
Responsive Preferences over Groups of Students and Group Stability
The previous results have shown that there exists stable matchings in college admission problems with preferences over individuals on both students’ and firms’ sides. We now consider the more complex problem where every college c 2 C has preferences P# c as already defined. In order to exhibit the difficulty raised by the introduction of groups, consider the previous DAA with students proposing. Assume that a college c chooses according to P# c its most preferred subset of students
among those admitted and those proposing according to P# c . Following this choice, a student (potentially, many students) may be rejected because of low complementarities but may be regretted in a subsequent round because of new proposals that make the rejected student now belong to c’s most preferred subset. In such case, both c and the rejected students would be matched with each others.
This opens the way toward the introduction of new stability concepts where groups matter and the introduction of assumptions on the structure of the preferences that may induce regretfree deferred acceptance-like processes and guarantee the existence of stablematchings. A natural way of constructing any college’s preferences over groups of students is to compare the groups differing by one student based on the preferences over the individuals. Such preferences over groups are called responsive preferences. We have the following formal definition, Definition 33 ([2], pp.128). The preference relation P# c over sets of students is responsive to the preferences Pc over individual students if, whenever μ0(c) = μ(c)[{s}\{æ} for æ in μ(c), then c prefers μ0(c) to μ(c) under P# c if and only if c prefers s to æ under Pc .
We now define two stability solution concepts, that involve subsets of players bigger than just pairs. These stabilities allow not only individuals or pairs (of the form (man,woman) or (student, college)) to block a matching but subsets possibly composed of several men and women or students and colleges that can re-organize the associations so as to benefit from the deviation. Each of these stability concept is differentiated from the other through the beneficiaries of the deviation and their enforcement power. The first solution concept has actually already been defined, it is the core. In the framework of many-to-one markets, we have the following definition of domination:
Definition 34 ([2], pp.166). A matching μ0 dominates another matching μ via a coalition C contained in C [S if for all students s and colleges c in C,
• If c0 = μ0(s) then c0 2 C
• If s0 2 μ0(c) then s0 2 C
• μ0(s)¬s μ(s)
• μ0(s)¬s μ(s)
Remember that the core is the set of undominated matching.
The Firms and Workers Model: Choice Functions, Subtitutability and Salaries
In this section, we introduce the substitutability property, another sufficient condition for the existence of stable matchings (but weaker that the responsive property). Furthermore, we introduce the choice functions formalism that will be used in the general models ofmatching with contracts. Consider the previous college-admission problem, turn the students into workers from a set of workers W = {w1, . . . ,wm}, the colleges into firms from a set F = {f1, . . . , fn} and assume that each pair (firm,worker) is characterized by a salary to be paid by the firm to the worker. This setting is known in the name of the firms and workers problem. For the sake of homogeneity w.r.t. [2] and simplicity, assume that any firm has quota m. As in the college admission problem, a matching μ is a function from the set F [W into the set of all subsets of F [W such that
1. |μ(w)| = 1 for every worker w and μ(w) = w if μ(w) 62F;
2. |μ( f )|Σm for every firm f and μ( f ) =; if f isn’t matched to any workers;
3. μ(w) = f if and only if w is in μ( f ).
The analytical formalism developed for themarriage and college-admission problems is based on order relations called preferences that are used to define the models and concepts or show the results. The notations were defined in terms of classical order-relations such as ¬i or ∫i . In the 1980’s, this formalism has been slightly changed for an alternative one based on choice functions that allow to define a new condition, called substitutability, in a convenient way. This notation is used in the most general matching models such as matching with contracts [4] and matching with contracts and externalities [5]. Nevertheless, the classical notation is not left aside and keep on being used when adapted to the problem (as an example of a recent paper using the order-based notation see [6]).
Complementarities and Peer Effects
As explained in the previous section, the substitutability property of the firms’ choice functions is a sufficient condition for the existence of stable matchings in matching games with preferences over groups on the firms’ side. The substitutability property induces that the workers are considered as substitutes rather that complements by the firms. In other words, either there are no complementarities or they are so weak that they cannot turn rejections into choices.
There are many settings and two-sided markets where such assumptions cannot hold and the workers can be considered by the firms as complements.
Table of contents :
Résumé détaillé en français
1 Introduction
2 Cooperation and Bargainings
2.1 Cooperation, Negotiation and Arbitration
2.2 The Nash Bargaining Solution
2.3 The Generalized Nash Bargaining
2.4 References
3 StableMatchings
3.1 StableMatchings
3.2 The StableMarriage Problem
3.3 The College Admission Problem
3.4 The Firms andWorkersModel: Choice Functions, Subtitutability and Salaries
3.5 Complementarities and Peer Effects
3.6 Matching with Contracts and Externalities
3.7 References
4 Nash Bargaining for Resource Allocation inWiFi
4.1 Competition for Resource Allocation in Networks
4.2 WiFi
4.3 WiFi as a Nash Bargaining
4.4 Conclusion
4.5 References
5 A Cooperative Game Theoretic Analysis ofWiFi
5.1 Introduction
5.2 System model
5.3 Matching Games Formulation
5.4 Existence of Core StableMatchings in the Game and Unemployment
5.5 Mechanism for controlledmatching game
5.6 Numerical Results
5.7 Conclusion
5.8 References
5.9 Appendix: Two examples of control of incentives in games
5.10 Appendix: Proofs
5.11 Appendix: Interpretation of BDAA in the economic framework
5.12 Appendix: Example
6 Video Caching and an Enumerative Cliques-Based Algorithm
6.1 Introduction
6.2 RelatedWorks
6.3 Contributions
6.4 Potential Coalition Games and Video Caching
6.5 An Anytime Centralized Enumerative Algorithm
6.6 Some elements about the complexity
6.7 Example
6.8 Conclusion
6.9 References
7 Fear of Ruin and Concavity Conditions in Coalition Games with Generalized Æ-Fair Resource Allocation
7.1 Introduction
7.2 Contributions
7.3 Model
7.4 Motivating Examples
7.5 The Generalized Æ-fair Allocation: Stability, Risks and Behaviors
7.6 Risks andMeasures of Aversion
7.7 Conclusion
7.8 References
7.9 Appendix: Proof of Proposition
8 Matching Games and Crowdsourcing
8.1 Introduction
8.2 Crowdsourcing System with Scheduling Constraints
8.3 Matching with Contracts, Externalities and Scheduling Constraints
8.4 The Crowdsourcing Problem in Normal form
8.5 The Crowdsourcing Problem in Extensive Form
8.6 Conclusion
8.7 References
8.8 Appendix: Insufficiency of Existing Solutions
8.9 Appendix: Proofs
8.10 Appendix: Alternative Stabilities
8.11 Appendix: Player-SpecificMatroid Congestion Games with Priorities
9 Open Questions
9.1 Nash Bargaining,Markov Chains and Relative Entropy
9.2 Strategic Information Transmission and Recommendations Systems
9.3 References
10 Conclusion
11 Publications
11.1 Journals
11.2 Conferences with review committee
11.3 Talks
