Completed
Global Newton Method [Govindan/Wilson 2003]
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Algorithms for Rank-1 Bimatrix Games
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Rank-k games
- 3 Suggested example of a rank-1 game
- 4 NE of games with parameter X
- 5 Global Newton Method [Govindan/Wilson 2003]
- 6 Rank reduction by intersection with hyperplane
- 7 works for rank 1: monotone path, unique rank-O NE
- 8 LP for zero-sum game
- 9 LP for parameterized zero-sum game
- 10 Parameterized matrix (column bonuses)
- 11 Equivalent: Parameterized objective function
- 12 "Wrap-around" hyperplane defines the path
- 13 Algorithm 1: Binary search
- 14 Algorithm 2: Enumeration
- 15 Parameterized LP [Murty 1980]
- 16 Inspired by Murty
- 17 Output efficiency
- 18 PPAD- versus NP-hardness
