Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/13525Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Karakostas, G. | en |
| dc.contributor.author | Kolliopoulos, S. G. | en |
| dc.date.accessioned | 2015-11-24T17:28:17Z | - |
| dc.date.available | 2015-11-24T17:28:17Z | - |
| dc.identifier.issn | 0178-4617 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/13525 | - |
| dc.rights | Default Licence | - |
| dc.subject | selfish routing | en |
| dc.subject | stackelberg strategies | en |
| dc.subject | price of anarchy | en |
| dc.subject | equilibrium | en |
| dc.title | Stackelberg Strategies for Selfish Routing in General Multicommodity Networks | en |
| heal.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.identifier.primary | DOI 10.1007/s00453-007-9018-5 | - |
| heal.identifier.secondary | <Go to ISI>://000262308900008 | - |
| heal.identifier.secondary | http://download.springer.com/static/pdf/251/art%253A10.1007%252Fs00453-007-9018-5.pdf?auth66=1390991993_198889fdc3792de55bb7126938b9ea23&ext=.pdf | - |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.publicationDate | 2009 | - |
| heal.abstract | A natural generalization of the selfish routing setting arises when some of the users obey a central coordinating authority, while the rest act selfishly. Such behavior can be modeled by dividing the users into an alpha fraction that are routed according to the central coordinator's routing strategy (Stackelberg strategy), and the remaining 1 - alpha that determine their strategy selfishly, given the routing of the coordinated users. One seeks to quantify the resulting price of anarchy, i.e., the ratio of the cost of the worst traffic equilibrium to the system optimum, as a function of alpha. It is well-known that for alpha = 0 and linear latency functions the price of anarchy is at most 4/3 (J.ACM 49, 236-259, 2002). If alpha tends to 1, the price of anarchy should also tend to 1 for any reasonable algorithm used by the coordinator. We analyze two such algorithms for Stackelberg routing, LLF and SCALE. For general topology networks, multicommodity users, and linear latency functions, we show a price of anarchy bound for SCALE which decreases from 4/3 to 1 as alpha increases from 0 to 1, and depends only on alpha. Up to this work, such a tradeoff was known only for the case of two nodes connected with parallel links (SIAM J. Comput. 33, 332 - 350, 2004), while for general networks it was not clear whether such a result could be achieved, even in the single-commodity case. We show a weaker bound for LLF and also some extensions to general latency functions. The existence of a central coordinator is a rather strong requirement for a network. We show that we can do away with such a coordinator, as long as we are allowed to impose taxes ( tolls) on the edges in order to steer the selfish users towards an improved system cost. As long as there is at least a fraction a of users that pay their taxes, we show the existence of taxes that lead to the simulation of SCALE by the tax-payers. The extension of the results mentioned above quantifies the improvement on the system cost as the number of tax-evaders decreases. | en |
| heal.journalName | Algorithmica | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά). ΜΑΘ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Karakostas-2009-Stackelberg Strategi.pdf | 530.44 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
