Stackelberg Strategies for Selfish Routing in General Multicommodity Networks
Φόρτωση...
Ημερομηνία
Συγγραφείς
Karakostas, G.
Kolliopoulos, S. G.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Algorithmica
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
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.
Περιγραφή
Λέξεις-κλειδιά
selfish routing, stackelberg strategies, price of anarchy, equilibrium
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
<Go to ISI>://000262308900008
http://download.springer.com/static/pdf/251/art%253A10.1007%252Fs00453-007-9018-5.pdf?auth66=1390991993_198889fdc3792de55bb7126938b9ea23&ext=.pdf
http://download.springer.com/static/pdf/251/art%253A10.1007%252Fs00453-007-9018-5.pdf?auth66=1390991993_198889fdc3792de55bb7126938b9ea23&ext=.pdf
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών