The equivalence of linear programs and zero-sum games

被引:48
作者
Adler, Ilan [1 ]
机构
[1] Univ Calif Berkeley, Dept IEOR, Berkeley, CA 94720 USA
关键词
Linear programming; Zero-sum games; Minimax theorem; Strong duality; Farkas' lemma; Villes' theorem;
D O I
10.1007/s00182-012-0328-8
中图分类号
F [经济];
学科分类号
02 ;
摘要
In 1951, Dantzig showed the equivalence of linear programming problems and two-person zero-sum games. However, in the description of his reduction from linear programs to zero-sum games, he noted that there was one case in which the reduction does not work. This also led to incomplete proofs of the relationship between the Minimax Theorem of game theory and the Strong Duality Theorem of linear programming. In this note, we fill these gaps.
引用
收藏
页码:165 / 177
页数:13
相关论文
共 14 条
[1]  
Adler I, 1997, ALGORITHMICA, V12, P436
[2]  
[Anonymous], 2003, Linear programming 2: theory and extensions
[3]  
Caratheodory C., 1911, Rend. Circ. Mat. Palermo (1884-1940), V32, P193, DOI [10.1007/BF03014795, DOI 10.1007/BF03014795]
[4]  
Dantzig GB, 1951, Cowles Commission Monograph, V13, P330
[5]  
Farkas J, 1902, J REINE ANGEW MATH, V124, P1
[6]  
Gale D., 1951, Activity Analysis of Production and Allocation, P317
[7]  
Gordan P, 1873, Math. Ann, V6, P23
[8]  
Luce RD., 1989, GAMES DECISIONS INTR
[9]  
Megiddo N, 1990, CONT MATH, V114, P35
[10]  
Raghavan TES, 1994, Handbook of Game Theory, V2, P735