[home] - [up]


Lectures and Colloquia during the semester



February 10, 2003

Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Math building - Room MA 042           - map -
Lecture - 14:15

Gerhard Wöginger -Technische Universität Twente

Cake cutting problems

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

Martin Kutz - Freie Universität Berlin

Weak Positional Games on 3-Uniform Hypergraphs

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.


[home] - [up] - [top]