Comments on J. Von Neumann's 'The Problem of Optimal Assignment in a Two-Person Game'

摘要

Certain arguments in J. von Neumann's paper reducing the optimal assignment problem to a two-person game can be simplified. A simple observation produces a proof that all vertices of the convex of solutions (or a related continuous problem) are permutations; hence, admissible solutions to the original combinatorial problem. (This is a modification of the author's proof that optimal solution to the transportation problem is integral if the row and column totals are integers.) The present proof depends on a well-known and easily verified theorem that the vertex of a convex defined by m-linear equations in n-non-negative variables (considered as a point in R sub N) has at most m positive components. (Author)