Abstract
Envy-freeness up to one good (EF1) is a well-studied fairness notion for indivisible goods that addresses pairwise envy by the removal of at most one good. In the worst case, each pair of agents might require the (hypothetical) removal of a di erent good, resulting in a weak aggregate guaran- tee. We study allocations that are nearly envy-free in aggregate, and de ne a novel fairness notion based on information withholding. Under our notion, an agent can withhold (or hide) some of the goods in its bundle and reveal the remaining goods to the other agents. We observe that in prac- tice, envy-freeness can be achieved by withholding only a small number of goods overall. We show that nding allocations that withhold an optimal number of goods is computationally hard even for highly restricted classes of valuations. On our way, we show that for binary valuations, nding an envy-free allocation is NP-complete—somewhat surprisingly, this fundamental question was unresolved prior to our work. In contrast to the worst-case results, our experiments on synthetic and real-world preference data show that existing algorithms for nding EF1 allocations withhold close-to-optimal amount of information.Time
2019-08-08 14:00 ~ 15:00Speaker
Lirong Xia, Rensselaer Polytechnic Institute (RPI)Room
Room 602,School of Information Management & Engineering, Shanghai University of Finance & Economics
