Vortrag Prof. William S. Zwicker

Datum / Uhrzeit:
22.03.19   /  13:00 - 14:30

25.12.02 Raum 33


Einladung des Lehrstuhls "Komplexitätstheorie und Kryptologie" zu einem

Vortrag mit dem Thema

Fair Division of a Graph: Envy-Freeness up to one Good, or two

von Herrn Prof. William S. Zwicker (Union College, Schenectady, NY, USA)

(Vittorio Biló, Ioannis Caragiannis, Michelle Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S. Zwicker)


In the classical fair-division framework, agents have private measures over a continuous cake (such as the [0,1] interval) and seek to divide it in a fair way.  An allocation wherein each agent measures her own piece as largest (or tied) is "envy free" (a popular fairness criterion).  One might also demand that each agent get a contiguous piece (an interval, if the cake is [0,1]).

If we replace our cake with a finite set of indivisible objects then envy-free allocations may no longer exist, but one can always find an "EF1" division – in which any envy agent A may feel for B's share can be cancelled by pretending B no longer holds the single item (from her share) that A values most.  What is the analogue, in this setting, of "contiguous piece?"  We argue that it is "connected subgraph" by providing differing results for 2 agents, for 3, for 4, and for 5 or more, decreasingly constructive.  Each builds on a classical technique from the continuous setting – "cut-and-choose" (from the Old Testament), moving knives (à la Stromquist), and Sperner's Lemma (as applied by Su) – though interesting complications abound.  In each case the paramount question becomes "Which graphs always admit connected EF1 allocations?"


Verantwortlich für den Inhalt: E-Mail sendenWE Informatik