34 citations · 120 across the 32 of their papers we have counts for
29 papers · 1 filter
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…
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…
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…
Universal Growth in Production Economies
Simina Brânzei, Ruta Mehta, Noam Nisan
We consider a simple variant of the von Neumann model of an expanding economy, in which multiple producers make goods according to their production function. The players trade thei…
Social welfare and profit maximization from revealed preferences
Ziwei Ji, Ruta Mehta, Matus Telgarsky
Consider the seller's problem of finding optimal prices for her (divisible) goods when faced with a set of consumers, given that she can only observe their purchased bundle…
Nash Social Welfare Approximation for Strategic Agents
Simina Brânzei, Vasilis Gkatzelis, Ruta Mehta
The fair division of resources is an important age-old problem that has led to a rich body of literature. At the center of this literature lies the question of whether there exist…
To Give or Not to Give: Fair Division for Single Minded Valuations
Simina Brânzei, Yuezhou Lv, Ruta Mehta
Single minded agents have strict preferences, in which a bundle is acceptable only if it meets a certain demand. Such preferences arise naturally in scenarios such as allocating co…
A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications
Nikhil Devanur, Jugal Garg, Ruta Mehta +2
We introduce a new class of combinatorial markets in which agents have covering constraints over resources required and are interested in delay minimization. Our market model is ap…
Settling Some Open Problems on 2-Player Symmetric Nash Equilibria
Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod
Over the years, researchers have studied the complexity of several decision versions of Nash equilibrium in (symmetric) two-player games (bimatrix games). To the best of our knowle…
Learning Economic Parameters from Revealed Preferences
Maria-Florina Balcan, Amit Daniely, Ruta Mehta +2
A recent line of work, starting with Beigman and Vohra (2006) and Zadimoghaddam and Roth (2012), has addressed the problem of {\em learning} a utility function from revealed prefer…