### Theory Tea 2018-2019

Posted:

**Wed Jun 26, 2019 12:18 am**Αυτή την Τετάρτη, 26/6, θα μας παρουσιάσει την διπλωματική του εργασία ο Αποστόλης Ντόκος, φοιτητής του μεταπτυχιακού προγράμματος στην Επιστήμη Υπολογιστών.

Η παρουσίαση είναι στην αίθουσα Α44 στις 16:00

Ακολουθούν ο τίτλος και η περίληψη της ομιλίας.

Αποστόλης Ντόκος

Title: Algorithms for Fair Division with Indivisible Items

Abstract:

The theory of fair division addresses the fundamental problem of allocating goods, items,

tasks or chores among agents in a fair and efficient manner. Such problems arise in many real-

world settings such as government auctions or divorce settlements. To model such allocation

problems, one needs to specify the preferences of the agents, and the fairness criterion. For the preferences, the usual assumption is to associate each agent with an additive valuation

function on a set of goods. As for fairness criteria, two of the classic notions that have been

proposed are:

• proportionality: A proportional division is a division of a resource among n agents such

that each agent receives a part worth for him at least a n fraction of the whole, where

n is the number of the agents.

• envy-freeness: Envy-freeness requires that each agent prefers its own allocation over

that of any other agent.

Envy-freeness notion is stronger than proportionality one. For the divisible setting of the problem, it has been proved that there always exists an allocation that is envy-free. Furthermore, such an allocation can be computed also in polynomial time. Unfortunately, these results do not extend to the setting of indivisible goods. In fact, many of the classical solution concepts and algorithms that have been developed for divisible goods are not directly applicable to the indivisible setting. Existence of envy-free allocations cannot be guaranteed and the relevant algorithmic and approximability questions are also computationally hard. These considerations have motivated recent work in theoretical computer science on developing relevant relaxed notions of fairness. These relaxations of envy-freeness seem more appropriate for settings with indivisible items. Four such notions are: envy-freeness up to one good (EF1), envy-freeness up to any good (EFX), maximin share fairness (MMS) and pairwise maximin

share fairness (PMMS). All these capture different ways of allowing envy in an allocation. In this work, we will mainly focus on the EFX relaxation and we investigate further the issues of existence and computation. We show that in some special cases an EFX allocation can be found using polynomial time algorithms. We also examine experimentally how often an EFX allocation is also envy-free and how often an EF1 allocations is EFX, too. Finally, we examine how the number of agents and items affects the existence or not of EFX allocations.

Η παρουσίαση είναι στην αίθουσα Α44 στις 16:00

Ακολουθούν ο τίτλος και η περίληψη της ομιλίας.

Αποστόλης Ντόκος

Title: Algorithms for Fair Division with Indivisible Items

Abstract:

The theory of fair division addresses the fundamental problem of allocating goods, items,

tasks or chores among agents in a fair and efficient manner. Such problems arise in many real-

world settings such as government auctions or divorce settlements. To model such allocation

problems, one needs to specify the preferences of the agents, and the fairness criterion. For the preferences, the usual assumption is to associate each agent with an additive valuation

function on a set of goods. As for fairness criteria, two of the classic notions that have been

proposed are:

• proportionality: A proportional division is a division of a resource among n agents such

that each agent receives a part worth for him at least a n fraction of the whole, where

n is the number of the agents.

• envy-freeness: Envy-freeness requires that each agent prefers its own allocation over

that of any other agent.

Envy-freeness notion is stronger than proportionality one. For the divisible setting of the problem, it has been proved that there always exists an allocation that is envy-free. Furthermore, such an allocation can be computed also in polynomial time. Unfortunately, these results do not extend to the setting of indivisible goods. In fact, many of the classical solution concepts and algorithms that have been developed for divisible goods are not directly applicable to the indivisible setting. Existence of envy-free allocations cannot be guaranteed and the relevant algorithmic and approximability questions are also computationally hard. These considerations have motivated recent work in theoretical computer science on developing relevant relaxed notions of fairness. These relaxations of envy-freeness seem more appropriate for settings with indivisible items. Four such notions are: envy-freeness up to one good (EF1), envy-freeness up to any good (EFX), maximin share fairness (MMS) and pairwise maximin

share fairness (PMMS). All these capture different ways of allowing envy in an allocation. In this work, we will mainly focus on the EFX relaxation and we investigate further the issues of existence and computation. We show that in some special cases an EFX allocation can be found using polynomial time algorithms. We also examine experimentally how often an EFX allocation is also envy-free and how often an EF1 allocations is EFX, too. Finally, we examine how the number of agents and items affects the existence or not of EFX allocations.