Key research themes
1. Under what conditions does a matching problem possess a unique stable matching, and how can these conditions be characterized using the concept of normal form and acyclic preferences?
This research area focuses on characterizing the uniqueness of stable matchings, a central question in matching theory and economics. Uniqueness is desirable as it ensures predictability, Pareto efficiency, and strategy-proofness in mechanisms. The concept of a problem's normal form—stripping preferences of irrelevant information for stable matchings—and the acyclicity condition on preferences within this normal form provide a necessary and sufficient characterization for uniqueness. This theme has significance both theoretically and practically, shedding light on market behavior and mechanism design.
2. How can many-to-many and one-sided matching problems with capacities, multiple partnerships, and complex preferences be modeled and computed to capture real-world scenarios beyond classical one-to-one matchings?
This theme investigates generalizations of classical matching models, such as many-to-many matchings with demands and capacities and one-sided many-to-many models allowing multiple edges between agents. These models apply to labor markets, sports scheduling, and kidney exchanges. They focus on stability and efficiency concepts adapted to more complex interaction patterns, developing algorithmic solutions including polynomial time algorithms and characterizations based on graph theory.
3. What algorithmic and theoretical frameworks can be used to efficiently solve graph and pattern matching problems, including order-preserving, parameterized, and quadratic assignment formulations?
This line of research studies algorithmic methods and mathematical characterizations for matching problems formulated as graph matching (quadratic assignment), order-preserving string matching, and parameterized matching. These problems arise in areas such as object categorization, music retrieval, software maintenance, and bioinformatics. Advances include continuous domain relaxations, efficient approximation algorithms, algorithms exploiting structural restrictions, and theoretical generalizations enabling practical computation.