Akce ČVUT

PIS 24. přednáška - prof. Vlach - Závisti prostá dělení

24.11.2016   16:00

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.

PŘEDNÁŠEJÍCÍ:

Milan Vlach zakončil svá vysokoškolská studia v roce 1963 na Lomonosovově státní universitě. Od té doby působí na Matematicko-fyzikální fakultě University Karlovy. Na pozvání učil a pracoval v zahraničí na řadě evropských, severoamerických a japonských universit a výzkumných institutů. V sedmdesátých letech se podílel na zavedení vysokoškolského i středoškolského studia informatických oborů a založení universitních pracovišť zaměřených na výuku a výzkum v oblasti počítačových věd. Jeho rané práce se týkají převážně speciálních úloh lineárního programování a rozvrhování výroby. Jeho články o víceindexových dopravních problémech jsou stále citovány. Později se jeho hlavní zájem soustřeďuje na optimalizaci v podmínkách neurčitosti. S podporou japonského ministerstva školství spoluzakládá Česko-japonský seminář o rozhodování v podmínkách neurčitosti a společně s Prof. Ramíkem vydává monografii Generalized Concavity in Fuzzy Optimization and Decision Analysis. V posledních letech se věnuje převážně teorii her a jejím aplikacím na problémy nestranné alokace omezených zdrojů. Jeho článek s Prof. Sagarou v International Journal of Game Theory je jednou z mála publikovaných prací o nestranném dělení v případě neaditivní representace preferencí.

O PRAŽSKÉM INFORMATICKÉM SEMINÁŘI:

Seminář se schází vždy 4. čtvrtek v měsíci v 16 hod. (s výjimkou letních měsíců a prosince), a to buď v budově FEL ČVUT na Karlově náměstí, nebo v budově MFF UK na Malostranském náměstí.
Jeho program je tvořen hodinovou přednáškou, po níž následuje časově neomezená diskuse. Základem přednášky je něco (v mezinárodním měřítku) mimořádného nebo aspoň pozoruhodného, na co přednášející přišel a co vysvětlí způsobem srozumitelným a zajímavým i pro širší informatickou obec. Přednášky jsou standardně v angličtině.
Formát semináře připravil přípravný výbor ve složení Michal Chytil (ÚI AVČR), Pavel Kordík (FIT ČVUT), Jan Kybic (FEL ČVUT), Michal Pěchouček (FEL ČVUT), Jiří Sgall (MFF UK), Vojtěch Svátek (FIS VŠE), Michal Šorel (ÚTIA AV ČR), Filip Železný (FEL ČVUT)
Idea Pražského informatického semináře vznikla z rozhovorů představitelů několika vědeckých institucí na téma, jak odstranit zbytečnou fragmentaci informatické komunity v ČR.

Místo konání

KN:E-301, Karlovo nám. 13, Praha 2

Pořadatel

Přípravný výbor PIS

Kontaktní osoba

Přípravný výbor PIS, info@praguecomputerscience.cz, 224 35 7667

Podrobnější informace

http://www.praguecomputerscience.cz/index.php?l=cz&p=24