ISSN:
2164-6066
eISSN:
2164-6074
Journal of Dynamics & Games
March & April 2015 , Volume 2 , Issue 3&4
Special issues on Matching: Theory and Applications,
dedicated to Marilda Sotomayor on the occasion of her 70th birthday
Select all articles
Export/Reference:
2015, 2(3&4): i-i
doi: 10.3934/jdg.201534i
+[Abstract](1780)
+[PDF](95.5KB)
Abstract:
The Journal of Dynamics and Games (JDG) is pleased to do publish these two special issues on Matching: Theory and Applications, dedicated to Marilda Sotomayor on the occasion of her 70th birthday.
Marilda Sotomayor's outstanding and innovative research in the field of matching models has made her renowned. In the paper On Marilda Sotomayor's extraordinary contribution to matching theory, published in these JDG special issues, Danilo Coelho and David Pérez-Castrillo briefly report on Marilda's outstanding contributions. In the paper, A survey on assignment markets, published in these JDG special issues, Marina Núñez and Carles Rafels do a survey on assignment games emphasizing the relevance in this research area of the book Two-sided Matching: A Study in Game-Theoretic Modeling and Analysis, authored by Alvin Roth and Marilda Sotomayor. In the paper, Why do stable clearinghouses work so well? -- small sets of stable matchings in typical environments, and the limits on manipulation theorem of Demange, Gale and Sotomayor, published in these JDG special issues, Alvin Roth explains how an important theorem from Marilda's early work helps us understand today why stable matching clearinghouses work as well as they do.
In these JDG special issues, scientists from all over the world share their latest insights and important results, including the exploration of emerging and current cutting-edge theories and methods in the field.
We are very thankful to the invited editors, Ahmet Alkan, David Pérez Castrillo, John Wooders and, specially, Myrna Wooders for having prepared a premium work of a remarkable scientific and social value!
The Journal of Dynamics and Games (JDG) is pleased to do publish these two special issues on Matching: Theory and Applications, dedicated to Marilda Sotomayor on the occasion of her 70th birthday.
Marilda Sotomayor's outstanding and innovative research in the field of matching models has made her renowned. In the paper On Marilda Sotomayor's extraordinary contribution to matching theory, published in these JDG special issues, Danilo Coelho and David Pérez-Castrillo briefly report on Marilda's outstanding contributions. In the paper, A survey on assignment markets, published in these JDG special issues, Marina Núñez and Carles Rafels do a survey on assignment games emphasizing the relevance in this research area of the book Two-sided Matching: A Study in Game-Theoretic Modeling and Analysis, authored by Alvin Roth and Marilda Sotomayor. In the paper, Why do stable clearinghouses work so well? -- small sets of stable matchings in typical environments, and the limits on manipulation theorem of Demange, Gale and Sotomayor, published in these JDG special issues, Alvin Roth explains how an important theorem from Marilda's early work helps us understand today why stable matching clearinghouses work as well as they do.
In these JDG special issues, scientists from all over the world share their latest insights and important results, including the exploration of emerging and current cutting-edge theories and methods in the field.
We are very thankful to the invited editors, Ahmet Alkan, David Pérez Castrillo, John Wooders and, specially, Myrna Wooders for having prepared a premium work of a remarkable scientific and social value!
2015, 2(3&4): 201-206
doi: 10.3934/jdg.2015001
+[Abstract](2374)
+[PDF](220.2KB)
Abstract:
We report on Marilda Sotomayor's extraordinay contribution to MatchingTheory on the occasion of her 70th anniversary.
We report on Marilda Sotomayor's extraordinay contribution to MatchingTheory on the occasion of her 70th anniversary.
2015, 2(3&4): 207-225
doi: 10.3934/jdg.2015002
+[Abstract](2112)
+[PDF](420.4KB)
Abstract:
This paper studies economies with indivisible goods and budget-constrained agents with unit-demand who act as both sellers and buyers. In prior literature on the existence of competitive equilibrium, it is assumed the indispensability of money, which in turn implies that budgets constraints are irrelevant. We introduce a new condition, Money Scarcity (MS), that considers agents' budget constraints and ensures the existence of equilibrium. Moreover, an extended version of Gale's top trading cycles algorithm is presented, and it is shown that under MS this mechanism is strategy-proof. Finally, we prove that this mechanism is the unique mechanism that minimizes money transactions at equilibrium.
This paper studies economies with indivisible goods and budget-constrained agents with unit-demand who act as both sellers and buyers. In prior literature on the existence of competitive equilibrium, it is assumed the indispensability of money, which in turn implies that budgets constraints are irrelevant. We introduce a new condition, Money Scarcity (MS), that considers agents' budget constraints and ensures the existence of equilibrium. Moreover, an extended version of Gale's top trading cycles algorithm is presented, and it is shown that under MS this mechanism is strategy-proof. Finally, we prove that this mechanism is the unique mechanism that minimizes money transactions at equilibrium.
2015, 2(3&4): 227-256
doi: 10.3934/jdg.2015003
+[Abstract](2359)
+[PDF](520.2KB)
Abstract:
The assignment game is a two-sided market, say buyers and sellers, where demand and supply are unitary and utility is transferable by means of prices. This survey is structured in three parts: a first part, from the introduction of the assignment game by Shapley and Shubik (1972) until the publication of the book of Roth and Sotomayor (1990), focused on the notion of core; the subsequent investigations that broaden the scope to other notions of solution for these markets; and its extensions to assignment markets with multiple sides or multiple partnership. These extended two-sided assignment markets, that allow for multiple partnership, better represent the situation in a labour market or an auction.
The assignment game is a two-sided market, say buyers and sellers, where demand and supply are unitary and utility is transferable by means of prices. This survey is structured in three parts: a first part, from the introduction of the assignment game by Shapley and Shubik (1972) until the publication of the book of Roth and Sotomayor (1990), focused on the notion of core; the subsequent investigations that broaden the scope to other notions of solution for these markets; and its extensions to assignment markets with multiple sides or multiple partnership. These extended two-sided assignment markets, that allow for multiple partnership, better represent the situation in a labour market or an auction.
2015, 2(3&4): 257-287
doi: 10.3934/jdg.2015004
+[Abstract](3220)
+[PDF](538.5KB)
Abstract:
We study a labor market with finitely many heterogeneous workers and firms to illustrate the decentralized (myopic) blocking dynamics in two-sided one-to-one matching markets with continuous side payments (assignment problems, Shapley and Shubik [24]).
Assuming individual rationality, a labor market is unstable if there is at least one blocking pair, that is, a worker and a firm who would prefer to be matched to each other in order to obtain higher payoffs than the payoffs they obtain by being matched to their current partners. A blocking path is a sequence of outcomes (specifying matchings and payoffs) such that each outcome is obtained from the previous one by satisfying a blocking pair (i.e., by matching the two blocking agents and assigning new payoffs to them that are higher than the ones they received before).
We are interested in the question if starting from any (unstable) individually rational outcome, there always exists a blocking path that will lead to a stable outcome. In contrast to discrete versions of the model (i.e., for marriage markets, one-to-one matching, or discretized assignment problems), the existence of blocking paths to stability cannot always be guaranteed. We identify a necessary and sufficient condition for an assignment problem (the existence of a stable outcome such that all matched agents receive positive payoffs) to guarantee the existence of paths to stability and show how to construct such a path whenever this is possible.
We study a labor market with finitely many heterogeneous workers and firms to illustrate the decentralized (myopic) blocking dynamics in two-sided one-to-one matching markets with continuous side payments (assignment problems, Shapley and Shubik [24]).
Assuming individual rationality, a labor market is unstable if there is at least one blocking pair, that is, a worker and a firm who would prefer to be matched to each other in order to obtain higher payoffs than the payoffs they obtain by being matched to their current partners. A blocking path is a sequence of outcomes (specifying matchings and payoffs) such that each outcome is obtained from the previous one by satisfying a blocking pair (i.e., by matching the two blocking agents and assigning new payoffs to them that are higher than the ones they received before).
We are interested in the question if starting from any (unstable) individually rational outcome, there always exists a blocking path that will lead to a stable outcome. In contrast to discrete versions of the model (i.e., for marriage markets, one-to-one matching, or discretized assignment problems), the existence of blocking paths to stability cannot always be guaranteed. We identify a necessary and sufficient condition for an assignment problem (the existence of a stable outcome such that all matched agents receive positive payoffs) to guarantee the existence of paths to stability and show how to construct such a path whenever this is possible.
2015, 2(3&4): 289-302
doi: 10.3934/jdg.2015005
+[Abstract](2113)
+[PDF](328.1KB)
Abstract:
For a model of many-to-many matching with contracts, we develop an algorithmto obtain stable allocations from sets of contracts satisfying asignificantly less restrictive condition. Then, we build the optimal stableallocations through a simple process, which is very similar to thepioneering Gale and Shapley's one. Also, we prove that the set of stable allocations has latticestructure with respect to Blair's partial orderings.
For a model of many-to-many matching with contracts, we develop an algorithmto obtain stable allocations from sets of contracts satisfying asignificantly less restrictive condition. Then, we build the optimal stableallocations through a simple process, which is very similar to thepioneering Gale and Shapley's one. Also, we prove that the set of stable allocations has latticestructure with respect to Blair's partial orderings.
2015, 2(3&4): 303-320
doi: 10.3934/jdg.2015007
+[Abstract](2438)
+[PDF](386.3KB)
Abstract:
We study a finite decision model where the utility function is an additive combination of a personal valuation component and an interaction component. Individuals are characterized according to these two components (their valuation type and externality type), and also according to their crowding type (how they influence others). We study how positive externalities lead to type symmetries in the set of Nash equilibria, while negative externalities allow the existence of equilibria that are not type-symmetric. In particular, we show that positive externalities lead to equilibria having a unique partition into a minimum number of societies (similar individuals using the same strategy, see [27]); and negative externalities lead to equilibria with multiple societal partitions, some with the maximum number of societies.
We study a finite decision model where the utility function is an additive combination of a personal valuation component and an interaction component. Individuals are characterized according to these two components (their valuation type and externality type), and also according to their crowding type (how they influence others). We study how positive externalities lead to type symmetries in the set of Nash equilibria, while negative externalities allow the existence of equilibria that are not type-symmetric. In particular, we show that positive externalities lead to equilibria having a unique partition into a minimum number of societies (similar individuals using the same strategy, see [27]); and negative externalities lead to equilibria with multiple societal partitions, some with the maximum number of societies.
2015, 2(3&4): 321-330
doi: 10.3934/jdg.2015008
+[Abstract](4297)
+[PDF](356.5KB)
Abstract:
In two-sided matching markets in which some doctors form couples, a stable matching does not necessarily exist.Wecharacterize the set of stable matchings as the fixed points of a function that is reminiscent of a tâtonnement process. Then we show that this function ismonotone decreasing with respect to a certain partialorder. Based on these results,wepresent an algorithm that finds all the stable matchings wheneverone exists, and otherwise demonstrates that there is no stable matching.
In two-sided matching markets in which some doctors form couples, a stable matching does not necessarily exist.Wecharacterize the set of stable matchings as the fixed points of a function that is reminiscent of a tâtonnement process. Then we show that this function ismonotone decreasing with respect to a certain partialorder. Based on these results,wepresent an algorithm that finds all the stable matchings wheneverone exists, and otherwise demonstrates that there is no stable matching.
2015, 2(3&4): 331-340
doi: 10.3934/jdg.2015009
+[Abstract](2012)
+[PDF](420.3KB)
Abstract:
Marilda Sotomayor is one of the pioneers of the theory of stable matching. She has published many important results, including some which are fundamental to subsequent developments. I will concentrate on one fundamental theorem, which today allows us to understand better why stable clearinghouses work so well. Demange, Gale and Sotomayor (1987)[16] proved a theorem which implies that when the set of stable matchings is small, participants in a stable clearinghouse will seldom be able to profit from strategically manipulating their preferences. More recent results show (empirically and theoretically) that the set of stable matchings can be expected to be small in typical applications. Therefore, reporting true preferences will be rewarded in clearinghouses that produce stable matchings in terms of stated preferences, and so there is a reason that such clearinghouses elicit sufficiently good preference data to produce matchings that are stable with respect to true preferences.
Marilda Sotomayor is one of the pioneers of the theory of stable matching. She has published many important results, including some which are fundamental to subsequent developments. I will concentrate on one fundamental theorem, which today allows us to understand better why stable clearinghouses work so well. Demange, Gale and Sotomayor (1987)[16] proved a theorem which implies that when the set of stable matchings is small, participants in a stable clearinghouse will seldom be able to profit from strategically manipulating their preferences. More recent results show (empirically and theoretically) that the set of stable matchings can be expected to be small in typical applications. Therefore, reporting true preferences will be rewarded in clearinghouses that produce stable matchings in terms of stated preferences, and so there is a reason that such clearinghouses elicit sufficiently good preference data to produce matchings that are stable with respect to true preferences.
2015, 2(3&4): 341-361
doi: 10.3934/jdg.2015010
+[Abstract](2221)
+[PDF](527.2KB)
Abstract:
We present a dynamic model of club formation in a society of identicalpeople. Coalitions consisting of members of the same club can form for oneperiod and coalition members can jointly deviate. The dynamic process isdescribed by a Markov chain defined by myopic optimization on the part ofcoalitions. We define a Nash club equilibrium (NCE) as a strategy profilethat is immune to such coalitional deviations. For single-peakedpreferences, we show that, if one exists, the process will converge to a NCEprofile with probability one. NCE is unique up to a renaming of players andlocations. Further, NCE corresponds to strong Nash equilibrium in the clubformation game. Finally, we deal with the case where NCE fails to exist.When the population size is not an integer multiple of an optimal club size,there may be `left over' players who prevent the process from `settlingdown'. To treat this case, we define the concept of $k$-remainderNCE, which requires that all but $k$ players are playing a Nash clubequilibrium, where $k$ is defined by the minimal number of left overplayers. We show that the process converges to an ergodic NCE, that is, aset of states consisting only of $k$-remainder NCE and provide somecharacterization of the set of ergodic NCE.
We present a dynamic model of club formation in a society of identicalpeople. Coalitions consisting of members of the same club can form for oneperiod and coalition members can jointly deviate. The dynamic process isdescribed by a Markov chain defined by myopic optimization on the part ofcoalitions. We define a Nash club equilibrium (NCE) as a strategy profilethat is immune to such coalitional deviations. For single-peakedpreferences, we show that, if one exists, the process will converge to a NCEprofile with probability one. NCE is unique up to a renaming of players andlocations. Further, NCE corresponds to strong Nash equilibrium in the clubformation game. Finally, we deal with the case where NCE fails to exist.When the population size is not an integer multiple of an optimal club size,there may be `left over' players who prevent the process from `settlingdown'. To treat this case, we define the concept of $k$-remainderNCE, which requires that all but $k$ players are playing a Nash clubequilibrium, where $k$ is defined by the minimal number of left overplayers. We show that the process converges to an ergodic NCE, that is, aset of states consisting only of $k$-remainder NCE and provide somecharacterization of the set of ergodic NCE.
2015, 2(3&4): 363-382
doi: 10.3934/jdg.2015011
+[Abstract](1773)
+[PDF](1268.8KB)
Abstract:
For the problem of adjudicating conflicting claims, we propose to compromise in the two-claimant case between the proportional and constrained equal awards rules by taking, for each problem, a weighted average of the awards vectors these two rules recommend. We allow the weights to depend on the claims vector, thereby generating a large family of rules. We identify the members of the family that satisfy particular properties.We then ask whether the rules can be extended topopulations of arbitrary sizes by imposing ``consistency": the recommendation made foreach problem should be ``in agreement" with the recommendation madefor each reduced problem that results when some claimants have received theirawards and left. We show that only the proportional and constrained equal awards rules qualify.We also study a dual compromise between the proportional and constrained equal losses rules.
For the problem of adjudicating conflicting claims, we propose to compromise in the two-claimant case between the proportional and constrained equal awards rules by taking, for each problem, a weighted average of the awards vectors these two rules recommend. We allow the weights to depend on the claims vector, thereby generating a large family of rules. We identify the members of the family that satisfy particular properties.We then ask whether the rules can be extended topopulations of arbitrary sizes by imposing ``consistency": the recommendation made foreach problem should be ``in agreement" with the recommendation madefor each reduced problem that results when some claimants have received theirawards and left. We show that only the proportional and constrained equal awards rules qualify.We also study a dual compromise between the proportional and constrained equal losses rules.
Authors
Editors
Referees
Librarians
Email Alert
Add your name and e-mail address to receive news of forthcoming issues of this journal:
[Back to Top]