Matching markets consist of two disjoint sets of agents, where each agent has a preference list over agents on the other side. The primary objective is to find a stable matching between the agents such that no unmatched pair of agents prefer each other to their matched partners. The incompatibility between stability and strategyproofness in this domain gives rise to a variety of strategic behavior of agents, which in turn may influence the resulting matching. In this paper, we discuss fundamental properties of stable matchings, review essential structural observations, survey key results in manipulation algorithms and their gametheoretical aspects, and more importantly, highlight a series of open research questions.
 Award ID(s):
 1909538
 NSFPAR ID:
 10448455
 Editor(s):
 Etessami, Kousha; Feige, Uriel; Puppis, Gabriele
 Date Published:
 Journal Name:
 Leibniz international proceedings in informatics
 Volume:
 261
 ISSN:
 18688969
 Page Range / eLocation ID:
 8:18:20
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


While the stable marriage problem and its variants model a vast range of matching markets, they fail to capture complex agent relationships, such as the affiliation of applicants and employers in an interview marketplace. To model this problem, the existing literature on matching with externalities permits agents to provide complete and total rankings over matchings based off of both their own and their affiliates' matches. This complete ordering restriction is unrealistic, and further the model may have an empty core. To address this, we introduce the Dichotomous Affiliate Stable Matching (DASM) Problem, where agents' preferences indicate dichotomous acceptance or rejection of another agent in the marketplace, both for themselves and their affiliates. We also assume the agent's preferences over entire matchings are determined by a general weighted valuation function of their (and their affiliates') matches. Our results are threefold: (1) we use a human study to show that realworld matching rankings follow our assumed valuation function; (2) we prove that there always exists a stable solution by providing an efficient, easilyimplementable algorithm that finds such a solution; and (3) we experimentally validate the efficiency of our algorithm versus a linearprogrammingbased approach.more » « less

Strategic behavior in twosided matching markets has been traditionally studied in a onesided manipulation setting where the agent who misreports is also the intended beneficiary. Our work investigates twosided manipulation of the deferred acceptance algorithm where the misreporting agent and the manipulator (or beneficiary) are on different sides. Specifically, we generalize the recently proposed accomplice manipulation model (where a man misreports on behalf of a woman) along two complementary dimensions: (a) the two for one model, with a pair of misreporting agents (man and woman) and a single beneficiary (the misreporting woman), and (b) the one for all model, with one misreporting agent (man) and a coalition of beneficiaries (all women). Our main contribution is to develop polynomialtime algorithms for finding an optimal manipulation in both settings. We obtain these results despite the fact that an optimal one for all strategy fails to be inconspicuous, while it is unclear whether an optimal two for one strategy satisfies the inconspicuousness property. We also study the conditions under which stability of the resulting matching is preserved. Experimentally, we show that twosided manipulations are more frequently available and offer better quality matches than their onesided counterparts.

We study the problem of capacity modification in the manytoone stable matching of workers and firms. Our goal is to systematically study how the set of stable matchings changes when some seats are added to or removed from the firms. We make three main contributions: First, we examine whether firms and workers can improve or worsen upon changing the capacities under workerproposing and firmproposing deferred acceptance algorithms. Second, we study the computational problem of adding or removing seats to either match a fixed workerfirm pair in some stable matching or make a fixed matching stable with respect to the modified problem. We develop polynomialtime algorithms for these problems when only the overall change in the firms’ capacities is restricted, and show NPhardness when there are additional constraints for individual firms. Lastly, we compare capacity modification with the classical model of preference manipulation by firms and identify scenarios under which one mode of manipulation outperforms the other. We find that a threshold on a given firm’s capacity, which we call its peak, crucially determines the effectiveness of different manipulation actions.more » « less

Singh, M. ; Williamson, D. (Ed.)Birkhoff’s representation theorem defines a bijection between elements of a distributive lattice L and the family of upper sets of an associated poset B. When elements of L are the stable matchings in an instance of Gale and Shapley’s marriage model, Irving et al. showed how to use B to devise a combinatorial algorithm for maximizing a linear function over the set of stable matchings. In this paper, we introduce a general property of distributive lattices, which we term as affine representability, and show its role in efficiently solving linear optimization problems over the elements of a distributive lattice, as well as describing the convex hull of the characteristic vectors of lattice elements. We apply this concept to the stable matching model with pathindependent quotafilling choice functions, thus giving efficient algorithms and a compact polyhedral description for this model. To the best of our knowledge, this model generalizes all models from the literature for which similar results were known, and our paper is the first that proposes efficient algorithms for stable matchings with choice functions, beyond extension of the Deferred Acceptance algorithm.more » « less