Abstract: Distributional constraints are important in many market design settings. Prominent examples include the minimum manning requirements at each Army branch in military cadet matching and diversity considerations in school choice, whereby school districts impose constraints on the demographic distribution of students at each school. Standard assignment mechanisms implemented in practice are unable to accommodate these constraints. This leads policymakers to resort to ad-hoc solutions that eliminate blocks of seats ex-ante (before agents submit their preferences) to ensure that all constraints are satisfied ex-post (after the mechanism is run). We show that these current solutions ignore important information contained in the submitted preferences, resulting in avoidable inefficiency. We then introduce new dynamic quotas mechanisms that result in Pareto superior allocations while at the same time respecting all distributional constraints and satisfying important fairness and incentive properties. We expect the use of our mechanisms to improve the performance of matching markets with distributional constraints in the field.

Abstract: We theoretically and experimentally study a college admissions problem in which colleges accept students by ranking students’ efforts in entrance exams. Students’ ability levels affect the cost of their efforts. We solve and compare equilibria of “centralized college admissions” (CCA) where students apply to all colleges, and “decentralized college admissions” (DCA) where students only apply to one college. We show that lower ability students prefer DCA whereas higher ability students prefer CCA. The main predictions of the theory are supported by experiments, yet we find a number of differences that render DCA less attractive than CCA compared to equilibrium benchmark.

Abstract: Trading networks generalize and unify models of matching with bilateral contracts and indivisible goods exchange. We extend earlier models' canonical definitions of substitutability to the trading network context and show that all these definitions are equivalent. We also find that substitutability is preserved under economically important transformations such as mergers and trade endowments. Furthermore, we show that substitutability implies a regularity condition called the Laws of Aggregate Supply and Demand.

Abstract: The aim of this paper is to propose a new solution for the roommate problem with strict preferences. We introduce the solution of máximum irreversibility and consider almost stable matchings (Abraham et al. (WAOA, 2006)) and maximum stable matchings (Tan (BIT, 1990) (Int. J. Comput. Math, 1991)). We find that almost stable matchings are incompatible with the other two solutions. Hence, to solve the roommate problem we propose matchings that lie at the intersection of the maximum irreversible matchings and maximum stable matchings, which are called Q-stable matchings. These matchings are core consistent and we offer an efficient algorithm for computing one of them. The outcome of the algorithm belongs to an absorbing set.

Abstract: We examine a T-period, bilateral matching economy without monetary transfers. Under natural restrictions on agents' preferences, which accommodate switching costs, status-quo bias, and other forms of inter-temporal complementarity, dynamically-stable matchings exist. We study the consequences of manipulating the market's time horizon on the set of stable outcomes and we investigate this set's lattice structure. Generally, "optimal" dynamically-stable matchings may not exist, but under a suitable partial order the stable set is a lattice. The welfare properties of different stable outcomes is ascertained and the implications for normative market-design are discussed.

Abstract: We study the problem of assigning indivisible and heterogenous objects (e.g., houses, jobs, offices, school or university admissions etc.) to agents. Each agent receives at most one object and monetary compensations are not possible. We consider mechanisms satisfying a set of basic properties.

In the house allocation problem, where at most one copy of each object is available, deferred-acceptance (DA)-mechanisms allocate objects based on exogenously fixed objects' priorities over agents and the agent-proposing deferred-acceptance-algorithm. For house allocation we show that DA-mechanisms are characterized by our basic properties and (i) strategy-proofness and population-monotonicity or (ii) strategy-proofness and resource-monotonicity.

Once we allow for multiple identical copies of objects, on the one hand the first characterization breaks down and there are unstable mechanisms satisfying property combination (i) with population-monotonicity. On the other hand, the property combination (ii) with resource-monotonicity characterizes (the most general) class of DA-mechanisms based on objects' fixed choice functions that are acceptant, monotonic, substitutable, and consistent. These choice functions are used by objects to reject agents in the agent-proposing deferred-acceptance-algorithm.

Therefore, in the general model resource-monotonicity is the "stronger" comparative statics requirement because it characterizes (together with our basic requirements and strategy-proofness) choice-based DA-mechanisms whereas population-monotonicity (together with our basic properties and strategy-proofness) does not.

Abstract: Choice functions are common tools in many-to-one or many-to-many matching models. They can represent more general preferences of agents than the classical form that consists of a list and a quota. Choice functions are usually assumed to satisfy the substitutability, which is an essential condition for the existence of stable matchings.

In this paper, we introduce ``matroidal choice functions" as a class of choice functions which satisfy a kind of matroid constraints in addition to the substitutability. We show that matroidal choice functions admit succinct representations, with which one can find a stable matching efficiently utilizing a greedy algorithm for matroids.

Furthermore, we show that matroidal choice functions afford nice properties of stable matchings such as the strategy-proofness of the deferred acceptance algorithm, and the distributive lattice structure of the set of stable matchings.

Abstract: We study the problem of approximate social welfare maximization (without money) in one-sided matching problems when agents have unrestricted cardinal preferences over a finite set of items. Random priority} is a very well-known truthful-in-expectation mechanism for the problem. We prove that the approximation ratio of random priority is Theta(n^{-1/2}) while no truthful-in-expectation mechanism can achieve an approximation ratio better than O(n^{-1/2}), where $n$ is the number of agents and items. Furthermore, we prove that the approximation ratio of all ordinal (not necessarily truthful-in-expectation) mechanisms is upper bounded by O(n^{-1/2}), indicating that random priority is asymptotically the best truthful-in-expectation mechanism and the best ordinal mechanism for the problem.

Abstract: The probabilistic serial (PS) rule is one of the most prominent randomized rules for the assignment problem. It is well-known for its superior fairness and welfare properties. However, PS is not immune to manipulative behaviour by the agents. We initiate the study of the computational complexity of an agent manipulating the PS rule. We show that computing an expected utility better response is NP-hard. On the other hand, we present a polynomial-time algorithm to compute a lexicographic best response. For the case of two agents, we show that even an expected utility best response can be computed in polynomial time. Our result for the case of two agents relies on an interesting connection with sequential allocation of discrete objects.

Abstract: A class of three-sided markets (and games) is considered, where value is generated by pairs or triplets of agents belonging to different sectors, as well as by individuals. For these markets we analyze the situation that arises when some agents leave the market with some payoff. To this end, we introduce the derived market (and game) and relate it to the Davis and Maschler (1965) reduced game. Consistency with respect to the derived market, together with singleness best and individual anti-monotonicity axiomatically characterize the core for these generalized three-sided assignment markets. These markets may have an empty core, but we define a balanced subclass, where the worth of each triplet is defined as the addition of the worths of the pairs it contains.

Abstract: Abstract This paper considers the problem of allocating N indivisible objects among N agents according to their preferences when transfers are not allowed, and studies the tradeoff between fairness and efficiency in the class of strategy-proof mechanisms. The main finding is that for strategy-proof mechanisms the following efficiency and fairness criteria are mutually incompatible: (1) Ex-post efficiency and envy-freeness, (2) ordinal efficiency and weak envy-freeness and (3) ordinal efficiency and equal division lower bound. Result (1) is the first impossibility result for this setting that uses ex-post efficiency; results (2) and (3) are more relevant for practical implementation than similar results in the literature. In addition, for N=3 the paper strengthens the characterization result by Bogomolnaia and Moulin (2001): the random serial dictatorship mechanism is the unique strategy-proof, ex-post efficient mechanism that eliminates strict envy between agents with the same preferences.

Abstract: Aziz and Stursberg [1] propose an "Egalitarian Simultaneous Reservation" rule (ESR), a generalization of Serial rule, one of the most discussed mechanisms in random assignment problem, to the more general random social choice domain. We provide an alternative definition, or characterization, of ESR as the unique most ordinally-egalitarian one. Specifically, given a lottery $p$ over alternatives, for each agent $i$ we define $t^p_i (k)$ to be the total share in p of objects from her first k indifference classes. ESR is shown to be the unique one which leximin maximizes the vector of all such shares $( t^p_i (k))_{i,k}$. Serial rule is known to be characterized by the same property (see [2]). Thus, we provide an alternative way to show that ESR, indeed, coincides with Serial rule on the assignment domain. Moreover, since both rules are defined as the unique most ordinally-egalitarian ones, out result shows that ESR is "the right way" to think about generalizing Serial rule.

Abstract: The theory of matroid-kernels and their corresponding sets of blockers and antiblockers can be utilized to obtain a linear description of the stable b-matching (MM) problem. We revisit that description to derive the dimension of the stable b-matching polytope P_I. Moreover, we provide a minimal representation of P_I by establishing its minimal equation system and identifying its facet-defining inequalities. This representation includes O(m) constraints, m being the number of pairs, hence being significantly smaller than the existing one and linear with respect to the size of the problem. This minimal representation carries over to the stable admissions (SA) problem, for which we also establish the facial correspondence of the linear representation based on matroid-kernels to the one based on combs.

Abstract: For probabilistic assignment of objects, when only ordinal preference information is available, we propose the following efficiency criterion: a probabilistic assignment dominates another assignment if, whenever the latter assignment is utilitarian efficient at a utility profile consistent with the ordinal preferences, the former assignment is utilitarian efficient too; and there is a utility profile consistent with the ordinal preferences at which the latter assignment is not utilitarian efficient but the former assignment is utilitarian efficient. We provide a simple characterization of probabilistic assignments which are not dominated in this sense. In particular, if preferences are strict, the only undominated probabilistic assignments are the Pareto efficient deterministic assignments. We revisit an extensively studied probabilistic assignment mechanism, the Probabilistic Serial rule, and show that it can be improved in efficiency without sacrificing fairness.

Abstract: Abstract In August of 2012 the Brazilian federal government enacted a law mandating the implementation of affirmative action policies in public federal universities for candidates from racial minorities, low income families and those coming from public high-schools. We show that by using the method proposed by the government, the choices made by the colleges will not satisfy a general fairness condition, and that moreover students who strategize over the privileges that they claim may improve their placement. Data from university admissions in more than 3,000 programs in 2013 show that the conditions for those undesirable incentives are observed in more than 49% of them. We propose a choice function for the colleges that removes any gain from strategizing over the privileges claimed, is fair, satisfies the substitutes condition and under reasonable assumptions on the type distribution of the population fully satisfies the diversity objectives expressed by the reserves. We finalize by proposing a strategy-proof mechanism that matches students and colleges with the use of the proposed choice function.

Abstract: Assignment markets involve matching with transfers, as in labor markets and housing markets. We consider a two-sided assignment market with agent types and stochastic structure similar to models used in empirical studies, and characterize the size of the core in such markets. Each agent has a randomly drawn productivity with respect to each type of agent on the other side. The value generated from a match between a pair of agents is the sum of the two productivity terms, each of which depends only on the type but not the identity of one of the agents, and a third deterministic term driven by the pair of types. We allow the number of agents to grow, keeping the number of agent types fixed. Let $n$ be the number of agents and $K$ be the number of types on the side of the market with more types. We find, under reasonable assumptions, that the relative variation in utility per agent over core outcomes is bounded as $O^*(1/n^{1/K})$, where polylogarithmic factors have been suppressed. Further, we show that this bound is tight in worst case. We also provide a tighter bound under more restrictive assumptions.

Abstract: Stable matching with ties and incomplete lists (SMTI) is one of the most prominent NP-hard problems in the domain of ordinal matching, where we seek to find a bipartite matching between a set of men and a set of women that is ``stable'' with respect to their preferences. When ties in preference lists are restricted to one side of the problem, Iwama et al. devised a variant of the famous Gale-Shapley stable matching algorithm that breaks ties using edge weights from a linear programming (LP) relaxation of the problem, leading to an approximation ratio of 25/17 (1.4706). We apply ideas from factor-revealing LPs to show, via computational proof involving the solution of massive LPs, that their analysis can be systematically improved to yield an approximation ratio of 19/13 (1.4615), improving the best currently-known ratio (obtained via different techniques by Radnai) of 41/28 (1.4643).

Abstract: A simple mechanism for allocating indivisible resources is sequential allocation in which agents take turns to pick items. We focus on possible and necessary allocation problems, checking whether allocations of a given form occur in some or all mechanisms for several commonly used classes of sequential allocation mechanisms. In particular, we consider whether a given agent receives a given item, a set of items, or a subset of items for five natural classes of sequential allocation mechanisms: balanced, recursively balanced, balanced alternating, strictly alternating and all policies. We identify characterizations of allocations produced balanced, recursively balanced, balanced alternating policies and strictly altnernating respectively, which extend the well-known characterization by Brams and King [2005] for policies without restrictions. In addition, we examine the computational complexity of possible and necessary allocation problems for these classes.

Abstract: The stable allocation problem is a many-to-many generalization of the well-known stable marriage problem, where we seek a bipartite assignment between, say, jobs (of varying sizes) and machines (of varying capacities) that is “stable” based on a set of underlying preference lists submitted by the jobs and machines. Building on the initial work of Dean et al., we study a natural “unsplittable” variant of this problem, where each assigned job must be fully assigned to a single machine. Such unsplittable bipartite assignment problems generally tend to be NP-hard, including previously-proposed variants of the unsplittable stable allocation problem. Our main result is to show that under an alternative model of stability, the unsplittable stable allocation problem becomes solvable in polynomial time; although this model is less likely to admit feasible solutions than the model proposed by McDermid and Manlove, we show that in the event there is no feasible solution, our approach computes a solution of minimal total congestion (overfilling of all machines collectively beyond their capacities). We also describe a technique for rounding the solution of a stable allocation problem to produce “relaxed” unsplit solutions that are only mildly infeasible, where each machine is overcongested by at most a single job.

Abstract: It is shown that a matching market with contracts may be embedded into a matching market with salaries under weaker conditions than substitutability of contracts. In particular, the result applies to the recently studied problem of cadet-to-branch matching. As an application of the embedding result, a new class of mechanisms for matching markets with contracts is defined that generalize the firm-proposing deferred acceptance algorithm to the case where contracts are unilateral substitutes for firms.

Abstract: In this talk, we first consider a matroid generalization of the popular matching problem (without ties) introduced by Abraham, Irving, Kavitha, and Mehlhorn, and give a polynomial-time algorithm for this problem. In the second half of this talk, we consider the problem of transforming a given instance of the popular matching problem (without ties) by deleting a minimum number of applicants so that it has a popular matching under matroid constraints. This problem is a matroid generalization of the popular condensation problem (without ties) proposed by Wu, Lin, Wang, and Chao. By using the results in the first half, we give a polynomial-time algorithm for this problem.

Abstract: We analyze the school choice model and introduce costly appeals against violations of students' priorities. If these costs are sufficiently high, then some of such appeals may not provide benefits to the parents even when their priorities are violated. Instead of working with cardinal notions, our construction elicits the relevant ordinal implications of these costs, the information about the least rank decrease a student would be appealing against a priority violation (his/her stickiness degree), from the students before the assignment is determined. Then the notion of stability, the main desiderata in school choice known to be at odds with efficiency, is weakened by disregarding priority violations not worth the cost and the notion of sticky stability is obtained. The first mechanism we introduce is ``efficiency improving deferred acceptance mechanism'' (EIDA) and we show that it is sticky stable and superior to the deferred acceptance mechanism (DA) in terms of efficiency and involves truthful revelations of the stickiness degrees. The EIDA not maximally improving efficiency in the class of sticky stable solutions, leads us to design ``efficiency corrected deferred acceptance mechanism'' (ECDA) which turns out to be both sticky stable and efficient within the class of sticky stable mechanisms. While both mechanisms lack full incentive properties in the complete information case, in certain incomplete information settings, the former becomes immune to manipulations, whereas, the latter is still manipulable but with a diminished scope.

Abstract: In 1976, Knuth asked if the stable marriage problem (SMP) can be generalized to marriages consisting of 3 genders. In 1988, Alkan showed that the natural generalization of SMP to 3 genders (3GSM) need not admit a stable marriage. Three years later, Ng and Hirschberg proved that it is NP-complete to determine if given preferences admit a stable marriage. They further prove an analogous result for the 3 person stable assignment (3PSA) problem.

In light of Ng and Hirschberg's NP-hardness result for 3GSM and 3PSA, we initiate the study of approximate versions of these problems. We describe two optimization variants of 3GSM and 3PSA: maximally stable marriage/matching (MSM) and maximum stable submarriage/submatching (MSS). We show that both variants are NP-hard to approximate within some fixed constant factor. Conversely, we describe a simple polynomial time algorithm which computes constant factor approximations for the maximally stable marriage and matching problems. Thus of MSM is APX-complete.

Abstract: Gale and Sotomayor (1985) gave a remark on the stable marriage problem that the set of people who are matched with themselves is the same for all stable matchings. Motivated by a larger cardinality matching, Huang and Kavitha (2013) investigated the structure of popular matchings, an extended notion of stable matching: Given an instance of the stable marriage problem, a matching M is popular if there is no matching M' such that more vertices are better off in M' than in M. They established the Gale-Sotomayor's type theorem for minimum cardinality popular matchings, and showed that any stable matching is a minimum cardinality popular matching. We establish the same type of theorem for maximum cardinality popular matchings. It implies that the family ${\cal V}$ of sets of endpoints of popular matchings has the (unique) maximum and minimum with respect to the inclusion relation, combining with Huang-Kavitha's result. As a consequence, one may naturally presume that ${\cal V}$ is closed under intersection and union, and then ${\cal V}$ forms a (distributive) lattice. We disprove the former presumption.

Abstract: We consider the clearing of barter exchange markets in which proposed transactions must be verified before they can proceed. Proposed transactions may fail to go forward if verification fails or if a participant withdraws. The clearing problem for these markets is a combinatorial optimization problem that can be modeled as a vertex-disjoint cycle packing problem in an unreliable digraph. The arcs and nodes of this graph are subject to failure. Our research finds a natural application in kidney exchange markets, which aim to enable transplants between incompatible donor-patient pairs. A set of pairs must be chosen in such a way that each selected patient can receive a kidney from a compatible donor from another pair in the set. The pairs are then notified and crossmatch tests must be performed to ensure the success of the transplants. In this work we assume that in case one or more matches fail, a new set of pairs may be selected. The new set should be as close as possible to the initial set in order to minimize the material and emotional costs of the alteration. We present a robust optimization approach that intends to maximize the number of pairs selected in both the first and second set in a worst case scenario.

Abstract: Inspired from real-life manipulations used when the Boston mechanism is in place, we study school choice markets where students submit preferences driven by priorities: they declare as more preferred those schools where they have high priority. We prove that when students follow this type of strategies, the outcome of the Boston mechanism is the school-optimal stable matching. Moreover, the condition is necessary: if the outcome of the Boston mechanism is the school-optimal stable matching, then preferences are driven by priorities. Thus, under these manipulations, the final allocation of students may be purely shaped by schools' priorities. Additionally, we run some computational simulations to show that the assumption of driven by priorities preferences can be relaxed by allowing non trivial degrees of idiosyncratic shocks in students' preferences, and our main results hold for almost all students.

Abstract: We consider general networks of bilateral contracts that include supply chains. We define a new stability concept called path stability and show that any network of bilateral contracts has a path-stable outcome whenever agents' preferences satisfy full substitutability. Path-stable outcomes may not be immune to group deviations or efficient. We extend previous results on group strategy-proofness and the rural hospitals theorem. When contracts specify trades and prices, we also show that competitive equilibrium exists in networked markets even in the absence of transferrable utility. The competitive equilibrium outcome is path-stable.

Abstract: Hospitals/Residents with Ties (HRT) forms a class of problems with many applications, some of which of considerable size. Solving these problems have been shown to be NP-hard. In previous work, we developed a local search algorithm which displays very high performance in solving Stable Matching with Ties and Incomplete lists (SMTI) problems. In this paper, we propose a method to tackle HRT problems with a slightly modified version of our SMTI solver. We describe our method and provide an initial performance assessment, which turns out to show that the resulting solver can deal with significant HR problems, providing optimal solutions in most cases, in a very short time.

Abstract: A recent result of Aharoni Berger and Gorelik is a weighted generalization of the well-known theorem of Sands Sauer and Woodrow on monochromatic paths. The authors prove the existence of a so called weighted kernel for any pair of weighted posets on the same ground set. In this work, we point out that this result is closely related to the stable marriage theorem of Gale and Shapley, and we generalize Blair's theorem by showing that weighted kernels form a lattice under a certain natural order. To illustrate the applicability of our approach, we prove further weighted generalizations of the Sands Sauer Woodrow result.

Abstract: This paper studies an allocation problem with multiple assignments, indivisible objects, no endowments and no monetary transfers. A single object may be assigned to several agents as long as the set of agents assigned the object satisfy a compatibility constraint. It is shown that, on the domain of complete, transitive and strict preferences, a rule is coalitionally strategyproof (or strategyproof and nonbossy), Pareto efficient and group-monotonic (or group-invariant) if and only if it is a group-sorting sequential dictatorship. It is also demonstrated that the characterization in Pápai (2001) of sequential dictatorships for the case where assignments are not allowed to overlap is contained in the main result of this paper.

Abstract: For the task assignment problem in an expert crowdsourcing platform, we propose that the dynamically arriving workers report their preferences for the tasks as ordinal preferences to the platform. We model then the task assignment problem as a dynamic two sided matching problem. In this paper we study the dynamic two sided matching when the men (the workers) side of the market is arriving dynamically and the women (the requesters) side is available since beginning. We assume strict preferences of the agents. Using a deferred acceptance algorithm as a building block, we first develop $f^{APODA}$, a class of strategy-proof online mechanisms. We design $f^{APODA}$ and $f^{ThODA}$ in this class. As no mechanism can achieve stability in our settings, we propose a weaker notion of stability, namely, progressive stability. We introduce an online mechanism $f^{RODA}$ that achieve the progressive stability. For achieving good rank-efficiency, we design an online matching mechanism $f^{BOMA}$. We study all the four mechanisms empirically for stability and rank-efficiency.

Abstract: When groups of schools within a single district run their admission processes independently of one another, the resulting match is often inefficient: many children are left unmatched and seats are left unfilled. We study the problem of re-matching students to take advantage of these empty seats in a context where there are priorities to respect. We propose an iterative way in which each group may independently match and re-match students to its schools. The advantages of this process are that every iteration leads to a Pareto improvement and a reduction in waste while maintaining respect of the priorities. Furthermore, it reaches a non-wasteful match within a finite number of iterations. While iterating may be costly, as it involves asking for inputs from the children, there are significant gains from the first few iterations. We show this analytically for certain stylized problems and computationally for a few others.

Abstract: We consider the setting of many-to-one matching with contracts, where firms may demand multiple contracts but each worker desires at most one contract. We introduce three conditions—observable substitutability, observable size monotonicity, and non-manipulability—and show that when these conditions are satisfied, a stable and strategy-proof (for workers) mechanism exists. Moreover, we show that if any of these conditions fail, one may construct preferences for the doctors and unit-demand choice functions for the other firms such that no stable and strategy-proof mechanism exists. Finally, we show that, whenever these conditions are satisfied, the outcome of any stable and strategy-proof mechanism coincides with the cumulative offer process.

Abstract: The two primary objections to the Boston Mechanism (BM) are that it is not strategy-proof and that sophisticated students benefit at the expense of naive students. However, it is an attractive algorithm from an optimization standpoint. We introduce an intuitive modification of BM that secures any school a student was initially guaranteed but otherwise prioritizes a student at a school based upon how she ranks it. This algorithm is less manipulatable than BM and provides some protection for naive students. Our main result is to show that an equilibrium, in undominated strategies, of this new algorithm Pareto dominates the Deferred Acceptance algorithm when the student optimal stable assignment is Pareto inefficient.

Abstract: Abstract Almost all school choice plans feature an additional supplementary round where students who declare to be dissatisfied with the outcome in the main round can appeal to be re-assigned. The largest of these plans, the current New York City (NYC) high school matching system, assigns students to the schools via Gale and Shapley Deferred Acceptance (DA) mechanism in the main round which is next followed by a supplementary round employing the Top Trading Cycles (TTC) mechanism. Although both DA and TTC are strategy-proof, the current two-round system does not eliminate students' incentives to be strategic in their reported choices. In particular, a student may misreport his preferences in the main round in order to be assigned to a school which he can later trade with a more desirable school in the supplementary round. We ask whether we can design two-round school choice systems with good incentive properties and show that the answer to this questions does not only depend on the properties of the specific mechanisms used in each round, but also whether or not the non-appealing students are taken into account in the supplementary round. Our results show that the deficiency of the NYC system can be mitigated by either reversing the order of the two mechanisms, or by applying DA in both rounds together with allowing non-appealing students to passively participate in the supplementary round.

Abstract: Abstract We consider the school choice problem where students may prefer to be assigned to the same school as a neighbor. In that setting, the set of stable matchings can be empty. Moreover, there does not exist a strategy-proof mechanism satisfying even a much weaker stability notion. Instead, we show that a variation on the Top Trading Cycles mechanism is both strategy-proof and Pareto efficient, and that it is in a well-defined sense one of the “most stable” strategy-proof mechanism. We also present a modified Deferred Acceptance algorithm with improved stability properties.

Abstract: We introduce multiple partners matching games, which consist of a graph $G=(N,E)$, with an integer vertex capacity function~$b$ and an edge weighting $w$. The set $N$ consists of a number of players that are to form a set $M\subseteq E$ of 2-player coalitions $ij$ with value $w_{ij}$, such that each player $i$ is in at most $b_i$ coalitions. A payoff $p$ is a vector with $p(i,j)+p(j,i)=w_{ij}$ if $ij\in M$ and $p(i,j)=p(j,i)=0$ if $ij\notin M$. The pair $(M,p)$ is called a solution. A pair of players $i,j$ with $ij\in E\setminus M$ blocks a solution $(M,p)$ if $i, j$ can form, possibly only after withdrawing from one of their existing 2-player coalitions, a new 2-player coalition in which they are mutually better off. A solution is stable if it has no blocking pairs. We give a polynomial-time algorithm that either finds that no stable solutions exists, or obtains a stable solution. This generalizes a known result of Sotomayor (1992) for multiple partners assignment games, where the underlying graph $G$ is bipartite. We also characterize the set of stable solutions and initiate a study on the core of the corresponding cooperative game, where coalitions of any size may be formed.

Abstract: We consider two-sided matching markets, and study the incentives of agents to circumvent a centralized clearing house by signing binding contracts with one another. It is well-known that if the clearing house implements a stable match and preferences are known, then no group of agents can profitably deviate in this manner.

We ask whether this property holds even when agents have incomplete information about their own preferences or the preferences of others. We find that it does not. In particular, when agents are uncertain about the preferences of others, every mechanism is susceptible to deviations by groups of agents. When, in addition, agents are uncertain about their own preferences, every mechanism is susceptible to deviations in which a single pair of agents agrees in advance to match to each other.