MATCHUP 2015


University of Glasgow, 1618 April 2015 
MATCHUP 2015 Accepted Papers (with abstracts)Papers listed in order of submissionMarket Design under Distributional Constraints: Diversity in School Choice and Other Applications 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 adhoc solutions that eliminate blocks of seats exante (before agents submit their preferences) to ensure that all constraints are satisfied expost (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. College Admissions with Entrance Exams: Centralized versus Decentralized 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. Full Substitutability in Trading Networks 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. A new solution for the roommate problem: The Qstable matchings 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 Qstable 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.
Time Horizons, Lattice Structures, and Welfare in Multiperiod Matching Markets Abstract: We examine a Tperiod, bilateral matching economy without monetary transfers. Under natural restrictions on agents' preferences, which accommodate switching costs, statusquo bias, and other forms of intertemporal complementarity, dynamicallystable 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" dynamicallystable 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 marketdesign are discussed. Object Allocation via DeferredAcceptance: StrategyProofness and Comparative Statics 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, deferredacceptance (DA)mechanisms allocate objects based on exogenously fixed objects' priorities over agents and the agentproposing deferredacceptancealgorithm. For house allocation we show that DAmechanisms are characterized by our basic properties and (i) strategyproofness and populationmonotonicity or (ii) strategyproofness and resourcemonotonicity. 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 populationmonotonicity. On the other hand, the property combination (ii) with resourcemonotonicity characterizes (the most general) class of DAmechanisms 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 agentproposing deferredacceptancealgorithm. Therefore, in the general model resourcemonotonicity is the "stronger" comparative statics requirement because it characterizes (together with our basic requirements and strategyproofness) choicebased DAmechanisms whereas populationmonotonicity (together with our basic properties and strategyproofness) does not. Matroidal Choice Functions Abstract: Choice functions are common tools in manytoone or manytomany 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 strategyproofness of the deferred acceptance algorithm, and the distributive lattice structure of the set of stable matchings. Social Welfare in Onesided Matchings: Random Priority and Beyond Abstract: We study the problem of approximate social welfare maximization (without money) in onesided matching problems when agents have unrestricted cardinal preferences over a finite set of items. Random priority} is a very wellknown truthfulinexpectation mechanism for the problem. We prove that the approximation ratio of random priority is Theta(n^{1/2}) while no truthfulinexpectation 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 truthfulinexpectation) mechanisms is upper bounded by O(n^{1/2}), indicating that random priority is asymptotically the best truthfulinexpectation mechanism and the best ordinal mechanism for the problem. Manipulating the Probabilistic Serial Rule Abstract: The probabilistic serial (PS) rule is one of the most prominent randomized rules for the assignment problem. It is wellknown 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 NPhard. On the other hand, we present a polynomialtime 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. Generalized threesided assignment markets: consistency and the core Abstract: A class of threesided 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 antimonotonicity axiomatically characterize the core for these generalized threesided 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. Fairness and Efficiency in a Random Assignment: Three Impossibility Results 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 strategyproof mechanisms. The main finding is that for strategyproof mechanisms the following efficiency and fairness criteria are mutually incompatible: (1) Expost efficiency and envyfreeness, (2) ordinal efficiency and weak envyfreeness and (3) ordinal efficiency and equal division lower bound. Result (1) is the first impossibility result for this setting that uses expost 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 strategyproof, expost efficient mechanism that eliminates strict envy between agents with the same preferences. The most ordinallyegalitarian of random voting rules 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 ordinallyegalitarian 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 ordinallyegalitarian ones, out result shows that ESR is "the right way" to think about generalizing Serial rule. Polyhedral aspects of stable bmatching Abstract: The theory of matroidkernels and their corresponding sets of blockers and antiblockers can be utilized to obtain a linear description of the stable bmatching (MM) problem. We revisit that description to derive the dimension of the stable bmatching polytope P_I. Moreover, we provide a minimal representation of P_I by establishing its minimal equation system and identifying its facetdefining 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 matroidkernels to the one based on combs. A New Efficiency Criterion for Probabilistic Assignments 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. College Admission with Multidimensional Privileges: The Brazilian Affirmative Action Case 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 highschools. 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 strategyproof mechanism that matches students and colleges with the use of the proposed choice function. The size of the core in assignment markets Abstract: Assignment markets involve matching with transfers, as in labor markets and housing markets. We consider a twosided 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. Factor Revealing LPs and Stable Matching with Ties and Incomplete Lists Abstract: Stable matching with ties and incomplete lists (SMTI) is one of the most prominent NPhard 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 GaleShapley 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 factorrevealing 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 currentlyknown ratio (obtained via different techniques by Radnai) of 41/28 (1.4643). Possible and Necessary Allocations via Sequential Mechanisms 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 wellknown 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. Improved Algorithmic Results for Unsplittable Stable Allocation Problems Abstract: The stable allocation problem is a manytomany generalization of the wellknown 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 NPhard, including previouslyproposed 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. Contracts versus Salaries in Matching: A General Result 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 cadettobranch matching. As an application
of the embedding result, a new class of mechanisms for matching
markets with contracts is defined that generalize the firmproposing
deferred acceptance algorithm to the case where contracts are unilateral
substitutes for firms. Matroid Generalizations of the Popular Matching and Condensation Problems with Strict Preferences 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 polynomialtime 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 polynomialtime algorithm for this problem. Sticky Matching in School Choice 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. It's Not Easy Being Three: The Approximability of Three Dimensional Stable Matching Problems 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 NPcomplete 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 NPhardness 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 NPhard 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 APXcomplete. On The Structure of Popular Matchings in The Stable Marriage Problem Who Can Join a Popular Matching? 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 GaleSotomayor'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 HuangKavitha'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. Robust models for the Kidney Exchange Problem 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 vertexdisjoint 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 donorpatient 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. Driven by priorities manipulations under the Boston mechanism Abstract: Inspired from reallife 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 schooloptimal stable matching. Moreover, the condition is necessary: if the outcome of the Boston mechanism is the schooloptimal 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.
Trading networks with bilateral contracts 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 pathstable outcome whenever agents' preferences satisfy full substitutability. Pathstable outcomes may not be immune to group deviations or efficient. We extend previous results on group strategyproofness 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 pathstable. A Local Search Algorithm for SMTI and its extension to HRT Problems 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 NPhard. 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. On weighted kernels of two posets Abstract: A recent result of Aharoni Berger and Gorelik is a weighted generalization
of the wellknown 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. Overlapping Multiple Assignments 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 groupmonotonic (or groupinvariant) if and only if it is a groupsorting 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. Dynamic Task Assignments: An Online Two Sided Matching Approach 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 strategyproof 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 rankefficiency, we design an online matching mechanism $f^{BOMA}$.
We study all the four mechanisms empirically for stability and rankefficiency. Two School Systems, One District: What to do when a unified admissions process is impossible 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 rematching 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 rematch 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 nonwasteful 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. StrategyProofness and Stability for Matching with Contracts Abstract: We consider the setting of manytoone 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 nonmanipulability—and show that when these conditions are satisfied, a stable
and strategyproof (for workers) mechanism exists. Moreover, we show that if any of
these conditions fail, one may construct preferences for the doctors and unitdemand
choice functions for the other firms such that no stable and strategyproof mechanism
exists. Finally, we show that, whenever these conditions are satisfied, the outcome of
any stable and strategyproof mechanism coincides with the cumulative offer process. The Secure Boston Mechanism Abstract: The two primary objections to the Boston Mechanism (BM) are that it
is not strategyproof 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. The Curse of Stability: Designing the Appeals Round in School Choice 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 reassigned. 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 strategyproof, the current tworound 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 tworound 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 nonappealing 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 nonappealing students to passively participate in the supplementary round. School Choice with Neighbors 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 strategyproof mechanism satisfying even a much weaker stability notion. Instead, we show that a variation on the Top Trading Cycles mechanism is both strategyproof and Pareto efficient, and that it is in a welldefined sense one of the “most stable” strategyproof mechanism. We also present a modified Deferred Acceptance algorithm with improved stability properties. The Stable Fixtures Problem with Payments 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 2player 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 2player coalitions, a new 2player coalition in which they are mutually better off. A solution is stable if it has no blocking pairs. We give a polynomialtime 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. The (Non)Existence of Stable Mechanisms in Incomplete Information Environments Abstract: We consider twosided matching markets, and study the incentives of agents to circumvent a centralized clearing house by signing binding contracts with one another. It is wellknown 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. 