101 citations · 211 across the 45 of their papers we have counts for
14 papers · 1 filter
Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations
Hannaneh Akrami, Kurt Mehlhorn, Masoud Seddighin +1
We consider the problem of guaranteeing maximin-share (MMS) when allocating a set of indivisible items to a set of agents with fractionally subadditive (XOS) valuations. For XOS va…
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…
Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability
Hannaneh Akrami, Bhaskar Ray Chaudhury, Martin Hoefer +6
We study the problem of allocating a set of indivisible goods among a set of agents with \emph{2-value additive valuations}. In this setting, each good is valued either or $p/q…
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…
Maximizing Nash Social Welfare in 2-Value Instances
Hannaneh Akrami, Bhaskar Ray Chaudhury, Martin Hoefer +6
We consider the problem of maximizing the Nash social welfare when allocating a set of indivisible goods to a set of agents. We study instances, in whic…
Nash Social Welfare for 2-value Instances
Hannaneh Akrami, Bhaskar Ray Chaudhury, Kurt Mehlhorn +2
This paper is merged with arXiv:2107.08965v2. We refer the reader to the full and updated version. We study the problem of allocating a set of indivisible goods among agents with 2…
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…
EFX Exists for Three Agents
Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn
We study the problem of distributing a set of indivisible items among agents with additive valuations in a manner. The fairness notion under consideration is Envy-f…
A Little Charity Guarantees Almost Envy-Freeness
Bhaskar Ray Chaudhury, Tellikepalli Kavitha, Kurt Mehlhorn +1
Fair division of indivisible goods is a very well-studied problem. The goal of this problem is to distribute goods to agents in a "fair" manner, where every agent has a val…
Combinatorial Algorithms for General Linear Arrow-Debreu Markets
Bhaskar Ray Chaudhury, Kurt Mehlhorn
We present a combinatorial algorithm for determining the market clearing prices of a general linear Arrow-Debreu market, where every agent can own multiple goods. The existing comb…
Computing Equilibria in Markets with Budget-Additive Utilities
Xiaohui Bei, Jugal Garg, Martin Hoefer +1
We present the first analysis of Fisher markets with buyers that have budget-additive utility functions. Budget-additive utilities are elementary concave functions with numerous ap…
Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design
Khaled Elbassioni, Kurt Mehlhorn, Fahimeh Ramezani
R. Lavy and C. Swamy (FOCS 2005, J. ACM 2011) introduced a general method for obtaining truthful-in-expectation mechanisms from linear programming based approximation algorithms. D…
On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets
Khaled Elbassioni, Kazuhisa Makino, Kurt Mehlhorn +1
Given two bounded convex sets $X\subseteq\RR^m$ and $Y\subseteq\RR^n,$ specified by membership oracles, and a continuous convex-concave function $F:X\times Y\to\RR$, we consider th…
Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms
George Christodoulou, Kurt Mehlhorn, Evangelia Pyrga
We reconsider the well-studied Selfish Routing game with affine latency functions. The Price of Anarchy for this class of games takes maximum value 4/3; this maximum is attained al…