Abstract
Congestion occurs when there is competition for resources by selfish agents. In this paper, we are concerned with smoothing out congestion in a network of resources by using personalized well-timed incentives that are subject to budget constraints. To that end, we provide: (i) a mathematical formulation that computes equilibrium for the resource sharing congestion game with incentives and budget constraints; (ii) an integrated approach that scales to larger problems by exploiting the factored network structure and approximating the attained equilibrium; (iii) an iterative best response algorithm for solving the unconstrained version (no budget) of the resource sharing congestion game; and (iv) theoretical and empirical results (on an illustrative theme park problem) that demonstrate the usefulness of our approach.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Axelrod, R.: The Complexity of Cooperation: Agent-Based Models of Competition and Collaboration. Princeton University Press (1997)
Shoham, Y., Tennenholtz, M.: Social laws for artificial agent societies: Off-line design. Artificial Intelligence 73 (1995)
Conitzer, V., Sandholm, T.: Complexity of mechanism design. In: Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp. 103–110. Morgan Kaufmann Publishers Inc. (2002)
Nisan, N., Ronen, A.: Algorithmic mechanism design. In: Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 129–140 (1999)
Bergendorff, P., Hearn, D., Ramana, M.: Congestion toll pricing of traffic networks. Lecture Notes in Economics and Mathematical Systems, pp. 51–71 (1997)
Hearn, D., Ramana, M.: Solving congestion toll pricing models. In: Marcotte, P., Nguyen, S. (eds.) Equilibrium and Advanced Transportation Modeling, pp. 109–124. Kluwer Academic Publishers (1997)
Dybvig, P., Spatt, C.: Adoption externalities as public goods. Journal of Public Economics 20, 231–247 (1983)
Segal, I.: Contracting with externalities. The Quarterly Journal of Economics 2, 337–388 (1999)
Leyton-Brown, K., Porter, R., Prabhakar, B., Shoham, Y., Venkataraman, S.: Incentive mechanisms for smoothing out a focused demand for network resources. Computer Communications 26(3), 237–250 (2003)
Monderer, D., Tennenholtz, M.: K-implementation. Journal of Artificial Intelligence Research 21, 37–62 (2004)
Law, L.M., Huang, J., Liu, M.: Price of anarchy for congestion games in cognitive radio networks. IEEE Transactions on Wireless Communications PP(99), 1–10 (2012)
Chen, H.L., Roughgarden, T., Valiant, G.: Designing network protocols for good equilibria. SIAM Journal on Computing 39(5), 1799–1832 (2010)
Monderer, D., Shapley, L.S.: Fictitious play property for games with identical interests. Journal of Economic Theory 68(1), 258–265 (1996)
Vetta, A.: Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pp. 416–425 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Varakantham, P., Fu, N., Yeoh, W., Cheng, SF., Lau, H.C. (2013). Budgeted Personalized Incentive Approaches for Smoothing Congestion in Resource Networks. In: Perny, P., Pirlot, M., Tsoukiàs, A. (eds) Algorithmic Decision Theory. ADT 2013. Lecture Notes in Computer Science(), vol 8176. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41575-3_29
Download citation
DOI: https://doi.org/10.1007/978-3-642-41575-3_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41574-6
Online ISBN: 978-3-642-41575-3
eBook Packages: Computer ScienceComputer Science (R0)