Equilibrium Computation in Two-Player Games - Algorithms and Strategies

lecture 5 equilibrium computation in two player n.w
1 / 51
Embed
Share

Explore equilibrium computation in two-player games including concepts like NE, ?-NE, support enumeration, and more. Understand algorithms for additive ?-approximate NE, with insights on player strategies and event probabilities.

  • Equilibrium Games
  • Game Theory
  • Algorithms
  • Strategies
rayaanacharya
car_spr Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Lecture 5: Equilibrium Computation in Two-player Games Ruta Mehta

  2. Algorithms So far 2-player zero-sum Linear programming (von Neuman 28, Dantzig 51) Lemke-Howson (1964) for the general case Motivation for defining class PPAD Exponential in the worst case Problem is PPAD-complete

  3. Today: Algorithm for Additive ?-approximate NE (?-NE) Support enumeration of size log ? ?2 O(?log ?)-time NE when rank(A+B)=1. LP + 1-D fixed point Poly-time despite disconnected solutions

  4. Bob n choices Alice m choices Randomize ?1 ?? ?? ?1 ?? ?? ?1 ?? ?? ?1 ?? ?? A B

  5. ?1 ?? ?? ?1 ?? ?? ?1 ?? ?? ?1 ?? ?? A B ???? ? ???, ? NE: ???? ???? , ? ?,? [0,1] ???? + ? ? ???, ? ?-NE: ???? + ? ???? , ?

  6. ?1 ?? ?? ?1 ?? ?? ?1 ?? ?? ?1 ?? ?? A B ? ??? ?-NE: ???? + ? max ? ???? + ? max ???? ?

  7. ?1 ?? ?? ?1 ?? ?? ?1 ?? ?? ?1 ?? ?? A B Alice playing move i ???? + ? ????, ? ?1 ?-NE: ???? + ? ?????, ? ?2 Bob playing move j

  8. ???? + ? ????,? ?1 ???? + ? ?????, ? ?2 ?-NE: event ?? event ?? ?2, ?? k independent samples as per ?(w/ repetition) ? =9 ln ? Theorem:Let (? ,? ) be a NE. ? = uniform(?? ), ? = uniform ?? Then, Good= ??? ???. Pr(Good) > 0 Algorithm: ln ? ?2 time. Takes ?? Try all ??,??. ?? = ?? = ?

  9. ???? + ? ????,? ?1 ???? + ? ?????, ? ?2 ?-NE: event ?? event ?? ?2, ?? k independent samples as per ?(w/ repetition) ? =9 ln ? Theorem:Let (? ,? ) be a NE. ? = uniform(Tx ), ? = uniform ?? Then, Good= ??? ???. Pr(Good) > 0 ? ??? ?. Good?= ??? Pr(?????) < 1

  10. ? ?? ??: ???? ??? + ? ? ???? ???? + ?/3 ??1 ??1: & OR ? ? ?? ??? + ?/3 ??2 ??2: & OR ? ??3 ??? ??? + ?/3 ??3:

  11. ?) ??: ???? ??? + ? ??(?? ?) ???? ???? > ?/3 ?: ??(??1 ??1 + ?) ?: ? ?? ??? > ?/3 ??(??2 ??2 + ?) ??(??3 ?: ??? ??? > ?/3 ??3

  12. Hoeffdings inequality: Let ?1, ,?? [0,1] iid random var. V =1 ?? ? ?(?) ? 2? 2??2 ? ??? Fix y . ??= ???? , ? ??? ??~? . ? = uniform(?? ). ? = ??? . ? ? = ? ?? 2? 2??2 ??? ? ?? ? = 2? 2 ?? 9 3 ?2, ?? k independent samples as per ?(w/ repetition) ? =9 ln ?

  13. ??? ??? ? Hoeffding s inequality 2? 2 Fix y . ? = uniform(?? ). ?? 3 ? ?? ? ?? ? 2? 2 Fix x . ? = uniform(?? ). ?? 3 ?) ??(?? < ??: ???? ??? + ? < 6? 2 ???? ???? > ?/3 ?: ? 2? 2 ??1 ?? ??1 + ?: ? ?? ??? > ?/3 ?) 2? 2 ??2 ??(??2 + ?) 2? 2 ?: ??(??3 ??? ??? > ?/3 ??3 ? ??? ?) Pr(Goodc) = pr( ??? < 12? ? 2< 1

  14. ??? ??? ? Hoeffding s inequality 2? 2 Fix y . ? = uniform(?? ). ?? 3 ? ?? ? ?? ? 2? 2 Fix x . ? = uniform(?? ). ?? 3 ?) ??(?? < ??: ???? ??? + ? < 6? 2 ? ???? ???? + ?/3 2? 2 ?? ??1 ??1: Almost NE payoff! & + ?) 2? 2 ? ?? ??? + ?/3 ??(??2 ??2: & + ?) 2? 2 ??(??3 ??? ??? + ??/3 ??3: Pr(Goodc) = pr( ??? ???) < 12? ? 2< 1

  15. Constant rank games

  16. Rank of a Game: rank(A+B) (Kannan and Theobald 05) Zero-sum (? = ?) is rank-0 LP 1 ????(?)-approx for constant rank What is the complexity of constant rank games? Can we solve even rank-1 games in polynomial time? Difficulty: Disconnected solution set Exponentially many even in rank-1 games (von Stengel 12)

  17. Today: Algorithm for Additive ?-approximate NE (?-NE) Support enumeration of size log ? ?2 O(?log ?)-time NE when rank(A+B)=1. LP + 1-D fixed point Poly-time despite disconnected solutions

  18. ?? strategy gives Alice ?1 ?2 ?? ??? ? A Max payoff is max (??)? ? Complementarity ? achieves max payoff iff ?,??> 0 (??)?= max (??)? ?

  19. Polyhedra Alice Scalar variable ? ?, ??? ? ? ? ?

  20. Polyhedra Bob Alice Scalar variable ? Scalar variable ? ?, ???? ? ? ? ? ?, ??? ? ? ? ?

  21. ?, ???? ? ? ? ?, ??? ? ? ? ? ? ?,?,?,? ? ? At least the sum of max payoffs Sum of payoffs ??? + ? ? ? + ? 0

  22. ?, ???? ? ? ? ?, ??? ? ? ? ? ? ?,?,?,? ? ? At least the sum of max payoffs Sum of payoffs ??? + ? ? ? + ? = ? Complementarity 1. (?,?) is a NE 2. ? and ? are the max payoffs

  23. ?, ???? ? ? ? ?, ??? ? ? ? ? ? ?,?,?,? ? ? At least the sum of max payoffs Sum of payoffs 2-Nash ??? + ? ? ? + ? max: = ? Complementarity s.t. ?,?,?,? ? ? 1. (?,?) is a NE 2. ? and ? are the max payoffs

  24. ?, ???? ? ? 0 ???= 1 ?, ??? ? ? 0 ???= 1 ? ? 2-Nash ??? + ? ? ? + ? max: s.t. ?,?,?,? ? ? Zero-sum ? + ? = 0

  25. ?, ???? ? ? 0 ???= 1 ?, ??? ? ? 0 ???= 1 ? ? 2-Nash ??0 ? ? + ? max: s.t. ?,?,?,? ? ? Zero-sum ? + ? = 0

  26. ?, ???? ? ? 0 ???= 1 ?, ??? ? ? 0 ???= 1 ? ? 2-Nash min: ? + ? s.t. ?,?,?,? ? ? Zero-sum ? + ? = 0 Linear program

  27. Rank 1 Game ? + ? = ? ?? ?? ?? Bilinear 2-Nash ??? + ? ? ? + ? max: s.t. ?,?,?,? ? ?

  28. Rank 1 Game ? + ? = ? ?? Product of two linear terms 2-Nash ??? (???) ? + ? max: s.t. ?,?,?,? ? ? Rank 1 QP is NP-hard in general

  29. Think Big! ? + ? = ? ?? (?,?,?) Consider a space of rank-1 games S = {(?,?,?)| ? ?}

  30. Think Big! ? + ? = ? ?? (?,?,?) Consider a space of rank 1 games S = ?, ,?

  31. Think Big! (?,?,?) 2-Nash max: ??? (???) ? + ? s.t. ? ? ??? ?? ???

  32. Think Big! Consider game space S = ?, ,? 2-Nash ?? (???) ? + ? max: s.t. ? ? ?? ?? ???

  33. Think Big! Consider game space S = ?, ,? All NE of S Complementarity Captures ?(???) ? + ? max: Solutions of LP(?) ? s.t. ? ? LP(?) ??? ???

  34. ? LP(?) (?,?,?,?) Claim: ? s.t. ?T? = ?, (?, ?) is a NE of game ?,?,?

  35. ? LP(?) (?,?,?,?) Goal: NE of ?,?,? If ? one of them then done! (m-1)-dimensional space in S Claim: ? s.t. ?T? = ?, (?, ?) is a NE of game ?,?,?

  36. Goal: NE of game ?,?,? ? LP(?) ?: (?,?,?,?) ??? If ??? =? then done!

  37. Goal: NE of game ?,?,? ? LP(?) ?: (?,?,?,?) ??? If ??? =? then done! NE of game ?,?,? Fixed points of ?

  38. NE of game ?,?,? Fixed points of ? :? ? ? = [????, ????] ? LP(?) Continuous ?: (?,??,?,??) ??? ???? ????

  39. 1-D Fixed Point Lower ? Upper ???? Upper Lower ???? ???? ?

  40. 1-D Fixed Point Lower ? Upper ???? Upper Lower ???? ???? ? And so on until the difference becomes small enough

  41. ? ??? ?, ? ??? ???? ?, ? ??? ? 0 ? ??(??? ???? ? 0, ? ?? LP(?) Add all ? ??? ? ? 0 (?,?,?,?) ? s.t. ?T? = ?, Proof: 1. At any feasible point Cost of LP(?) zero. (?, ?) is a NE of game ?,?,? .

  42. ? ??? ?, ? ??? ???? ?, ? ??? ? 0 ? ??(??? ???? ? 0, ? ?? LP(?) Complementarity ??? ? = 0, ? ????? ???? ? = 0, ? ?? ? ??? ? ? = 0 (?,?,?,?) ? s.t. ?T? = ?, Proof: 1. 2. At any feasible point Cost of LP(?) zero. It is zero iff complemetarity. (?, ?) is a NE of game ?,?,? .

  43. ? ??? ?, ? ??? ???? ?, ? ??? ?, ? ???? ?, ? LP(?) ??? = ?? ??? (?,?,?,?) ? s.t. ?T? = ?, (?, ?) is a NE of game ?,?,? . Proof: 1. 2. 3. At any feasible point Cost of LP(?) zero. It is zero iff complemetarity. NE (?, ?) of ?,? = ?? ? is feasible.

  44. ? ??? ? ??? ? ???? ? ??? ???? ? LP(?) Complementarity ??? ? = 0, ? ????? ???? ? = 0, ? Complementarity ??? ? = 0, ? ???? ? = 0, ? ?? ?? (?,?,?,?) ?? ??? = ?? ??? ? s.t. ?T? = ?, (?, ?) is a NE of game ?,?,? . Proof: 1. 2. 3. At any feasible point Cost of LP(?) zero. It is zero iff complemetarity. NE (?, ?) of ?,? = ?? ? is feasible. (NE iff complementarity) cost is zero.

  45. ? ??? ? ??? ? ???? ? ??? ???? ? LP(?) Complementarity ??? ? = 0, ? ????? ???? ? = 0, ? Complementarity ??? ? = 0, ? ???? ? = 0, ? ?? ?? (?,?,?,?) ?? ?? ??? = ?T? ? ??? = ??? ? s.t. ?T? = ?, Proof: 1. 2. 3. At any feasible point Cost of LP(?) zero. It is zero iff complemetarity. NE (?, ?) of ?,? = ?? ? is feasible. (NE iff complementarity) cost is zero. Since ?T? = ? , for ? = ??? ? too (?, ?) is feasible and satisfies complementarity. (?, ?) is a NE of game ?,?,? . 4. QED

  46. What about rank-2 or more?

  47. Rank-0 (zero-sum) games LP Von Neumann (1928) ? ? = LP(?) Rank-1 games ??? ?1 ?2 Rank-2 games ? = LP(?1,?2) ??? ???

  48. Rank-0 (zero-sum) games LP Von Neumann (1928) 1-D Fixed Point Rank-1 games In P 2-D Fixed Point Rank-2 games

  49. Rank-0 (zero-sum) games LP Von Neumann (1928) 1-D Fixed Point Rank-1 games PPAD-hard in general 2-D Fixed Point Rank-2 games

  50. Rank-0 (zero-sum) games LP Von Neumann (1928) 1-D Fixed Point Rank-1 games PPAD-hard in general ? 2-D Fixed Point Rank-2 games

Related


No related presentations.

More Related Content