I recently participated in the successful doctoral defense of Rohith Reddy Gangam, a student of Vijay Vazirani at UC Irvine. His dissertation combined research from multiple papers on three topics: robust stable matching, robust popular matching, and fair core imputations.

In papers with Vijay, Tung Mai, and Nitya Raju (FSTTCS 2022, GAIW 2024, and arXiv 2026), Rohith defines a matching as “robust” if it is a stable matching for two different systems of preferences, and he studies what kinds of changes from one system of preferences to another make it possible to find these matchings. In a matching between workers and firms, if only the workers (or only the firms) change preferences, or if only one agent on the other side changes preferences, then the solutions remain well behaved, forming a distributive lattice and an integral polytope. If two on each side change preferences, the solutions don’t have these nice properties, but he can still find a stable matching in a time bound whose exponent depends on the number of agents with changed preferences (complexity class \(\mathsf{XP}\)).

Popular matching is a relaxation of stable matching, where agents can vote on whether they like one matching over another and a matching is popular if it is a Condorcet winner: in each head-to-head vote against any other matching, a majority of the agents like it better or are indifferent to the change. In situations where the allowed matched pairs do not form a complete bipartite graph, different popular matchings can have different numbers of matched pairs, and the stable matchings have the fewest; instead one often wants to find a popular matching with the most pairs. Here, Rohith has a paper with Martin Bullinger and Parnian Shahkar (AAMAS 2024, adding Gergely Csáji in an updated arXiv preprint) showing that a robust solution can be found in polynomial time when one agent changes preferences, but that the problem is already \(\mathsf{NP}\)-complete with changes from two agents, whether on the same side or opposite.

The third part was about the cores of cooperative games: some “valuation” assigns value to subsets of agents (“coalitions”), and the goal is to split the value of the whole set of players among all players in such a way that no smaller coalition could get more value by playing separately. In one of the two games that Rohith studied, the agents are edges in a maximum flow instance, and the value of a coalition is the amount of flow that can be carried using only its edges. In another, an unweighted graph with a marked root vertex has an agent for each non-root vertex, and the agents must share the costs of a minimum-weight tree connecting them to the root. As an earlier paper of Vijay showed, merely finding a value assignment (“imputation”) in the core can be unfair to some players, but Vijay defined a notion of an equitable imputation that avoids this problem. Here Rohith has 2024 and 2025 arXiv preprints with Naveen Garg, Parnian Shahkar, and Vijay and with Shayan Taherijam and Vijay. He didn’t have time to provide much detail about these in his thesis defense, but the main idea is that for these games it is infeasible to find an equitable imputation in the core, but one can find one efficiently in a restricted subset of the core, the “Owen set” defined as the optimal solution set of a dual linear program.

With his doctorate completed, Rohith is going into industry, working for a Bay Area startup in on-call debugging.

Congratulations, Rohith!

(Discuss on Mastodon)