Optimal strategies in fractional games: vertex cover and domination

Abstract

In a hypergraph with vertex set $V$ and edge set $E$, a real-valued function $f:V\to [0,1]$ is a fractional transversal if ${\sum }_{v\in e}f(v)\ge 1$ for every edge $e\in E$. Its size is $|f|:={\sum }_{v\in V}f(v)$, and the fractional transversal number is the smallest possible $|f|$. We consider a game scenario where two players with opposite goals construct a fractional transversal incrementally, trying to minimize and maximize $|f|$, respectively. We prove that both players have strategies to achieve their common optimum, and they can reach their goals using rational weights.

18 pages, 1 figure