A unified distributed algorithm for non-cooperative games

doi:10.1017/CBO9781316162750.005

4 - A unified distributed algorithm for non-cooperative games

from Part I - Mathematical foundations

Published online by Cambridge University Press: 18 December 2015

Jong-Shi Pang and

Meisam Razaviyayn

Edited by

Shuguang Cui ,

Alfred O. Hero, III ,

Zhi-Quan Luo and

José M. F. Moura

Show author details

Jong-Shi Pang: Affiliation:
University of Southern California, USA
Meisam Razaviyayn: Affiliation:
Stanford University, USA
Shuguang Cui: Affiliation:
Texas A & M University
Alfred O. Hero, III: Affiliation:
University of Michigan, Ann Arbor
Zhi-Quan Luo: Affiliation:
University of Minnesota
José M. F. Moura: Affiliation:
Carnegie Mellon University, Pennsylvania

Book contents

Get access

Summary

This chapter presents a unified framework for the design and analysis of distributed algorithms for computing first-order stationary solutions of non-cooperative games with non-differentiable player objective functions. These games are closely associated with multi-agent optimization wherein a large number of selfish players compete noncooperatively to optimize their individual objectives under various constraints. Unlike centralized algorithms that require a certain system mechanism to coordinate the players’ actions, distributed algorithms have the advantage that the players, either individually or in subgroups, can each make their best responses without full information of their rivals’ actions. These distributed algorithms by nature are particularly suited for solving hugesize games where the large number of players in the game makes the coordination of the players almost impossible. The distributed algorithms are distinguished by several features: parallel versus sequential implementations, scheduled versus randomized player selections, synchronized versus asynchronous transfer of information, and individual versus multiple player updates. Covering many variations of distributed algorithms, the unified algorithm employs convex surrogate functions to handle nonsmooth nonconvex functions and a (possibly multi-valued) choice function to dictate the players’ turns to update their strategies. There are two general approaches to establish the convergence of such algorithms: contraction versus potential based, each requiring different properties of the players’ objective functions. We present the details of the convergence analysis based on these two approaches and discuss randomized extensions of the algorithms that require less coordination and hence are more suitable for big data problems.

Introduction

Introduced by John von Neumann [1], modern-day game theory has developed into a very fruitful research discipline with applications in many fields. There are two major classifications of a game, cooperative versus non-cooperative. This chapter pertains to one aspect of non-cooperative games for potential applications to big data, namely, the computation of a “solution” to such a game by a distributed algorithm. In a (basic) non-cooperative game, there are finitely many selfish players/agents each optimizing a rival-dependent objective by choosing feasible strategies satisfying certain private constraints. Providing a solution concept to such a game, a Nash equilibrium (NE) [2, 3] is by definition a tuple of strategies, one for each player, such that no player will be better off by unilaterally deviating from his/her equilibrium strategy while the rivals keep executing their equilibrium strategies.

Type: Chapter
Information: Big Data over Networks , pp. 101 - 134

DOI: https://doi.org/10.1017/CBO9781316162750.005 [Opens in a new window]

Publisher: Cambridge University Press

Print publication year: 2016

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Book purchase

Temporarily unavailable

References

[1] J. v., Neumann, “Zur theorie der gesellschaftsspiele,” Mathematische Annalen, vol. 100, no. 1, pp. 295–320, 1928.Google Scholar

[2] J. F., Nash, “Equilibrium points in n-person games,” Proceedings of the National Academy of Sciences, vol. 36, no. 1, pp. 48–49, 1950.Google Scholar

[3] J., Nash, “Non-cooperative games,” Annals of Mathematics, pp. 286–295, 1951.Google Scholar

[4] Z.-Q., Luo and J.-S., Pang, “Analysis of iterative waterfilling algorithm for multiuser power control in digital subscriber lines,” EURASIP Journal on Advances in Signal Processing, 2006.Google Scholar

[5] G., Scutari and J.-S., Pang, “Joint sensing and power allocation in nonconvex cognitive radio games: quasi-Nash equilibria,” in IEEE Transactions on Signal Processing, vol. 61, IEEE, 2013, pp. 2366–2382.Google Scholar

[6] G., Scutari, F., Facchinei, J.-S., Pang, and D., Palomar, “Real and complex monotone communication games,” IEEE Transactions on Information Theory, pp. 4197–4231, 2014.Google Scholar

[7] G., Scutari, D. P., Palomar, F., Facchinei, and J.-S., Pang, “Convex optimization, game theory, and variational inequality theory,” IEEE Signal Processing Magazine, vol. 27, no. 3, pp. 35– 49, 2010.Google Scholar

[8] G., Scutari, D. P., Palomar, J.-S., Pang, and F., Facchinei, “Flexible design of cognitive radio wireless systems,” IEEE Signal Processing Magazine, vol. 26, no. 5, pp. 107–123, 2009.Google Scholar

[9] G., Scutari and J.-S., Pang, “Joint sensing and power allocation in nonconvex cognitive radio games: Nash equilibria and distributed algorithms,” IEEE Transactions on Information Theory, vol. 59, pp. 4626–4661, 2013.Google Scholar

[10] W., Yu, G., Ginis, and J. M., Cioffi, “Distributed multiuser power control for digital subscriber lines,” IEEE Journal on Selected Areas in Communications, vol. 20, no. 5, pp. 1105–1115, 2002.Google Scholar

[11] C. J., Day, B. F., Hobbs, and J.-S., Pang, “Oligopolistic competition in power networks: a conjectured supply function approach,” IEEE Transactions on Power Systems, vol. 17, no. 3, pp. 597–607, 2002.Google Scholar

[12] B. F., Hobbs and U., Helman, Complementarity-based equilibrium modeling for electric power markets. Chapter 3 in D. W., Bunn, editor, Modeling Prices in Competitive Electricity Markets, Citeseer, 2004.Google Scholar

[13] B., Hobbs, C. B., Metzler, and J.-S., Pang, “Nash–Cournot equilibria in power markets on a linearized DC network with arbitrage: formulations and properties,” Networks and Spatial Economics, vol. 3, no. 2, pp. 123–150, 2003.Google Scholar

[14] J.-S., Pang and B. F., Hobbs, “Spatial oligopolistic equilibria with arbitrage, shared resources, and price function conjectures,” Mathematical Programming, vol. 101, no. 1, pp. 57–94, 2004.Google Scholar

[15] J., Zhao, B. F., Hobbs, and J.-S., Pang, “Long-run equilibrium modeling of alternative emissions allowance allocation systems in electric power markets,” Operations Research, vol. 58, pp. 529–548, 2010.Google Scholar

[16] F., Facchinei and C., Kanzow, “Generalized Nash equilibrium problems,” Annals ofOperations Research, [This is an updated version of the survey paper that appeared in AOR (2007) 173– 210], pp. 177–211, 2010.Google Scholar

[17] F., Facchinei and J.-S., Pang, Nash equilibria: the variational approach. In Y., Eldar and D., Palomar, Eds., Convex Optimization in Signal Processing and Communications, Cambridge University Press, 2010.Google Scholar

[18] L. M., Bruce, “Game theory applied to big data analytics in geosciences and remote sensing.” IEEE International Conference on Geoscience and Remote Sensing Symposium (IGARSS), pp. 4094–4097, 2013.Google Scholar

[19] H., Baligh, M., Hong, W.-C., Liao, Z.-Q., Luo, M., Razaviyayn, M., Sanjabi, and R., Sun, “Cross-layer provision of future cellular networks: A WMMSE-based approach,” IEEE Signal Processing Magazine, vol. 31, no. 6, pp. 56–68, 2014.Google Scholar

[20] I., Guyon and A., Elisseeff, “An introduction to variable and feature selection,” The Journal of Machine Learning Research, vol. 3, pp. 1157–1182, 2003.Google Scholar

[21] Y., Saeys, I., Inza, and P., Larra˜naga, “A review of feature selection techniques in Bioinformatics,” Bioinformatics, vol. 23, no. 19, pp. 2507–2517, 2007.Google Scholar

[22] T., Joachims, Text Categorization With Support Vector Machines: Learning With Many Relevant Features, Springer, 1998.Google Scholar

[23] F., Facchinei, A., Fischer, and V., Piccialli, “Generalized Nash equilibrium problems and Newton methods,” Mathematical Programming, vol. 117, no. 1–2, pp. 163–194, 2009.Google Scholar

[24] F., Facchinei, V., Piccialli, and M., Sciandrone, “Decomposition algorithms for generalized potential games,” Computational Optimization and Applications, vol. 50, no. 2, pp. 237–262, 2011.Google Scholar

[25] A., Alvarado, G., Scutari, and J.-S., Pang, “A new decomposition method for multiuser DCprogramming and its applications,” IEEE Transactions on Signal Processing, vol. 62, no. 11, pp. 2984–2998, 2013.Google Scholar

[26] G., Scutari, F., Facchinei, P., Song, D. P., Palomar, and J.-S., Pang, “Decomposition by partial linearization: parallel optimization of multi-agent systems,” IEEE Transaction on Signal Processing, pp. 641–656, 2014.Google Scholar

[27] J.-S., Pang and G., Scutari, “Nonconvex games with side constraints,” SIAM Journal on Optimization, vol. 21, no. 4, pp. 1491–1522, 2011.Google Scholar

[28] B. R., Marks and G. P., Wright, “Technical note – a general inner approximation algorithm for nonconvex mathematical programs,” Operations Research, vol. 26, no. 4, pp. 681–683, 1978.Google Scholar

[29] M., Razaviyayn, “Successive convex approximation: analysis and applications,” Ph.D. dissertation, University of Minnesota, 2014.

[30] M., Razaviyayn, M., Hong, and Z.-Q., Luo, “Aunified convergence analysis of block successive minimizationmethods for nonsmooth optimization,” SIAM Journal on Optimization, vol. 23, no. 2, pp. 1126–1153, 2013.Google Scholar

[31] J., Bolte, S., Shoham, and M., Teboulle, “Proximal alternating linearized minimization for nonconvex and nonsmooth problems,” Mathematical Programming, pp. 1–36, 2013.Google Scholar

[32] J., Mairal, “Optimization with first-order surrogate functions,” arXiv preprint arXiv: 1305.3120, 2013.

[33] M., Hong, X., Wang, M., Razaviyayn, and Z.-Q., Luo, “Iteration complexity analysis of block coordinate descent methods,” arXiv preprint arXiv:1310.6957, 2013.

[34] M., Razaviyayn, M., Hong, Z.-Q., Luo, and J.-S., Pang, “Parallel successive convex approximation for nonsmooth nonconvex optimization,” arXiv preprint arXiv:1406.3665, 2014.

[35] F., Facchinei, S., Sagratella, and G., Scutari, “Flexible parallel algorithms for big data optimization,” arXiv preprint arXiv:1311.2444, 2013.

[36] M., Hong, T. H., Chang, X., Wang, M., Razaviyayn, S., Ma, and Z.-Q., Luo, “A block successive upper bound minimization method of multipliers for linearly constrained convex optimization,” arXiv preprint arXiv:1401.7079, 2014.

[37] M., Razaviyayn, M., Sanjabi, and Z.-Q., Luo, “A stochastic successive minimization method for nonsmooth nonconvex optimization with applications to transceiver design in wireless communication networks,” arXiv preprint arXiv:1307.4457, 2013.

[38] J. M., Ortega and W. C., Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, SIAM Classics in Applied Mathematics, 2000, vol. 30.Google Scholar

[39] R. W., Cottle, J.-S., Pang, and R. E., Stone, The Linear Complementarity Problem. SIAM, 2009, vol. 60.Google Scholar

[40] J.-S., Pang and D., Chan, “Iterative methods for variational and complementarity problems,” Mathematical Programming, vol. 24, no. 1, pp. 284–313, 1982.Google Scholar

[41] J.-S., Pang, “Asymmetric variational inequality problems over product sets: applications and iterative methods,” Mathematical Programming, vol. 31, no. 2, pp. 206–219, 1985.Google Scholar

[42] D. P., Bertsekas and J. N., Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Athena Scientific, 1989.Google Scholar

[43] J.-S., Pang, G., Scutari, F., Facchinei, and C., Wang, “Distributed power allocation with rate constraints in Gaussian parallel interference channels,” IEEE Transactions on Information Theory, vol. 54, no. 8, pp. 3471–3489, 2008.Google Scholar

[44] J.-S., Pang, G., Scutari, D. P., Palomar, and F., Facchinei, “Design of cognitive radio systems under temperature-interference constraints: a variational inequality approach,” IEEE Transactions on Signal Processing, vol. 58, no. 6, pp. 3251–3271, 2010.Google Scholar

[45] F., Facchinei and J.-S., Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, 2003, vols. I and II.Google Scholar

[46] J.-S., Pang, M., Razaviyayn, and A., Alvarado, “Computing b-stationary points of nonsmooth dc programs,” Manuscript. Department of Industrial and Systems Engineering, University of Southern California, 2014.

[47] D., Monderer and L. S., Shapley, “Potential games,” Games and Economic Behavior, vol. 14, no. 1, pp. 124–143, 1996.Google Scholar

[48] R. T., Rockafellar, Convex Analysis, Princeton University Press, 1970.Google Scholar

[49] R. T., Rockafellar and R. J. B., Wets, Variational Analysis, Springer, 1998, vol. 317.Google Scholar

[50] G., Scutari, F., Facchinei, L., Lampariello, and P., Song, “Parallel and distributed methods for nonconvex optimization,” In Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2014.Google Scholar

[51] B. E., Fristedt and L. F., Gray, A Modern Approach to Probability Theory, Springer, 1997.Google Scholar

[52] D. P., Bertsekas, Nonlinear Programming, Athena Scientific, 1999.Google Scholar

[53] D. P., Bertsekas and J. N., Tsitsiklis, Neuro-dynamic Programming, Athena Scientific, 1996.Google Scholar