Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:A Little Charity Guarantees Almost Envy-Freeness
Speaker:Bhaskar Ray Chaudhury
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D3, D4, RG1, MMCI, D2, D5, SWS
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 13 August 2019
Duration:45 Minutes
Building:E1 4
Please note: New Room!
Fair division of indivisible goods is a very well-studied problem. The goal of this problem is to distribute m goods to n agents in a "fair" manner, where every agent has a valuation for each subset of goods. We assume general valuations.

Envy-freeness is the most extensively studied notion of fairness. However, envy-free allocations do not always exist when goods are indivisible. The notion of fairness we consider here is "envy-freeness up to any good" (EFX) where no agent envies another agent after the removal of any single good from the other agent's bundle. It is not known if such an allocation always exists even when n=3.
We show there is always a partition of the set of goods into n+1 subsets (X_1,…,X_n,P) where for i∈[n], X_i is the bundle allocated to agent i and the set P is unallocated (or donated to charity) such that we have:

1) envy-freeness up to any good,
2) no agent values P higher than her own bundle, and
3) fewer than n goods go to charity, i.e., |P|<n (typically m≫n).

Our proof is constructive. When agents have additive valuations we show that we can obtain guarantees for many other notions of fairness simultaneously.

Name(s):Bhaskar Ray Chaudhury
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Bhaskar Ray Chaudhury, 08/12/2019 02:11 PM
  • Bhaskar Ray Chaudhury, 07/15/2019 11:25 AM
  • Bhaskar Ray Chaudhury, 07/12/2019 12:57 PM
  • Bhaskar Ray Chaudhury, 07/11/2019 09:17 AM -- Created document.