Canonical monotone decompositions of fractional stable matchings

This paper continues recent work that introduced algebraic methods for studying the stable marriage problem of Gale and Shapley [1962]. Vande Vate [1989] and Rothblum [1992] identified a set of linear inequalities which define a polytope whose extreme points correspond to the stable matchings. Points in this polytope are called fractional stable matchings. Here we identify a unique representation of fractional stable matchings as a convex combination of stable matchings that are arrangeable in a man-decreasing order. We refer to this representation and to a dual one, in terms of woman-decreasing order, as the canonical monotone representations. These representations can be interpreted as time-sharing stable matchings where particular stable matchings are used at each time-instance but the scheduled stable matchings are (occasionally) switched over time. The new representations allow us to extend, in a natural way, the lattice structure of the set of stable matchings to the set of all fractional stable matchings.     

Two-sided coalitional matchings

In a two-sided coalitional matching problem agents on each side of the market simultaneously form coalitions which then are matched to coalitions from the other market side. We assume that each agent has preferences over groups on his own market side and over groups on the opposite market side. These preferences are combined lexicographically as to examine how the existence of core stable partitions on the distinct market sides, the restriction of agents’ preferences over groups to strict orderings, and the extent to which individual preferences respect common rankings shape the existence of core stable coalitional matchings.     

Rank of maximum matchings in a graph

The matching polytope is the convex hull of the incidence vectors of all (not necessarily perfect) matchings of a graphG. We consider here the problem of computing the dimension of the face of this polytope which contains the maximum cardinality matchings ofG and give a good characterization of this quantity, in terms of the cyclomatic number of the graph and families of odd subsets of the nodes which are always nearly perfectly matched by every maximum matching.This is equivalent to finding a maximum number of linearly independent representative vectors of maximum matchings ofG; the size of such a set is called thematching rank ofG. We also give in the last section a way of computing that rank independently of those parameters.Note that this gives us a good lower bound on the number of those matchings.     

Stability of marriage with externalities

In many matching problems, it is natural to consider that agents may have preferences not only over the set of potential partners but also over what other matches occur. Once such externalities are considered, the set of stable matchings will depend on what agents believe will happen if they deviate. In this paper, we introduce endogenously generated beliefs (which depend on the preferences). We introduce a particular notion of endogenous beliefs, called sophisticated expectations, and show that with these beliefs, stable matchings always exist. I would like to thank the editor, William Thomson, two anonymous referees, Kalyan Chatterjee, Federico Echenique, Matthew Jackson, Tarık Kara, Semih Koray, and Manabu Toda for their comments and suggestions. I am very much indebted to Vijay Krishna for his guidance and support.     

Median Stable Matching for College Admissions

We give a simple and concise proof that so-called generalized median stable matchings are well-defined for college admissions problems. Furthermore, we discuss the fairness properties of median stable matchings and conclude with two illustrative examples of college admissions markets, the lattices of stable matchings, and the corresponding generalized median stable matchings.     

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.     

Graphs isomorphic to their maximum matching graphs

The maximum matching graph M（G） of a graph G is a simple graph whose vertices are the maximum matchings of G and where two maximum matchings are adjacent in M（G） if they differ by exactly one edge. In this paper, we prove that if a graph is isomorphic to its maximum matching graph, then every block of the graph is an odd cycle.     

The (conditional) matching preclusion for burnt pancake graphs

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings, and the conditional matching preclusion number of a graph is the minimum number of edges whose deletion leaves a resulting graph with no isolated vertices that has neither perfect matchings nor almost perfect matchings. In this paper, we find these two numbers for the burnt pancake graphs and show that every optimal (conditional) matching preclusion set is trivial.     

Welfare and stability in senior matching markets

We consider matching markets at a senior level, where workers are assigned to firms at an unstable matching—the status-quo—which might not be Pareto efficient. It might also be that none of the matchings Pareto superior to the status-quo are Core stable. We propose two weakenings of Core stability: status-quo stability and weakened stability, and the respective mechanisms which lead any status-quo to matchings meeting the stability requirements above mentioned. The first one is inspired by the Top trading cycle and Deferred Acceptance procedures, the other one belongs to the family of Branch and Bound algorithms. The last procedure finds a core stable matching in many-to-one markets whenever it exists, dispensing with the assumption of substitutability.     

The pareto-stability concept is a natural solution concept for discrete matching markets with indifferences

In a decentralized setting the game-theoretical predictions are that only strong blockings are allowed to rupture the structure of a matching. This paper argues that, under indifferences, also weak blockings should be considered when these blockings come from the grand coalition. This solution concept requires stability plus Pareto optimality. A characterization of the set of Pareto-stable matchings for the roommate and the marriage models is provided in terms of individually rational matchings whose blocking pairs, if any, are formed with unmatched agents. These matchings always exist and give an economic intuition on how blocking can be done by non-trading agents, so that the transactions need not be undone as agents reach the set of stable matchings. Some properties of the Pareto-stable matchings shared by the Marriage and Roommate models are obtained.     

Nonexistence of stable threesome matchings

A counterexample shows stable matchings need not exist in societies where threesomes are to form. The stability theorem breaks down, in fact, for K-some formations for all K≥3, even when preferences are restricted to be separable.     

一类二分图的k-匹配数

设G是一个具有二分类(X_1,X_2)的简单偶图,|X_1|=|X_2|=n,如果对于给定的c>0,|M(S)|≥(1+c)|S|对任意满足|S|≤n/2的S(?)X_i(i=1,2)都成立,其中N(S)是S的邻集,则称G是(n,c)-扩张图.给出了(n,c)-扩张图的k-匹配数与完美匹配数之比的顺从界.     

Geometric properties of Poisson matchings

Suppose that red and blue points occur as independent Poisson processes of equal intensity in ${\mathbb {R}^d}$ , and that the red points are matched to the blue points via straight edges in a translation-invariant way. We address several closely related properties of such matchings. We prove that there exist matchings that locally minimize total edge length in d?=?1 and d??? 3, but not in the strip ${\mathbb {R}\times[0,1]}$ . We prove that there exist matchings in which every bounded set intersects only finitely many edges in d ?? 2, but not in d = 1 or in the strip. It is unknown whether there exists a matching with no crossings in d = 2, but we prove positive answers to various relaxations of this question. Several open problems are presented.     

Matchings and spanning trees in Boolean weighted graphs

It is shown that in a 0-sum Boolean weighted graph G the sum of the weights taken over all the spanning trees equals the sum of the weights taken over all the perfect matchings in the graph G − v, where v is any vertex of G. Several related theorems are proved which include parity results on perfect matchings and spanning trees in Eulerian graphs. The ideas on perfect matchings in 0-sum Boolean weighted graphs are generalized to matchings in any Boolean weighted graph.     

Sparsely intersecting perfect matchings in cubic graphs

In 1971, Fulkerson made a conjecture that every bridgeless cubic graph contains a family of six perfect matchings such that each edge belongs to exactly two of them; equivalently, such that no three of the matchings have an edge in common. In 1994, Fan and Raspaud proposed a weaker conjecture which requires only three perfect matchings with no edge in common. In this paper we discuss these and other related conjectures and make a step towards Fulkerson’s conjecture by proving the following result: Every bridgeless cubic graph which has a 2-factor with at most two odd circuits contains three perfect matchings with no edge in common.     

Efficient edge domination in regular graphs

An induced matching of a graph G is a matching having no two edges joined by an edge. An efficient edge dominating set of G is an induced matching M such that every other edge of G is adjacent to some edge in M. We relate maximum induced matchings and efficient edge dominating sets, showing that efficient edge dominating sets are maximum induced matchings, and that maximum induced matchings on regular graphs with efficient edge dominating sets are efficient edge dominating sets. A necessary condition for the existence of efficient edge dominating sets in terms of spectra of graphs is established. We also prove that, for arbitrary fixed p≥3, deciding on the existence of efficient edge dominating sets on p-regular graphs is NP-complete.     

渺位六角系统完美匹配Z——变换图

六角系统是2-连通的平面图，其每个内部面都是单位正六边形．六角系统的完美匹配是化学中苯类芳烃体系的Kekule结构．一个六角系统H完美匹配Z—变换图Z（H）是一个图，它的顶点集是H的完匹配集，两个匹配相邻当且仅当它们的对称差是一个单位正六边形．本文用乘积图刻划了沙位六角系统Z—变换图的结构．     

最大匹配的路变换图

图G的最大匹配的路变换图NM(G)是这样一个图,它以G的最大匹配为顶点,如果两个最大匹配M_1与M_2的对称差导出的图是一条路(长度没有限制),那么M_1和M_2在NM(G)中相邻.研究了这个变换图的连通性,分别得到了这个变换图是一个完全图或一棵树或一个圈的充要条件.     

Counting perfect matchings in n-extendable graphs

The structural theory of matchings is used to establish lower bounds on the number of perfect matchings in n-extendable graphs. It is shown that any such graph on p vertices and q edges contains at least ⌈(n+1)!/4[q-p-(n-1)(2Δ-3)+4]⌉ different perfect matchings, where Δ is the maximum degree of a vertex in G.