This content will become publicly available on August 1, 2025
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.
more » « less Award ID(s):
 2144413
 NSFPAR ID:
 10533710
 Publisher / Repository:
 International Joint Conferences on Artificial Intelligence Organization
 Date Published:
 ISBN:
 9781956792041
 Page Range / eLocation ID:
 8077 to 8085
 Format(s):
 Medium: X
 Location:
 Jeju, South Korea
 Sponsoring Org:
 National Science Foundation
More Like this

Etessami, Kousha ; Feige, Uriel ; Puppis, Gabriele (Ed.)To guarantee all agents are matched in general, the classic Deferred Acceptance algorithm needs complete preference lists. In practice, preference lists are short, yet stable matching still works well. This raises two questions: Why does it work well? Which proposals should agents include in their preference lists? We study these questions in a model, introduced by Lee, with preferences based on correlated cardinal utilities: these utilities are based on common public ratings of each agent together with individual private adjustments. Lee showed that for suitable utility functions, in large markets, with high probability, for most agents, all stable matchings yield similar valued utilities. By means of a new analysis, we strengthen Lee's result, showing that in large markets, with high probability, for all but the agents with the lowest public ratings, all stable matchings yield similar valued utilities. We can then deduce that for all but the agents with the lowest public ratings, each agent has an easily identified length O(log n) preference list that includes all of its stable matches, addressing the second question above. We note that this identification uses an initial communication phase. We extend these results to settings where the two sides have unequal numbers of agents, to manytoone settings, e.g. employers and workers, and we also show the existence of an epsilonBayesNash equilibrium in which every agent makes relatively few proposals. These results all rely on a new technique for sidestepping the conditioning between the tentative matching events that occur over the course of a run of the Deferred Acceptance algorithm. We complement these theoretical results with an experimental study.more » « less

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

We study the problem of online learning in competitive settings in the context of twosided matching markets. In particular, one side of the market, the agents, must learn about their preferences over the other side, the firms, through repeated interaction while competing with other agents for successful matches. We propose a class of decentralized, communication and coordinationfree algorithms that agents can use to reach to their stable match in structured matching markets. In contrast to prior works, the proposed algorithms make decisions based solely on an agent’s own history of play and requires no foreknowledge of the firms’ preferences.Our algorithms are constructed by splitting up the statistical problem of learning one’s preferences, from noisy observations, from the problem of competing for firms. We show that under realistic structural assumptions on the underlying preferences of the agents and firms, the proposed algorithms incur a regret which grows at most logarithmically in the time horizon. However, we note that in the worst case, it may grow exponentially in the size of the market.more » « less

The matching law describes the tendency of agents to match the ratio of choices allocated to the ratio of rewards received when choosing among multiple options (Herrnstein, 1961). Perfect matching, however, is infrequently observed. Instead, agents tend to undermatch or bias choices toward the poorer option. Overmatching, or the tendency to bias choices toward the richer option, is rarely observed. Despite the ubiquity of undermatching, it has received an inadequate normative justification. Here, we assume agents not only seek to maximize reward, but also seek to minimize cognitive cost, which we formalize as policy complexity (the mutual information between actions and states of the environment). Policy complexity measures the extent to which the policy of an agent is state dependent. Our theory states that capacityconstrained agents (i.e., agents that must compress their policies to reduce complexity) can only undermatch or perfectly match, but not overmatch, consistent with the empirical evidence. Moreover, using mouse behavioral data (male), we validate a novel prediction about which task conditions exaggerate undermatching. Finally, in patients with Parkinson's disease (male and female), we argue that a reduction in undermatching with higher dopamine levels is consistent with an increased policy complexity.
SIGNIFICANCE STATEMENT The matching law describes the tendency of agents to match the ratio of choices allocated to different options to the ratio of reward received. For example, if option a yields twice as much reward as option b, matching states that agents will choose option a twice as much. However, agents typically undermatch: they choose the poorer option more frequently than expected. Here, we assume that agents seek to simultaneously maximize reward and minimize the complexity of their action policies. We show that this theory explains when and why undermatching occurs. Neurally, we show that policy complexity, and by extension undermatching, is controlled by tonic dopamine, consistent with other evidence that dopamine plays an important role in cognitive resource allocation. 
Twosided matching markets have long existed to pair agents in the absence of regulated exchanges. A common example is school choice, where a matching mechanism uses student and school preferences to assign students to schools. In such settings, forming preferences is both difficult and critical. Prior work has suggested various prediction mechanisms that help agents make decisions about their preferences. Although often deployed together, these matching and prediction mechanisms are almost always analyzed separately. The present work shows that at the intersection of the two lies a previously unexplored type of strategic behavior: agents returning to the market (e.g., schools) can attack future predictions by interacting shortterm nonoptimally with their matches. Here, we first introduce this type of strategic behavior, which we call an adversarial interaction attack. Next, we construct a formal economic model that captures the feedback loop between prediction mechanisms designed to assist agents and the matching mechanism used to pair them. Finally, in a simplified setting, we prove that returning agents can benefit from using adversarial interaction attacks and gain progressively more as the trust in and accuracy of predictions increases. We also show that this attack increases inequality in the student population.more » « less