More Web Proxy on the site http://driver.im/

Article

The Online Best Reply Algorithm for Resource Allocation Problems

Authors:

Daniel Schmand,

Andreas TönnisAuthors Info & Claims

Algorithmic Game Theory: 12th International Symposium, SAGT 2019, Athens, Greece, September 30 – October 3, 2019, Proceedings

Pages 200 - 215

https://doi.org/10.1007/978-3-030-30473-7_14

Published: 30 September 2019 Publication History

Abstract

We study the performance of a best reply algorithm for online resource allocation problems with a diseconomy of scale. In an online resource allocation problem, we are given a set of resources and a set of requests that arrive in an online manner. Each request consists of a set of feasible allocations and an allocation is a set of resources. The total cost of an allocation vector is given by the sum of the resources’ costs, where each resource’s cost depends on the total load on the resource under the allocation vector. We analyze the natural online procedure where each request is allocated greedily to a feasible set of resources that minimizes the individual cost of that particular request. In the literature, this algorithm is also known as a one-round walk in congestion games starting from the empty state. For unweighted resource allocation problems with polynomial cost functions with maximum degree d, upper bounds on the competitive ratio of this greedy algorithm were known only for the special cases . In this paper, we show a general upper bound on the competitive ratio of for the unweighted case where W denotes the Lambert-W function on . For the weighted case, we show that the competitive ratio of the greedy algorithm is bounded from above by .

References

[1]

Aland S, Dumrauf D, Gairing M, Monien B, and Schoppmann F Exact price of anarchy for polynomial congestion games SIAM J. Comput. 2011 40 1211-1233

Digital Library

[2]

Albers S Energy-efficient algorithms Commun. ACM 2010 53 5 86-96

Digital Library

[3]

Awerbuch B, Azar Y, and Epstein A The price of routing unsplittable flow SIAM J. Comput. 2013 42 1 160-177

Digital Library

[4]

Awerbuch, B., Azar, Y., Epstein, A., Mirrokni, V.S., Skopalik, A.: Fast convergence to nearly optimal solutions in potential games. In: Proceedings of the 9th ACM Conference on Electronic Commerce (EC), pp. 264–273 (2008)

[5]

Awerbuch, B., Azar, Y., Grove, E.F., Kao, M., Krishnan, P., Vitter, J.S.: Load balancing in the l norm. In: Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 383–391 (1995)

[6]

Bilò V A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games Theory Comput. Syst. 2018 62 5 1288-1317

[7]

Bilò V, Fanelli A, Flammini M, and Moscardelli L Performance of one-round walks in linear congestion games Theory Comput. Syst. 2011 49 1 24-45

Digital Library

[8]

Bilò, V., Vinci, C.: On the impact of singleton strategies in congestion games. In: Proceedings of the 25th Annual European Symposium on Algorithms (ESA), pp. 17:1–17:14 (2017)

[9]

Bjelde, A., Klimm, M., Schmand, D.: Brief announcement: approximation algorithms for unsplittable resource allocation problems with diseconomies of scale. In: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 227–229 (2017)

[10]

Caragiannis, I.: Better bounds for online load balancing on unrelated machines. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 972–981 (2008)

[11]

Caragiannis I, Flammini M, Kaklamanis C, Kanellopoulos P, and Moscardelli L Tight bounds for selfish and greedy load balancing Algorithmica 2011 61 3 606-637

Digital Library

[12]

Christodoulou G and Gairing M Price of stability in polynomial congestion games ACM Trans. Econ. Comput. 2016 4 2 10:1-10:17

Digital Library

[13]

Christodoulou, G., Gairing, M., Giannakopoulos, Y., Spirakis, P.G.: The price of stability of weighted congestion games. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 150:1–150:16 (2018)

[14]

Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 67–73 (2005)

[15]

Christodoulou G, Mirrokni VS, and Sidiropoulos A Convergence and approximation in potential games Theor. Comput. Sci. 2012 438 13-27

Digital Library

[16]

Fabrikant, A., Papadimitriou, C.H., Talwar, K.: The complexity of pure nash equilibria. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pp. 604–612 (2004)

[17]

Fanelli A, Flammini M, and Moscardelli L The speed of convergence in congestion games under best-response dynamics ACM Trans. Algorithms 2012 8 3 25:1-25:15

Digital Library

[18]

Farzad, B., Olver, N., Vetta, A.: A priority-based model of routing. Chicago J. Theor. Comput. Sci. 2008 (2008). Article 1

[19]

Goemans, M.X., Mirrokni, V.S., Vetta, A.: Sink equilibria and convergence. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 142–154 (2005)

[20]

Harks T, Heinz S, and Pfetsch ME Competitive online multicommodity routing Theory Comput. Syst. 2009 45 3 533-554

Digital Library

[21]

Harks, T., Heinz, S., Pfetsch, M.E., Vredeveld, T.: Online multicommodity routing with time windows. ZIB Report 07-22, Zuse Institute Berlin (2007)

[22]

Harks T and Klimm M On the existence of pure nash equilibria in weighted congestion games Math. Oper. Res. 2012 37 419-436

Digital Library

[23]

Klimm, M., Schmand, D., Tönnis, A.: The online best reply algorithm for resource allocation problems. CoRR abs/1805.02526. https://arxiv.org/abs/1805.02526

[24]

Makarychev, K., Sviridenko, M.: Solving optimization problems with diseconomies of scale via decoupling. In: Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 571–580 (2014)

[25]

Meyers CA and Schulz AS The complexity of welfare maximization in congestion games Networks 2012 59 2 252-260

Digital Library

[26]

Mirrokni VS and Vetta A Jansen K, Khanna S, Rolim JDP, and Ron D Convergence issues in competitive games Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 2004 Heidelberg Springer 183-194

[27]

Orlin JB, Punnen AP, and Schulz AS Approximate local search in combinatorial optimization SIAM J. Comput. 2004 33 5 1201-1214

Digital Library

[28]

Roughgarden, T.: Barriers to near-optimal equilibria. In: Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 71–80 (2014)

[29]

Roughgarden T Intrinsic robustness of the price of anarchy J. ACM 2015 62 5 32:1-32:42

Digital Library

[30]

Suri S, Tóth CD, and Zhou Y Selfish load balancing and atomic congestion games Algorithmica 2007 47 1 79-96

Digital Library

[31]

U.S. Bureau of Public Roads: Traffic assignment manual. U.S. Department of Commerce, Urban Planning Division, Washington, DC (1964)

Cited By

Paccagnan DGairing M(2024)In Congestion Games, Taxes Achieve Optimal ApproximationOperations Research10.1287/opre.2021.052672:3(966-982)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1287/opre.2021.0526
Bilò VMonaco GMoscardelli LVinci C(2022)Nash Social Welfare in Selfish and Online Load BalancingACM Transactions on Economics and Computation10.1145/354497810:2(1-41)Online publication date: 7-Oct-2022
https://dl.acm.org/doi/10.1145/3544978
Bilò VMonaco GMoscardelli LVinci C(2020)Nash Social Welfare in Selfish and Online Load BalancingWeb and Internet Economics10.1007/978-3-030-64946-3_23(323-337)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-64946-3_23
Show More Cited By

Recommendations

A Novel Hybrid Algorithm for Big Resource Allocation Problems
CIT '12: Proceedings of the 2012 IEEE 12th International Conference on Computer and Information Technology

The complexity of resource allocation problems is usually NP-complete, which makes exact method inadequate to handle Resource allocation problems, and encourages heuristic techniques to this class of problems for obtaining approximate solutions in ...
Nash Social Welfare in Selfish and Online Load Balancing
In load-balancing problems there is a set of clients, each wishing to select a resource from a set of permissible ones to execute a certain task. Each resource has a latency function, which depends on its workload, and a client’s cost is the completion ...
Optimal Posted Prices for Online Cloud Resource Allocation
Performance evaluation review

We study online resource allocation in a cloud computing platform, through a posted pricing mechanism: The cloud provider publishes a unit price for each resource type, which may vary over time; upon arrival at the cloud system, a cloud user either ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Algorithmic Game Theory: 12th International Symposium, SAGT 2019, Athens, Greece, September 30 – October 3, 2019, Proceedings

Sep 2019

400 pages

ISBN:978-3-030-30472-0

DOI:10.1007/978-3-030-30473-7

Editors:
Dimitris Fotakis
National Technical University of Athens, Athens, Greece
,
Evangelos Markakis
Athens University of Economics and Business, Athens, Greece

© Springer Nature Switzerland AG 2019.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 30 September 2019

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Paccagnan DGairing M(2024)In Congestion Games, Taxes Achieve Optimal ApproximationOperations Research10.1287/opre.2021.052672:3(966-982)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1287/opre.2021.0526
Bilò VMonaco GMoscardelli LVinci C(2022)Nash Social Welfare in Selfish and Online Load BalancingACM Transactions on Economics and Computation10.1145/354497810:2(1-41)Online publication date: 7-Oct-2022
https://dl.acm.org/doi/10.1145/3544978
Bilò VMonaco GMoscardelli LVinci C(2020)Nash Social Welfare in Selfish and Online Load BalancingWeb and Internet Economics10.1007/978-3-030-64946-3_23(323-337)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-64946-3_23
Ravindran Vijayalakshmi VSkopalik A(2020)Improving Approximate Pure Nash Equilibria in Congestion GamesWeb and Internet Economics10.1007/978-3-030-64946-3_20(280-294)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-64946-3_20
Bilò VVinci C(2020)Congestion Games with Priority-Based SchedulingAlgorithmic Game Theory10.1007/978-3-030-57980-7_5(67-82)Online publication date: 16-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-57980-7_5

View Options

View options

Media

Figures

Other

Tables

View Table of Contents