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 o [0, 1]

is a fractional transversal if

s u m_{v i n e} f (v) g e 1

for every edge

e i n E

. Its size is

| f | := s u m_{v i n 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.

This page was built for publication: Optimal strategies in fractional games: vertex cover and domination