Name
Title | ||
|---|---|---|
On the characterization and computation of Nash equilibria on parallel networks with horizontal queues. |
Abstract | ||
|---|---|---|
We study inefficiencies in parallel networks with horizontal queues due to the selfish behavior of players, by comparing social optima to Nash equilibria. The article expands studies on routing games which traditionally model congestion with latency functions that increase with the flow on a particular link. This type of latency function cannot capture congestion effects on horizontal queues. Latencies on horizontal queues increase as a function of density, and flow can decrease with increasing latencies. This class of latency functions arises in transportation networks. For static analysis of horizontal queues on parallel-link networks, we show that there may exist multiple Nash equilibria with different total costs, which contrasts with results for increasing latency functions. We present a novel algorithm, quadratic in the number of links, for computing the Nash equilibrium that minimizes total cost (best Nash equilibrium). The relative inefficiencies of best Nash equilibria are evaluated through analysis of the price of stability, and analytical results are presented for two-link networks. Price of stability is shown to be sensitive to changes in demand when links are near capacity, and congestion mitigation strategies are discussed, motivated by our results. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/CDC.2012.6426543 | CDC |
Keywords | Field | DocType |
game theory,minimisation,network theory (graphs),parallel algorithms,queueing theory,stability,Nash equilibrium computation,congestion mitigation strategies,horizontal queues,latency function,parallel-link networks,routing games,selfish behavior,social optima,stability,static analysis,total cost minimization,transportation networks,two-link networks | Mathematical optimization,Price of stability,Latency (engineering),Computer science,Parallel algorithm,Queue,Minimisation (psychology),Queueing theory,Game theory,Nash equilibrium | Conference |
ISSN | Citations | PageRank |
0743-1546 | 7 | 0.63 |
References | Authors | |
6 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Walid Krichene | 1 | 108 | 14.02 |
| Jack Reilly | 2 | 33 | 4.49 |
| Saurabh Amin | 3 | 1122 | 87.45 |
| Alexandre M. Bayen | 4 | 1250 | 137.72 |