Αυτή την Παρασκευή θα κανω μια παρουσίαση για καποια προβλήματα σε fair division (cake-cutting problems) και εν τελει θα μιλήσω και για μια πρόσφατη δουλειά μας πανω σε αυτά με τον Γ. Αμανατίδη και άλλους συνεργάτες. Όποιος θέλει μπορεί να φέρει κάποια τούρτα για να εφαρμόσουμε τους αλγορίθμους σε πραγματικό cake
Αίθουσα A36 στις 5.
Ακολουθούν οι λεπτομέρειες της ομιλίας
Title: Maximin share allocations and other solution concepts in fair division
We study fair division problems, where a set of resources needs to be allocated to a set of agents in some fair manner.
The first part of the talk will give an overview of some solution concepts that are used in fair division, along with existing results (in particular, we will mainly discuss the notions of proportionality, envy-freeness, maximin fair shares, and competitive equilibrium from equal incomes).
In the second part of the talk, we will focus on the problem of computing maximin share guarantees, a recently introduced fairness notion. Given a set of n agents, the maximin share of a single agent is the best that he can guarantee to himself, if he partitions the goods into n bundles
and then let other agents choose a bundle before him (i.e., running a generalization of the cut-and-choose protocol). The objective then is to find
a partition, so that each player is guaranteed his maximin share. In
the presence of indivisible goods, such allocations are not guaranteed
to exist, hence, we resort to approximation algorithms. I will present
a 2/3-approximation algorithm, which runs in polynomial time for any number of agents and goods, improving upon previous results in the literature. We will also investigate some special cases where we can provide better guarantees.
Finally, I will conclude the talk with some more open problems on fair division with either divisible or indivisible items.
Parts of this talk are based on joint work with Georgios Amanatidis, Afshin Nikzad, Amin Saberi