It is well known that the Nash equilibrium in network routing games can have strictly higher cost than the optimum cost. In Stackelberg routing games, where a fraction of flow is centrally-controlled, a natural problem is to route the centrally-controlled flow such that the overall cost of the resulting equilibrium is minimized. We consider the scenario where the network administrator wants to know the minimum amount of centrally-controlled flow such that the cost of the resulting equilibrium solution is strictly less than the cost of the Nash equilibrium. We call this threshold the Stackelberg threshold and prove that for networks of parallel links with linear latency functions, it is equal to the minimum of the Nash flows on links carrying more optimum flow than Nash flow. Our approach also provides a simpler proof of characterization of the minimum fraction that must be centrally controlled to induce the optimum solution.
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
page. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
Volume (Year): 67 (2009) Issue (Month): 1 (September) Pages: 174-190 Download reference. The following formats are available: HTML
(with abstract),
plain text
(with abstract),
BibTeX,
RIS (EndNote, RefMan, ProCite),
ReDIF