Algorithmic Game Theory & Applications

Many multi-agent systems (such as communication systems, cognitive radio networks, etc.) contain multiple uncoordinated users that share a common medium or limited resources. In many scenarios, a natural model for these systems is to consider agents as individual decision makers that compete or (partially) cooperate for optimizing their own performance. Game theory is then the right framework to study such competitive-cooperative distributed networks of users. Two remarkable theoretical contributions in this context are briefly outlined next.

1) We have developed a unified (asynchronous) algorithmic framework able to explore the desired level of competition/cooperation among the users in order to reach in a distributed way the “best” available equilibrium in the system. The framework has been successfully applied to the design of several multi-agent systems in different areas.
Examples include (nonexhaustive list):

  • Optimal noncooperative resource allocation in SISO/MIMO ad-hoc networks [1, 2, 3], [4, 5] (the Asynchronous Iterative Waterfilling Algorithm is an instance of the developed algorithmic framework); [1] is a Highly cited paper (ISI Essential Science Indicators);

  • QoS optimization of interfering ad-hoc networks [6];

  • Distributed design of MIMO Cognitive Networks [7, 8, 9] (the resulting class of algorithms has been patented, US patent #20,120,071,102);

  • Robust design of MIMO multi-user interfering systems in the presence of partial channel and interference state information, based either on worst-case or Bayesian approaches [10];

  • Cross-layer game theoretical design of ad-hoc networks [11];

  • Noncooperative demand-side management methods for smart grids [12].


2) Toward the first algorithmic theory for nonconvex games: A second major result we recently achieved is the extension of the aforementioned framework to noncovex games with coupling (nonconvex) constraints [13]. Nonconvex optimization problems are notoriously difficult to solve; nonconvex games (where there are multiple nonconvex objective functions, one for each player) are even more challenging. To cope with the nonconvexity, we introduced a new concept of (relaxed) equilibrium for such nonconvex games and develop a general existence theory for such equilibria as well as design distributed (convergent) solution methods. To the best of our knowledge, our results are the first step toward a systematic algorithmic framework for nonconvex games. The proposed framework has also been applied to solve nonconvex games modeling some novel resource allocation problems in cognitive radio networks and physical layer security [14, 15, 16].

Related Publications

  1. Gesualdo Scutari, Daniel P. Palomar, and Sergio Barbarossa, “Optimal Linear Precoding Strategies for Wideband Noncooperative Systems Based on Game Theory – Part I: Nash Equilibria,” IEEE Trans. on Signal Processing, vol. 56, no. 3, pp. 1230–1249, March 2008. [Highly cited paper (ISI Web of Knowledge)].
  2. Gesualdo Scutari, Daniel P. Palomar, and Sergio Barbarossa, “Optimal Linear Precoding Strategies for Wideband Noncooperative Systems Based on Game Theory – Part II: Algorithms,” IEEE Trans. on Signal Processing, vol. 56, no. 3, pp. 1250–1267, March 2008.
  3. Gesualdo Scutari, Daniel P. Palomar, and Sergio Barbarossa, “Asynchronous Iterative Water-Filling for Gaussian Frequency-Selective Interference Channels,” IEEE Trans. on Information Theory, vol. 54, no. 7, pp. 2868–2878, July 2008.
  4. Gesualdo Scutari, Daniel P. Palomar, and Sergio Barbarossa, “Competitive Design of Multiuser MIMO Systems based on Game Theory: A Unified View,” IEEE Journal on Selected Areas in Communications: Special Issue on Game Theory, vol. 25, no. 7, pp. 1089–1103, Sept. 2008.
  5. Gesualdo Scutari, Daniel P. Palomar, and Sergio Barbarossa, “The MIMO Iterative Waterfilling Algorithm,” IEEE Trans. on Signal Processing, vol. 57, no. 5, pp. 1917–1935, May 2009. [Top 10 downloaded articles in IEEE TSP (May – July 2009)].
  6. Jong-Shi Pang, Gesualdo Scutari, Francisco Facchinei, and Chaoxiong Wang, “Distributed Power Allocation With Rate Constraints in Gaussian Parallel Interference Channels,” IEEE Trans. on Information Theory, vol. 54, no. 8, pp. 3471–3489, Aug. 2008.
  7. Gesualdo Scutari and Daniel P. Palomar, “MIMO Cognitive Radio: A Game-Theoretical Approach,” IEEE Trans. on Signal Processing, vol. 58, no. 2, pp. 761-780, Feb. 2010. [Top 10 downloaded articles in IEEE TSP (Jan.-March 2010)].
  8. Gesualdo Scutari, Daniel P. Palomar, and Sergio Barbarossa, “Cognitive MIMO Radio: Competitive Optimality Design Based on Subspace Projections,” IEEE Signal Processing Magazine, vol. 25, no. 6, pp. 46–59, Nov. 2008. [Top 100 downloaded articles in IEEE among 1.25 million articles available (Jan. – Mar. 2009)], [Top 10 downloaded articles in IEEE SP Magazine (Mar. 2009)].
  9. Gesualdo Scutari, Daniel P. Palomar, and Sergio Barbarossa, "Competitive Optimization of Cognitive Radio MIMO Systems via Game Theory,” Chapter 11, in Convex Optimization in Signal Processing and Communications, Cambridge University Press, 2009.
  10. Jiaheng Wang, Gesualdo Scutari, and Daniel P. Palomar, “Robust MIMO Cognitive Radio via Game Theory,” in IEEE Trans. on Signal Processing, vol. 59, no. 3, pp. 1182–1201, March 2011. [Top 10 downloaded articles in IEEE TSP (March 2011)].
  11. Z. Guan, T. Melodia, and G. Scutari, “To transmit or not to transmit? Distributed queueing games for infrastructureless wireless networks,” IEEE Trans. on Networking, (submitted, Dec. 2013). Conference version appeared in Proc. of IEEE ICC 2013.
  12. Italo Atzeni, Luis G. Ordonez, Gesualdo Scutari, Daniel P. Palomar, and Javier R. Fonollosa, “Noncooperative Day-Ahead Bidding Strategies for Demand-Side Expected Cost Minimization with Real-Time Adjustments,” IEEE Trans. on Signal Processing, vol. 62, no. 9, pp. 2397-2412, May 2014. [PDF]
  13. Jong-Shi Pang and Gesualdo Scutari, “Nonconvex Games with Side Constraints,” SIAM Jour. On Optimization, vol. 21, no. 4, pp. 1491–1522, Dec. 2011.
  14. Jong-Shi Pang and Gesualdo Scutari, “Joint Sensing and Power Allocation in Nonconvex Cognitive Radio Games: Nash Equilibria and Distributed Algorithms,” IEEE Trans. on Signal Processing, vol. 61, no. 9, pp. 2366–2382, May 2013.
  15. Gesualdo Scutari and Jong-Shi Pang “Joint Sensing and Power Allocation in Nonconvex Cognitive Radio Games: Nash Equilibria and Distributed Algorithms,” IEEE Trans. on Information Theory, vol. 59, no. 7, pp. 4626–4661, July 2013.
  16. Alberth Alvarado, Gesualdo Scutari, and Jong-Shi Pang, "A New Distributed DC-Programming Method and its Application to Physical Layer Security," IEEE Trans. on Signal Processing, vol. 62, no. 11, pp. 2984-2998, June 2014.