Computing approximate Nash equilibria in general network revenue management games

• Published in: European journal of operational research 2014-09, Vol.237 (3), p.1008-1020
• Main Authors: Grauberger, W., Kimms, A.
• Format: Article
• Language: English
• Subjects: Algorithmic game theory; Allocations; Approximate Nash equilibria; Approximation; Competition; Computation; Equilibrium; Game theory; Heuristic; Management; Mathematical analysis; Network revenue management; Networks; Resource allocation; Revenue management; Revenues; Studies
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/j.ejor.2014.02.045

•A network revenue management problem under competition is studied.•Booking limits for competing airlines are computed.•A heuristic for computing an approximate Nash equilibrium is introduced.•Payoff values are computed on demand, i.e. there is no need to provide the complete playoff matrix in advance. Computing optimal capacity allocations in network revenue management is computationally hard. The problem of computing exact Nash equilibria in non-zero-sum games is computationally hard, too. We present a fast heuristic that, in case it cannot converge to an exact Nash equilibrium, computes an approximation to it in general network revenue management problems under competition. We also investigate the question whether it is worth taking competition into account when making (network) capacity allocation decisions. Computational results show that the payoffs in the approximate equilibria are very close to those in exact ones. Taking competition into account never leads to a lower revenue than ignoring competition, no matter what the competitor does. Since we apply linear continuous models, computation time is very short.