Title

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

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

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