Euler Complexes (Oiks)

详细信息    查看全文

• 作者：Jack Edmonds
• 关键词：exchange algorithm ; Euler complex ; simplicial pseudo-manifold ; room family ; room partition ; Euler graph ; binary matroid ; Euler binary matroid ; Nash equilibrium ; Lemke-Howson algorithm ; matching algorithm ; matroid partition algorithm
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2010
• 出版时间：1 August 2010
• 年：2010
• 卷：36
• 期：Complete
• 页码：1289-1293
• 全文大小：160 K

文摘

We present a class of instances of the existence of a second object of a specified type, in fact, of an even number of objects of a specified type, which generalizes the existence of an equilibrium for bimatrix games. The proof is an abstract generalization of the Lemke-Howson algorithm for finding an equilibrium of a bimatrix game.

Versions of this note, with various examples, were presented at a Dagstuhl conference in 2007, the Dubrovnik ECCO XXI conference in 2008, the Paris TGGT conference in 2008, and the Bonn conference, “Recent trends in Combinatorial Optimization”, proceedings: Springer, 2009. The version here is meant to be updated convenience for the session on Oiks, ISCO, 2010.