Skip to Main content Skip to Navigation
Journal articles

influence: a partizan scoring game on graphs

Abstract : We introduce the game influence, a scoring combinatorial game, played on a directed graph where each vertex is either colored black or white. The two players, Black and White, play alternately by taking a vertex of their color and all its successors (for Black) or all its predecessors (for White). The score of each player is the number of vertices he has taken. We prove that influence is a nonzugzwang game, meaning that no player has interest to pass at any step of the game, and thus belongs to Milnor's universe. We study this game in the particular class of paths where black and white vertices are alternated. We give an almost tight strategy for both players when there is one path. More precisely, we prove that the first player always gets a strictly better score than the second one, but that the difference between the scores is bounded by 5. Finally, we exhibit some graphs for which the initial proportion of vertices of the color of a player is as small as possible but where this player can get almost all the vertices.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03064908
Contributor : Aline Parreau Connect in order to contact the contributor
Submitted on : Monday, December 14, 2020 - 4:02:38 PM
Last modification on : Tuesday, November 9, 2021 - 10:20:08 AM
Long-term archiving on: : Monday, March 15, 2021 - 7:49:05 PM

File

Influence_subHAL.pdf
Files produced by the author(s)

Identifiers

Citation

Eric Duchene, Stéphane Gonzalez, Aline Parreau, Eric Rémila, Philippe Solal. influence: a partizan scoring game on graphs. Theoretical Computer Science, Elsevier, 2021, 878-879, pp.26-46. ⟨10.1016/j.tcs.2021.05.028⟩. ⟨hal-03064908⟩

Share

Metrics

Record views

134

Files downloads

148