Source-linked AI summary
Formulating an $n$-person noncooperative game as a tensor complementarity problem
Zheng-Hai Huang, Liqun Qi
TL;DR
The paper addresses how to formulate and solve n-person games with tensor-defined homogeneous-polynomial utilities. It introduces multilinear games, reformulates them as tensor complementarity problems, proves equivalence with Nash equilibria, and reports preliminary algorithmic results.
Problem
Finding Nash equilibria effectively in n-person noncooperative games depends on a suitable mathematical formulation, while existing bimatrix and polymatrix formulations use linear complementarity problems.
Method
The paper models player utilities as homogeneous polynomials defined by payoff tensors and reformulates the resulting multilinear game as a tensor complementarity problem.
Results
The paper proves that multilinear-game Nash equilibria are equivalent to tensor complementarity solutions and establishes an explicit one-to-one correspondence between them.
Takeaways & Limitations
The correspondence allows either the multilinear game or tensor complementarity problem to be investigated using the theory and methods of the other.
Takeaways & Limitations
The model considers Nash equilibria in mixed strategies and reports only preliminary numerical results.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper motivates extending complementarity-based formulations from two-player bimatrix and polymatrix games to n-person games with tensor-defined utilities. It introduces multilinear games and reformulates them as tensor complementarity problems, establishing solution equivalence and preliminary algorithmic results.
- Economic models commonly use n-person noncooperative games, making effective computation of Nash equilibria an important concern.
- Bimatrix games represent each player’s utility as a quadratic form and can be reformulated as linear complementarity problems.
- Polymatrix games extend bimatrix games by summing pairwise quadratic utilities and also admit linear complementarity formulations.
- Tensor complementarity problems generalize linear complementarity problems through functions defined by homogeneous polynomials of degree n, with n > 2.
- The paper defines multilinear games using player-specific payoff tensors and homogeneous polynomial utilities, then reformulates them as tensor complementarity problems.
- It proves Nash equilibrium equivalence with tensor complementarity solutions, gives an explicit correspondence, and applies a smoothing-type algorithm with preliminary numerical results.
2 Preliminaries
The preliminaries establish tensor notation, mode products, contractions, and standing dimensional assumptions used in the subsequent complementarity analysis.
- The paper assumes positive integers m1, m2, ..., mn and n > 2 unless stated otherwise, and denotes {1, 2, ..., n} by [n].
- A real n-th order tensor is a multidimensional array in R^{m1×m2×···×mn}, with equal dimensions denoted by Tn,l.
- The k-mode vector product contracts a tensor with a vector in its kth mode and produces an (n−1)-th order tensor.
- Tensor notation such as Bu1u2···un denotes successive mode products, while Bu2···un omits the first mode product.
- The preliminaries introduce derived tensors and establish derivative and inner-product identities for homogeneous tensor polynomials.
3 Description of the multilinear game
The multilinear game models finite n-player games whose mixed-strategy utilities are homogeneous polynomials defined by payoff tensors. The paper relates Nash equilibria to an optimization characterization and records scope assumptions and comparisons with polymatrix games.
- A multilinear game has n players, each with finitely many pure strategies, and represents each player’s payoff by a payoff tensor.
- Each player’s mixed strategy is a nonnegative probability vector, and a joint mixed strategy concatenates the players’ individual mixed strategies.
- The multilinear-game utility is defined from the player’s payoff tensor and the joint mixed strategy, and Nash equilibrium is characterized through an optimization problem.
- The model uses Nash equilibria in mixed strategies rather than pure strategies throughout the paper.
- Polymatrix games use sums of pairwise quadratic forms, whereas the multilinear game is presented as a more natural bimatrix extension.
- Adding a sufficiently large constant c to every payoff tensor preserves the multilinear game’s Nash equilibrium points.
4 Reformulation of the multilinear game
The paper reformulates the multilinear game as a specific tensor complementarity problem and establishes an explicit correspondence between their solutions. This connects the game-theoretic formulation to complementarity methods while retaining the bimatrix-game case as a special case.
- Special case: When n = 2, the tensor complementarity formulation reduces to a linear complementarity problem corresponding to the bimatrix game.This recovers the established two-player reformulation as a special case.
- Construction: The constructed problem TCP(q, A) imposes nonnegativity, complementarity, and a tensor-polynomial feasibility condition on y.The tensor A and vector q are built from the payoff tensors, with A y^(m−1) defined through the tensor products.
- Solution correspondence: A Nash equilibrium of the multilinear game yields a solution of TCP(q, A) through an explicit transformation defined from the equilibrium strategies.The forward relation uses y* defined by equation (4.7).
- Main result: Theorem 4.1 establishes a one-to-one correspondence between multilinear-game solutions and solutions of the constructed tensor complementarity problem.The paper describes this correspondence as a bridge between the two problem classes.
- Solution correspondence: Conversely, a TCP(q, A) solution produces a Nash equilibrium through the transformation in equation (4.8), with every block y_k* nonzero.The nonzero-block property is used to define normalized strategy vectors x_k* and establish the reverse implication.
- Existence and computation: Because the multilinear game has at least one Nash equilibrium by Nash’s result, the constructed tensor complementarity problem has at least one solution.The existence conclusion follows through the established correspondence.
5 Algorithm and numerical results
The paper applies a smoothing-type algorithm to the tensor complementarity formulation and reports preliminary numerical results for multilinear and bimatrix games. The experiments indicate that the algorithm can effectively solve the resulting complementarity problems and recover Nash equilibria.
- Algorithm: The smoothing-type algorithm solves a smooth system H(µ, y, s) = 0 while driving µ toward zero to obtain a solution of the tensor complementarity problem.The formulation uses a continuously differentiable smoothing function for µ > 0 and Newton-type iterations.
- Algorithm: Algorithm 5.1 is a globally convergent framework under suitable assumptions.The framework was proposed in prior work and is applied here to the resulting tensor complementarity problem.
- Numerical experiments: The experiments use randomly generated three-player multilinear games and test each fixed problem size ten times.Table 1 reports average, minimum, and maximum iteration counts and CPU times, together with average residuals.
- Numerical results: The tensor complementarity problems in the random experiments can be effectively solved by Algorithm 5.1, yielding Nash equilibria through Theorem 4.1.The paper then tests two specific problems to make this correspondence explicit.
- Numerical results: For the three-player specific game, Algorithm 5.1 obtains a solution in 10 iterative steps and 0.0156 seconds.The corresponding Nash equilibrium is x1* = (1.0000, 0.0000)^T, x2* = (1.0000, 0.0000, 0.0000)^T, and x3* = (1.0000, 0.0000)^T.
- Numerical results: For the Battle of the Sexes bimatrix game, Algorithm 5.1 obtains a solution in 5 iterative steps and 0.0156 seconds.The numerical results are presented as evidence that the algorithm is effective for the tensor complementarity problem.
6 Conclusions
The paper establishes an equivalence between multilinear-game Nash equilibria and solutions of a tensor complementarity problem, with a one-to-one correspondence between the solution sets. It also applies a smoothing-type algorithm and reports preliminary numerical results, while identifying the need for more effective structure-exploiting algorithms.
- Conclusions: The multilinear game is reformulated as a tensor complementarity problem, and its Nash equilibria correspond one-to-one with complementarity solutions.This correspondence allows theory and methods for either problem to be used to investigate the other.
- Conclusions: A smoothing-type algorithm is applied to the resulting tensor complementarity problem, with preliminary numerical results for multilinear games.The paper suggests designing more effective algorithms using tensor structure and homogeneous-polynomial properties.