5 papers
Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores
Shant Boodaghians, Bhaskar Ray Chaudhury, Ruta Mehta
Competitive equilibrium with equal income (CEEI) is considered one of the best mechanisms to allocate a set of items among agents fairly and efficiently. In this paper, we study th…
Smoothed Complexity of 2-player Nash Equilibria
Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins +1
We prove that computing a Nash equilibrium of a two-player () game with payoffs in is PPAD-hard (under randomized reductions) even in the smoothed analysis set…
Smoothed Efficient Algorithms and Reductions for Network Coordination Games
Shant Boodaghians, Rucha Kulkarni, Ruta Mehta
Worst-case hardness results for most equilibrium computation problems have raised the need for beyond-worst-case analysis. To this end, we study the smoothed complexity of finding…
Revealed Preference Dimension via Matrix Sign Rank
Shant Boodaghians
Given a data-set of consumer behaviour, the Revealed Preference Graph succinctly encodes inferred relative preferences between observed outcomes as a directed graph. Not all graphs…
Performance Metric Elicitation from Pairwise Classifier Comparisons
Gaurush Hiranandani, Shant Boodaghians, Ruta Mehta +1
Given a binary prediction problem, which performance metric should the classifier optimize? We address this question by formalizing the problem of Metric Elicitation. The goal of m…