CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

On the uniqueness of equilibrium in atomic splittable routing games

U. Bhaskar ; L. Fleischer ; D. Hoy ; Chien-Chung Huang (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers))
Mathematics of Operations Research (0364-765X). Vol. 40 (2015), 3, p. 634-654.
[Artikel, refereegranskad vetenskaplig]

In routing games with infinitesimal players, it follows from well-known convexity arguments that equilibria exist and are unique. In routing games with atomic players with splittable flow, equilibria exist, but uniqueness of equilibria has been demonstrated only in limited cases: in two-terminal nearly parallel graphs, when all players control the same amount of flow, and when latency functions are polynomials of degree at most three. There are no known examples of multiple equilibria in these games. In this work, we show that in contrast to routing games with infinitesimal players, atomic splittable routing games admit multiple equilibria. We demonstrate this multiplicity via two specific examples. In addition, we show that our examples are topologically minimal by giving a complete characterization of the class of network topologies for which multiple equilibria exist. Our proofs and examples are based on a novel characterization of these topologies in terms of sets of circulations.

Nyckelord: Atomic players, Multiple equilibria, Network flows, Routing game

Denna post skapades 2015-08-25. Senast ändrad 2015-10-22.
CPL Pubid: 221141


Läs direkt!

Länk till annan sajt (kan kräva inloggning)