Nash equilibrium design and price-based coordination in hierarchical systems

Michał P. Karpowicz

International Journal of Applied Mathematics and Computer Science (2012)

  • Volume: 22, Issue: 4, page 951-969
  • ISSN: 1641-876X

Abstract

top
This paper deals with the problem of designing Nash equilibrium points in noncooperative games in which agents anticipate values of Lagrange multipliers coordinating their payoff functions. The addressed model of agents' interactions, referred to as the price-anticipation game, is studied within the framework of coordination and mechanism design theory for hierarchical systems. Sufficient conditions are formulated for Nash implementation of a regular and isolated solution to a coordination problem. An equilibrium design procedure is proposed and applied as an analytic tool in a study of mechanism design games. In the setting considered the well-known fact is demonstrated that gains from reaching a desired solution to a coordination problem in a Nash equilibrium point need not balance the overall costs of its implementation. However, it is also demonstrated how these costs can be distributed among the agents and related to the particular organization of interactions in the system. Finally, application of the developed framework in the field of Internet traffic engineering is presented.

How to cite

top

Michał P. Karpowicz. "Nash equilibrium design and price-based coordination in hierarchical systems." International Journal of Applied Mathematics and Computer Science 22.4 (2012): 951-969. <http://eudml.org/doc/244538>.

@article{MichałP2012,
abstract = {This paper deals with the problem of designing Nash equilibrium points in noncooperative games in which agents anticipate values of Lagrange multipliers coordinating their payoff functions. The addressed model of agents' interactions, referred to as the price-anticipation game, is studied within the framework of coordination and mechanism design theory for hierarchical systems. Sufficient conditions are formulated for Nash implementation of a regular and isolated solution to a coordination problem. An equilibrium design procedure is proposed and applied as an analytic tool in a study of mechanism design games. In the setting considered the well-known fact is demonstrated that gains from reaching a desired solution to a coordination problem in a Nash equilibrium point need not balance the overall costs of its implementation. However, it is also demonstrated how these costs can be distributed among the agents and related to the particular organization of interactions in the system. Finally, application of the developed framework in the field of Internet traffic engineering is presented.},
author = {Michał P. Karpowicz},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {Nash equilibrium; coordination in hierarchical systems; decentralized control; asymmetric information},
language = {eng},
number = {4},
pages = {951-969},
title = {Nash equilibrium design and price-based coordination in hierarchical systems},
url = {http://eudml.org/doc/244538},
volume = {22},
year = {2012},
}

TY - JOUR
AU - Michał P. Karpowicz
TI - Nash equilibrium design and price-based coordination in hierarchical systems
JO - International Journal of Applied Mathematics and Computer Science
PY - 2012
VL - 22
IS - 4
SP - 951
EP - 969
AB - This paper deals with the problem of designing Nash equilibrium points in noncooperative games in which agents anticipate values of Lagrange multipliers coordinating their payoff functions. The addressed model of agents' interactions, referred to as the price-anticipation game, is studied within the framework of coordination and mechanism design theory for hierarchical systems. Sufficient conditions are formulated for Nash implementation of a regular and isolated solution to a coordination problem. An equilibrium design procedure is proposed and applied as an analytic tool in a study of mechanism design games. In the setting considered the well-known fact is demonstrated that gains from reaching a desired solution to a coordination problem in a Nash equilibrium point need not balance the overall costs of its implementation. However, it is also demonstrated how these costs can be distributed among the agents and related to the particular organization of interactions in the system. Finally, application of the developed framework in the field of Internet traffic engineering is presented.
LA - eng
KW - Nash equilibrium; coordination in hierarchical systems; decentralized control; asymmetric information
UR - http://eudml.org/doc/244538
ER -

References

top
  1. Alpcan, T. and Pavel, L. (2009). Nash equilibrium design and optimization, International Conference on Game Theory for Networks, GameNets' 09, Istanbul, Turkey, pp. 164-170. 
  2. Alpcan, T., Pavel, L. and Stefanovic, N. (2010). An optimization and control theoretic approach to noncooperative game design, arXiv:1007.0144. 
  3. Arrow, K.J. and Hurwicz, L. (1977). Studies in Resource Allocation Processes, Cambridge University Press, New York, NY. 
  4. Basar, T. and Olsder, G. J. (1999). Dynamic Noncooperative Game Theory, SIAM Classics in Applied Mathematics, SIAM, Philadelphia, PA. Zbl0946.91001
  5. Bertsekas, D. and Ozdaglar, A. (2002). Pseudonormality and a Lagrange multiplier theory for constrained optimization, Journal of Optimization Theory and Applications 114(2): 287-343. Zbl1026.90092
  6. Chao, H. and Guo, X. (2002). Quality of Service Control in High-Speed Networks, John Wiley & Sons, New York, NY. 
  7. Clempner, J.B. and Poznyak, A.S. (2011). Convergence method, properties and computational complexity for Lyapunov games, International Journal of Applied Mathematics and Computer Science 21(2): 349-361, DOI: 10.2478/v10006-011-0026-x. Zbl1272.91030
  8. Cramton, P. (1997). The FCC spectrum auctions: An early assessment, Journal of Economics and Management Strategy 6(3): 431-495. 
  9. Fiacco, A.V. and McCormick, G.P. (1990). Nonlinear Programming: Sequential Unconstrained Minimization Techniques, SIAM Classics in Applied Mathematics, SIAM, Philadelphia, PA. Zbl0713.90043
  10. Findeisen, W. (1968). Parametric optimization by primal method in multilevel systems, IEEE Transactions on Systems Science and Cybernetics 4(2): 155-164. Zbl0181.16501
  11. Findeisen, W., Bailey, F.N., Brdyś, M., Malinowski, K., Tatjewski, P. and Woźniak, A. (1980). Control and Coordination in Hierarchical Systems, John Wiley & Sons, New York, NY. Zbl0534.93002
  12. Findeisen, W., Brdyś, M., Malinowski, K., Tatjewski, P. and Woźniak, A. (1978). On-line hierarchical control for steady-state systems, IEEE Transactions on Automatic Control 23(2): 189-209. Zbl0385.93005
  13. Fudenberg, D. and Tirole, J. (1991). Game Theory, The MIT Press, Cambridge, MA. Zbl0596.90015
  14. Green, J.R. and Laffont, J.-J. (1979). Incentives in Public Decision-making, North-Holland Publishing Company, Amsterdam. Zbl0417.90001
  15. Grossman, S.J. and Stiglitz, J. (1980). On the impossibility of informationally efficient markets, American Economic Review 70(3): 393-408. 
  16. Groves, T., Radner, R. and Reiter, S. (Eds.) (1987). Information, Incentives, and Economic Mechanisms: Essays in Honor of Leonid Hurwicz, University of Minnesota Press, Mineapolis, MN. 
  17. Hurwicz, L. (1977). On Informationally Decentralized Systems, Studies in Resource Allocation Processes, Cambridge University Press, New York, NY, Chapter 4, pp. 425-459. 
  18. Hurwicz, L. (1979). On allocations attainable through Nash equilibria, Journal of Economic Theory 21(1): 140-165. Zbl0418.90009
  19. Hurwicz, L., Maskin, E. and Postlewaite, A. (1995). Feasible implementation of social choice correspondences by Nash equilibria, in J.O. Ledyard (Ed.), Essays in Honor of Stanley Reiter, Kluwer Academic Publishers, Norwell, MA, pp. 367-433. 
  20. Hurwicz, L. and Walker, M. (1990). On the generic nonoptimality of dominant-strategy allocation mechanisms: A general theorem that includes pure exchange economies, Econometrica 58(3): 683-704. Zbl0728.90027
  21. Jin, C., Wei, D., Low, S., Bunn, J., Choe, H., Doylle, J., Newman, H., Ravot, S., Singh, S. and Paganini, F. (2005). FAST TCP: From theory to experiments, IEEE Network 19(1): 4-11. 
  22. Jofré, A., Rockafellar, R. and Wets, R. (2007). Variational inequalities and economic equilibrium, Mathematics of Operations Research 32(1): 32. Zbl1276.91070
  23. Johari, R. (2004). Efficiency Loss in Market Mechanisms for Resource Allocation, Ph.D. thesis, MIT, Cambridge, MA. 
  24. Johari, R., Mannor, S. and Tsitsiklis, J.N. (2005). Efficiency loss in a network resource allocation game: The case of elastic supply, IEEE Transactions on Automatic Control 50(11): 1712-1724. 
  25. Johari, R. and Tsitsiklis, J.N. (2004). Efficiency loss in a network resource allocation game, Mathematics of Operation Research 29(3): 407-435. Zbl1082.90015
  26. Johari, R. and Tsitsiklis, J.N. (2009). Efficiency of scalar-parameterized mechanisms, Operations Research 57(4): 823-839. Zbl1233.91161
  27. Kakutani, S. (1941). A generalization of Brouwer's fixed point theorem, Duke Mathematical Journal 8(3): 457-459. Zbl67.0742.03
  28. Karpowicz, M. (2010). Coordination in Hierarchical Systems with Rational Agents, Ph.D. thesis, Warsaw University of Technology, Warsaw. Zbl1194.35486
  29. Karpowicz, M. (2011). Designing auctions: A historical perspective, Journal of Telecommunications and Information Technology 3: 114-122. 
  30. Kelly, F.P. (1997). Charging and rate control for elastic traffic, European Transactions on Telecommunications 8(1): 33-37. 
  31. Kelly, F.P., Maulloo, A.K. and Tan, D.K. (1998). Rate control for communication networks: Shadow prices, proportional fairness, and stability, Journal of the Operational Research Society 49(3): 237-252. Zbl1111.90313
  32. Kołodziej, J. and Xhafa, F. (2011). Modern approaches to modeling user requirements on resource and task allocation in hierarchical computational grids, International Journal of Applied Mathematics and Computer Science 21(2): 243-257, DOI: 10.2478/v10006-011-0018-x. 
  33. Krishna, V. (2002). Auction Theory, Academic Press, San Diego, CA. 
  34. La, R.J. and Anantharam, V. (2000). Charge-sensitive TCP and rate control in the Internet, IEEE INFOCOM 2000, TelAviv, Israel, pp. 1166-1175. 
  35. Laffont, J.-J. and Martimort, D. (2002). The Theory of Incentives, Princeton University Press, Princeton, NJ. 
  36. Low, S.H. (2003). A duality model of TCP and queue management algorithms, IEEE/ACM Transactions on Networking 11(4): 525-536. 
  37. Low, S.H. and Lapsley, D.E. (1999). Optimization flow control, I: Basic algorithm and convergence, IEEE/ACM Transactions on Networking 7(6): 861-874. 
  38. Low, S., Paganini, F., Wang, J. and Doyle, J. (2003). Linear stability of TCP/RED and a scalable control, Computer Networks 43(5): 633-647. Zbl1078.68542
  39. Low, S., Peterson, L. and Wang, L. (2002). Understanding TCP Vegas: A duality model, Journal of the ACM (JACM) 49(2): 207-235. Zbl1323.68056
  40. Lubacz, J. (Ed.) (2011). Auction Mechanisms in Telecommunications, WKŁ, Warsaw, (in Polish). 
  41. Maheswaran, R. and Basar, T. (2004). Social welfare of selfish agents: Motivating efficiency for divisible resources, Proceedings of the 43rd IEEE Conference on Decision and Control, The Bahamas. 
  42. Malinowski, K. (2002). Optimization network flow control and price coordination with feedback: Proposal of a new distributed algorithm, Computer Communications 25(11-12): 1028-1036. 
  43. Mas-Colell, A., Whinston, M.D. and Green, J.R. (1995). Microeconomic Theory, Oxford University Press, New York, NY. Zbl1256.91002
  44. Maskin, E. (1999). Nash equilibrium and welfare optimality, The Review of Economic Studies 66(1): 23-38. Zbl0956.91034
  45. Milgrom, P. (2004). Putting Auction Theory to Work, Cambridge University Press, New York, NY. 
  46. Milgrom, P. and Weber, R. (1982). A theory of auctions and competitive bidding, Econometrica 50(5): 1089-1122. Zbl0487.90017
  47. Mo, J. and Walrand, J. (2000). Fair end-to-end window-based congestion control, IEEE/ACM Transactions on Networking 8(5): 556-567. 
  48. Myerson, R.B. (1981). Optimal auction design, Mathematics of Operations Research 6(1): 58-73. Zbl0496.90099
  49. Myerson, R.B. (1991). Game Theory: Analysis of Conflict, Harvard University Press, Cambridge, MA. Zbl0729.90092
  50. Nash, J. (1950). Equilibrium points in n-person games, Proceedings of National Academy of Science 36(1): 48-49. Zbl0036.01104
  51. Nash, J. (1951). Non-cooperative games, Annals of Mathematics 54(2): 289-295. Zbl0045.08202
  52. Negishi, T. (1960). Welfare economics and existence of an equilibrium for a competitive economy, Metroeconomica 12(2-3): 92-97. Zbl0104.38403
  53. Ogryczak, W., Pióro, M. and Tomaszewski, A. (2005). Telecommunications network design and max-min optimization problem, Journal of Telecommunications and Information Technology 3: 43-56. 
  54. Ogryczak, W., Wierzbicki, A. and Milewski, M. (2008). A multi-criteria approach to fair and efficient bandwidth allocation, Omega 36(3): 451-463. 
  55. Pióro, M. and Medhi, D. (2004). Routing, Flow, and Capacity Design in Communication and Computer Networks, Morgan Kaufmann, San Francisco, CA. Zbl1069.68021
  56. Rockafellar, R.T. and Wets, R.J.-B. (2004). Variational Analysis, A Series of Comprehensive Studies in Mathematics, Vol. 317, Springer-Verlag, Berlin/Heidelberg. 
  57. Rosen, J.B. (1965). Existence and uniqueness of equilibrium points for concave n-person games, Econometrica 33(3): 520-534. Zbl0142.17603
  58. Rotschild, M. and Stiglitz, J. (1976). Equilibrium in competitive insurance markets: An essay on the economics of imperfect information, Quarterly Journal of Economics 90(4): 630-649. 
  59. Sen, A. (1969). Quasi-transitivity, rational choice and collective decisions, Review of Economic Studies 36(107): 381-93. Zbl0181.47302
  60. Sen, A. (1970). Interpersonal aggregation and partial comparability, Econometrica 38(3): 393-409. 
  61. Sen, A. (1977). On weights and measures: Informational constraints in social welfare, Econometrica 45(7): 1539-1572. Zbl0377.90002
  62. Srikant, R. (2003). The Mathematics of Internet Congestion Control, Birkhäuser, Boston, MA. Zbl1086.68018
  63. Stallings, W. (1998). High-Speed Networks, Prentice Hall, Upper Saddle River, NJ. 
  64. Stiglitz, J. (2000). The contributions of the economics of information to twentieth century economics, The Quarterly Journal of Economics 115(4): 1441-1478. Zbl0970.91515
  65. Uzawa, H. (1960). Market mechanisms and mathematical programming, Econometrica 28(4): 872-881. Zbl0098.33602
  66. Vickrey, W. (1961). Counterspeculation, auctions and competitive sealed tenders, Journal of Finance 16(1): 8-37. 
  67. Wei, D.X., Jin, C., Low, S.H. and Hegde, S. (2006). FAST TCP: Motivation, architecture, algorithms, performance, IEEE/ACM Transactions on Networking 16(6): 1246-1259. 
  68. Wierzbicki, A. P., Makowski, M. and Wessels, J. (2001). ModelBased Decision Support Methodology with Environmental Applications, Kluwer Academic Publishers, Dordrecht. Zbl0992.91003
  69. Yang, S. and Hajek, B. (2005). Revenue and stability of a mechanism for efficient allocation of a divisible good, Mimeo, University of Illinois, Urbana-Champaign, IL. 
  70. Yang, S. and Hajek, B. (2007). VCG-Kelly mechanisms for allocation of divisible goods: Adapting VCG mechanisms to one-dimensional signals, IEEE Journal on Selected Areas in Communications 25(6): 1237-1243. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.