Buying optimal payoffs in bi-matrix games.

*(English)*Zbl 1418.91120Summary: We consider non-zero sum bi-matrix games where one player presumes the role of a leader in the Stackelberg model, while the other player is her follower. We show that the leader can improve her reward if she can incentivise her follower by paying some of her own utility to the follower for assigning a particular strategy profile. Besides assuming that the follower is rational in that he tries to maximise his own payoff, we assume that he is also friendly towards his leader in that he chooses, ex aequo, the strategy suggested by her – at least as long as it does not affect his expected payoff. Assuming this friendliness is, however, disputable: one could also assume that, ex aequo, the follower acts adversarially towards his leader. We discuss these different follower behavioural models and their implications. We argue that the friendliness leads to an obligation for the leader to choose, ex aequo, an assignment that provides the highest follower return, resulting in ‘friendly incentive equilibria’. For the antagonistic assumption, the stability requirements for a strategy profile should be strengthened, comparable to the secure Nash equilibria. In general, no optimal incentive equilibrium for this condition exists, and therefore we introduce \(\varepsilon\)-optimal incentive equilibria for this case. We show that the construction of all of these incentive equilibria (and all the related leader equilibria) is tractable.

PDF
BibTeX
XML
Cite

\textit{A. Gupta} and \textit{S. Schewe}, Games 9, No. 3, Paper No. 40, 36 p. (2018; Zbl 1418.91120)

Full Text:
DOI

##### References:

[1] | Stackelberg, H.V.; ; Marktform und Gleichgewicht: Berlin, Germany 1934; . |

[2] | James, W.F.; Oligopoly and the theory of games; Advanced Textbooks in Economics: Amsterdam, The Netherlands 1977; . |

[3] | Tucker, A.W.; ; A Two-Person Dilemma: Stanford, CA, USA 1950; . |

[4] | Krishnendu, C.; Thomas, A.H.; Marcin, J.; Games with secure equilibria; Formal Methods for Components and Objects: Berlin/Heidelberg, Germnay 2005; ,141-161. · Zbl 1143.68447 |

[5] | Vincent, C.; Tuomas, S.; Computing the optimal strategy to commit to; Proceedings of the 7th ACM Conference on Electronic Commerce, EC ’06: ; ,82-90. |

[6] | Bernhard, V.S.; Shmuel, Z.; Leadership games with convex strategy sets; Games Econ. Behav.: 2010; Volume 69 ,446-457. · Zbl 1230.91022 |

[7] | Matthew, O.J.; Simon, W.; Endogenous games and mechanisms: Side payments among players; Rev. Econ. Stud.: 2005; Volume 72 ,543-566. · Zbl 1121.91013 |

[8] | Bernhard, V.S.; Shmuel, Z.; ; Leadership with Commitment to Mixed Strategies: London, UK 2004; . |

[9] | Ashton, A.; Yoav, S.; Alon, A.; Internal implementation; Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: ; Volume Volume 1 ,191-198. |

[10] | Dov, M.; Moshe, T.; K-implementation; J. Artif. Intelli. Res.: 2004; Volume 21 ,37-62. |

[11] | Harri, E.; Hämäläinen, R.P.; On affine incentives for dynamic decision problems; Dynamic Games and Applications in Economics: Berlin/Heidelberg, Germany 1986; Volume Volume 265 ,47-63. |

[12] | Harri, E.; Hämäläinen, R.P.; Incentive strategies and equilibria for dynamic games with delayed information; J. Opt. Theory Appl.: 1989; Volume 63 ,355-369. |

[13] | Oded, S.; Altruism and the quality of life; Am. Econ. Rev.: 1989; Volume 79 ,86-90. |

[14] | Oded, S.; On private charity and altruism; Pub. Choice: 1985; Volume 46 ,325-332. |

[15] | Krishnendu, C.; Thomas, A.H.; Marcin, J.; Games with secure equilibria; Theor. Comput. Sci.: 2006; Volume 365 ,67-82. · Zbl 1108.91007 |

[16] | Julie, D.P.; János, J.; Jeroen, K.; Gijs, S.; Koos, V.; Existence of secure equilibrium in multi-player games with perfect information; Mathematical Foundations of Computer Science 2014: Berlin/Heidelberg, Germany 2014; Volume Volume 8635 ,213-225. · Zbl 1427.91010 |

[17] | Gupta, A.; Schewe, S.; It Pays to Pay in Bi-Matrix Games: A Rational Explanation for Bribery; Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015): New York, NY, USA 2015; ,1361-1369. |

[18] | Tim, R.; Algorithmic game theory; Commun. ACM: 2010; . |

[19] | Dov, M.; Lloyd, S.S.; Potential games; Games Econ. Behav.: 1996; Volume 14 ,124-143. · Zbl 0862.90137 |

[20] | Constantinos, D.; Paul, W.G.; Christos, H.P.; The complexity of computing a Nash equilibrium; Commun. ACM: 2009; Volume 52 ,89-97. · Zbl 1185.91019 |

[21] | Carlton, E.; Joseph, T.; Equilibrium points of bimatrix games; J. Soc. Ind. Appl. Math.: 1964; Volume 12 ,413-423. |

[22] | John, N.; Equilibrium points in n-person games; Proc. Natl. Acad. Sci. USA: 1950; Volume 36 ,48-49. · Zbl 0036.01104 |

[23] | Narendra, K.; A new polynomial-time algorithm for linear programming; Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing;: New York, NY, USA 1984; ,302-311. |

[24] | Khachian, L.G.; A polynomial algorithm in linear programming; Doklady Akademii Nauk SSSR: 1979; Volume 244 ,1093-1096. · Zbl 0414.90086 |

[25] | Dmytro, K.; Zhengyu, Y.; Christopher, K.; Vincent, C.; Milind, T.; Stackelberg vs. nash in security games: Anextended investigation of interchangeability, equivalence, and uniqueness; J. Artif. Int. Res.: 2011; Volume 41 ,297-327. · Zbl 1241.91036 |

[26] | Eikland, K.; Berkelaar, M.; Notebaert, P.; lp_solve, a Mixed Integer Linear Programming (MILP) solver; ; . |

[27] | Richard, D.M.; Andrew, M.M.; Theodore, L.T.; Gambit: Software Tools for Game Theory; 2013; . |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.