|
|
Петербургский геометрический семинар им. А. Д. Александрова
21 марта 2022 г. 17:00–19:00, г. Санкт-Петербург, ПОМИ, наб. р. Фонтанки, 27, ауд. 203
|
|
|
|
|
|
О делении без зависти в присутствии дракона
Г. Ю. Панина Санкт-Петербургское отделение Математического института им. В. А. Стеклова Российской академии наук
|
Количество просмотров: |
Эта страница: | 123 |
|
Аннотация:
Доклад по совместной работе с Р. Живалевичем https://arxiv.org/abs/2112.12969.
We prove several results addressing the envy-free division problem in the presence of an unpredictable (secretive) player, called the "dragon". There are two basic scenarios.
1. There are r−1 players and a dragon. Once the "cake" is divided into r parts, the dragon makes his choice and grabs one of the pieces. After that the players want to divide the remaining pieces in an envy-free fashion.
2. There are r+1 players who divide the cake into r pieces. A ferocious dragon comes and swallows one of the players. The players want to cut the cake in advance in such a way that no matter who is the unlucky player swallowed by the dragon, the remaining players can share the tiles in an envy-free manner.
In both settings the players are allowed to choose degenerate pieces of the cake. Moreover, they construct in advance both a cut of the cake and a "decision tree", allowing them to minimize the uncertainty of what pieces can be given to each of the players.
|
|