7 papers
Robust Stable Matchings: Dealing with Changes in Preferences
Rohith Reddy Gangam, Tung Mai, Nitya Raju +1
We study stable matchings that are robust to preference changes in the two-sided stable matching setting of Gale and Shapley [GS62]. Given two instances and on the same set…
Fair Rent Division: New Budget and Rent Constraints
Rohith Reddy Gangam, Shayan Taherijam, Vijay V. Vazirani
We study the classical rent division problem, where agents must allocate indivisible rooms and split a fixed total rent . The goal is to compute an envy-free (EF) alloca…
On the Core of the -Matching Game
Rohith Reddy Gangam, Shayan Taherijam, Vijay V. Vazirani
The core is a quintessential solution concept for profit sharing in cooperative game theory. An imputation allocates the worth of the given game among its agents. The imputation li…
Equitable Core Imputations for Max-Flow, MST and -Matching Games
Rohith R. Gangam, Naveen Garg, Parnian Shahkar +1
We study fair allocation of profit (or cost) for three central problems from combinatorial optimization: Max-Flow, MST and -matching. The essentially unequivocal choice of solut…
Robust Popular Matchings
Martin Bullinger, Gergely Csáji, Rohith Reddy Gangam +1
We study popularity for matchings under preferences. This solution concept captures matchings that do not lose against any other matching in a majority vote by the agents. A popula…
Stable Matching: Dealing with Changes in Preferences
Rohith Reddy Gangam, Tung Mai, Nitya Raju +1
We study stable matchings that are robust to preference changes in the two-sided stable matching setting of Gale and Shapley[GS62]. Given two instances and on the same set…
A Structural and Algorithmic Study of Stable Matching Lattices of "Nearby" Instances, with Applications
Rohith Reddy Gangam, Tung Mai, Nitya Raju +1
Recently MV18 identified and initiated work on the new problem of understanding structural relationships between the lattices of solutions of two "nearby" instances of stable match…