An Optimal Randomized Algorithm for Finding the Saddlepoint.

Justin Dallant; Frederik Haagensen; Riko Jacob; László Kozma; Sebastian Wild

doi:10.4230/LIPICS.ESA.2024.44

An Optimal Randomized Algorithm for Finding the Saddlepoint.

Justin Dallant
, Frederik Haagensen
, Riko Jacob
, László Kozma
, Sebastian Wild

Research output: Journal Article or Conference Article in Journal › Conference article › Research › peer-review

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) 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.

Original language	English
Conference proceedings	Leibniz International Proceedings in Informatics (LIPIcs)
Volume	308
Pages (from-to)	1-12
Number of pages	12
ISSN	1868-8969
DOIs	https://doi.org/10.4230/LIPICS.ESA.2024.44
Publication status	Published - 23 Sept 2024
Event	European Symposium on Algorithms - Royal Holloway University, Egham, United Kingdom Duration: 2 Sept 2024 → 4 Sept 2024 Conference number: 32 https://algo-conference.org/2024/esa/

Conference

Conference	European Symposium on Algorithms
Number	32
Location	Royal Holloway University
Country/Territory	United Kingdom
City	Egham
Period	02/09/2024 → 04/09/2024
Internet address	https://algo-conference.org/2024/esa/

Keywords

saddlepoint
matrix-game
nash-equilibria
randomized-algorithm
time-complexity

Access to Document

10.4230/LIPICS.ESA.2024.44Licence: CC BY

https://arxiv.org/abs/2401.06512Licence: CC BY-NC-SA

Cite this

@inproceedings{4448e6289e814a2d8f2e7f20d7123fc1,

title = "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) we recently gave an O(n log∗ n)-time algorithm, improving the O(n log n) bounds from 1991 of Bienstock, Chung, Fredman, Sch{\"a}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.",

keywords = "saddlepoint, matrix-game, nash-equilibria, randomized-algorithm, time-complexity",

author = "Justin Dallant and Frederik Haagensen and Riko Jacob and L{\'a}szl{\'o} Kozma and Sebastian Wild",

note = "DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.; European Symposium on Algorithms, ESA ; Conference date: 02-09-2024 Through 04-09-2024",

year = "2024",

month = sep,

day = "23",

doi = "10.4230/LIPICS.ESA.2024.44",

language = "English",

volume = "308",

pages = "1--12",

journal = "Leibniz International Proceedings in Informatics (LIPIcs)",

issn = "1868-8969",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH",

url = "https://algo-conference.org/2024/esa/",

}

TY - GEN

T1 - An Optimal Randomized Algorithm for Finding the Saddlepoint.

AU - Dallant, Justin

AU - Haagensen, Frederik

AU - Jacob, Riko

AU - Kozma, László

AU - Wild, Sebastian

N1 - Conference code: 32

PY - 2024/9/23

Y1 - 2024/9/23

N2 - 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.

AB - 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.

KW - saddlepoint

KW - matrix-game

KW - nash-equilibria

KW - randomized-algorithm

KW - time-complexity

U2 - 10.4230/LIPICS.ESA.2024.44

DO - 10.4230/LIPICS.ESA.2024.44

M3 - Conference article

SN - 1868-8969

VL - 308

SP - 1

EP - 12

JO - Leibniz International Proceedings in Informatics (LIPIcs)

JF - Leibniz International Proceedings in Informatics (LIPIcs)

T2 - European Symposium on Algorithms

Y2 - 2 September 2024 through 4 September 2024

ER -

An Optimal Randomized Algorithm for Finding the Saddlepoint.

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this