Tutte seminar - Bernhard von StengelExport this event to calendar

Friday, June 22, 2012 — 3:30 PM to 4:30 PM EDT

Constructing and computing equilibria for two-player games

Speaker: Bernhard von Stengel
Affiliation: London School of Economics
Room: Mathematics & Computer Building (MC) 5158

Abstract:

A bimatrix game is a two-player game in strategic form, a basic model in game theory. A Nash equilibrium is a pair of (possibly randomized) strategies, one for each player, so that no player can do better by unilaterally changing their strategy. We give an introduction to the structure of Nash equilibria of bimatrix games based on best-reply regions derived from the payoff matrices. The corresponding mathematical objects are two polytopes for the two players and their combinatorial properties. With this geometric insight, one can construct games with certain properties, and understand algorithms for computing equilibria. We explain the classic Lemke-Howson algorithm, a pivoting method similar to the simplex algorithm for linear programming, that finds one Nash equilibrium. It also shows that a generic game has an odd number of equilibria.

We describe a class of square bimatrix games for which the shortest Lemke-Howson path grows exponentially in the dimension d of the game. We construct the games using pairs of dual cyclic polytopes with 2d facets in d-space and a suitable "labelling" of their facets.

The latter result is joint work with Rahul Savani, published in: R. Savani and B. von Stengel (2006), Hard-to-Solve Bimatrix Games. Econometrica 74, 397-429.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
26
27
28
29
30
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
5
6
  1. 2021 (92)
    1. October (5)
    2. September (12)
    3. August (6)
    4. July (10)
    5. June (12)
    6. May (7)
    7. April (9)
    8. March (13)
    9. February (8)
    10. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)