Kirill Rudov

Abstract. We study the impacts of incomplete information on centralized one-to-one matching markets. We focus on the commonly used Deferred Acceptance mechanism (Gale and Shapley, 1962). We show that many complete-information results are fragile to a small infusion of uncertainty about others' preferences.

Abstract. Traditional matching theory, and its canonical stability notion, assumes that agents can freely and costlessly switch partners. Without switching costs, large matching markets have a small number of stable matchings. In reality, however, switching partners is often costly: in labor markets, employees may need to move; in marriage markets, divorce frequently carries financial and emotional burdens. We study the impacts of switching costs and find that they can dramatically expand the set of stable matchings, even in large markets, and with vanishingly small costs. We precisely characterize the threshold of switching costs that triggers transformative expansion: an explosion in the number of stable matchings. From a market design perspective, accounting for switching costs, stability allows for significantly more room for policy interventions than previously thought. Our results provide insights into competitive forces in markets with imbalances between supply and demand.

Abstract. We show how fragile stable matchings are in a decentralized one-to-one matching setting. The classical work of Roth and Vande Vate (1990) suggests simple decentralized dynamics in which randomly-chosen blocking pairs match successively. Such decentralized interactions guarantee convergence to a stable matching. Our first theorem shows that, under mild conditions, any unstable matching—including a small perturbation of a stable matching—can culminate in any stable matching through these dynamics. Our second theorem highlights another aspect of fragility: stabilization may take a long time. Even in markets with a unique stable matching, where the dynamics always converge to the same matching, decentralized interactions can require an exponentially long duration to converge. A small perturbation of a stable matching may lead the market away from stability and involve a sizable proportion of mismatched participants for extended periods. Our results hold for a broad class of dynamics.

Presentations. Stony Brook GT Conference, BFI Theory Conference at UChicago, Columbia Theory Conference, Penn State (2024); AEA Meeting, UC Berkeley (2025).

Abstract. In many settings, agents can communicate—either directly or through intermediaries—before they engage in strategic interactions. We explore when such communication can be beneficial in general strategic contexts. We show that this question reduces, for any non-degenerate objective, to determining when Nash equilibria are extreme points within the set of correlated equilibria. Our results demonstrate that any sufficiently random mixed Nash equilibrium, involving at least three agents randomizing, can always be improved by either correlating agents' actions or switching to a less random equilibrium, regardless of the underlying objective. As a result, symmetric equilibria in a variety of symmetric environments—such as auctions, voting, and matching—are inherently suboptimal, no matter the goal.

Abstract. We propose simple dynamics that generate a stable supply chain network. We prove that any unstable network can reach a stable network through decentralized interactions where randomly-selected blocking chains form successively. Our proof suggests an algorithm for finding a stable network that generalizes the classical Gale and Shapley (1962) deferred acceptance algorithm.

Abstract. We study the effectiveness of iterated elimination of strictly dominated actions in normal-form games within a random games framework. Our results show that the likelihood of dominance solvability diminishes rapidly as the action set of at least one player expands. Moreover, when games are dominance-solvable, the number of iterations required to reach a Nash equilibrium increases significantly with the size of the action sets. However, in highly imbalanced games, iterated elimination can still greatly simplify the analysis by excluding a large fraction of actions. From a technical perspective, we demonstrate the value of recent combinatorial methods for analyzing general games.