Nash equilibrium design and price-based coordination in hierarchical systems

Karpowicz, M. P.

International Journal of Applied Mathematics and Computer Science, Tome 22 (2012) no. 4, pp. 951-969.

Résumé

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.

Détail

Keywords: Nash equilibrium, coordination in hierarchical systems, decentralized control, asymmetric information
Mots-clés : równowaga Nasha, system hierarchiczny, sterowanie rozproszone

Bibliographie

[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.

[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.

[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.

[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.

[10] Findeisen,W. (1968). Parametric optimization by primal method in multilevel systems, IEEE Transactions on Systems Science and Cybernetics 4(2): 155-164.

[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.

[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.

[13] Fudenberg, D. and Tirole, J. (1991). Game Theory, The MIT Press, Cambridge, MA.

[14] Green, J. R. and Laffont, J.-J. (1979). Incentives in Public Decision-making, North-Holland Publishing Company, Amsterdam.

[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.

[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.

[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.

[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.

[26] Johari, R. and Tsitsiklis, J. N. (2009). Efficiency of scalar-parameterized mechanisms, Operations Research 57(4): 823-839.

[27] Kakutani, S. (1941). A generalization of Brouwer's fixed point theorem, Duke Mathematical Journal 8(3): 457-459.

[28] Karpowicz, M. (2010). Coordination in Hierarchical Systems with Rational Agents, Ph.D. thesis, Warsaw University of Technology, Warsaw.

[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.

[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, Tel-Aviv, 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.

[39] Low, S., Peterson, L. and Wang, L. (2002). Understanding TCP Vegas: A duality model, Journal of the ACM (JACM) 49(2): 207-235.

[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.

[44] Maskin, E. (1999). Nash equilibrium and welfare optimality, The Review of Economic Studies 66(1): 23-38.

[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.

[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.

[49] Myerson, R. B. (1991). Game Theory: Analysis of Conflict, Harvard University Press, Cambridge, MA.

[50] Nash, J. (1950). Equilibrium points in n-person games, Proceedings of National Academy of Science 36(1): 48-49.

[51] Nash, J. (1951). Non-cooperative games, Annals of Mathematics 54(2): 289-295.

[52] Negishi, T. (1960). Welfare economics and existence of an equilibrium for a competitive economy, Metroeconomica 12(2-3): 92-97.

[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.

[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.

[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.

[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.

[62] Srikant, R. (2003). The Mathematics of Internet Congestion Control, Birkhäuser, Boston, MA.

[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.

[65] Uzawa, H. (1960). Market mechanisms and mathematical programming, Econometrica 28(4): 872-881.

[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). Model-Based Decision Support Methodology with Environmental Applications, Kluwer Academic Publishers, Dordrecht.

[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.