Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Dynamic Games and Applications
Published in: Dynamic Games and Applications 2/2015

01-06-2015

Transfer Implementation in Congestion Games

Author: Itai Arieli

Published in: Dynamic Games and Applications | Issue 2/2015

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We study an implementation problem faced by a planner who can influence selfish behavior in a roadway network. It is commonly known that Nash equilibrium does not necessarily minimize the total latency on a network and that levying a tax on road users that is equal to the marginal congestion effect each user causes implements the optimal latency flow. This holds, however, only under the assumption that taxes have no effect on the utility of the users. In this paper, we consider taxes that satisfy the budget balance condition and that are therefore obtained using a money transfer among the network users. Hence at every state the overall taxes imposed upon the users sum up to zero. We show that the optimal latency flow can be guaranteed as a Nash equilibrium using a simple, easily computable transfer scheme that is obtained from a fixed matrix. In addition, the resulting game remains a potential game, and the levied tax on every edge is a function of its congestion.
previous article Evolutionary Dynamics of the Handicap Principle: An Example
next article Conditions for Cooperation to be More Abundant than Defection in a Hierarchically Structured Population

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Footnotes
1
In contrast, Cole et al. [3] demonstrate that when only fixed positive taxes are allowed, calculating an approximately optimal tax scheme is NP hard.
 
2
We note that \(X\) corresponds to the set of all non-negative weights \(\{x_e\}_{e\in E}\) such that the outflow from node \(s\) and the inflow to node \(t\) are \(1\), and for any other node \(v\) the inflow to \(v\) equals the outflow from \(v\).
 
3
This standard assumption is guaranteed, for example, whenever \(x_e l''_e(x_e)+2l'_e(x_e)>0\) for every \(e\in E\) and \(x_e\in [0,1].\)
 
4
The proof of Lemma 1 is presented as part of the proof of our Main Theorem in Sect. 2.
 
5
\(\mathrm {int}(X)\) corresponds to the set of flows \(x\in X\) with \(x_e>0\) for every edge \(e\).
 
6
Note that \(\frac{\partial h}{\partial x_i}(x)=\sum _{e\in \Phi _i}\frac{\partial h}{\partial x_e}(x)\).
 
7
Note that \(h_0=\sum _{e\in E}x^*_e\tau _e\).
 
8
Note that \(V^M(X)\) is uniformly bounded by \(n\sum _{e\in E}q_e\) for every \(M\) and \(x\).
 
9
See Chapter 4.1.2 in [9] for details.
 
10
This indeed holds for many studied learning dynamics such as pairwise comparisons, projection dynamic, and better-reply dynamics, as well as whenever the potential function serves as a Lyaponov function for the learning process described in equation (7). Again, see Chapter 7.1 in [9].
 
Literature
1.
Beckmann M, McGuire CB, Winsten CB (1956) Studies in the economics of transportation. Yale University Press, New Haven, CT
2.
Bergendorff P, Hearn DW, Ramana MV (1997) Congestion toll pricing of traffic networks. In: Pardalos PM, Hearn DW, Hager WW (eds) Network optimization. Springer, Berlin, pp 51–71CrossRef
3.
4.
Cole R, Dodis Y, Roughgarden T (2003) Pricing network edges for heterogeneous selfish users. ACM symposium on theory of, computing, pp 521–530
5.
Fleischer L, Jain K, Mahdian M (2004) Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. In: Proceedings of the 45th symposium on foundations of computer science, pp 277–285
6.
Hearn DW, Ramana MV (1998) Solving congestion toll pricing models. In: Marcotte P, Nguyen S (eds) Equilibrium and advanced transportation modeling. Kluwer Academic Publishers, Dordrecht, pp 109–124CrossRef
7.
Pigou AC (1920) The economics of welfare. Macmillan, New York
8.
9.
Sandholm B (2010) Population games and evolutionary dynamics. MIT Press, Cambridge, MAMATH
10.
Sandholm WH (2007) Pigouvian pricing and stochastic evolutionary implementation. J Econ Theory 132:367–382
11.
Sandholm WH (2005) Negative externalities and evolutionary implementation. Rev Econ Stud 72:885–915
12.
Sandholm WH (2002) Evolutionary implementation and congestion pricing. Rev Econ Stud 69:667–689
13.
Smith MJ (1979) The marginal cost taxation of a transportation network. Transp Res Part B 13(3):237–242CrossRef
Metadata
Title
Transfer Implementation in Congestion Games
Author
Itai Arieli
Publication date
01-06-2015
Publisher
Springer US
Published in
Dynamic Games and Applications / Issue 2/2015
Print ISSN: 2153-0785
Electronic ISSN: 2153-0793
DOI
https://doi.org/10.1007/s13235-014-0132-0

Other articles of this Issue 2/2015

Dynamic Games and Applications 2/2015 Go to the issue

OriginalPaper

Evolutionary Dynamics of the Handicap Principle: An Example

OriginalPaper

Combinatorial Aspects of Parker’s Model

OriginalPaper

Normal Forms and Unfoldings of Singular Strategy Functions

OriginalPaper

An Effective Replicator Equation for Games with a Continuous Strategy Set

OriginalPaper

Conditions for Cooperation to be More Abundant than Defection in a Hierarchically Structured Population

EditorialNotes

Dynamic Games and Applications: Second Special Issue on Population Games: Introduction

Premium Partner

    Image Credits