Game-theoretic analysis of an ancient Chinese horse race problem
Document Type
Journal article
Source Publication
Computers & Operations Research
Publication Date
7-2006
Volume
33
Issue
7
First Page
2033
Last Page
2055
Publisher
Pergamon Press
Keywords
Chinese horse race problem; Probability; Constant-sum game; Mixed strategy, Non-numeric linear programming
Abstract
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 (i) deterministic, (ii) probabilistic within the same class, and (iii) 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.
DOI
10.1016/j.cor.2004.09.039
Print ISSN
03050548
E-ISSN
1873765X
Publisher Statement
Copyright © 2004 Elsevier B.V. All rights reserved.
Access to external full text or publisher's version may require subscription.
Full-text Version
Publisher’s Version
Language
English
Recommended Citation
Leng, M., & Parlar, M. (2006). Game-theoretic analysis of an ancient Chinese horse race problem. Computers & Operations Research, 33(7), 2033-2055. doi: 10.1016/j.cor.2004.09.039