An Optimal Randomized Algorithm for Finding the Saddlepoint.

A saddlepoint of an n × n matrix is an entry that is the maximum of its row and the minimum of its column. Saddlepoints give the value of a two-player zero-sum game, corresponding to its pure-strategy Nash equilibria; efficiently finding a saddlepoint is thus a natural and fundamental algorithmic task.
For finding a strict saddlepoint (an entry that is the strict maximum of its row and the strict minimum of its column) we recently gave an O(n log∗ n)-time algorithm, improving the O(n log n) bounds from 1991 of Bienstock, Chung, Fredman, Schäffer, Shor, Suri and of Byrne and Vaserstein. In this paper we present an optimal O(n)-time algorithm for finding a strict saddlepoint based on random sampling. Our algorithm, like earlier approaches, accesses matrix entries only via unit-cost
binary comparisons. For finding a (non-strict) saddlepoint, we extend an existing lower bound to randomized algorithms, showing that the trivial O(n2) runtime cannot be improved even with the use of randomness.