Optimal strategies in fractional games: vertex cover and domination - Bujtás, Csilla (Ars mathematica contemporanea, 2024)
In a hypergraph ?${\cal H}=(V,{\cal E})$? with vertex set ?$V$? and edge set ?${\cal E}$?, a real-valued function ?$f: V → 0, 1$? is a fractional transversal if ?$\sum_{v\in E} f(v) \ge 1$? for every edge ?$E \in {\cal E}$?. Its size is ?$|f| := \sum_{v \in V} f(v)$?, and the fractional transversal number ?$τ^*({\cal H})$? 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.
Keywords: fractional domination game; fractional transversal game; fractional vertex cover