Formulating an n-person noncooperative game as a tensor complementarity problem

Zheng Hai Huang, Liqun Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

67 Citations (Scopus)

Abstract

In this paper, we consider a class of n-person noncooperative games, where the utility function of every player is given by a homogeneous polynomial defined by the payoff tensor of that player, which is a natural extension of the bimatrix game where the utility function of every player is given by a quadratic form defined by the payoff matrix of that player. We will call such a problem the multilinear game. We reformulate the multilinear game as a tensor complementarity problem, a generalization of the linear complementarity problem; and show that finding a Nash equilibrium point of the multilinear game is equivalent to finding a solution of the resulted tensor complementarity problem. Especially, we present an explicit relationship between the solutions of the multilinear game and the tensor complementarity problem, which builds a bridge between these two classes of problems. We also apply a smoothing-type algorithm to solve the resulted tensor complementarity problem and give some preliminary numerical results for solving the multilinear games.
Original languageEnglish
Pages (from-to)557-576
Number of pages20
JournalComputational Optimization and Applications
Volume66
Issue number3
DOIs
Publication statusPublished - 1 Apr 2017

Keywords

  • Bimatrix game
  • Game theory
  • n-person noncooperative game
  • Nash equilibrium
  • Tensor complementarity problem

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics

Cite this