[home] - [up] |
Abstract: In the cake cutting problem, n>=2 players want to cut a cake into n pieces so that every player gets a 'fair' share of the cake by her own measure. The talk discusses the existence and non-existence of fair, envy-free, simple and efficient protocols in certain cake cutting models.
Colloquium - 16:00
Abstract: There exists the following natural generalization of the well-known game 'Tic-Tac-Toe'. Two players, Black and White, alternately color the vertices of a hypergraph H=(V,E) in their respective color. The player who first succeeds to paint all vertices of some edge e in E in his color wins.
We investigate an asymmetric version of such games, so-called 'weak positional games'. In this variant, one player, 'Maker', wins by forming a monochromatic edge, as before; but his opponent, 'Breaker', must prevent this, he does not win by getting an edge himself but only by spoiling Makers plans.
Not much is known about the complexity of such weak games. While the symmetric version, the so-called 'strong games' are PSPACE-complete (Reisch 1980), it seems plausible that weak games are somehow simpler.
In this talk we make a first step in this direction by showing that winning positions of weak positional games on 3-uniform hypergraphs (each edge has size 3) can be detected in polynomial time.