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. 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.

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.

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.

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.