research
∙
05/08/2023
Fair and Efficient Allocation of Indivisible Chores with Surplus
We study fair division of indivisible chores among n agents with additiv...
share
research
∙
11/29/2022
On the Envy-free Allocation of Chores
We study the problem of allocating a set of indivisible chores to three ...
research
∙
11/03/2022
Fairness in Federated Learning via Core-Stability
Federated learning provides an effective paradigm to jointly optimize a ...
research
∙
09/16/2022
Prophet Inequalities for Cost Minimization
Prophet inequalities for rewards maximization are fundamental to optimal...
research
∙
05/23/2022
Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness
We study the computational complexity of finding a competitive equilibri...
research
∙
05/16/2022
EFX Allocations: Simplifications and Improvements
The existence of EFX allocations is a fundamental open problem in discre...
research
∙
02/06/2022
(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna
We study the problem of finding fair and efficient allocations of a set ...
research
∙
07/12/2021
Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores
Competitive equilibrium with equal income (CEEI) is considered one of th...
research
∙
03/02/2021
Improving EFX Guarantees through Rainbow Cycle Number
We study the problem of fairly allocating a set of indivisible goods amo...
research
∙
08/06/2020
Competitive Allocation of a Mixed Manna
We study the fair division problem of allocating a mixed manna under add...
research
∙
08/01/2020
Dividing Bads is Harder than Dividing Goods: On the Complexity of Fair and Efficient Division of Chores
We study the chore division problem where a set of agents needs to divid...
research
∙
07/17/2020
Approximating Maximin Shares with Mixed Manna
We initiate the study of fair allocations of a mixed manna under the pop...
research
∙
05/13/2020
Fair and Efficient Allocations under Subadditive Valuations
We study the problem of allocating a set of indivisible goods among agen...
research
∙
06/24/2019
Online Revenue Maximization for Server Pricing
Efficient and truthful mechanisms to price resources on remote servers/m...
research
∙
12/11/2018
Fast Algorithms for Rank-1 Bimatrix Games
The rank of a bimatrix game is the matrix rank of the sum of the two pay...
research
∙
11/09/2018
Unique End of Potential Line
This paper studies the complexity of problems in PPAD ∩ PLS that have un...
research
∙
09/07/2018
Smoothed Efficient Algorithms and Reductions for Network Coordination Games
Worst-case hardness results for most equilibrium computation problems ha...
research
∙
09/07/2018
Nash Equilibrium in Smoothed Polynomial Time for Network Coordination Games
Extensive work in the last two decades has led to deep insights into the...
research
∙
08/24/2018
Resource Allocation Game on Social Networks: Best Response Dynamics and Convergence
The decisions that human beings make to allocate time has significant be...
research
∙
06/25/2018
Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium
Several works have shown unconditional hardness (via integrality gaps) o...
research
∙
06/05/2018
Eliciting Binary Performance Metrics
Given a binary prediction problem, which performance metric should the c...
research
∙
04/22/2018
Maximizing Profit with Convex Costs in the Random-order Model
Suppose a set of requests arrives online: each request gives some value ...
research
∙
04/10/2018
End of Potential Line
We introduce the problem EndOfPotentialLine and the corresponding comple...
research
∙
02/21/2018
Universal Growth in Production Economies
We study a simple variant of the von Neumann model of an expanding econo...
research
∙
11/06/2017