Dallant, J, Haagensen, F, Jacob, R, Kozma, L and Wild, S 
ORCID: 0000-0002-6061-9177
(2024)
An Optimal Randomized Algorithm for Finding the Saddlepoint.
.
Abstract
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) an O(n log<sup>∗</sup> n)-time algorithm was recently obtained by Dallant, Haagensen, Jacob, Kozma, and Wild, 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(n<sup>2</sup>) runtime cannot be improved even with the use of randomness.
| Item Type: | Conference Item (Unspecified) |
|---|---|
| Divisions: | Faculty of Science and Engineering Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 19 Nov 2024 08:26 |
| Last Modified: | 09 Jun 2025 14:41 |
| DOI: | 10.4230/LIPIcs.ESA.2024.44 |
| Open Access URL: | https://drops.dagstuhl.de/entities/document/10.423... |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3188747 |
Altmetric
Altmetric