THIS SITE

Information for

Tutte Colloquium - Bernhard von StengelExport this event to calendar

Friday, July 27, 2018 — 3:30 PM EDT

Title: Algorithms for Rank-1 Bimatrix Games

Speaker: Bernhard von Stengel
Affiliation: London School of Economics
Room: MC 5501

Abstract:

The rank of a bimatrix game is the matrix rank of the sum of the two payoff matrices. For a game of rank k, the set of its Nash equilibria is the intersection of a one-dimensional set of equilibria of parameterized games of rank k-1 with a hyperplane. For a game of rank 1, this is a monotonic path of solutions to a parameterized zero-sum game and hence LP. One intersection of this path with the hyperplane can be found in polynomial time by binary search. This gives a polynomial-time algorithm to find an equilibrium of a game of rank 1. On the other hand, there are rank-1 games with exponentially many equilibria, which answers an open problem by Kannan and Theobald (2010). Hence, the exponential multiplicity of equilibria does not prevent one equilibrium in polynomial time. In this spirit, we conjecture that the UNIQUENESS of an equilibrium of a rank-1 game is co-NP-hard. For games of higher rank, the parameterized equilibria of lower rank correspond to the computation of the global Newton method by Govindan and Wilson (2003), which for two-player games is a special case of Lemke's algorithm.

Joint work with Bharat Adsul, Jugal Garg, Ruta Mehta, and Milind Sohoni.

Location 
MC - Mathematics & Computer Building
5501
200 University Avenue West
Waterloo, ON N2L 3G1
Canada

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
  1. 2018 (94)
    1. August (1)
    2. July (10)
    3. June (13)
    4. May (17)
    5. April (9)
    6. March (19)
    7. February (14)
    8. January (11)
  2. 2017 (103)
    1. December (4)
    2. November (19)
    3. October (11)
    4. September (7)
    5. August (3)
    6. July (5)
    7. June (9)
    8. May (10)
    9. April (7)
    10. March (13)
    11. February (10)
    12. January (5)
  3. 2016 (137)
  4. 2015 (136)
  5. 2014 (88)
  6. 2013 (48)
  7. 2012 (39)
  8. 2011 (36)
  9. 2010 (40)
  10. 2009 (40)
  11. 2008 (39)
  12. 2007 (15)