Algorithms for Rank-1 Bimatrix Games

Algorithms for Rank-1 Bimatrix Games

Hausdorff Center for Mathematics via YouTube Direct link

Output efficiency

17 of 18

17 of 18

Output efficiency

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. 1 Intro
  2. 2 Rank-k games
  3. 3 Suggested example of a rank-1 game
  4. 4 NE of games with parameter X
  5. 5 Global Newton Method [Govindan/Wilson 2003]
  6. 6 Rank reduction by intersection with hyperplane
  7. 7 works for rank 1: monotone path, unique rank-O NE
  8. 8 LP for zero-sum game
  9. 9 LP for parameterized zero-sum game
  10. 10 Parameterized matrix (column bonuses)
  11. 11 Equivalent: Parameterized objective function
  12. 12 "Wrap-around" hyperplane defines the path
  13. 13 Algorithm 1: Binary search
  14. 14 Algorithm 2: Enumeration
  15. 15 Parameterized LP [Murty 1980]
  16. 16 Inspired by Murty
  17. 17 Output efficiency
  18. 18 PPAD- versus NP-hardness

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.