Computing solutions of the multiclass network equilibrium problem with affine cost functions
From MaRDI portal
Abstract: We consider a nonatomic congestion game on a graph, with several classes of players. Each player wants to go from its origin vertex to its destination vertex at the minimum cost and all players of a given class share the same characteristics: cost functions on each arc, and origin-destination pair. Under some mild conditions, it is known that a Nash equilibrium exists, but the computation of an equilibrium in the multiclass case is an open problem for general functions. We consider the specific case where the cost functions are affine. We show that this problem is polynomially solvable when the number of vertices and the number of classes are fixed. In particular, it shows that the parallel-link case with a fixed number of classes is polynomially solvable. On a more practical side, we propose an extension of Lemke's algorithm able to solve this problem.
Recommendations
- A Lemke-like algorithm for the multiclass network equilibrium problem
- Equilibria in Multiclass and Multidimensional Atomic Congestion Games
- Computation of tolls in infinitely multiclass network equilibrium problems
- Equilibrium computation in atomic splittable singleton congestion games
- Algorithm for Searching an Equilibrium in a Routing Game with Piecewise Constant Cost Functions
Cites work
- scientific article; zbMATH DE number 3854804 (Why is no real title available?)
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 53115 (Why is no real title available?)
- scientific article; zbMATH DE number 1749054 (Why is no real title available?)
- scientific article; zbMATH DE number 964349 (Why is no real title available?)
- A Lemke-like algorithm for the multiclass network equilibrium problem
- A Pivotal Method for Affine Variational Inequalities
- A class of games possessing pure-strategy Nash equilibria
- A direct proof of the existence of pure strategy equilibria in games with a continuum of players
- A survey on networking games in telecommunications
- Accelerating the convergence of the diagonalization and projection algorithms for finite-dimensional variational inequalities
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Computational techniques of the simplex method
- Computing Economic Equilibria on Affine Networks with Lemke's Algorithm
- Congestion games with player-specific payoff functions
- Constructing Arrangements of Lines and Hyperplanes with Applications
- Equilibria on a Congested Transportation Network
- Equilibrium points of nonatomic games
- Generic uniqueness of equilibrium in large crowding games
- Nested monotony for variational inequalities over product of spaces and convergence of iterative algorithms
- Network flows. Theory, algorithms, and applications.
- Non-cooperative games
- On the \(\epsilon\)-perturbation method for avoiding degeneracy
- On the complexity of the parity argument and other inefficient proofs of existence
- On the solution of affine generalized Nash equilibrium problems with shared constraints by Lemke's method
- Polymatrix Games with Joint Constraints
- Settling the complexity of computing two-player Nash equilibria
- The complexity of pure Nash equilibria
- The directed subgraph homeomorphism problem
Cited in
(3)
This page was built for publication: Computing solutions of the multiclass network equilibrium problem with affine cost functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1730728)
