Sperner Oiks

Jack Edmonds; Stéphane Gaubert; Vladimir Gurvich

doi:10.1016/j.endm.2010.05.161

Sperner Oiks

Jack Edmonds
, Stéphane Gaubert
, Vladimir Gurvich

Rutgers University–New Brunswick

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

The idea of "Lemke pivoting in a family of oiks (Euler complexes)" generalizes, and abstracts to pure combinatorics, the Lemke-Howson exchange algorithm for finding a Nash equilibrium in bimatrix games, as well as the classical algorithm for finding the properly colored room in Sperner's Lemma. Given a "room-partitioning", this algorithm finds another (distinct) room-partitioning by traversing the exchange graph. In this paper we show that each family of k oiks O={O1, ... ,Ok} can be reduced to a pair of oiks O'={O1+ ... +Ok,O0} (one of which, O0, is a Sperner oik) such that the exchange graphs for O and O' are isomorphic. Numerous applications of Sperner's Lemma in combinatorial topology are well known.

langue originale	Anglais
Pages (de - à)	1273-1280
Nombre de pages	8
journal	Electronic Notes in Discrete Mathematics
Volume	36
Numéro de publication	C
Les DOIs	https://doi.org/10.1016/j.endm.2010.05.161
état	Publié - 1 janv. 2010

Accès au document

10.1016/j.endm.2010.05.161

Contient cette citation

@article{94b949b3cef443cd8526bb6a30bcab17,

title = "Sperner Oiks",

abstract = "The idea of {"}Lemke pivoting in a family of oiks (Euler complexes){"} generalizes, and abstracts to pure combinatorics, the Lemke-Howson exchange algorithm for finding a Nash equilibrium in bimatrix games, as well as the classical algorithm for finding the properly colored room in Sperner's Lemma. Given a {"}room-partitioning{"}, this algorithm finds another (distinct) room-partitioning by traversing the exchange graph. In this paper we show that each family of k oiks O=\{O1, ... ,Ok\} can be reduced to a pair of oiks O'=\{O1+ ... +Ok,O0\} (one of which, O0, is a Sperner oik) such that the exchange graphs for O and O' are isomorphic. Numerous applications of Sperner's Lemma in combinatorial topology are well known.",

keywords = "Brouwer Theorem, Euler complex (oik), Exchange algorithm, KKM-Theorem, Lemke-Howson algorithm, Manifold, Pivot, Room, Sperner Lemma, Wall",

author = "Jack Edmonds and St{\'e}phane Gaubert and Vladimir Gurvich",

year = "2010",

month = jan,

day = "1",

doi = "10.1016/j.endm.2010.05.161",

language = "English",

volume = "36",

pages = "1273--1280",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

number = "C",

}

TY - JOUR

T1 - Sperner Oiks

AU - Edmonds, Jack

AU - Gaubert, Stéphane

AU - Gurvich, Vladimir

PY - 2010/1/1

Y1 - 2010/1/1

N2 - The idea of "Lemke pivoting in a family of oiks (Euler complexes)" generalizes, and abstracts to pure combinatorics, the Lemke-Howson exchange algorithm for finding a Nash equilibrium in bimatrix games, as well as the classical algorithm for finding the properly colored room in Sperner's Lemma. Given a "room-partitioning", this algorithm finds another (distinct) room-partitioning by traversing the exchange graph. In this paper we show that each family of k oiks O={O1, ... ,Ok} can be reduced to a pair of oiks O'={O1+ ... +Ok,O0} (one of which, O0, is a Sperner oik) such that the exchange graphs for O and O' are isomorphic. Numerous applications of Sperner's Lemma in combinatorial topology are well known.

AB - The idea of "Lemke pivoting in a family of oiks (Euler complexes)" generalizes, and abstracts to pure combinatorics, the Lemke-Howson exchange algorithm for finding a Nash equilibrium in bimatrix games, as well as the classical algorithm for finding the properly colored room in Sperner's Lemma. Given a "room-partitioning", this algorithm finds another (distinct) room-partitioning by traversing the exchange graph. In this paper we show that each family of k oiks O={O1, ... ,Ok} can be reduced to a pair of oiks O'={O1+ ... +Ok,O0} (one of which, O0, is a Sperner oik) such that the exchange graphs for O and O' are isomorphic. Numerous applications of Sperner's Lemma in combinatorial topology are well known.

KW - Brouwer Theorem

KW - Euler complex (oik)

KW - Exchange algorithm

KW - KKM-Theorem

KW - Lemke-Howson algorithm

KW - Manifold

KW - Pivot

KW - Room

KW - Sperner Lemma

KW - Wall

U2 - 10.1016/j.endm.2010.05.161

DO - 10.1016/j.endm.2010.05.161

M3 - Article

AN - SCOPUS:77954943242

SN - 1571-0653

VL - 36

SP - 1273

EP - 1280

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

IS - C

ER -

Sperner Oiks

Résumé

Accès au document

Empreinte digitale

Contient cette citation