Pražský informatický seminář

Dvacátéčtvrté setkání Pražského informatického semináře
proběhne 24. listopadu 2016
v posluchárně E-301, FEL ČVUT, Karlovo nám. 13, Praha 2.

Na programu je Milan Vlach: Závisti prostá dělení

Anotace:
Problém rozdělení dělitelného objektu mezi konečný počet osob tak, aby každý účastník dělení byl se svou částí spokojen, patří nepochybně mezi nejstarší otázky, se kterými se lidé během historie setkávali. Po formalizaci základních pojmů dělitelnosti objektu a individuální spokojenosti s rozdělením budeme při výkladu sledovat historii matematických a výpočetních modelů problému proporcionálního a závisti prostého dělení. Nejprve připomeneme klasické postupy Steinhause, Knastera a Banacha pro konstrukci proporcionálních děleni a Dubinsovo-Spanierovo výsledky o existenci řešení. V této souvislosti zmíníme i rozšíření výsledků o existenci řešení získané Sagarou a Vlachem pro závisti prostá řešení v případě neaditivních preferencí a nekonečně mnoha osob. Dále pak uvedeme nedávné algoritmické výsledky Woegingera a Sgalla, Edmondse a Pruhse, a Procaccia, které ukazuji, že v poměrně obecném standardním modelu je dosažení závisti prostého dělení prokazatelně obtížnější než dosažení jeho proporcionality a že proporcionalitě dnes rozumíme mnohem lépe než závisti.
Například víme, že ve zmíněném standardním modelu existují rychlé konečné proporcionální procedury, jejichž počet kroků lze omezit funkcí počtu účastníků nezávislou na jejich preferencích. Naproti tomu donedávna převládalo mínění, že pro závisti prostá dělení takové procedury neexistují. Závěr pak věnujeme diskusi o nedávno předloženém postupu Azize a Mackenzieho, který tuto domněnku vyvrací. Ukazuje se však, že rozdíl mezi známými dolními odhady a horním odhadem počtu kroků této procedury je neobyčejně velký a dá se tedy očekávat, že, za předpokladu korektnosti procedury, povede další zlepšování procedury k prakticky použitelnému postupu.
Bližší informace najdete na webové stránce PIS.