Program

Lecturers

Schedule at a glance

Monday Tuesday Wednesday Thursday Friday
09:00-09:30 Welcome Fairness Protocols Cost-sharing Mechanism Design
09:30-10:00 vs Efficiency for Fair Division (I) Problems and Fair Allocation
10:00-10:30 Preferences Problems
10:30-11:00 for Fair Division Coffee break Coffee break Coffee break Coffee break
11:00-11:30 Cake-cutting Protocols Experimental Mechanism Design
11:30-12:00 for Fair Division (II) Fair division and Fair Allocation
12:00-12:30 Problems
12:30-13:00
13:00-13:30 Lunch break Lunch break Lunch break Lunch break Lunch break
13:30-14:00
14:00-14:30 Preferences Social Event: Application Experimental Posters
14:30-15:00 for Fair Division Hiking Session Fair Division and Farewell
15:00-15:30 Coffee break
15:30-16:00 Fairness Coffee break Coffee break
16:00-16:30 vs Efficiency Posters Posters
16:30-17:00

Detailed schedule

Monday, July the 13th

Tuesday, July the 14th

Wednesday, July the 15th

Thursday, July the 16th

Friday, July the 17th

Lectures

Preferences for Fair Division

Lecturer: Jérôme Lang

The specification of a discrete fair division problem includes the agent’s preferences on the bundles of items she may possibly receive. The choice of a model of preferences (e.g., utility functions or binary relations) does not say how preferences should be elicited or specified. As there are exponentially many bundles, enumerating all possible bundles in their order of preference (or with their utility value) is infeasible in practice (except when the number of items is very small). Preference representation languages allow to express preferences over sets of bundles as succinctly as possible. The lecture will review some of these languages, both for ordinal and for cardinal preferences. We will discuss their expressivity as well as their computational and communication complexity.

Slides: Preferences for Fair Division

Fairness vs Efficiency

Lecturer: Ioannis Caragiannis

In this lecture, we will discuss the impact of fairness, as a restrictive property of allocations, to economic and computational efficiency. When the tradeoff between fairness and economic efficiency is our concern, a representative question is as follows: how close to optimality can the social welfare of a fair (e.g., proportional, envy-free) allocation can be? In the second direction, we will explore the computational hardness (inefficiency) of fair allocation problems. In the lecture, we will consider settings with both divisible and indivisible goods under simple assumptions such as additive utility functions.

Slides: Fairness vs Efficiency

Cake-cutting

Lecturer: Ulle Endriss

This lecture will be an introduction to the problem of fairly dividing a cake between several people. Here, the "cake" may stand for any kind of infinitely divisible resource, such as a piece of land or an amount of bandwidth. We will focus on classical procedures, such as cut-and-choose and divide-and-conquer, but also briefly review more recent contributions emphasising algorithmic aspects of the problem.

Slides: Cake-cutting

Protocols for Allocating Indivisible Goods

Lecturers: Ulle Endriss and Christian Klamler

This set of two lectures will focus on procedures that people can use to agree on an allocation of indivisible goods between them. This will include the adjusted-winner procedure, the descending-demand procedure, the undercut procedure, procedures based on picking sequences, and procedures based on sequences of local exchanges. We will consider these procedures from a variety of different angles: the economic fairness and efficiency properties they can guarantee, the amount of information they elicit from the participants, the kinds of assumptions they place on individual preferences, and the computational complexity of the allocation problems they allow us to solve.

Slides: Protocols for Allocating Indivisible Goods, part one

Slides: Protocols for Allocating Indivisible Goods, part two

Cost-Sharing Problems

Lecturer: Christian Klamler

Cost-sharing problems consider the fair division of costs among a set of agents. In this lecture we will discuss various cost-sharing procedures analyzed in the literature. Starting point will be the simple claims model in which a social endowment of a single good (money) has to be distributed among a group of agents with incompatible claims on it. Extensions to variable returns, network structures and the introduction of games in coalitional form will eventually lead us to one of the most famous sharing-methods, the Shapley value. Besides the algorithmic part of the procedures, special focus will be given to their normative aspects.

Slides: Cost-Sharing Problems

Experimental Fair Division

Lecturer: Dorothea Herreiner

TBA

Mechanism Design and Fair Allocation Problems

Lecturer: Gianluigi Greco

Whenever the outcome of some social choice process depends on the information collected from a number of self-interested agents, strategic issues may come into play and mechanism design techniques have to be used in order to motivate all agents to truthfully report the relevant information they own as their private knowledge. The first part of the lecture is devoted to present some general background on these techniques. In addition, it illustrates specific methods that can be applied when some kind of verification on the declarations of the agents is possible. The second part of the lecture is then devoted to analyze a class of mechanisms that naturally arise in the context of allocation problems, by proposing to interpret them in terms of well-known solution concepts for coalitional games. Complexity issues arising in this setting are also discussed, and structural requirements are investigated which can be used to identify islands of tractability.

Slides: Mechanism Design and Fair Allocation Problems

Application talks

The Italian Research Assessment Program

Lecturer: Gianluigi Greco

The Italian Agency for the Evaluation of Universities and Research Institutes has recently promoted the VQR assessment program to evaluate the quality of the whole national research production. According to the program, every University receive funds proportionally to the quality of the publications selected by the structure and submitted for the evaluation. Since publications might have authors affiliated to different Departments, distributing the funds within such substructures in a way that clearly reflects the specific contribution of each of them is not an easy task. The lecture shows that this real-world application can be modeled as an allocation problem, and that strategic issues can emerge there. Moreover, it shows that the simplest distribution rules that one may think of are unsatisfactory for a number of reasons. Eventually, desirable properties for any reasonable fair division rule are identified, and a distribution rule satisfying all of them is presented.

Slides: The Italian Research Assessment Program

Fair sharing of Earth observing satellite resources

Lecturer: Michel Lemaître

Because they are more and more costly, space projects are more and more frequently funded by several entities, which share the use of the space system. This sharing must, on the one hand, satisfy as best as possible each entity and, at the same time, be fair.

Studies on this subject have been conducted by the Office National d'Etudes et de Recherches Aérospatiales (ONERA) on behalf of the french Centre National d'Etudes Spatiales (CNES) from 2001 to 2004, in the specific context of the shared constellation of Earth observation satellites PLEIADES. This talk will give a flavor of the results of these studies.

After an exposition of the simplified problem, we will describe the different sharing principles and rules that we proposed.  Then we will give some insights into the complications of the real problem.  Last, we will give some partial issues of how the proposed protocols have been received and are currently used in practice (as far as we know), and how these applicative studies have give rise to more theoretical ones.

Slides: Fair sharing of Earth observing satellite resources

Video: The Pléiades satellite system

Application of Fair Division for High-Performance Computing platforms

Lecturer: Denis Trystram

The fair usage of the available distributed resources in a computing parallel platform is a key issue. This talk will present the problem and detail a fair sharing algorithm implemented in the job manager SLURM.

Slides: Fairness issues in new large scale parallel platforms

Posters

The following posters will be presented during the poster session.