Optimal strategies in fractional games: vertex cover and domination

Abstract

In a hypergraph ℋ = (V, ℰ) with vertex set V and edge set ℰ, a real-valued function f: V → [0, 1] is a fractional transversal if ∑v ∈ E f(v) ≥ 1 holds for every E ∈ ℰ. Its size is |f| := ∑v ∈ V f(v), and the fractional transversal number τ*(ℋ) is the smallest possible |f|.

We consider a game scenario where two players have opposite goals, one of them trying to minimize and the other to maximize the size of a fractional transversal constructed incrementally. We prove that both players have strategies to achieve their common optimum, and they can reach their goals using rational weights.