Decentralized job matching

This paper studies a multi-stage decentralized matching model where firms sequentially propose their (unique) positions to workers. At each stage workers sequentially decide which offer to accept (if any). A firm whose offer has been declined may make an offer to another worker in the next stage. The game stops when all firms either have been matched to a worker or have already made unsuccessful offers to any worker remaining in the market. We show that there is a unique subgame-perfect equilibrium outcome, the worker-optimal matching. Firms in this game have a weakly dominant strategy, which consists of making offers in the same order as given by their preferences. When workers play simultaneously any stable matching can be obtained as an equilibrium outcome, but an unstable matching can obtain in equilibrium.     

Instability of matchings in decentralized markets with various preference structures

In any two-sided matching market, a stable matching can be found by a central agency using the deferred acceptance procedure of Gale and Shapley. But if the market is decentralized and information is incomplete then stability of the ensuing matching is not to be expected. Despite the prevalence of such matching situations, and the importance of stability, little theory exists concerning instability. We discuss various measures of instability and analyze how they interact with the structure of the underlying preferences. Our main result is that even the outcome of decentralized matching with incomplete information can be expected to be “almost stable” under reasonable assumptions.     

Paths to stability in two-sided matching under uncertainty

We consider one-to-one matching problems under two modalities of uncertainty in which types are assigned to agents either with or without replacement. Individuals have preferences over the possible types of the agents from the opposite market side and initially know the ‘name’ but not the ‘type’ of their potential partners. In this context, learning occurs via matching and using Bayes’ rule. We introduce the notion of a stable and consistent outcome, and show how the interaction between blocking and learning behavior shapes the existence of paths to stability in each of these two uncertainty environments. Existence of stable and consistent outcomes then follows as a side result.     

On the equivalence of two competing affirmative actions in school choice

This note analyzes the outcome equivalence conditions of two popular affirmative action policies, majority quota and minority reserve, under the student optimal stable mechanism. These two affirmative actions generate an identical matching outcome, if the market either is effectively competitive or contains a sufficiently large number of schools.     

The stability of the equilibrium outcomes in the admission games induced by stable matching rules

A stable matching rule is used as the outcome function for the Admission game where colleges behave straightforwardly and the students’ strategies are given by their preferences over the colleges. We show that the college-optimal stable matching rule implements the set of stable matchings via the Nash equilibrium (NE) concept. For any other stable matching rule the strategic behavior of the students may lead to outcomes that are not stable under the true preferences. We then introduce uncertainty about the matching selected and prove that the natural solution concept is that of NE in the strong sense. A general result shows that the random stable matching rule, as well as any stable matching rule, implements the set of stable matchings via NE in the strong sense. Precise answers are given to the strategic questions raised.     

Optimal Pair Matching With Two Control Groups

In an effort to detect hidden biases due to failure to control for an unobserved covariate, some observational or nonrandomized studies include two control groups selected to systematically vary the unobserved covariate. Comparisons of the treated group and two control groups must, of course, control for imbalances in observed covariates. Using the three groups, we form pairs optimally matched for observed covariates—that is, we optimally construct from observational data an incomplete block design. The incomplete block design may use all available data, or it may use data selectively to produce a balanced incomplete block design, or it may be the basis for constructing a matched sample when expensive outcome information is to be collected only for sampled individuals. The problem of optimal pair matching with two control groups is shown by a series of transformations to be equivalent to a particular form of optimal nonbipartite matching, a problem for which polynomial time algorithms exist. In our examples, we implement the procedure using a nonbipartite matching algorithm due to Derigs. We illustrate the method with data from an observational study of the employment effects of the minimum wage.     

Comparison of Multivariate Matching Methods: Structures,Distances, and Algorithms

Abstract

A comparison and evaluation is made of recent proposals for multivariate matched sampling in observational studies, where the following three questions are answered: (1) Algorithms: In current statistical practice, matched samples are formed using “nearest available” matching, a greedy algorithm. Greedy matching does not minimize the total distance within matched pairs, though good algorithms exist for optimal matching that do minimize the total distance. How much better is optimal matching than greedy matching? We find that optimal matching is sometimes noticeably better than greedy matching in the sense of producing closely matched pairs, sometimes only marginally better, but it is no better than greedy matching in the sense of producing balanced matched samples. (2) Structures: In common practice, treated units are matched to one control, called pair matching or 1–1 matching, or treated units are matched to two controls, called 1–2 matching, and so on. It is known, however, that the optimal structure is a full matching in which a treated unit may have one or more controls or a control may have one or more treated units. Optimal 1 — k matching is compared to optimal full matching, finding that optimal full matching is often much better. (3) Distances: Matching involves defining a distance between covariate vectors, and several such distances exist. Three recent proposals are compared. Practical advice is summarized in a final section.     

Probabilistic stable rules and Nash equilibrium in two-sided matching problems

We study many-to-many matching with substitutable and cardinally monotonic preferences. We analyze stochastic dominance (sd) Nash equilibria of the game induced by any probabilistic stable matching rule. We show that a unique match is obtained as the outcome of each sd-Nash equilibrium. Furthermore, individual-rationality with respect to the true preferences is a necessary and sufficient condition for an equilibrium outcome. In the many-to-one framework, the outcome of each equilibrium in which firms behave truthfully is stable for the true preferences. In the many-to-many framework, we identify an equilibrium in which firms behave truthfully and yet the equilibrium outcome is not stable for the true preferences. However, each stable match for the true preferences can be achieved as the outcome of such equilibrium.     

Fuzzy play,matching devices and coordination failures

We revisit n-player coordination games with Pareto-ranked Nash equilibria. As a novelty, we introduce fuzzy play and a matching device. By fuzzy play we mean that each player does not choose which pure strategy to play, but instead chooses a nonempty subset of his strategy set that he submits to the matching device. The matching device is a very simple one. It randomly selects a match if possible, and it selects randomly some strategy belonging to the strategy set sent by each player otherwise. That is, it does not impose that the best alternatives are matched. Using the concepts of perfect Nash equilibrium and of trembling-hand perfect rationalizability, we show that players coordinate directly on the Pareto optimal outcome. This implies that they neither use the option of fuzzy play, nor make use of the matching device.We thank an anonymous referee and an Associate Editor for valuable comments. Jean-Jacques Herings would like to thank the Netherlands Organisation for Scientific Research (NWO) for financial support. Vincent Vannetelbosch is Chercheur Qualifié at the Fonds National de la Recherche Scientifique. The research of Ana Mauleon has been made possible by a fellowship of the Fonds Européen du Développement Economique Régional (FEDER). Financial support from the Belgian French Communitys program Action de Recherches Concertée 99/04-235 (IRES, Université catholique de Louvain) is gratefully acknowledged.     

Perfect matchings in hexagonal systems

A simple algorithm is developed which allows to decide whether or not a given hexagonal system has a perfect matching (and to find such a matching). This decision is also of chemical relevance since a hexagonal system is the skeleton of a benzenoid hydrocarbon molecule if and only if it has a perfect matching. Dedicated to Paul Erdős on his seventieth birthday     

Asymmetric equilibria in dynamic two-sided matching markets with independent preferences

A fundamental fact in two-sided matching is that if a market allows several stable outcomes, then one is optimal for all men in the sense that no man would prefer another stable outcome. We study a related phenomenon of asymmetric equilibria in a dynamic market where agents enter and search for a mate for at most n rounds before exiting again. Assuming independent preferences, we find that this game has multiple equilibria, some of which are highly asymmetric between sexes. We also investigate how the set of equilibria depends on a sex difference in the outside option of not being mated at all.     

匹配最大根小于等于2的图的匹配等价

给出了十六个匹配等价桥,证明了两个匹配最大根小于等于2的图匹配等价当且仅当它们之间可以由这十六个匹配等价桥进行等价转换,完整地刻画了这些图的补图的匹配等价图类,找到了这些图和它们的补图中的所有匹配唯一图．     

A maximum stable matching for the roommates problem

The stable roommates problem is that of matchingn people inton/2 disjoint pairs so that no two persons, who are not paired together, both prefer each other to their respective mates under the matching. Such a matching is called a complete stable matching. It is known that a complete stable matching may not exist. Irving proposed anO(n ²) algorithm that would find one complete stable matching if there is one, or would report that none exists. Since there may not exist any complete stable matching, it is natural to consider the problem of finding a maximum stable matching, i.e., a maximum number of disjoint pairs of persons such that these pairs are stable among themselves. In this paper, we present anO(n ²) algorithm, which is a modified version of Irving's algorithm, that finds a maximum stable matching.This research was supported by National Science Council of Republic of China under grant NSC 79-0408-E009-04.     

Social norms and choice: a weak folk theorem for repeated matching games

A folk theorem which holds for all repeated matching games is established. The folk theorem holds any time the stage game payoffs of any two players are not affinely equivalent. The result is independent of population size and matching rule—including rules that depend on players choices or the history of play.      

Random paths to pairwise stability in many-to-many matching problems: a study on market equilibration

This paper considers a decentralized process in many-to-many matching problems. We show that if agents on one side of the market have substitutable preferences and those on the other side have responsive preferences, then, from an arbitrary matching, there exists a finite path of matchings such that each matching on the path is formed by satisfying a blocking individual or a blocking pair for the previous matching, and the final matching is pairwise-stable. This implies that an associated stochastic process converges to a pairwise-stable matching in finite time with probability one, if each blocking individual or pair is satisfied with a positive probability at each period along the process.     

A Linear Programming Approach to Designing an Optimum Tax Package

This paper describes the application of linear programming to the problem of designing an optimum tax package to make the 1967 British devaluation work. The objective was to show how to release sufficient domestic resources so as to meet the extra exports demanded as a result of devaluation. It is important to realize that what matters is not the total amount of resources taken from the consumers, but the matching of these resources with the exportable goods demanded overseas. If this matching is not obtained, the tax policy may only cut down domestic production and employment without solving the balance-of-payments problem. The linear programming technique proved useful in tackling this problem of matching of demand and supply in particular directions. The particular tax package derived is heavy on those goods which have good export potential and/or high import content, and it avoids imposing taxes which will reduce domestic consumption without helping the balance of payments.     

A general two-sided matching market with discrete concave utility functions

In the theory of two-sided matching markets there are two standard models: (i) the marriage model due to Gale and Shapley and (ii) the assignment model due to Shapley and Shubik. Recently, Eriksson and Karlander introduced a hybrid model, which was further generalized by Sotomayor. In this paper, we propose a common generalization of these models by utilizing the framework of discrete convex analysis introduced by Murota, and verify the existence of a pairwise-stable outcome in our general model.     

非线性系统的一种模糊滑模变结构控制方案

基于HM模型对非线性系统进行描述，采用Lyapunov方法设计出确保系统全局渐近稳定的滑模变结构控制器。对满足匹配条件和不满足匹配条件的情况均适用。并用一级倒立摆系统进行仿真验证。成功的将变结构控制应用于非线性控制系统中。     

Bipartite graphs with every matching in a cycle

We give sufficient Ore-type conditions for a balanced bipartite graph to contain every matching in a hamiltonian cycle or a cycle not necessarily hamiltonian. Moreover, for the hamiltonian case we prove that the condition is almost best possible.     

最大匹配图的围长

将一个图的所有最大匹配作为顶点集,称两个最大匹配相邻,若它们之一通过交换一条边得到另一个,由引所得图为该图的最大匹配图。本文研究了最大匹配图的围长,从而给出了最大匹配图是树或完全图的条件。