Algorithms for Rank-1 Bimatrix Games

Algorithms for Rank-1 Bimatrix Games

Hausdorff Center for Mathematics via YouTube Direct link

Intro

1 of 18

1 of 18

Intro

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.