Working papers
-
A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation (a short note with Haris Aziz and Herve Moulin)
R&R in Operations Research Letters
September 2019, arXiv:1909.00740
In this note, we show that Pareto-optimal and almost-fair (Proportional up to 1 item) allocations of a mixture of indivisible goods and bads always exist and can be computed in strongly-polynomial time.
The technique is based on the trading-cycle algorithm for finding divisible Pareto-improvements from the recent working paper "Fair division with minimal sharing" with Erel Segal-Halevi and on an extension of Barman-Krishnamurthy rounding.
-
Fair Division with minimal sharing (with Erel Segal-Halevi)
August 2019, arXiv:1908.01669
slides (De Aequa Divisione workshop on Fair Division, LUISS, Rome, May 2019)
Siblings inherited several apartments would not be satisfied by an allocation giving them an apartment with probability 50% or envy-free up to one apartment. We suggest a new approach to fair division with valuable items, which bridges the modern "divisible" and "indivisible" literature: sharing minimization. The problem of sharing-minimization among fair Pareto-optimal allocations turns out to be algorithmically-tractable for almost all instances.
-
Algorithms for Competitive Division of Chores (with Simina Branzei)
July 2019, arXiv:1907.01766
slides (Algorithms Seminar, TAU, March 2019)
This is the first explicit algorithm for computing market equilibria of "non-convex" exchange economies that have disconnected equilibrium set. We avoid the "black-box" of Cell-Enumeration technique, used in the literature, by the novel approach based on enumeration of all the faces of the Pareto frontier via a simple 2-agent reduction.
The results are applied to approximately fair division of indivisible chores.
-
Protecting the Protected Group: Circumventing Harmful Fairness (with Omer Ben-Porat and Moshe Tennenholtz)
May 2019, arXiv:1905.10546
Fairness constraints used for Fair Machine Learning may harm the protected group because the "price of fairness" is reallocated to this group by self-interested decision makers (e.g., a bank giving loans).
-
A simple online fair division problem (with Herve Moulin and Anna Bogomolnaia)
R&R in Management Science
March 2019, arXiv:1903.10361
slides with a different set of results including exact Price of Fairness for general bargaining (CompEcon seminar at HUJI, May 2019)
We propose a new family of allocation rules that, using minimal statistical information about the environment, achieve fairness and welfare guarantees. These are the first results on dynamic resource allocation that combine both fairness and efficiency design objectives.
-
Feasible joint posterior beliefs (with Itai Arieli, Yakov Babichenko, and Omer Tamuz)
quite soon on arXiv.org
slides (Caltech, December 2019)
-
Second-hand social learning and (non-)importance of intermediaries (with Itai Arieli and Rann Smorodinskiy)
quite soon on arXiv.org
Selected publications
-
Competitive division of a mixed manna (with Anna Bogomolnaia, Herve Moulin, and Elena Yanovskaya)
Econometrica, 2017, vol.85:6, p.1847-1871
preprint: arXiv:1702.00616
slides (CompEcon seminar, HUJI, November 2017)
_
-
Dividing bads under additive utilities (with Anna Bogomolnaia, Herve Moulin, and Elena Yanovskaya)
Social Choice and Welfare, 2019, vol.52:3, p.395-417
preprint: arXiv:1608.01540
_
Dynamic Games and Applications, 2018, vol.8:1, p. 180-198
preprint: arXiv:1509.01727
_