Replica symmetry of the minimum matching (Q431636)

The author introduces exploration games, a type of two-person games, which are played on graphs with lengths assigned to the edges. These games are also related to Geography games as studied by \textit{E. D. Demaine} and \textit{R. A. Hearn} [in:Twenty-Third Annual IEEE Conference on Computational Complexity, IEEE Computer Soc., Los Alamitos, CA, 149--162 (2008; \url{doi:10.1109/CCC.2008.35})] from the perspective of combinatorial game theory. In some way Exploration corresponds to minimum matching while modifications of the rules will produce games corresponding to other optimization problems such as the TSP. It is shown that on certain infinite graphs with random edge lengths, Exploration has an almost surely well-defined game theoretical value. The author argues that this property is the essence of replica symmetry for the minimum matching problem.