Combinatorial games on networks
- Speaker
- Zihui Liang
- Affiliation
- Ph.D. student in University of Electronic Science and Technology of China
- Date
- Time
- – Asia/Shanghai
- Venue
- B1-518B, Research Building 4
Abstract
We introduce new combinatorial games played on graphs that we call network-control games. These games model the influence of competing two parties aiming to control the network. In a network-control game, the players move alternatively on a given undirected graph. At each turn, a player selects an unclaimed vertex and its unclaimed neighbours within distance $t$. The goal is to decide which player claims most of the vertices. We study greedy strategies, symmetric strategies, and fully solve network-control games played on multilines, cycles and a special class of caterpillars. We develop a framework that reduces the sizes of graphs by preserving the winner of the original game. Some proofs involve computer assisted techniques. We study a relaxed version of the network-control games and prove that finding the winner in such games is a PSPACE-complete problem. We show that by changing the underlying graph slightly (by using quasi-isometries), the network-control game can be solved efficiently in the modified graph.
Schedule
- 16:20-17:20 (Time in Beijing)
- 21:20-22:20 (Time in Auckland)
- March 18, 2022 (Friday)