An improved algorithm for finding saddlepoints of two-person zero-sum games

C. C. Byrne; L. N. Vaserstein

doi:10.1007/BF01240275

An improved algorithm for finding saddlepoints of two-person zero-sum games

C. C. Byrne, L. N. Vaserstein

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

It is well-known that one can sort (order)n real numbers in at most F₀(n) =nl - 2^l + 1 steps (comparisons), where l = [log₂n]. We snow how to find the strict saddlepoint or prove its absence in an m by n matrix, m ≤n, in at most F₀(m)+F₀(m+1)+n+m - 3 + (n-m) [log₂(m+1)] steps.

Original language	English (US)
Pages (from-to)	149-159
Number of pages	11
Journal	International Journal of Game Theory
Volume	20
Issue number	2
DOIs	https://doi.org/10.1007/BF01240275
State	Published - Jun 1991

All Science Journal Classification (ASJC) codes

Statistics and Probability
Mathematics (miscellaneous)
Social Sciences (miscellaneous)
Economics and Econometrics
Statistics, Probability and Uncertainty

Access to Document

10.1007/BF01240275

Cite this

@article{5a06901028de468b99fa16b48580090e,

title = "An improved algorithm for finding saddlepoints of two-person zero-sum games",

abstract = "It is well-known that one can sort (order)n real numbers in at most F0(n) =nl - 2l + 1 steps (comparisons), where l = [log2n]. We snow how to find the strict saddlepoint or prove its absence in an m by n matrix, m ≤n, in at most F0(m)+F0(m+1)+n+m - 3 + (n-m) [log2(m+1)] steps.",

author = "Byrne, {C. C.} and Vaserstein, {L. N.}",

year = "1991",

month = jun,

doi = "10.1007/BF01240275",

language = "English (US)",

volume = "20",

pages = "149--159",

journal = "International Journal of Game Theory",

issn = "0020-7276",

publisher = "Springer Verlag",

number = "2",

}

TY - JOUR

T1 - An improved algorithm for finding saddlepoints of two-person zero-sum games

AU - Byrne, C. C.

AU - Vaserstein, L. N.

PY - 1991/6

Y1 - 1991/6

N2 - It is well-known that one can sort (order)n real numbers in at most F0(n) =nl - 2l + 1 steps (comparisons), where l = [log2n]. We snow how to find the strict saddlepoint or prove its absence in an m by n matrix, m ≤n, in at most F0(m)+F0(m+1)+n+m - 3 + (n-m) [log2(m+1)] steps.

AB - It is well-known that one can sort (order)n real numbers in at most F0(n) =nl - 2l + 1 steps (comparisons), where l = [log2n]. We snow how to find the strict saddlepoint or prove its absence in an m by n matrix, m ≤n, in at most F0(m)+F0(m+1)+n+m - 3 + (n-m) [log2(m+1)] steps.

UR - http://www.scopus.com/inward/record.url?scp=34249919931&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34249919931&partnerID=8YFLogxK

U2 - 10.1007/BF01240275

DO - 10.1007/BF01240275

M3 - Article

AN - SCOPUS:34249919931

SN - 0020-7276

VL - 20

SP - 149

EP - 159

JO - International Journal of Game Theory

JF - International Journal of Game Theory

IS - 2

ER -

An improved algorithm for finding saddlepoints of two-person zero-sum games

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this