6 papers
A Moderatorless Protocol for WEREWOLF
Naoki Kitamura, Hironori Kiya, Hirotaka Ono
Social deduction games, or hidden-role games, are multiplayer games in which players are assigned private roles and act under asymmetric information about other players' roles and…
Finding a HIST: Chordality, Structural Parameters, and Diameter
Tesshu Hanaka, Hironori Kiya, Hirotaka Ono
A homeomorphically irreducible spanning tree (HIST) is a spanning tree with no degree-2 vertices, serving as a structurally minimal backbone of a graph. While the existence of HIST…
Enforce and selective operators of combinatorial games
Tomoaki Abuku, Shun-ichi Kimura, Hironori Kiya +4
We consider an {\em enforce operator} on impartial rulesets similar to the Muller Twist and the comply/constrain operator of Smith and St\u anic\u a, 2002. Applied to the rulesets…
Turning Tiles is PSPACE-complete
Kanae Yoshiwatari, Hironori Kiya, Koki Suetsugu +2
In combinatorial game theory, the winning player for a position in normal play is analyzed and characterized via algebraic operations. Such analyses define a value for each positio…
Winner Determination Algorithms for Graph Games with Matching Structures
Tesshu Hanaka, Hironori Kiya, Hirotaka Ono +1
Cram, Domineering, and Arc Kayles are well-studied combinatorial games. They are interpreted as edge-selecting-type games on graphs, and the selected edges during a game form a mat…
Computational Complexity of Hedonic Games on Sparse Graphs
Tesshu Hanaka, Hironori Kiya, Yasuhide Maei +1
The additively separable hedonic game (ASHG) is a model of coalition formation games on graphs. In this paper, we intensively and extensively investigate the computational complexi…