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 study decentralized one-to-one matching markets. Roth and Vande Vate (1990) showed that for any unstable matching, there are simple dynamics generating a stable one. Nonetheless, stable outcomes are fragile. First, we prove that any stable matching can be attained using these dynamics from any unstable one under mild conditions. Next, we quantify fragility. We show markets in which (i) some stable matchings are more robust than others; (ii) extremal stable matchings are most fragile; (iii) all stable matchings are fragile. Finally, even in markets with unique stable matchings, re-equilibration usually takes a long time and involves many market participants unmatched and rematched for a substantial number of periods. We prove that the addition of a small fraction of market participants can make stabilization dynamics in the new market take an exponentially long time for almost any perturbation.

Abstract. We study the effectiveness of iterated elimination of strictly-dominated actions in random games. We show that dominance solvability of games is vanishingly small as the number of at least one player's actions grows. Furthermore, conditional on dominance solvability, the number of iterations required to converge to Nash equilibrium grows rapidly as action sets grow. Nonetheless, when games are highly imbalanced, iterated elimination simplifies the game substantially by ruling out a sizable fraction of actions. Technically, we illustrate the usefulness of recent combinatorial methods for the analysis of general games.