• ### Mean-field Games for Bio-inspired Collective Decision-making in Dynamical Networks(1802.03435)

Feb. 9, 2018 cs.MA, cs.SY
Given a large number of homogeneous players that are distributed across three possible states, we consider the problem in which these players have to control their transition rates, while minimizing a cost. The optimal transition rates are based on the players' knowledge of their current state and of the distribution of all the other players, and this introduces mean-field terms in the running and the terminal cost. The first contribution involves a mean-field game model that brings together macroscopic and microscopic dynamics. We obtain the mean-field equilibrium associated with this model, by solving the corresponding initial-terminal value problem. We perform an asymptotic analysis to obtain a stationary equilibrium for the system. The second contribution involves the study of the microscopic dynamics of the system for a finite number of players that interact in a structured environment modeled by an interaction topology. The third contribution is the specialization of the model to describe honeybee swarms, virus propagation, and cascading failures in interconnected smart-grids. A numerical analysis is conducted which involves two types of cyber-attacks. We simulate in which ways failures propagate across the interconnected smart grids and the impact on the grids frequencies. We reframe our analysis within the context of Lyapunov's linearisation method and stability theory of nonlinear systems and Kuramoto coupled oscillators model.
• ### Nonlinear network dynamics for interconnected micro-grids(1708.07296)

Aug. 24, 2017 math.OC
This paper deals with transient stability in interconnected micro-grids. The main contribution involves i) robust classification of transient dynamics for different intervals of the micro-grid parameters (synchronization, inertia, and damping); ii) exploration of the analogies with consensus dynamics and bounds on the damping coefficient separating underdamped and overdamped dynamics iii) the extension to the case of disturbed measurements due to hackering or parameter uncertainties.
• ### Distributionally Robust Games: f-Divergence and Learning(1702.05371)

July 23, 2017 cs.GT, math.OC
In this paper we introduce the novel framework of distributionally robust games. These are multi-player games where each player models the state of nature using a worst-case distribution, also called adversarial distribution. Thus each player's payoff depends on the other players' decisions and on the decision of a virtual player (nature) who selects an adversarial distribution of scenarios. This paper provides three main contributions. Firstly, the distributionally robust game is formulated using the statistical notions of $f$-divergence between two distributions, here represented by the adversarial distribution, and the exact distribution. Secondly, the complexity of the problem is significantly reduced by means of triality theory. Thirdly, stochastic Bregman learning algorithms are proposed to speedup the computation of robust equilibria. Finally, the theoretical findings are illustrated in a convex setting and its limitations are tested with a non-convex non-concave function.
• ### Bio-inspired Evolutionary Game Dynamics on Complex Networks under Uncertain Cross-inhibitory Signals(1706.01257)

June 5, 2017 cs.SY
Given a large population of players, each player has three possible choices between option 1 or 2 or no option. The two options are equally favorable and the population has to reach consensus on one of the two options quickly and in a distributed way. The more popular an option is, the more likely it is to be chosen by uncommitted players. Uncommitted players can be attracted by those committed to any of the other two options through a cross-inhibitory signal. This model originates in the context of honeybees swarms, and we generalize it to duopolistic competition and opinion dynamics. The contributions of this work include (1) the formulation of an evolutionary game model to explain the behavioral traits of the honeybees, (2) the study of the individuals and collective behavior including equilibrium points and stability, (3) the extension of the results to the case of structured environment via complex network theory, (4) the analysis of the impact of the connectivity on consensus, and (5) the study of absolute stability for the collective system under time-varying and uncertain cross-inhibitory parameter.
• ### A game-theoretic approach to dynamic demand response management(1410.6840)

Oct. 24, 2014 math.OC
Within the realm of dynamic of \emph{smart buildings} and \emph{smart cities}, dynamic response management is playing an ever-increasing role thus attracting the attention of scientists from different disciplines. Dynamic demand response management involves a set of operations aiming at decentralizing the control of loads in large and complex power networks. Each single appliance if fully responsive and readjusts its energy demand to the overall network load. A main issue is related to mains frequency oscillations resulting from an unbalance between supply and demand. In a nutshell, this paper contributes to the topic by equipping each signal consumer with strategic insight. In particular, we highlight three main contributions and a few other minor contributions. First, we design a mean-field game for the TCLs application, study the mean-field equilibrium for the deterministic mean-field game and investigate on asymptotic stability for the microscopic dynamics. Second, we extend the analysis and design to imperfect models which involve both stochastic or deterministic disturbances. This leads to robust mean-field equilibrium strategies guaranteeing stochastic and worst-case stability, respectively. Minor contributions involve the use of stochastic control strategies rather than deterministic, and some numerical studies illustrating the efficacy of the proposed strategies.
• ### Approachability in Population Games(1407.3910)

July 15, 2014 math.OC
This paper reframes approachability theory within the context of population games. Thus, whilst one player aims at driving her average payoff to a predefined set, her opponent is not malevolent but rather extracted randomly from a population of individuals with given distribution on actions. First, convergence conditions are revisited based on the common prior on the population distribution, and we define the notion of \emph{1st-moment approachability}. Second, we develop a model of two coupled partial differential equations (PDEs) in the spirit of mean-field game theory: one describing the best-response of every player given the population distribution (this is a \emph{Hamilton-Jacobi-Bellman equation}), the other capturing the macroscopic evolution of average payoffs if every player plays its best response (this is an \emph{advection equation}). Third, we provide a detailed analysis of existence, nonuniqueness, and stability of equilibria (fixed points of the two PDEs). Fourth, we apply the model to regret-based dynamics, and use it to establish convergence to Bayesian equilibrium under incomplete information.
• ### Mean-Field Games for Marriage(1404.3389)

April 13, 2014 math.PR, math.DS, cs.GT, math.OC, cs.SY
This article examines mean-field games for marriage. The results support the argument that optimizing the long-term well-being through effort and social feeling state distribution (mean-field) will help to stabilize marriage. However, if the cost of effort is very high, the couple fluctuates in a bad feeling state or the marriage breaks down. We then examine the influence of society on a couple using mean field sentimental games. We show that, in mean-field equilibrium, the optimal effort is always higher than the one-shot optimal effort. We illustrate numerically the influence of the couple's network on their feeling states and their well-being.
• ### Attainability in Repeated Games with Vector Payoffs(1201.6054)

March 6, 2014 cs.GT, math.OC
We introduce the concept of attainable sets of payoffs in two-player repeated games with vector payoffs. A set of payoff vectors is called {\em attainable} if player 1 can ensure that there is a finite horizon $T$ such that after time $T$ the distance between the set and the cumulative payoff is arbitrarily small, regardless of what strategy player 2 is using. This paper focuses on the case where the attainable set consists of one payoff vector. In this case the vector is called an attainable vector. We study properties of the set of attainable vectors, and characterize when a specific vector is attainable and when every vector is attainable.
• ### Finite Alphabet Control of Logistic Networks with Discrete Uncertainty(1111.0700)

Oct. 9, 2013 math.OC, cs.SY
We consider logistic networks in which the control and disturbance inputs take values in finite sets. We derive a necessary and sufficient condition for the existence of robustly control invariant (hyperbox) sets. We show that a stronger version of this condition is sufficient to guarantee robust global attractivity, and we construct a counterexample demonstrating that it is not necessary. Being constructive, our proofs of sufficiency allow us to extract the corresponding robust control laws and to establish the invariance of certain sets. Finally, we highlight parallels between our results and existing results in the literature, and we conclude our study with two simple illustrative examples.
• ### Distributed $n$-player approachability and consensus in coalitional games(1310.1874)

Oct. 7, 2013 math.OC
We study a distributed allocation process where, repeatedly in time, every player renegotiates past allocations with neighbors and allocates new revenues. The average allocations evolve according to a doubly (over time and space) averaging algorithm. We study conditions under which the average allocations reach consensus to any point within a predefined target set even in the presence of adversarial disturbances. Motivations arise in the context of coalitional games with transferable utilities (TU) where the target set is any set of allocations that make the grand coalitions stable.
• ### Lyapunov stochastic stability and control of robust dynamic coalitional games with transferable utilities(1106.1933)

April 23, 2012 cs.GT, math.OC, cs.LG, cs.SY
This paper considers a dynamic game with transferable utilities (TU), where the characteristic function is a continuous-time bounded mean ergodic process. A central planner interacts continuously over time with the players by choosing the instantaneous allocations subject to budget constraints. Before the game starts, the central planner knows the nature of the process (bounded mean ergodic), the bounded set from which the coalitions' values are sampled, and the long run average coalitions' values. On the other hand, he has no knowledge of the underlying probability function generating the coalitions' values. Our goal is to find allocation rules that use a measure of the extra reward that a coalition has received up to the current time by re-distributing the budget among the players. The objective is two-fold: i) guaranteeing convergence of the average allocations to the core (or a specific point in the core) of the average game, ii) driving the coalitions' excesses to an a priori given cone. The resulting allocation rules are robust as they guarantee the aforementioned convergence properties despite the uncertain and time-varying nature of the coaltions' values. We highlight three main contributions. First, we design an allocation rule based on full observation of the extra reward so that the average allocation approaches a specific point in the core of the average game, while the coalitions' excesses converge to an a priori given direction. Second, we design a new allocation rule based on partial observation on the extra reward so that the average allocation converges to the core of the average game, while the coalitions' excesses converge to an a priori given cone. And third, we establish connections to approachability theory and attainability theory.
• ### Dynamic Coalitional TU Games: Distributed Bargaining among Players' Neighbors(1101.4536)

Jan. 24, 2011 math.OC
We consider a sequence of transferable utility (TU) games where, at each time, the characteristic function is a random vector with realizations restricted to some set of values. The game differs from other ones in the literature on dynamic, stochastic or interval valued TU games as it combines dynamics of the game with an allocation protocol for the players that dynamically interact with each other. The protocol is an iterative and decentralized algorithm that offers a paradigmatic mathematical description of negotiation and bargaining processes. The first part of the paper contributes to the definition of a robust (coalitional) TU game and the development of a distributed bargaining protocol. We prove the convergence with probability 1 of the bargaining process to a random allocation that lies in the core of the robust game under some mild conditions on the underlying communication graphs. The second part of the paper addresses the more general case where the robust game may have empty core. In this case, with the dynamic game we associate a dynamic average game by averaging over time the sequence of characteristic functions. Then, we consider an accordingly modified bargaining protocol. Assuming that the sequence of characteristic functions is ergodic and the core of the average game has a nonempty relative interior, we show that the modified bargaining protocol converges with probability 1 to a random allocation that lies in the core of the average game.
• ### Mixed integer predictive control and shortest path reformulation(1003.2889)

March 15, 2010 math.DS, math.OC
Mixed integer predictive control deals with optimizing integer and real control variables over a receding horizon. The mixed integer nature of controls might be a cause of intractability for instances of larger dimensions. To tackle this little issue, we propose a decomposition method which turns the original $n$-dimensional problem into $n$ indipendent scalar problems of lot sizing form. Each scalar problem is then reformulated as a shortest path one and solved through linear programming over a receding horizon. This last reformulation step mirrors a standard procedure in mixed integer programming. The approximation introduced by the decomposition can be lowered if we operate in accordance with the predictive control technique: i) optimize controls over the horizon ii) apply the first control iii) provide measurement updates of other states and repeat the procedure.
• ### Consensus for switched networks with unknown but bounded disturbances(math/0612834)

Dec. 28, 2006 math.OC
We consider stationary consensus protocols for networks of dynamic agents with switching topologies. The measure of the neighbors' state is affected by Unknown But Bounded disturbances. Here the main contribution is the formulation and solution of what we call the $\epsilon$-consensus problem, where the states are required to converge in a tube of ray $\epsilon$ asymptotically or in finite time.