Csilla Bujtás, Günter Rote, and Zsolt Tuza:

Optimal strategies in fractional games: vertex cover and domination

Manuscript, May 2021, 18 pages, arXiv:2105.03890 [math.CO], submitted for publication. →BibTeX

Abstract

In a hypergraph with vertex set V and edge set E, a real-valued function f: V→[0, 1] is a fractional transversal if the sum of f(v) over all vertices v in an edge e is ≥1 for every edge eE. Its size |f| is the sum of f(v) over all vertices vV. 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.

other papers about this subject
Last update: October 27, 2021.