8 citations · 20 across the 7 of their papers we have counts for
8 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…
Pandora's Box Problem with Order Constraints
Shant Boodaghians, Federico Fusco, Philip Lazos +1
The Pandora's Box Problem, originally formalized by Weitzman in 1979, models selection from set of random, alternative options, when evaluation is costly. This includes, for exampl…
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…
Testing Consumer Rationality using Perfect Graphs and Oriented Discs
Shant Boodaghians, Adrian Vetta
Given a consumer data-set, the axioms of revealed preference proffer a binary test for rational behaviour. A natural (non-binary) measure of the degree of rationality exhibited by…
The Combinatorial World (of Auctions) According to GARP
Shant Boodaghians, Adrian Vetta
Revealed preference techniques are used to test whether a data set is compatible with rational behaviour. They are also incorporated as constraints in mechanism design to encourage…