6 papers · 1 filter
Finding Representative and Approximately Efficient Committees
Dominik Peters, Rohit Vaish, Jatin Yadav
In approval-based committee voting, proportional approval voting (PAV) is a well-studied rule that combines proportional representation with Pareto efficiency. However, computing a…
Easier, but Not Easy: Nash Welfare under Lexicographic Valuations
Soumil Aggarwal, Rohit Vaish, Jatin Yadav
Maximizing Nash welfare over indivisible goods is a central problem in resource allocation. For additive valuations, the best-known approximation factor is roughly $e^{-1/e}\approx…
Best-of-Both-Worlds Guarantees with Fairer Endings
Telikepalli Kavitha, Surya Panchapakesan, Rohit Vaish +2
Fair allocation of indivisible goods is a fundamental problem at the interface of economics and computer science. Traditional approaches focus either on randomized allocations that…
Connected Equitable Cake Division via Sperner's Lemma
Umang Bhaskar, A. R. Sricharan, Rohit Vaish
We study the problem of fair cake-cutting where each agent receives a connected piece of the cake. A division of the cake is deemed fair if it is equitable, which means that all ag…
Approximating One-Sided and Two-Sided Nash Social Welfare With Capacities
Salil Gokhale, Harshul Sagar, Rohit Vaish +2
We study the problem of maximizing Nash social welfare, which is the geometric mean of agents' utilities, in two well-known models. The first model involves one-sided preferences,…
Capacity Modification in the Stable Matching Problem
Salil Gokhale, Shivika Narang, Samarth Singla +1
We study the problem of capacity modification in the many-to-one stable matching of workers and firms. Our goal is to systematically study how the set of stable matchings changes w…