34 citations · 120 across the 32 of their papers we have counts for
41 papers
Competitive Equilibrium in Labor Economies through the Lens of Goods and Chores Fisher Markets
Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta +2
In this paper, we study a two-sided labor market that couples the classical Fisher market with goods and the Fisher market with bads into a single unified framework. In our model,…
Competitive Equilibrium for Chores: from Dual Eisenberg-Gale to a Fast, Greedy, LP-based Algorithm
Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta +1
We study the computation of competitive equilibrium for Fisher markets with agents and divisible chores. Competitive equilibria for chores are known to correspond to the no…
Fair and Efficient Allocation of Indivisible Chores with Surplus
Hannaneh Akrami, Bhaskar Ray Chaudhury, Jugal Garg +2
We study fair division of indivisible chores among agents with additive disutility functions. Two well-studied fairness notions for indivisible items are envy-freeness up to on…
On the Envy-free Allocation of Chores
Lang Yin, Ruta Mehta
We study the problem of allocating a set of indivisible chores to three agents, among whom two have additive cost functions, in a fair manner. Two fairness notions under considerat…
Fairness in Federated Learning via Core-Stability
Bhaskar Ray Chaudhury, Linyi Li, Mintong Kang +2
Federated learning provides an effective paradigm to jointly optimize a model benefited from rich distributed data while protecting data privacy. Nonetheless, the heterogeneity nat…
Prophet Inequalities for Cost Minimization
Vasilis Livanos, Ruta Mehta
Prophet inequalities for rewards maximization are fundamental to optimal stopping theory with extensive applications to mechanism design and online optimization. We study the \emph…
Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness
Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin +1
We study the computational complexity of finding a competitive equilibrium (CE) with chores when agents have linear preferences. CE is one of the most preferred mechanisms for allo…
EFX Allocations: Simplifications and Improvements
Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury +3
The existence of EFX allocations is a fundamental open problem in discrete fair division. Given a set of agents and indivisible goods, the goal is to determine the existence of an…
(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna
Vasilis Livanos, Ruta Mehta, Aniket Murhekar
We study the problem of finding fair and efficient allocations of a set of indivisible items to a set of agents, where each item may be a good (positively valued) for some agents a…
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…
Improving EFX Guarantees through Rainbow Cycle Number
Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn +2
We study the problem of fairly allocating a set of indivisible goods among agents with additive valuations. Envy-freeness up to any good (EFX) is arguably the most compelling f…
Competitive Allocation of a Mixed Manna
Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin +1
We study the fair division problem of allocating a mixed manna under additively separable piecewise linear concave (SPLC) utilities. A mixed manna contains goods that everyone like…
Dividing Bads is Harder than Dividing Goods: On the Complexity of Fair and Efficient Division of Chores
Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin +1
We study the chore division problem where a set of agents needs to divide a set of chores (bads) among themselves fairly and efficiently. We assume that agents have linear disutili…
Indivisible Mixed Manna: On the Computability of MMS + PO Allocations
Rucha Kulkarni, Ruta Mehta, Setareh Taki
In this paper we initiate the study of finding fair and efficient allocations of an indivisible mixed manna: Divide m indivisible items among n agents under the fairness notion of…
Fair and Efficient Allocations under Subadditive Valuations
Bhaskar Ray Chaudhury, Jugal Garg, Ruta Mehta
We study the problem of allocating a set of indivisible goods among agents with subadditive valuations in a fair and efficient manner. Envy-Freeness up to any good (EFX) is the mos…
Online Revenue Maximization for Server Pricing
Shant Boodaghians, Federico Fusco, Stefano Leonardi +2
Efficient and truthful mechanisms to price resources on remote servers/machines has been the subject of much work in recent years due to the importance of the cloud market. This pa…
Fast Algorithms for Rank-1 Bimatrix Games
Bharat Adsul, Jugal Garg, Ruta Mehta +2
The rank of a bimatrix game is the matrix rank of the sum of the two payoff matrices. This paper comprehensively analyzes games of rank one, and shows the following: (1) For a game…
Unique End of Potential Line
John Fearnley, Spencer Gordon, Ruta Mehta +1
This paper studies the complexity of problems in PPAD PLS that have unique solutions. Three well-known examples of such problems are the problem of finding a fixpoint of a c…
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…
Resource Allocation Game on Social Networks: Best Response Dynamics and Convergence
Wei-Chun Lee, Vasilis Livanos, Ruta Mehta +1
The decisions that human beings make to allocate time has significant bearing on economic output and to the sustenance of social networks. The time allocation problem motivates our…
Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium
Pravesh K. Kothari, Ruta Mehta
Several works have shown unconditional hardness (via integrality gaps) of computing equilibria using strong hierarchies of convex relaxations. Such results however only apply to th…
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…
Maximizing Profit with Convex Costs in the Random-order Model
Anupam Gupta, Ruta Mehta, Marco Molinaro
Suppose a set of requests arrives online: each request gives some value if accepted, but requires using some amount of each of resources. Our cost is a convex function of…
End of Potential Line
John Fearnley, Spencer Gordon, Ruta Mehta +1
We introduce the problem EndOfPotentialLine and the corresponding complexity class EOPL of all problems that can be reduced to it in polynomial time. This class captures problems t…