Bidding combinatorial games (Q6194250): Difference between revisions

Summary: Combinatorial game theory is a branch of mathematics and theoretical computer science that studies sequential 2-player games with perfect information. Normal play is the convention where a player who cannot move loses. Here, we generalize the classical alternating normal play to infinitely many game families, by means of discrete Richman auctions [\textit{M. Develin} and \textit{S. Payne}, Electron. J. Comb. 17, No. 1, Research Paper R85, 40 p. (2010; Zbl 1188.91048); \textit{R. K. Rai} et al., Int. J. Game Theory 50, No. 3, 695--728 (2021; Zbl 1478.91042); \textit{A. J. Lazarus} et al., ``Richman games'', in: R. J. Nowakowski (ed.), Games of no chance. Cambridge: Cambridge University Press. 439--449 (1996)]. We generalize the notion of a perfect play outcome, and find an exact characterization of outcome feasibility. As a main result, we prove existence of a game form for each such outcome class; then we describe their lattice structures. By imposing restrictions to the general families, such as impartial and symmetric termination, we find surprising analogies with alternating play.