|
Spring 2025: COL749 - Computational Social Choice Fall 2024: COL351 - Analysis and Design of Algorithms |
|
Haris Aziz, Rupert Freeman, Nisarg Shah, and Rohit Vaish Operations Research Journal paper (combines the EC 2020 paper by Freeman, Shah, and Vaish and the WINE 2020 paper by Aziz) A polynomial-time algorithm for finding a distribution over EF1 allocations that is envy-free in expectation. |
Umang Bhaskar, A R Sricharan, and Rohit Vaish APPROX 2021 Conference paper / arXiv / Video (17 min) from GAIW 2021 Resolving arbitrary envy cycles could fail to achieve EF1 even for additive chores. The paper proposes the top-trading envy cycle algorithm that guarantees EF1 for monotone chores. |
|
Ioannis Caragiannis, Aris Filos-Ratsikas, Panagiotis Kanellopoulos, and Rohit Vaish EC 2019 and Artificial Intelligence Conference paper / Journal paper / arXiv / Video (14 min) from EC 2019 / Video (30 mins) from COMSOC video seminar The paper studies computational aspects of the stable matching problem when agents have cardinal preferences and one seeks a fractional solution with high social welfare. |
|
Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish AAMAS 2018 (Best Paper Nomination) Conference paper / arXiv A polynomial-time algorithm for maximizing Nash social welfare under binary valuations. |
|
Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish EC 2018 Conference paper / arXiv An algorithmic framework for finding an allocation that is envy-free up to one good (EF1) and Pareto optimal (PO), and a 1.45-approximation algorithm for Nash social welfare. |
|
Avrim Blum, Ioannis Caragiannis, Nika Haghtalab, Ariel Procaccia, Eviatar Procaccia, and Rohit Vaish SODA 2017 Conference paper / arXiv The paper studies a semi-random model for kidney exchange with a worst-case compatibility graph and a uniformly random assignment of patient-donor pairs to hospitals. |
|
Rohit Vaish and Dinesh Garg IJCAI 2017 Conference paper Under the deferred acceptance algorithm, optimal manipulation by an agent on the proposed-to side is inconspicuous and stability-preserving. |