Στο πλαίσιο της διοργάνωσης των σεμιναρίων του τμήματος, θα πραγματοποιηθεί την Παρασκευή 13/11/2015 και ώρα 12:00 στην αίθουσα Σεμιναρίων του Τμήματος Μηχανικών Η/Υ και Πληροφορικής, ομιλία με τίτλο "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 agents express preferences over the resources through valuation functions. 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, and maximin fair shares).
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 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.