580 California St., Suite 400
San Francisco, CA, 94104
Key research themes
1. What are the structural conditions that guarantee uniqueness and facilitate efficient enumeration of stable matchings in algorithmic matchmaking?
Understanding when a stable matching is unique and characterizing the structure of all stable matchings are fundamental for both theoretical insights and practical algorithms in a variety of two-sided matching markets. Uniqueness simplifies prediction and strategy-proofness, whereas the combinatorial structure of stable matchings (e.g., rotation posets) informs efficient algorithms for solution enumeration and fair match selection.
Key finding: Provides the first necessary and sufficient condition for the uniqueness of stable matchings by introducing the concept of the 'normal form' of a matching problem and showing that uniqueness holds if and only if preferences... Read more
Key finding: Characterizes the rotation poset structure underlying stable matchings in instances with restricted preferences, such as k-bounded, k-attribute, k-range, and k-list models. Demonstrates that even under strong preference... Read more
Key finding: Introduces advanced integer linear programming (ILP) models incorporating dummy variables, constraint merging, and sophisticated preprocessing to efficiently solve NP-hard maximum-size and maximum-weight stable matching... Read more
Key finding: Establishes that the optimization variants of Stable Matching and Stable Roommates with ties and incomplete lists are fixed-parameter tractable (FPT) with respect to solution size and structural parameters by presenting... Read more
2. How can algorithmic learning methods enable stable matching in large-scale, data-driven markets with uncertain or unknown preferences?
In dynamic platforms (e.g., gig economy, online marketplaces), agents’ preferences are not fully known upfront and must be learned from bandit feedback or data-driven interaction. Achieving (approximate) equilibrium stable outcomes under such uncertainty is crucial for platform viability and agent incentives. This theme investigates frameworks and algorithms for incentive-aware learning of stable matchings and market outcomes, considering complex utilities such as transferable utilities and monetary transfers.
Key finding: Develops a formal framework casting the problem of learning stable market outcomes with transferable utilities under preference uncertainty as a stochastic multi-armed bandit problem, introducing the 'Subset Instability'... Read more
3. What challenges arise from strategic behavior and gaming in algorithmic matchmaking, and how can these dynamics be understood or mitigated?
Algorithmic matchmaking systems are embedded in socio-technical settings where agents may manipulate their reported preferences or behaviors to game the system for personal advantage. Understanding the strategic interplay (moves and countermoves) between agents and matchmaking algorithms is essential for designing robust, fair, and effective systems. This theme explores models and frameworks capturing this algorithm game, including legal and distributional implications.
Key finding: Introduces a conceptual framework for analyzing the strategic dynamics between agents and automated decisionmaking algorithms in matchmaking and resource allocation, emphasizing the recursive gaming and countergaming... Read more
Key finding: Formulates a game-theoretic setting where teams strategically misreport availability in scheduling polls to maximize their relative attendance in meeting time selections. Provides algorithms to compute optimal deviations for... Read more