Recent Work
- J. R. Marden, S. D. Ruben, and L. Y. Pao, "A Model-Free Approach to Wind Farm Control Using Game Theoretic Methods,"
submitted for journal publication, 2012.
[PDF] [Abstract] [Bibtex]This paper surveys recent results in game theory and cooperative control and highlights their application to the problem of optimizing energy production in wind farms. One such result is a simple model-free control strategy that is completely decentralized and leads to efficient system behavior in virtually any distributed system. We demonstrate that this learning rule can be used to provably maximize energy production in wind farms without explicitly modeling the aerodynamic interaction amongst the turbines.@unpublished{li-marden-2011c,
author = "J. R. Marden and S. D. Ruben and L. Y. Pao",
title = "A Model-Free Approach to Wind Farm Control Using Game Theoretic Methods",
year = "2012",
note = "under submission"}
- J. R. Marden, H. Peyton Young, and Lucy Y. Pao, "Achieving Pareto Optimality Through Distributed Learning" discussion paper,
University of Colorado and University of Oxford, 2011.
[PDF] [Abstract] [Bibtex]We propose a simple payoff-based learning rule that is completely decentralized, and that leads to an efficient configuration of actions in any n-person game with generic payoffs. The algorithm requires no communication. Agents respond solely to changes in their own realized payoffs, which are affected by the actions of other agents in the system in ways that they do not generally understand. The method has potential application to the optimization of complex systems with many distributed components, such as the routing of information in networks and the design and control of wind farms.@unpublished{marden-young-2011,
author = "J. R. Marden and H. Peyton Young and L. Y. Pao",
title = "Achieving pareto optimality through distributed learning",
year = "2011",
note = "under submission"}
- N. Li and J. R. Marden, "Decoupling Coupled Constraints Through Utility Design" submitted for journal publication,
2011.
[PDF] [Abstract] [Bibtex]The central goal in multiagent systems is to design local control laws for the individual agents to ensure that the emergent global behavior is desirable with respect to a given system level objective. In many systems this control design is further complicated by coupled constraints on the agents' behavior. This paper seeks to address the design of such algorithms using the field of game theory. In particular, is it possible to design local agent utility functions for an \emph{unconstrained} game such that all resulting pure Nash equilibria (i) optimize the given system level objective and (ii) satisfy the given coupled constraint. Such developments would greatly simplify the control design by eliminating the need to explicitly consider the constraint. Unfortunately, we illustrate that the standard game theoretic framework is not suitable for this design objective. However, we demonstrate that by adding an additional state variable in the game environment, i.e., moving towards a special class of Markov games termed state based games, we can satisfy these performance criteria through utility design. The key to this realization is incorporating exterior penalty functions and barrier functions into the design of the agents' utility functions.@unpublished{na-marden-2011a,
author = "N. Li and J. R. Marden",
title = "Decoupling Coupled Constraints Through Utility Design",
year = "2011",
note = "Discussion paper, Department of ECEE, University of Colorado at Boulder"}
- J. R. Marden, "State Based Potential Games" submitted for journal publication, 2011.
[PDF][Abstract] [Bibtex]There is a growing interest in the application of game theoretic methods to the design and control of multiagent systems. However, the existing game theoretic framework possesses inherent limitations with regards to these new prescriptive challenges. In this paper we propose a new framework, termed stated based games, which introduces an underlying state space into the game theoretic environment. This state space provides a system designer with an additional degree of freedom to help coordinate group behavior and overcome these limitations. We develop a spectrum of learning algorithms for classes of state based games and demonstrate the applicability of this enhanced framework on a broad spectrum of cooperative control problems.@unpublished{marden-2011,
author = "J. R. Marden",
title = "State Based Potential Games",
note = "submitted for journal publication",
year = "2011",}
- J. R. Marden and A. Wierman, "Overcoming the Limitations of Utility Design for Multiagent Systems" submitted for journal publication, 2011.
[PDF] [Abstract] [Bibtex]Cooperative control focuses on deriving desirable collective behavior in multiagent systems through the design of local control algorithms. Game theory is beginning to emerge as a valuable set of tools for achieving this objective. A central component of this game theoretic approach is the assignment of utility functions to the individual agents. Here, the goal is to assign utility functions within an ŇadmissibleÓ design space such that the resulting game possesses desirable properties. Our first set of results illustrates the complexity associated with such a task. In particular, we prove that if we restrict the class of utility functions to be local, scalable, and budget-balanced then (i) ensuring that the resulting game possesses a pure Nash equilibrium requires computing a Shapley value, which can be computationally prohibitive for large-scale systems, and (ii) ensuring that the allocation which optimizes the system level objective is a pure Nash equilibrium is impossible. The last part of this paper demonstrates that both limitations can be overcome by introducing an underlying state space into the potential game structure.@unpublished{marden-wierman-2011,
author = "J. R. Marden and A. Wierman",
title = "The Limitations of Utility Design for Multiagent Systems",
note = "submitted for journal publication",
year = "2011"}
- N. Li and J. R. Marden, "Designing Games for Distributed Optimization" to appear in the Proceedings of 50th IEEE Conference on Decision and Control, 2011.
[PDF] [Abstract] [Bibtex]The central goal in multiagent systems is to design local control laws for the individual agents to ensure that the emergent global behavior is desirable with respect to a given system level objective. Ideally, a system designer seeks to satisfy this goal while conditioning each agent's control law on the least amount of information possible. Unfortunately, there are no existing methodologies for addressing this design challenge. The goal of this paper is to address this challenge using the field of game theory. Utilizing game theory for the design and control of multiagent systems requires two steps: (i) defining a local objective function for each decision maker and (ii) specifying a distributed learning algorithm to reach a desirable operating point. One of the core advantages of this game theoretic approach is that this two step process can be decoupled by utilizing specific classes of games. For example, if the designed objective functions result in a potential game then the system designer can utilize distributed learning algorithms for potential games to complete step (ii) of the design process. Unfortunately, designing agent objective functions to meet objectives such as locality of information and efficiency of resulting equilibria within the framework of potential games is fundamentally challenging and in many case impossible. In this paper we develop a systematic methodology for meeting these objectives using a broader framework of games termed state based potential games. State based potential games is an extension of potential games where an additional state variable is introduced into the game environment hence permitting more flexibility in our design space. Furthermore, state based potential games possess an underlying structure that can be exploited by distributed learning algorithms in a similar fashion to potential games hence providing a new baseline for our decomposition.@ inproceedings{na-marden-2011b,
author = "N. Li and J. R. Marden",
title = "Designing Games for Distributed Optimization",
booktitle = "Proceedings of the 50th IEEE Conference on Decision and Control",
year = "2011",
note = "to appear"}
Journals
- J. R. Marden and M. Effros, "The Price of Selfishness in Network Coding" submitted for journal publication, 2009.
[PDF] [Abstract] [Bibtex]A game theoretic framework is introduced for studying selfish user behavior in shared wireless networks. Specifically, the investigation treats an n-unicast problem in a wireless network that employs a restricted form of network coding called reverse carpooling. Each unicast session independently chooses a route from its transmitter to its receiver. The true cost of a particular set of unicast routes is the number of wireless transmissions required to establish the n unicast connections across the network using those routes; we here assume the optimal application of reverse carpooling network codes for the routes in operation. A family of mechanisms for distributing the cost of a solution among the participating unicasts is studied; each mechanism is independent of the network topology. Game theory is employed as a tool for analyzing the impact of these mechanisms on the global system performance when each unicast independently and selfishly chooses its route to minimize its individual cost. The investigation focuses on the performance of stable solutions - where stability here refers to a form of Nash equilibrium defined in the text. Results include bounds on the best- and worst-case stable solutions as compared to the best performance that could be found and implemented using a centralized controller. The optimal cost sharing protocol is derived. The resulting bound on worst-case stable performance cannot be improved using cost sharing protocols that are independent of the network structure.@unpublished{marden-effros-09,
author = "J. R. Marden and M. Effros",
title = "The price of selfishness in network coding",
year = "2009",
note = "submitted for journal publication"}
- J. R. Marden and A. Wierman, "Distributed Welfare Games" submitted for journal publication, 2008.
[PDF] [Abstract] [Bibtex]Game-theoretic tools are becoming a popular design choice for distributed resource allocation algorithms. A central component of this design choice is the assignment of utility functions to the individual agents. The goal is to assign each agent an admissible utility function such that the resulting game possesses a host of desirable properties including scalability, tractability, and existence and efficiency of pure Nash equilibria. In this paper we formally study this question of utility design on a class of games terms distributed welfare games.We identify several utility design methodologies that guarantee desirable game properties irrespective of the specific application domain. Lastly, we illustrate the results in this paper on two commonly studied classes of resource allocation problem: "coverage" problems and "coloring" problems.@unpublished{marden-dwg,
author = "J. R. Marden and A. Wierman",
title = "Distributed Welfare Games",
year = "2008",
note = "submitted for journal publication"}
- J. R. Marden and J. S. Shamma, "Revisiting Log-Linear Learning: Asynchrony, Completeness and a Payoff-based Implementation"
accepted for publication in Games and Economic Behavior, 2011.
[PDF] [Abstract] [Bibtex]Log-linear learning is a learning algorithm with equilibrium selection properties. Log-linear learning provides guarantees on the percentage of time that the joint action profile will be at a potential maximizer in potential games. The traditional analysis of log-linear learning has centered around explicitly computing the stationary distribution. This analysis relied on a highly structured setting: i) players' utility functions constitute a potential game, ii) players update their strategies one at a time, which we refer to as asynchrony, iii) at any stage, a player can select any action in the action set, which we refer to as completeness, and iv) each player is endowed with the ability to assess the utility he would have received for any alternative action provided that the actions of all other players remain fixed. Since the appeal of log-linear learning is not solely the explicit form of the stationary distribution, we seek to address to what degree one can relax the structural assumptions while maintaining that only potential function maximizers are the stochastically stable action profiles. In this paper, we introduce slight variants of log-linear learning to include both synchronous updates and incomplete action sets. In both settings, we prove that only potential function maximizers are stochastically stable. Furthermore, we introduce a payoff-based version of log-linear learning, in which players are only aware of the utility they received and the action that they played. Note that log-linear learning in its original form is not a payoff-based learning algorithm. In payoff-based log-linear learning, we also prove that only potential maximizers are stochastically stable. The key enabler for these results is to change the focus of the analysis away from deriving the explicit form of the stationary distribution of the learning process towards characterizing the stochastically stable states. The resulting analysis uses the theory of resistance trees for regular perturbed Markov decision processes, thereby allowing a relaxation of the aforementioned structural assumptions.@article{marden-shamma-08,
author = "J. R. Marden and J. S. Shamma",
title = "Revisiting Log-Linear Learning: Asynchrony, Completeness and a Payoff-based Implementation",
journal = "Games and Economic Behavior",
year = "2011",
note = "to appear"}
- R. Gopalakrishnan, J. R. Marden, and A. Wierman "An architectural view of game theoretic control",
ACM SIGMETRICS Performance Evaluation Review, Volume 38, Number 3, 2011.
[PDF] [Abstract] [Bibtex]Game-theoretic control is a promising new approach for distributed resource allocation. In this paper, we describe how game-theoretic control can be viewed as having an intrinsic layered architecture, which provides a modularization that simplifies the control design. We illustrate this architectural view by presenting details about one particular instantiation using potential games as an interface. This example serves to highlight the strengths and limitations of the proposed architecture while also illustrating the relationship between game-theoretic control and other existing approaches to dis- tributed resource allocation.@article{gopalakrishnan2011architectural,
title={An architectural view of game theoretic control},
author={Gopalakrishnan, R. and Marden, J. R. and Wierman, A.},
journal={ACM SIGMETRICS Performance Evaluation Review},
volume={38},
number={3},
pages={31--36},
issn={0163-5999},
year={2011},
publisher={ACM}}
- J. R. Marden G. Arslan and J. S. Shamma, "Cooperative Control and Potential Games"
IEEE Transactions on Systems, Man and Cybernetics. Part B: Cybernetics, 39:1393-1407, December, 2009.
[PDF] [Abstract] [Bibtex]We present a view of cooperative control using the language of learning in games. We review the game theoretic concepts of potential games and weakly acyclic games and demonstrate how several cooperative control problems such as consensus and dynamic sensor coverage can be formulated in these settings. Motivated by this connection, we build upon game theoretic concepts to better accommodate a broader class of cooperative control problems. In particular, we extend existing learning algorithms to accommodate (i) restricted action sets caused by limitations in agent capabilities and (ii) group based decision making. Furthermore, we also introduce a new class of games, called sometimes weakly acyclic games, for time-varying objective functions and action sets, and provide distributed algorithms for convergence to an equilibrium.@article{marden-connections,
author = "J. R. Marden and G. Arslan and J. S. Shamma",
title = "Connections Between Cooperative Control and Potential Games",
journal = "IEEE Transactions on Systems, Man and Cybernetics. Part B: Cybernetics",
year = "2009",
volume = "39",
issue = "6",
month = "December",
pages = "1393-1407"}
- J. R. Marden, H. P. Young, G. Arslan and J. S. Shamma, "Payoff-Based Dynamics for Multi-Player Weakly Acyclic Games"
SIAM Journal on Control and Optimization, special issue on "Control and Optimization in Cooperative Networks", Volume 48, Issue 1, February 2009, pp. 373-396.
[PDF] [Abstract] [Bibtex]We consider repeated multi-player games in which players repeatedly and simultaneously choose strategies from a finite set of available strategies according to some strategy adjustment process. We focus on the specific class of weakly acyclic games, which is particularly relevant for multi-agent cooperative control problems. A strategy adjustment process determines how players select their strategies at any stage as a function of the information gathered over previous stages. Of particular interest are "payoff based" processes, in which at any stage, players only know their own actions and (noise corrupted) payoffs from previous stages. In particular, players do not know the actions taken by other players and do not know the structural form of payoff functions. We introduce three different payoff based processes for increasingly general scenarios and prove that after a sufficiently large number of stages, player actions constitute a Nash equilibrium at any stage with arbitrarily high probability. We also show how to modify player utility functions through tolls and incentives in so-called congestion games, a special class of weakly acyclic games, to guarantee that a centralized objective can be realized as a Nash equilibrium. We illustrate the methods with a simulation of distributed routing over a network.@article{marden-payoff,
author = "J. R. Marden and H. P. Young and G. Arslan and J. S. Shamma",
title = "Payoff based dynamics for multi-player weakly acyclic games",
journal = "SIAM Journal on Control and Optimization",
volume = "48",
issue = "1",
pages = "373--396",
month = "February",
year = "2009"}
- J. R. Marden, G. Arslan and J. S. Shamma, "Joint Strategy Fictitious Play with Inertia for Potential Games"
IEEE Transactions on Automatic Control, Volume 54, Issue 2, February 2009, pp. 208-220.
[PDF] [Abstract] [Bibtex]We consider multi-player repeated games involving a large number of players with large strategy spaces and enmeshed utility structures. In these "large-scale" games, players are inherently faced with limitations in both their observational and computational capabilities. Accordingly, players in largescale games need to make their decisions using algorithms that accommodate limitations in information gathering and processing. This disqualifies some of the well known decision making models such as "Fictitious Play" (FP), in which each player must monitor the individual actions of every other player and must optimize over a high dimensional probability space. We will show that Joint Strategy Fictitious Play (JSFP), a close variant of FP, alleviates both the informational and computational burden of FP. Furthermore, we introduce JSFP with inertia, i.e., a probabilistic reluctance to change strategies, and establish the convergence to a pure Nash equilibrium in all generalized ordinal potential games in both cases of averaged or exponentially discounted historical data. We illustrate JSFP with inertia on the specific class of congestion games, a subset of generalized ordinal potential games. In particular, we illustrate the main results on a distributed traffic routing problem and derive tolling procedures that can lead to optimized total traffic congestion.@article{marden05-jsfp-journal,
author = "J. R. Marden and G. Arslan and J. S. Shamma",
title = "Joint Strategy Fictitious Play with Inertia for Potential Games",
journal = "IEEE Transactions on Automatic Control",
volume = "54",
issue = "2",
pages = "208--220",
month = "February",
year = "2009"}
- G. Arslan, J. R. Marden and J. S. Shamma, "Autonomous vehicle-target assignment: a game theoretical formulation",
ASME Journal of Dynamic Systems, Measurement and Control special issue on "Analysis and Control of Multi-Agent Dynamic Systems",
Volume 129, Issue 5, September 2007, pp. 584-596.
[PDF] [Abstract] [Bibtex]We consider an autonomous vehicle-target assignment problem where a group of vehicles are expected to optimally assign themselves to a set of targets. We introduce a game- theoretical formulation of the problem in which the vehicles are viewed as self-interested decision makers. Thus, we seek the optimization of a global utility function through autonomous vehicles that are capable of making individually rational decisions to opti- mize their own utility functions. The first important aspect of the problem is to choose the utility functions of the vehicles in such a way that the objectives of the vehicles are localized to each vehicle yet aligned with a global utility function. The second important aspect of the problem is to equip the vehicles with an appropriate negotiation mechanism by which each vehicle pursues the optimization of its own utility function. We present several design procedures and accompanying caveats for vehicle utility design. We present two new negotiation mechanisms, namely, "generalized regret monitoring with fading memory and inertia" and "selective spatial adaptive play," and provide accompanying proofs of their convergence. Finally, we present simulations that illustrate how vehicle negotiations can consistently lead to near-optimal assignments provided that the utilities of the vehicles are designed appropriately.@article{ams07, author = "G. Arslan and J. R. Marden and J. S. Shamma",
title = "Autonomous vehicle-target assignment: a game theoretical formulation",
journal = "ASME Journal of Dynamic Systems, Measurement and Control",
volume = "129",
issue = "5",
month = "September",
year = "2007",
pages = "584--596"}
Conferences and Workshops
- J. R. Marden, S. D. Ruben, and L. Y. Pao, "Surveying Game Theoretic Approaches for Wind Farm Optimization,"
Proceedings of the AIAA Aerospace Sciences Meeting, 2012.
[Abstract] [Bibtex]This paper surveys recent results in game theory and cooperative control and highlights their implications for the problem of optimizing energy production in wind farms. One such result is a simple payoff-based learning rule that is completely decentralized and leads to an efficient configuration of actions in virtually any distributed system. We demonstrate that this learning rule can be used to provably maximize energy production in wind farms without explicitly modeling the aerodynamic interaction amongst the turbines.@inproceedings{marden-etal-2011,
author = "J. R. Marden and S. D. Ruben and L. Y. Pao",
title = "Surveying Game Theoretic Approaches for Wind Farm Optimization",
booktitle = "Proceedings of the AIAA Aerospace Sciences Meeting",
year = "2012"}
- R. Gopalakrishnan, J. R. Marden, and A. Wierman, "Characterizing distribution rules for cost sharing games,"
NetGCoop, 2011.
[PDF] [Abstract] [Bibtex]We consider the problem of designing the distribution rule used to share "welfare" (cost or revenue) among individually strategic agents. There are many distribution rules known to guarantee the existence of a (pure Nash) equilibrium in this setting, e.g., the Shapley value and its weighted variants; however a characterization of the space of distribution rules that yield the existence of a Nash equilibrium is unknown. Our work provides a step towards such a characterization. We prove that when the welfare function is strictly submodular, a budget-balanced distribution rule guarantees equilibrium existence for all games (i.e., all possible sets of resources, agent action sets, etc.) if and only if it is a weighted Shapley value.@unpublished{gmw-2011,
author = "R. Gopalakrishnan and J. R. Marden and A. Wierman",
title = "Characterizing distribution rules for cost sharing games",
booktitle = "Proceedings of NetGCoop",
year = "2011"}
- D. S. Leslie and J. R. Marden, "Equilibrium Selection in Potential Games with Noisy Rewards,"
Proceedings of NetGCoop, 2011.
[Abstract] [Bibtex]Game theoretical learning in potential games is a highly active research area stemming from the connection between potential games and distributed optimisation. In many settings an optimisation problem can be represented by a poten- tial game where the optimal solution corresponds to the potential function maximizer. Accordingly, significant research attention has focused on the design of distributed learning algorithms that guarantee convergence to the potential maximizer in potential games. However, there are currently no existing algorithms that provide convergence to the potential function maximiser when utility functions are corrupted by noise. In this paper we rectify this issue by demonstrating that a version of payoff-based log- linear learning guarantees that the only stochastically stable states are potential function maximisers even in noisy settings..@inproceedings{lesmar-2011,
author = "D. S. Leslie and J. R. Marden",
title = "Equilibrium Selection in Potential Games with Noisy Rewards",
booktitle = "Proceedings of NetGCoop",
year = "2011"}
- J. R. Marden and T. Roughgarden, "Generalized Efficiency Bounds in Distributed Resource Allocation",
Proceedings of 49th IEEE Conference on Decision and Control, 2010.
[PDF] [Abstract] [Bibtex]Game theory is emerging as a popular tool for distributed control of multiagent systems. In order to take advantage of these game theoretic tools the interactions of the autonomous agents must be designed within a game theoretic environment. A central component of this game theoretic design is the assignment of a local objective function to each decision-maker. One promising approach to utility design is assigning each agent an objective function in accordance with the agent's Shapley value. This method frequently results in games that possess many desirable features including existence and efficiency of pure Nash equilibria. In this paper we explore the relationship between the Shapley value utility design and the resulting efficiency of pure Nash equilibria. To study this relationship we introduce a simple class of resource allocation problems. We then derive an explicit relationship between the structure of the resource allocation problem and the efficiency of the resulting equilibria. Lastly, we derive a bicriteria bound for these resource allocation problems. By bicriteria bound, we mean a bound on the value of the optimal allocation relative to the value of an equilibrium allocation with additional agents.@inproceedings{marden-roughgarden,
author = "J. R. Marden and T. Roughgarden",
title = "Generalized Efficiency Bounds for Distributed Resource Allocation",
booktitle = "Proceedings of the 48th IEEE Conference on Decision and Control",
month = "December",
year = "2010",
location = "Atlanta, Georgia"}
- N. Li and J. R. Marden, "Designing Games to Handle Coupled Constraints", Proceedings of 49th IEEE Conference on Decision and Control, 2010.
- J. R. Marden and A. Wierman, "Overcoming Limitations of Game-Theoretic Distributed Control", Proceedings of 48th IEEE Conference on Decision and Control, 2009.
- N. Li, J. R. Marden and J. S. Shamma, "Learning Approaches to the Witsenhausen Counterexample from a View of Potential Games", Proceedings of the 48th IEEE Conference on Decision and Control, 2009. [PDF]
- J. R. Marden and M. Effros, "The Price of Selfishness in Network Coding," 5th Workshop on Network Coding Theory and Applications, June, 2009.
- J. R. Marden and M. Effros, "A Game Theoretic Approach to Network Coding," Information Theory Workshop on Networking and Information Theory, June, 2009 (invited session)
- H. Chen, J. R. Marden and A. Wierman, "On the Impact of Heterogeneity and Back-end Scheduling in Load Balancing Designs"
- IEEE Conference on Computer Communications (INFOCOM), March, 2009. [PDF]
- shorter version in Performance Evaluation Review, 2008.
- J. R. Marden and A. Wierman, "Distributed Welfare Games"
- Proceedings of the 47th IEEE Conference on Decision and Control" , December, 2008.
- to be presented at the International Conference on Game Theory, July, 2009.
- J. R. Marden and J. S. Shamma, "Revisiting Log-Linear Learning: Asynchrony, Completeness and a Payoff-based Implementation" presented at GAMES 2008 &ndash Third World Congress of the Game Theory Society, July, 2008.
- J. R. Marden, H. P. Young, G. Arslan and J. S. Shamma, "Payoff-Based Dynamics for Multi-Player Weakly Acyclic Games"
- Proceedings of the 46th IEEE Conference on Decision and Control" , December, 2007.
- presented at the 18th Annual International Conference on Game Theory, July, 2007.
- J. R. Marden G. Arslan and J. S. Shamma, "Cooperative Control and Potential Games" Proceedings of the 2007 European Control Conference, June, 2007.
- J. R. Marden, G. Arslan and J. S. Shamma, "Regret Based Dynamics: Convergence in Weakly Acyclic Games", Sixth International Joint Conference on Autonomous Agents and Multi-Agent Systems, May 2007. [PDF]
- J. R. Marden, G. Arslan and J. S. Shamma, "Joint Strategy Fictitious Play with Inertia for Potential Games"
- Proceedings of the 44th IEEE Conference on Decision and Control , December, 2005.
- presented at the 17th Annual International Conference on Game Theory, July, 2006.
Theses
- J. R. Marden, "Learning in Large-Scale Games and Cooperative Control", Ph.D. Dissertation, UCLA, Los Angeles, CA, June, 2007. [PDF]
- J. R. Marden, "Coordination of Multiple Agents Using Neuro-Dynamic Programming", MS Thesis, UCLA, Los Angeles, CA, June, 2004.