Game-theoretic analysis of an ancient Chinese horse race problem

摘要

This paper analyzes a legendary Chinese horse race problem involving the King of Qi and General Tianji which took place more than 2000 years ago. In this problem each player owns three horses of different speed classes and must choose the sequence of horses to compete against each other. Depending on the payoffs received by the players as a result of the horse races, we analyze two groups of constant-sum games. In each group, we consider three separate cases where the outcomes of the races are (ⅰ) deterministic, (ⅱ) probabilistic within the same class, and (ⅲ) probabilistic across classes. In the first group, the player who wins the majority of races receives a one-unit payoff. For this group we show analytically that the three different games with non-singular payoff matrices have the same solution where each player has a unique optimal mixed strategy with equal probabilities. For the second group of games where the payoff to a player is the total number of races his horses have won, we use linear programming with non-numeric data to show that the solution of the three games are mixed strategies given as a convex combination of two extreme points. We invoke results from information theory to prove that to maximize the opponent's "entropy" the players should use the equal probability mixed strategy that was found for the one-unit games.