SU\G(𝔸)/K·U
Sign Up for free Log In

Author Description

Login to generate an author description

Ask a Question About This Mathematician

All published works (92)

Distributed Learning Dynamics Converging to the Core of B-Matchings

2024-12-16
Aya Hamed , Jeff S. Shamma
Chat View PDF

Payoff-Based Dynamics for Multi-Player Weakly Acyclic Games

2024-10-10
H. Peyton Young , Jason R. Marden , Gürdal Arslan +1 more
Abstract This chapter focusses on the class of n-person games that are weakly acyclic in better replies, that is, from any initial combination of stage-game strategies there is a sequence … Abstract This chapter focusses on the class of n-person games that are weakly acyclic in better replies, that is, from any initial combination of stage-game strategies there is a sequence of better replies that lead to a pure Nash equilibrium. An adaptive process is payoff-based or completely uncoupled if the process depends only on a player’s own actions and own payoffs from previous play; it does not depend on the actions taken by other players or their realized payoffs. The chapter analyses simple payoff-based learning processes in which players occasionally experiment with alternative actions and retain them if they yield higher payoffs. In a weakly acyclic game this type of decentralized learning process leads to equilibrium play with probability one. An important application is to multi-agent distributed control problems. The methodology is illustrated with simulations of distributed routing over a network.

Distributed Learning Dynamics Converging to the Core of $B$-Matchings

2024-09-12
Aya Hamed , Jeff S. Shamma
$B$-Matching is a special case of matching problems where nodes can join multiple matchings with the degree of each node constrained by an upper bound, the node's $B$-value. The core … $B$-Matching is a special case of matching problems where nodes can join multiple matchings with the degree of each node constrained by an upper bound, the node's $B$-value. The core solution of a bipartite $B$-matching is both a matching between the nodes respecting the upper bound constraint and an allocation of the weights of the edges among the nodes such that no group of nodes can deviate and collectively gain higher allocation. We present two learning dynamics that converge to the core of the bipartite $B$-matching problems. The first dynamics are centralized dynamics in the nature of the Hungarian method, which converge to the core in a polynomial time. The second dynamics are distributed dynamics, which converge to the core with probability one. For the distributed dynamics, a node maintains only a state consisting of (i) the aspiration levels for all of its possible matches and (ii) the matches, if any, to which it belongs. The node does not keep track of its history nor is it aware of the environment state. In each stage, a randomly activated node proposes to form a new match and changes its aspiration based on the success or failure of its proposal. At this stage, the proposing node inquires about the aspiration of the node it wants to match with to calculate the feasibility of the match. The environment matching structure changes whenever a proposal succeeds. A state is absorbing for the distributed dynamics if and only if it is in the core of the $B$-matching.
Chat View PDF

Polynomial Lyapunov Functions and Invariant Sets from a New Hierarchy of Quadratic Lyapunov Functions for LTV Systems

2024-07-10
Hassan Abdelraouf , Éric Féron , Jeff S. Shamma
Chat View PDF

Equilibrium Selection for Multi-agent Reinforcement Learning: A Unified Framework

2024-06-13
Runyu Zhang , Jeff S. Shamma , Na Li
While there are numerous works in multi-agent reinforcement learning (MARL), most of them focus on designing algorithms and proving convergence to a Nash equilibrium (NE) or other equilibrium such as … While there are numerous works in multi-agent reinforcement learning (MARL), most of them focus on designing algorithms and proving convergence to a Nash equilibrium (NE) or other equilibrium such as coarse correlated equilibrium. However, NEs can be non-unique and their performance varies drastically. Thus, it is important to design algorithms that converge to Nash equilibrium with better rewards or social welfare. In contrast, classical game theory literature has extensively studied equilibrium selection for multi-agent learning in normal-form games, demonstrating that decentralized learning algorithms can asymptotically converge to potential-maximizing or Pareto-optimal NEs. These insights motivate this paper to investigate equilibrium selection in the MARL setting. We focus on the stochastic game model, leveraging classical equilibrium selection results from normal-form games to propose a unified framework for equilibrium selection in stochastic games. The proposed framework is highly modular and can extend various learning rules and their corresponding equilibrium selection results from normal-form games to the stochastic game setting.
Chat View PDF

Polynomial Lyapunov Functions and Invariant Sets from a New Hierarchy of Quadratic Lyapunov Functions for LTV Systems

2024-01-01
Hassan Abdelraouf , Éric Féron , Jeff S. Shamma
We introduce a new class of quadratic functions based on a hierarchy of linear time-varying (LTV) dynamical systems. These quadratic functions in the higher order space can be also seen … We introduce a new class of quadratic functions based on a hierarchy of linear time-varying (LTV) dynamical systems. These quadratic functions in the higher order space can be also seen as a non-homogeneous polynomial Lyapunov functions for the original system, i.e the first system in the hierarchy. These non-homogeneous polynomials are used to obtain accurate outer approximation for the reachable set given the initial condition and less conservative bounds for the impulse response peak of linear, possibly time-varying systems. In addition, we pose an extension to the presented approach to construct invariant sets that are not necessarily Lyapunov functions. The introduced methods are based on elementary linear systems theory and offer very much flexibility in defining arbitrary polynomial Lyapunov functions and invariant sets for LTV systems.
Chat View PDF

Distributed Learning Dynamics for Coalitional Games

2023-12-13
Aya Hamed , Jeff S. Shamma
In the framework of transferable utility coalitional games, a scoring (characteristic) function determines the value of any subset/coalition of agents. Agents decide on both which coalitions to form and the … In the framework of transferable utility coalitional games, a scoring (characteristic) function determines the value of any subset/coalition of agents. Agents decide on both which coalitions to form and the allocations of the values of the formed coalitions among their members. An important concept in coalitional games is that of a core solution, which is a partitioning of agents into coalitions and an associated allocation to each agent under which no group of agents can get a higher allocation by forming an alternative coalition. We present distributed learning dynamics for coalitional games that converge to a core solution whenever one exists. In these dynamics, an agent maintains a state consisting of (i) an aspiration level for its allocation and (ii) the coalition, if any, to which it belongs. In each stage, a randomly activated agent proposes to form a new coalition and changes its aspiration based on the success or failure of its proposal. The coalition membership structure is changed, accordingly, whenever the proposal succeeds. Required communications are that: (i) agents in the proposed new coalition need to reveal their current aspirations to the proposing agent, and (ii) agents are informed if they are joining the proposed coalition or if their existing coalition is broken. The proposing agent computes the feasibility of forming the coalition. We show that the dynamics hit an absorbing state whenever a core solution is reached. We further illustrate the distributed learning dynamics on a multi-agent task allocation setting.
Chat View PDF

Can Competition Outperform Collaboration? The Role of Misbehaving Agents

2023-11-03
Luca Ballotta , Giacomo Como , Jeff S. Shamma +1 more
We investigate a novel approach to resilient distributed optimization with quadratic costs in a multiagent system prone to unexpected events that make some agents misbehave. In contrast to commonly adopted … We investigate a novel approach to resilient distributed optimization with quadratic costs in a multiagent system prone to unexpected events that make some agents misbehave. In contrast to commonly adopted filtering strategies, we draw inspiration from phenomena modeled through the Friedkin-Johnsen dynamics and argue that adding competition to the mix can improve resilience in the presence of misbehaving agents. Our intuition is corroborated by analytical and numerical results showing that <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(i)</i> there exists a nontrivial trade-off between full collaboration and full competition and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(ii)</i> our competition-based approach can outperform state-of-the-art algorithms based on Weighted Mean Subsequence Reduced. We also study impact of communication topology and connectivity on resilience, pointing out insights to robust network design.
Chat View PDF

Online switching control with stability and regret guarantees

2023-01-01
Yingying Li , James A. Preiss , Na Li +3 more
This paper considers online switching control with a finite candidate controller pool, an unknown dynamical system, and unknown cost functions. The candidate controllers can be unstabilizing policies. We only require … This paper considers online switching control with a finite candidate controller pool, an unknown dynamical system, and unknown cost functions. The candidate controllers can be unstabilizing policies. We only require at least one candidate controller to satisfy certain stability properties, but we do not know which one is stabilizing. We design an online algorithm that guarantees finite-gain stability throughout the duration of its execution. We also provide a sublinear policy regret guarantee compared with the optimal stabilizing candidate controller. Lastly, we numerically test our algorithm on quadrotor planar flights and compare it with a classical switching control algorithm, falsification-based switching, and a classical multi-armed bandit algorithm, Exp3 with batches.
Chat View PDF

Algebraic Lyapunov Functions for Homogeneous Dynamic Systems

2023-01-01
Hassan Abdelraouf , Éric Féron , Jeff S. Shamma
A method for constructing homogeneous Lyapunov functions of degree 1 from polynomial invariant sets is presented for linear time varying systems, homogeneous dynamic systems and the class of nonlinear systems … A method for constructing homogeneous Lyapunov functions of degree 1 from polynomial invariant sets is presented for linear time varying systems, homogeneous dynamic systems and the class of nonlinear systems that can be represented as such. The method allows the development of Lyapunov functions that are not necessarily symmetric about the origin, unlike the polynomial, homogeneous Lyapunov functions discussed in the prior literature. The work is illustrated by very simple examples.
Chat View PDF

Higher-Order Uncoupled Dynamics Do Not Lead to Nash Equilibrium -- Except When They Do

2023-01-01
Sarah A. Toonsi , Jeff S. Shamma
The framework of multi-agent learning explores the dynamics of how individual agent strategies evolve in response to the evolving strategies of other agents. Of particular interest is whether or not … The framework of multi-agent learning explores the dynamics of how individual agent strategies evolve in response to the evolving strategies of other agents. Of particular interest is whether or not agent strategies converge to well known solution concepts such as Nash Equilibrium (NE). Most "fixed order" learning dynamics restrict an agent's underlying state to be its own strategy. In "higher order" learning, agent dynamics can include auxiliary states that can capture phenomena such as path dependencies. We introduce higher-order gradient play dynamics that resemble projected gradient ascent with auxiliary states. The dynamics are "payoff based" in that each agent's dynamics depend on its own evolving payoff. While these payoffs depend on the strategies of other agents in a game setting, agent dynamics do not depend explicitly on the nature of the game or the strategies of other agents. In this sense, dynamics are "uncoupled" since an agent's dynamics do not depend explicitly on the utility functions of other agents. We first show that for any specific game with an isolated completely mixed-strategy NE, there exist higher-order gradient play dynamics that lead (locally) to that NE, both for the specific game and nearby games with perturbed utility functions. Conversely, we show that for any higher-order gradient play dynamics, there exists a game with a unique isolated completely mixed-strategy NE for which the dynamics do not lead to NE. These results build on prior work that showed that uncoupled fixed-order learning cannot lead to NE in certain instances, whereas higher-order variants can. Finally, we consider the mixed-strategy equilibrium associated with coordination games. While higher-order gradient play can converge to such equilibria, we show such dynamics must be inherently internally unstable.
Chat View PDF

Non-asymptotic System Identification for Linear Systems with Nonlinear Policies

2023-01-01
Yingying Li , Tianpeng Zhang , Subhro Das +2 more
This paper considers a single-trajectory system identification problem for linear systems under general nonlinear and/or time-varying policies with i.i.d. random excitation noises. The problem is motivated by safe learning-based control … This paper considers a single-trajectory system identification problem for linear systems under general nonlinear and/or time-varying policies with i.i.d. random excitation noises. The problem is motivated by safe learning-based control for constrained linear systems, where the safe policies during the learning process are usually nonlinear and time-varying for satisfying the state and input constraints. In this paper, we provide a non-asymptotic error bound for least square estimation when the data trajectory is generated by any nonlinear and/or time-varying policies as long as the generated state and action trajectories are bounded. This significantly generalizes the existing non-asymptotic guarantees for linear system identification, which usually consider i.i.d. random inputs or linear policies. Interestingly, our error bound is consistent with that for linear policies with respect to the dependence on the trajectory length, system dimensions, and excitation levels. Lastly, we demonstrate the applications of our results by safe learning with robust model predictive control and provide numerical analysis.
Chat View PDF

Distributed Learning Dynamics for Coalitional Games

2023-01-01
Aya Hamed , Jeff S. Shamma
In the framework of transferable utility coalitional games, a scoring (characteristic) function determines the value of any subset/coalition of agents. Agents decide on both which coalitions to form and the … In the framework of transferable utility coalitional games, a scoring (characteristic) function determines the value of any subset/coalition of agents. Agents decide on both which coalitions to form and the allocations of the values of the formed coalitions among their members. An important concept in coalitional games is that of a core solution, which is a partitioning of agents into coalitions and an associated allocation to each agent under which no group of agents can get a higher allocation by forming an alternative coalition. We present distributed learning dynamics for coalitional games that converge to a core solution whenever one exists. In these dynamics, an agent maintains a state consisting of (i) an aspiration level for its allocation and (ii) the coalition, if any, to which it belongs. In each stage, a randomly activated agent proposes to form a new coalition and changes its aspiration based on the success or failure of its proposal. The coalition membership structure is changed, accordingly, whenever the proposal succeeds. Required communications are that: (i) agents in the proposed new coalition need to reveal their current aspirations to the proposing agent, and (ii) agents are informed if they are joining the proposed coalition or if their existing coalition is broken. The proposing agent computes the feasibility of forming the coalition. We show that the dynamics hit an absorbing state whenever a core solution is reached. We further illustrate the distributed learning dynamics on a multi-agent task allocation setting.
Chat View PDF

Non-asymptotic System Identification for Linear Systems with Nonlinear Policies

2023-01-01
Yingying Li , Tianpeng Zhang , Subhro Das +2 more
This paper considers a single-trajectory system identification problem for linear systems under general nonlinear and/or time-varying policies with i.i.d. random excitation noises. The problem is motivated by safe learning-based control … This paper considers a single-trajectory system identification problem for linear systems under general nonlinear and/or time-varying policies with i.i.d. random excitation noises. The problem is motivated by safe learning-based control for constrained linear systems, where the safe policies during the learning process are usually nonlinear and time-varying for satisfying the state and input constraints. In this paper, we provide a non-asymptotic error bound for least square estimation when the data trajectory is generated by any nonlinear and/or time-varying policies as long as the generated state and action trajectories are bounded. This significantly generalizes the existing non-asymptotic guarantees for linear system identification, which usually consider i.i.d. random inputs or linear policies. Interestingly, our error bound is consistent with that for linear policies with respect to the dependence on the trajectory length, system dimensions, and excitation levels. Lastly, we demonstrate the applications of our results by safe learning with robust model predictive control and provide numerical analysis.
Chat View PDF

Competition-Based Resilience in Distributed Quadratic Optimization

2022-12-06
Luca Ballotta , Giacomo Como , Jeff S. Shamma +1 more
We propose a competition-based approach to resilient distributed optimization with quadratic costs in Networked Control Systems (e.g., wireless sensor network, power grid, robotic team) where a fraction of agents may … We propose a competition-based approach to resilient distributed optimization with quadratic costs in Networked Control Systems (e.g., wireless sensor network, power grid, robotic team) where a fraction of agents may misbehave (through, e.g., hacking or power outage). Departing from classical filtering strategies proposed in literature, and inspired by a game-theoretic interpretation of consensus, we propose to introduce competition among normally behaving agents as a mean to enhance resilience against malicious attacks. Our proposal is supported by formal and heuristic results which show that i) there exists a nontrivial trade-off between blind collaboration and full competition and ii) the proposed approach can outperform standard techniques based on the algorithm Mean Subsequence Reduced.
Chat View PDF

Competition-Based Resilience in Distributed Quadratic Optimization

2022-01-01
Luca Ballotta , Giacomo Como , Jeff S. Shamma +1 more
This paper proposes a novel approach to resilient distributed optimization with quadratic costs in a networked control system (e.g., wireless sensor network, power grid, robotic team) prone to external attacks … This paper proposes a novel approach to resilient distributed optimization with quadratic costs in a networked control system (e.g., wireless sensor network, power grid, robotic team) prone to external attacks (e.g., hacking, power outage) that cause agents to misbehave. Departing from classical filtering strategies proposed in literature, we draw inspiration from a game-theoretic formulation of the consensus problem and argue that adding competition to the mix can enhance resilience in the presence of malicious agents. Our intuition is corroborated by analytical and numerical results showing that i) our strategy highlights the presence of a nontrivial tradeoff between blind collaboration and full competition, and ii) such competition-based approach can outperform state-of-the-art algorithms based on Mean Subsequence Reduced.
Chat View PDF

Can Competition Outperform Collaboration? The Role of Misbehaving Agents

2022-01-01
Luca Ballotta , Giacomo Como , Jeff S. Shamma +1 more
We investigate a novel approach to resilient distributed optimization with quadratic costs in a multi-agent system prone to unexpected events that make some agents misbehave. In contrast to commonly adopted … We investigate a novel approach to resilient distributed optimization with quadratic costs in a multi-agent system prone to unexpected events that make some agents misbehave. In contrast to commonly adopted filtering strategies, we draw inspiration from phenomena modeled through the Friedkin-Johnsen dynamics and argue that adding competition to the mix can improve resilience in the presence of misbehaving agents. Our intuition is corroborated by analytical and numerical results showing that (i) there exists a nontrivial trade-off between full collaboration and full competition and (ii) our competition-based approach can outperform state-of-the-art algorithms based on Weighted Mean Subsequence Reduced. We also study impact of communication topology and connectivity on resilience, pointing out insights to robust network design.
Chat View PDF

Multi-sided Matching for the Association of Space-Air-Ground Integrated Systems

2021-10-19
Doha Hamza , Hajar El Hammouti , Jeff S. Shamma +1 more
Space-air-ground integrated networks (SAGINs) will play a key role in 6G communication systems. They are considered a promising technology to enhance the network capacity in highly dense agglomerations and to … Space-air-ground integrated networks (SAGINs) will play a key role in 6G communication systems. They are considered a promising technology to enhance the network capacity in highly dense agglomerations and to provide connectivity in rural areas. The multi-layer and heterogeneous nature of SAGINs necessitates an innovative design of their multi-tier associations. We propose a modeling of the SAGINs association problem using multi-sided matching theory. Our aim is to provide a reliable, asynchronous and fully distributed approach that associates nodes across the layers so that the total end-to-end rate of the assigned agents is maximized. To this end, our problem is modeled as a multi-sided many-to-one matching game. A randomized matching algorithm with low information exchange is proposed. The algorithm is shown to reach an efficient and stable association between nodes in adjacent layers. Our simulation results show that the proposed approach achieves significant gain compared to the greedy and distance-based algorithms.
Chat View PDF

The Optimal and the Greedy: Drone Association and Positioning Schemes for Internet of UAVs

2021-03-31
Hajar El Hammouti , Doha Hamza , Basem Shihada +2 more
This work considers the deployment of unmanned aerial vehicles (UAVs) over a predefined area to serve a number of ground users. Due to the heterogeneous nature of the network, the … This work considers the deployment of unmanned aerial vehicles (UAVs) over a predefined area to serve a number of ground users. Due to the heterogeneous nature of the network, the UAVs may cause severe interference to the transmissions of each other. Hence, a judicious design of the user-UAV association and UAV locations is desired. A potential game is defined where the players are the UAVs. The potential function is the total sum rate of the users. The agents' utility in the potential game is their marginal contribution to the global welfare or their so-called wonderful life utility. A game-theoretic learning algorithm, binary log-linear learning (BLLL), is then applied to the problem. Given the potential game structure, a consequence of our utility design, the stochastically stable states using BLLL are guaranteed to be the potential maximizers. Hence, we optimally solve the joint user-UAV association and 3-D-location problem. Next, we exploit the submodular features of the sum rate function for a given configuration of UAVs to design an efficient greedy algorithm. Despite the simplicity of the greedy algorithm, it comes with a performance guarantee of 1-1/e of the optimal solution. To further reduce the number of iterations, we propose another heuristic greedy algorithm that provides very good results. Our simulations show that, in practice, the proposed greedy approaches achieve significant performance in a few iterations.
Chat View PDF

RISCuer: a reliable multi-UAV search and rescue testbed

2021-01-01
Mohamed Abdelkader , Usman A. Fiaz , Noureddine Toumi +2 more
Chat View PDF

Safe Adaptive Learning-based Control for Constrained Linear Quadratic Regulators with Regret Guarantees

2021-01-01
Yingying Li , Subhro Das , Jeff S. Shamma +1 more
We study the adaptive control of an unknown linear system with a quadratic cost function subject to safety constraints on both the states and actions. The challenges of this problem … We study the adaptive control of an unknown linear system with a quadratic cost function subject to safety constraints on both the states and actions. The challenges of this problem arise from the tension among safety, exploration, performance, and computation. To address these challenges, we propose a polynomial-time algorithm that guarantees feasibility and constraint satisfaction with high probability under proper conditions. Our algorithm is implemented on a single trajectory and does not require system restarts. Further, we analyze the regret of our learning algorithm compared to the optimal safe linear controller with known model information. The proposed algorithm can achieve a $\tilde O(T^{2/3})$ regret, where $T$ is the number of stages and $\tilde O(\cdot)$ absorbs some logarithmic terms of $T$.
Chat View PDF

Multi-sided Matching for the Association of Space-Air-Ground Integrated Systems

2021-01-01
Doha Hamza , Hajar El Hammouti , Jeff S. Shamma +1 more
Space-air-ground integrated networks (SAGINs) will play a key role in 6G communication systems. They are considered a promising technology to enhance the network capacity in highly dense agglomerations and to … Space-air-ground integrated networks (SAGINs) will play a key role in 6G communication systems. They are considered a promising technology to enhance the network capacity in highly dense agglomerations and to provide connectivity in rural areas. The multi-layer and heterogeneous nature of SAGINs necessitates an innovative design of their multi-tier associations. We propose a modeling of the SAGINs association problem using multi-sided matching theory. Our aim is to provide a reliable, asynchronous and fully distributed approach that associates nodes across the layers so that the total end-to-end rate of the assigned agents is maximized. To this end, our problem is modeled as a multi-sided many-to-one matching game. A randomized matching algorithm with low information exchange is proposed. The algorithm is shown to reach an efficient and stable association between nodes in adjacent layers. Our simulation results show that the proposed approach achieves significant gain compared to the greedy and distance-based algorithms.
Chat View PDF

Path to Stochastic Stability: Comparative Analysis of Stochastic Learning Dynamics in Games

2020-11-20
Hassan Jaleel , Jeff S. Shamma
Stochastic stability is an important solution concept for stochastic learning dynamics in games. However, a limitation of this solution concept is its inability to distinguish between different learning rules that … Stochastic stability is an important solution concept for stochastic learning dynamics in games. However, a limitation of this solution concept is its inability to distinguish between different learning rules that lead to the same steady-state behavior. We identify this limitation and develop a framework for the comparative analysis of the transient behavior of stochastic learning dynamics. We present the framework in the context of two learning dynamics: Log-linear learning (LLL) and Metropolis learning (ML). Although both of these dynamics lead to the same steady-state behavior, they correspond to different behavioral models for decision making. In this article, we propose multiple criteria to analyze and quantify the differences in the short and medium-run behaviors of stochastic dynamics. We derive upper bounds on the expected hitting time of the set of Nash equilibria for both LLL and ML. For the medium to long-run behavior, we identify a set of tools from the theory of perturbed Markov chains that result in a hierarchical decomposition of the state space into collections of states called cycles. We compare LLL and ML based on the proposed criteria and develop invaluable insights into the behavior of the two dynamics.
Chat View PDF

The Optimal and the Greedy: Drone Association and Positioning Schemes for Internet of UAVs.

2020-04-02
Hajar El Hammouti , Doha Hamza , Basem Shihada +2 more
This work considers the deployment of unmanned aerial vehicles (UAVs) over a predefined area to serve a number of ground users. Due to the heterogeneous nature of the network,the UAVs … This work considers the deployment of unmanned aerial vehicles (UAVs) over a predefined area to serve a number of ground users. Due to the heterogeneous nature of the network,the UAVs may cause severe interference to the transmissions of each other. Hence, a judicious design of the user-UAV association and UAV locations is desired. A potential game is defined where the players are the UAVs. The potential function is the total sum-rate of the users. The agents utility in the potential games is their marginal contribution to the global welfare or their so-called wonderful life utility. A game-theoretic learning algorithm, binary log-linear learning (BLLL), is then applied to the problem. Given the potential game structure, a consequence of our utility design, the stochastically stable states using BLLL are guaranteed to be the potential maximizers. Hence, we optimally solve the user-UAV association and 3D-location problem. Next, we exploit the sub-modular features of the sum rate function for a given configuration of UAVs to design an efficient greedy algorithm. Despite the simplicity of the greedy algorithm, it comes with a guaranteed performance of $1-1/e$ of the optimal solution. To further reduce the number of iterations, we propose another heuristic greedy algorithm that provides very good results. Our simulations show that, in practice, the proposed greedy approaches achieve significant performance in a few number of iterations.

Point-to-Point Communication in Integrated Satellite-Aerial Networks: State-of-the-art and Future Challenges

2020-01-01
Nasir Saeed , Heba Almorad , Hayssam Dahrouj +3 more
This paper overviews point-to-point (P2P) links for integrated satellite-aerial networks, which are envisioned to be among the key enablers of the sixth-generation (6G) of wireless networks vision. The paper first … This paper overviews point-to-point (P2P) links for integrated satellite-aerial networks, which are envisioned to be among the key enablers of the sixth-generation (6G) of wireless networks vision. The paper first outlines the unique characteristics of such integrated large-scale complex networks, often denoted by spatial networks, and focuses on two particular space-air infrastructures, namely, satellites networks and high-altitude platforms (HAPs). The paper then classifies the connecting P2P communications links as satellite-to-satellite links at the same layer (SSLL), satellite-to-satellite links at different layers (SSLD), and HAP-to-HAP links (HHL). The paper overviews each layer of such spatial networks separately, and highlights the possible natures of the connecting links (i.e., radio-frequency or free-space optics) with a dedicated overview to the existing link-budget results. The paper, afterwards, presents the prospective merit of realizing such an integrated satellite-HAP network towards providing broadband services in under-served and remote areas. Finally, the paper sheds light on several future research directions in the context of spatial networks, namely large-scale network optimization, intelligent offloading, smart platforms, energy efficiency, multiple access schemes, and distributed spatial networks.
Chat View PDF

The Optimal and the Greedy: Drone Association and Positioning Schemes for Internet of UAVs

2020-01-01
Hajar El Hammouti , Doha Hamza , Basem Shihada +2 more
This work considers the deployment of unmanned aerial vehicles (UAVs) over a predefined area to serve a number of ground users. Due to the heterogeneous nature of the network,the UAVs … This work considers the deployment of unmanned aerial vehicles (UAVs) over a predefined area to serve a number of ground users. Due to the heterogeneous nature of the network,the UAVs may cause severe interference to the transmissions of each other. Hence, a judicious design of the user-UAV association and UAV locations is desired. A potential game is defined where the players are the UAVs. The potential function is the total sum-rate of the users. The agents utility in the potential games is their marginal contribution to the global welfare or their so-called wonderful life utility. A game-theoretic learning algorithm, binary log-linear learning (BLLL), is then applied to the problem. Given the potential game structure, a consequence of our utility design, the stochastically stable states using BLLL are guaranteed to be the potential maximizers. Hence, we optimally solve the user-UAV association and 3D-location problem. Next, we exploit the sub-modular features of the sum rate function for a given configuration of UAVs to design an efficient greedy algorithm. Despite the simplicity of the greedy algorithm, it comes with a guaranteed performance of $1-1/e$ of the optimal solution. To further reduce the number of iterations, we propose another heuristic greedy algorithm that provides very good results. Our simulations show that, in practice, the proposed greedy approaches achieve significant performance in a few number of iterations.
Chat View PDF

Network Effects on the Robustness of Dynamic Systems

2019-11-08
Ketan Savla , Jeff S. Shamma , Munther A. Dahleh
We review selected results related to the robustness of networked systems in finite and asymptotically large size regimes in static and dynamical settings. In the static setting, within the framework … We review selected results related to the robustness of networked systems in finite and asymptotically large size regimes in static and dynamical settings. In the static setting, within the framework of flow over finite networks, we discuss the effect of physical constraints on robustness to loss in link capacities. In the dynamical setting, we review several settings in which small-gain-type analysis provides tight robustness guarantees for linear dynamics over finite networks toward worst-case and stochastic disturbances. We discuss network flow dynamic settings where nonlinear techniques facilitate understanding the effect, on robustness, of constraints on capacity and information, substituting information with control action, and cascading failure. We also contrast cascading failure with a representative contagion model. For asymptotically large networks, we discuss the role of network properties in connecting microscopic shocks to emergent macroscopic fluctuations under linear dynamics as well as for economic networks at equilibrium. Through this review, we aim to achieve two objectives: to highlight selected settings in which the role of the interconnectivity structure of a network in its robustness is well understood, and to highlight a few additional settings in which existing system-theoretic tools give tight robustness guarantees and that are also appropriate avenues for future network-theoretic investigations.
Chat View PDF

Network Effects on Robustness of Dynamic Systems

2019-09-14
Ketan Savla , Jeff S. Shamma , Munther A. Dahleh
We review selected results related to robustness of networked systems in finite and asymptotically large size regimes, under static and dynamical settings. In the static setting, within the framework of … We review selected results related to robustness of networked systems in finite and asymptotically large size regimes, under static and dynamical settings. In the static setting, within the framework of flow over finite networks, we discuss the effect of physical constraints on robustness to loss in link capacities. In the dynamical setting, we review several settings in which small gain type analysis provides tight robustness guarantees for linear dynamics over finite networks towards worst-case and stochastic disturbances. We also discuss network flow dynamic settings where nonlinear techniques facilitate in understanding the effect on robustness of constraints on capacity and information, substituting information with control action, and cascading failure. We also contrast the latter with a representative contagion model. For asymptotically large networks, we discuss the role of network properties in connecting microscopic shocks to emergent macroscopic fluctuations under linear dynamics as well as for economic networks at equilibrium. Through the review of these results, the paper aims to achieve two objectives. First, to highlight selected settings in which the role of interconnectivity structure of a network on its robustness is well-understood. Second, to highlight a few additional settings in which existing system theoretic tools give tight robustness guarantees, and which are also appropriate avenues for future network-theoretic investigations.
Chat View PDF

Herdability of Linear Systems Based on Sign Patterns and Graph Structures.

2019-04-17
Sebastian F. Ruf , Magnus Egerstedt , Jeff S. Shamma
We consider the notion of herdability, a set-based reachability condition, which asks whether the state of a system can be controlled to be element-wise larger than a non-negative threshold. First … We consider the notion of herdability, a set-based reachability condition, which asks whether the state of a system can be controlled to be element-wise larger than a non-negative threshold. First a number of foundational results on herdability of a continuous time, linear time invariant system are presented. These show that the herdability of a linear system can be determined based on certain matrices, such as the controllability matrix, which arise in the study of controllability of linear systems. Second, the relationship between the sign pattern of the underlying graph structure of a system and the herdability properties of the system is investigated. In doing so the notion of sign herdability is introduced which captures classes of systems whose sign pattern determines their herdability. We identify a set of conditions, first on the sign pattern of the controllability matrix and then on the underlying graph structure, that ensure that the system is sign herdable.
Chat View PDF

Payoff Dynamics Model and Evolutionary Dynamics Model: Feedback and Convergence to Equilibria

2019-03-05
Shinkyu Park , Nuno C. Martins , Jeff S. Shamma
This tutorial article puts forth a framework to analyze the noncooperative strategic interactions among the members of a large population of bounded rationality agents. Our approach hinges on, unifies and … This tutorial article puts forth a framework to analyze the noncooperative strategic interactions among the members of a large population of bounded rationality agents. Our approach hinges on, unifies and generalizes existing methods and models predicated in evolutionary and population games. It does so by adopting a system-theoretic formalism that is well-suited for a broad engineering audience familiar with the basic tenets of nonlinear dynamical systems, Lyapunov stability, storage functions, and passivity. The framework is pertinent for engineering applications in which a large number of agents have the authority to select and repeatedly revise their strategies. A mechanism that is inherent to the problem at hand or is designed and implemented by a coordinator ascribes a payoff to each possible strategy. Typically, the agents will prioritize switching to strategies whose payoff is either higher than the current one or exceeds the population average. The article puts forth a systematic methodology to characterize the stability of the dynamical system that results from the feedback interaction between the payoff mechanism and the revision process. This is important because the set of stable equilibria is an accurate predictor of the population's long-term behavior. The article includes rigorous proofs and examples of application of the stability results, which also extend the state of the art because, unlike previously published work, they allow for a rather general class of dynamical payoff mechanisms. The new results and concepts proposed here are thoroughly compared to previous work, methods and applications of evolutionary and population games.
Chat View PDF

usBot: A Modular Robotic Testbed for Programmable Self-Assembly

2019-01-01
Usman A. Fiaz , Jeff S. Shamma
We present the design, characterization, and experimental results for a new modular robotic system for programmable self-assembly. The proposed system uses the Hybrid Cube Model (HCM), which integrates classical features … We present the design, characterization, and experimental results for a new modular robotic system for programmable self-assembly. The proposed system uses the Hybrid Cube Model (HCM), which integrates classical features from both deterministic and stochastic self-organization models. Thus, for instance, the modules are passive as far as their locomotion is concerned (stochastic), and yet they possess an active undocking routine (deterministic). The robots are constructed entirely from readily accessible components and unlike many existing robots, their excitation is not fluid mediated. Instead, the actuation setup is a solid state, independently programmable and highly portable platform. The system is capable of demonstrating fully autonomous and distributed stochastic self-assembly in two dimensions. It is shown to emulate the performance of several existing modular systems and promises to be a substantial effort towards developing a universal testbed for programmable self-assembly.
Chat View PDF

Smart Jammer and LTE Network Strategies in An Infinite-Horizon Zero-Sum Repeated Game with Asymmetric and Incomplete Information

2019-01-01
Farhan M. Aziz , Lichun Li , Jeff S. Shamma +1 more
LTE/LTE-Advanced networks are known to be vulnerable to denial-of-service and loss-of-service attacks from smart jammers. In this article, the interaction between a smart jammer and LTE network is modeled as … LTE/LTE-Advanced networks are known to be vulnerable to denial-of-service and loss-of-service attacks from smart jammers. In this article, the interaction between a smart jammer and LTE network is modeled as an infinite-horizon, zero-sum, asymmetric repeated game. The smart jammer and eNode B are modeled as the informed and the uninformed player, respectively. The main purpose of this article is to construct efficient suboptimal strategies for both players that can be used to solve the above-mentioned infinite-horizon repeated game with asymmetric and incomplete information. It has been shown in game-theoretic literature that security strategies provide optimal solution in zero-sum games. It is also shown that both players' security strategies in an infinite-horizon asymmetric game depend only on the history of the informed player's actions. However, fixed-sized sufficient statistics are needed for both players to solve the above-mentioned game efficiently. The smart jammer uses its evolving belief state as the fixed-sized sufficient statistics for the repeated game. Whereas, the LTE network (uninformed player) uses worst-case regret of its security strategy and its anti-discounted update as the fixed-sized sufficient statistics. Although fixed-sized sufficient statistics are employed by both players, optimal security strategy computation in λ-discounted asymmetric games is still hard to perform because of non-convexity. Hence, the problem is convexified in this article by devising `approximated' security strategies for both players that are based on approximated optimal game value. However, `approximated' strategies require full monitoring. Therefore, a simplistic yet effective `expected' strategy is also constructed for the LTE network that does not require full monitoring. The simulation results show that the smart jammer plays non-revealing and misleading strategies.
Chat View PDF

Network Effects on Robustness of Dynamic Systems

2019-01-01
Ketan Savla , Jeff S. Shamma , Munther A. Dahleh
We review selected results related to robustness of networked systems in finite and asymptotically large size regimes, under static and dynamical settings. In the static setting, within the framework of … We review selected results related to robustness of networked systems in finite and asymptotically large size regimes, under static and dynamical settings. In the static setting, within the framework of flow over finite networks, we discuss the effect of physical constraints on robustness to loss in link capacities. In the dynamical setting, we review several settings in which small gain type analysis provides tight robustness guarantees for linear dynamics over finite networks towards worst-case and stochastic disturbances. We also discuss network flow dynamic settings where nonlinear techniques facilitate in understanding the effect on robustness of constraints on capacity and information, substituting information with control action, and cascading failure. We also contrast the latter with a representative contagion model. For asymptotically large networks, we discuss the role of network properties in connecting microscopic shocks to emergent macroscopic fluctuations under linear dynamics as well as for economic networks at equilibrium. Through the review of these results, the paper aims to achieve two objectives. First, to highlight selected settings in which the role of interconnectivity structure of a network on its robustness is well-understood. Second, to highlight a few additional settings in which existing system theoretic tools give tight robustness guarantees, and which are also appropriate avenues for future network-theoretic investigations.
Chat View PDF

Herdability of Linear Systems Based on Sign Patterns and Graph Structures

2019-01-01
Sebastian F. Ruf , Magnus Egerstedt , Jeff S. Shamma
We consider the notion of herdability, a set-based reachability condition, which asks whether the state of a system can be controlled to be element-wise larger than a non-negative threshold. First … We consider the notion of herdability, a set-based reachability condition, which asks whether the state of a system can be controlled to be element-wise larger than a non-negative threshold. First a number of foundational results on herdability of a continuous time, linear time invariant system are presented. These show that the herdability of a linear system can be determined based on certain matrices, such as the controllability matrix, which arise in the study of controllability of linear systems. Second, the relationship between the sign pattern of the underlying graph structure of a system and the herdability properties of the system is investigated. In doing so the notion of sign herdability is introduced which captures classes of systems whose sign pattern determines their herdability. We identify a set of conditions, first on the sign pattern of the controllability matrix and then on the underlying graph structure, that ensure that the system is sign herdable.
Chat View PDF

Payoff Dynamics Model and Evolutionary Dynamics Model: Feedback and Convergence to Equilibria

2019-01-01
Shinkyu Park , Nuno C. Martins , Jeff S. Shamma
This tutorial article puts forth a framework to analyze the noncooperative strategic interactions among the members of a large population of bounded rationality agents. Our approach hinges on, unifies and … This tutorial article puts forth a framework to analyze the noncooperative strategic interactions among the members of a large population of bounded rationality agents. Our approach hinges on, unifies and generalizes existing methods and models predicated in evolutionary and population games. It does so by adopting a system-theoretic formalism that is well-suited for a broad engineering audience familiar with the basic tenets of nonlinear dynamical systems, Lyapunov stability, storage functions, and passivity. The framework is pertinent for engineering applications in which a large number of agents have the authority to select and repeatedly revise their strategies. A mechanism that is inherent to the problem at hand or is designed and implemented by a coordinator ascribes a payoff to each possible strategy. Typically, the agents will prioritize switching to strategies whose payoff is either higher than the current one or exceeds the population average. The article puts forth a systematic methodology to characterize the stability of the dynamical system that results from the feedback interaction between the payoff mechanism and the revision process. This is important because the set of stable equilibria is an accurate predictor of the population's long-term behavior. The article includes rigorous proofs and examples of application of the stability results, which also extend the state of the art because, unlike previously published work, they allow for a rather general class of dynamical payoff mechanisms. The new results and concepts proposed here are thoroughly compared to previous work, methods and applications of evolutionary and population games.
Chat View PDF

An LP Approach for Solving Two-Player Zero-Sum Repeated Bayesian Games

2018-12-07
Lichun Li , Cédric Langbort , Jeff S. Shamma
This paper studies two-player zero-sum repeated Bayesian games in which every player has a private type that is unknown to the other player, and the initial probability of the type … This paper studies two-player zero-sum repeated Bayesian games in which every player has a private type that is unknown to the other player, and the initial probability of the type of every player is publicly known. The types of players are independently chosen according to the initial probabilities, and are kept the same all through the game. At every stage, players simultaneously choose actions, and announce their actions publicly. For finite horizon cases, an explicit linear program is provided to compute players' security strategies. Moreover, this paper shows that a player's sufficient statistics, which is independent of the strategy of the other player, consists of the belief over the player's own type, the regret over the other player's type, and the stage. Explicit linear programs, whose size is linear in the size of the game tree, are provided to compute the initial regrets, and the security strategies that only depends on the sufficient statistics. For discounted cases, following the same idea in the finite horizon, this paper shows that a player's sufficient statistics consists of the belief of the player's own type and the antidiscounted regret with respect to the other player's type. Besides, an approximated security strategy depending on the sufficient statistics is provided, and an explicit linear program to compute the approximated security strategy is given. This paper also obtains a bound on the performance difference between the approximated security strategy and the security strategy, and shows that the bound converges to 0 exponentially fast.
Chat View PDF

Passivity and Evolutionary Game Dynamics

2018-12-01
Shinkyu Park , Jeff S. Shamma , Nuno C. Martins
This paper investigates an energy conservation and dissipation - passivity - aspect of dynamic models in evolutionary game theory. We define a notion of passivity using the state-space representation of … This paper investigates an energy conservation and dissipation - passivity - aspect of dynamic models in evolutionary game theory. We define a notion of passivity using the state-space representation of the models. Our main contributions include devising systematic methods to examine passivity and identifying properties of passive dynamic models. We explain how our main results can be used to establish a connection between passivity and stability of equilibrium in population games and provide numerical simulations to illustrate stability in population games.
Chat View PDF

Infrastructure-free Localization of Aerial Robots with Ultrawideband Sensors

2018-09-21
Samet Güler , Mohamed Abdelkader , Jeff S. Shamma
Robots in a swarm take advantage of a motion capture system or GPS sensors to obtain their global position. However, motion capture systems are environment-dependent and GPS sensors are not … Robots in a swarm take advantage of a motion capture system or GPS sensors to obtain their global position. However, motion capture systems are environment-dependent and GPS sensors are not reliable in occluded environments. For a reliable and versatile operation in a swarm, robots must sense each other and interact locally. Motivated by this requirement, here we propose an on-board localization framework for multi-robot systems. Our framework consists of an anchor robot with three ultrawideband (UWB) sensors and a tag robot with a single UWB sensor. The anchor robot utilizes the three UWB sensors as a localization infrastructure and estimates the tag robot's location by using its on-board sensing and computational capabilities solely, without explicit inter-robot communication. We utilize a dual Monte-Carlo localization approach to capture the agile maneuvers of the tag robot with an acceptable precision. We validate the effectiveness of our algorithm with simulations and indoor and outdoor experiments on a two-drone setup. The proposed dual MCL algorithm yields highly accurate estimates for various speed profiles of the tag robot and demonstrates a superior performance over the standard particle filter and the extended Kalman Filter.

Herdable Systems Over Signed, Directed Graphs

2018-06-01
Sebastian F. Ruf , Magnus Egerstedt , Jeff S. Shamma
This paper considers the notion of herdability, a set-based reachability condition, which asks whether the state of a system can be controlled to be element-wise larger than a non-negative threshold. … This paper considers the notion of herdability, a set-based reachability condition, which asks whether the state of a system can be controlled to be element-wise larger than a non-negative threshold. The basic theory of herdable systems is presented, including a necessary and sufficient condition for herdability. This paper then considers the impact of the underlying graph structure of a linear system on the herdability of the system, for the case where the graph is represented as signed and directed. By classifying nodes based on the length and sign of walks from an input, we find a class of completely herdable systems as well as provide a complete characterization of nodes that can be herded in systems with an underlying graph that is a directed out-branching rooted at a single input.
Chat View PDF

Herding Complex Networks

2018-04-12
Sebastian F. Ruf , Magnus Egersted , Jeff S. Shamma
The problem of controlling complex networks is of interest to disciplines ranging from biology to swarm robotics. However, controllability can be too strict a condition, failing to capture a range … The problem of controlling complex networks is of interest to disciplines ranging from biology to swarm robotics. However, controllability can be too strict a condition, failing to capture a range of desirable behaviors. Herdability, which describes the ability to drive a system to a specific set in the state space, was recently introduced as an alternative network control notion. This paper considers the application of herdability to the study of complex networks under the assumption that a positive system evolves on the network. The herdability of a class of networked systems is investigated and two problems related to ensuring system herdability are explored. The first is the input addition problem, which investigates which nodes in a network should receive inputs to ensure that the system is herdable. The second is a related problem of selecting the best single node from which to herd the network, in the case that a single node is guaranteed to make the system is herdable. In order to select the best herding node, a novel control energy based herdability centrality measure is introduced.
Chat View PDF

Herdable Systems Over Signed, Directed Graphs

2018-04-11
Sebastian F. Ruf , Magnus Egerstedt , Jeff S. Shamma
This paper considers the notion of herdability, a set-based reachability condition, which asks whether the state of a system can be controlled to be element-wise larger than a non-negative threshold. … This paper considers the notion of herdability, a set-based reachability condition, which asks whether the state of a system can be controlled to be element-wise larger than a non-negative threshold. The basic theory of herdable systems is presented, including a necessary and sufficient condition for herdability. This paper then considers the impact of the underlying graph structure of a linear system on the herdability of the system, for the case where the graph is represented as signed and directed. By classifying nodes based on the length and sign of walks from an input, we find a class of completely herdable systems as well as provide a complete characterization of nodes that can be herded in systems with an underlying graph that is a directed out-branching rooted at a single input.
Chat View PDF

Path to Stochastic Stability: Comparative Analysis of Stochastic Learning Dynamics in Games.

2018-04-08
Hassan Jaleel , Jeff S. Shamma
Stochastic stability is a popular solution concept for stochastic learning dynamics in games. However, a critical limitation of this solution concept is its inability to distinguish between different learning rules … Stochastic stability is a popular solution concept for stochastic learning dynamics in games. However, a critical limitation of this solution concept is its inability to distinguish between different learning rules that lead to the same steady-state behavior. We address this limitation for the first time and develop a framework for the comparative analysis of stochastic learning dynamics with different update rules but same steady-state behavior. We present the framework in the context of two learning dynamics: Log-Linear Learning (LLL) and Metropolis Learning (ML). Although both of these dynamics have the same stochastically stable states, LLL and ML correspond to different behavioral models for decision making. Moreover, we demonstrate through an example setup of sensor coverage game that for each of these dynamics, the paths to stochastically stable states exhibit distinctive behaviors. Therefore, we propose multiple criteria to analyze and quantify the differences in the short and medium run behavior of stochastic learning dynamics. We derive and compare upper bounds on the expected hitting time to the set of Nash equilibria for both LLL and ML. For the medium to long-run behavior, we identify a set of tools from the theory of perturbed Markov chains that result in a hierarchical decomposition of the state space into collections of states called cycles. We compare LLL and ML based on the proposed criteria and develop invaluable insights into the comparative behavior of the two dynamics.

Passivity and Evolutionary Game Dynamics

2018-03-21
Shinkyu Park , Jeff S. Shamma , Nuno C. Martins
This paper investigates an energy conservation and dissipation -- passivity -- aspect of dynamic models in evolutionary game theory. We define a notion of passivity using the state-space representation of … This paper investigates an energy conservation and dissipation -- passivity -- aspect of dynamic models in evolutionary game theory. We define a notion of passivity using the state-space representation of the models, and we devise systematic methods to examine passivity and to identify properties of passive dynamic models. Based on the methods, we describe how passivity is connected to stability in population games and illustrate stability of passive dynamic models using numerical simulations.
Chat View PDF

Herding Positive, Complex Networks

2018-01-01
Sebastian F. Ruf , Magnus Egerstedt , Jeff S. Shamma
The problem of controlling complex networks is of interest to disciplines ranging from biology to swarm robotics. However, controllability can be too strict a condition, failing to capture a range … The problem of controlling complex networks is of interest to disciplines ranging from biology to swarm robotics. However, controllability can be too strict a condition, failing to capture a range of desirable behaviors. Herdability, which describes the ability to drive a system to a specific set in the state space, was recently introduced as an alternative network control notion. This paper considers the application of herdability to the study of complex networks under the assumption that a positive system evolves on the network. The herdability of a class of networked systems is investigated and two problems related to ensuring system herdability are explored. The first is the input addition problem, which investigates which nodes in a network should receive inputs to ensure that the system is herdable. The second is a related problem of selecting the best single node from which to herd the network, in the case that a single node is guaranteed to make the system is herdable. In order to select the best herding node, a novel control energy based herdability centrality measure is introduced.
Chat View PDF

Infrastructure-free Localization of Aerial Robots with Ultrawideband Sensors

2018-01-01
Samet Güler , M.M. Abdel-Kader , Jeff S. Shamma
Robots in a swarm take advantage of a motion capture system or GPS sensors to obtain their global position. However, motion capture systems are environment-dependent and GPS sensors are not … Robots in a swarm take advantage of a motion capture system or GPS sensors to obtain their global position. However, motion capture systems are environment-dependent and GPS sensors are not reliable in occluded environments. For a reliable and versatile operation in a swarm, robots must sense each other and interact locally. Motivated by this requirement, here we propose an on-board localization framework for multi-robot systems. Our framework consists of an anchor robot with three ultrawideband (UWB) sensors and a tag robot with a single UWB sensor. The anchor robot utilizes the three UWB sensors as a localization infrastructure and estimates the tag robot's location by using its on-board sensing and computational capabilities solely, without explicit inter-robot communication. We utilize a dual Monte-Carlo localization approach to capture the agile maneuvers of the tag robot with an acceptable precision. We validate the effectiveness of our algorithm with simulations and indoor and outdoor experiments on a two-drone setup. The proposed dual MCL algorithm yields highly accurate estimates for various speed profiles of the tag robot and demonstrates a superior performance over the standard particle filter and the extended Kalman Filter.
Chat View PDF

Passivity and Evolutionary Game Dynamics

2018-01-01
Shinkyu Park , Jeff S. Shamma , Nuno C. Martins
This paper investigates an energy conservation and dissipation -- passivity -- aspect of dynamic models in evolutionary game theory. We define a notion of passivity using the state-space representation of … This paper investigates an energy conservation and dissipation -- passivity -- aspect of dynamic models in evolutionary game theory. We define a notion of passivity using the state-space representation of the models, and we devise systematic methods to examine passivity and to identify properties of passive dynamic models. Based on the methods, we describe how passivity is connected to stability in population games and illustrate stability of passive dynamic models using numerical simulations.
Chat View PDF

Herdable Systems Over Signed, Directed Graphs

2018-01-01
Sebastian F. Ruf , Magnus Egerstedt , Jeff S. Shamma
This paper considers the notion of herdability, a set-based reachability condition, which asks whether the state of a system can be controlled to be element-wise larger than a non-negative threshold. … This paper considers the notion of herdability, a set-based reachability condition, which asks whether the state of a system can be controlled to be element-wise larger than a non-negative threshold. The basic theory of herdable systems is presented, including a necessary and sufficient condition for herdability. This paper then considers the impact of the underlying graph structure of a linear system on the herdability of the system, for the case where the graph is represented as signed and directed. By classifying nodes based on the length and sign of walks from an input, we find a class of completely herdable systems as well as provide a complete characterization of nodes that can be herded in systems with an underlying graph that is a directed out-branching rooted at a single input.
Chat View PDF

Path to Stochastic Stability: Comparative Analysis of Stochastic Learning Dynamics in Games

2018-01-01
Hassan Jaleel , Jeff S. Shamma
Stochastic stability is a popular solution concept for stochastic learning dynamics in games. However, a critical limitation of this solution concept is its inability to distinguish between different learning rules … Stochastic stability is a popular solution concept for stochastic learning dynamics in games. However, a critical limitation of this solution concept is its inability to distinguish between different learning rules that lead to the same steady-state behavior. We address this limitation for the first time and develop a framework for the comparative analysis of stochastic learning dynamics with different update rules but same steady-state behavior. We present the framework in the context of two learning dynamics: Log-Linear Learning (LLL) and Metropolis Learning (ML). Although both of these dynamics have the same stochastically stable states, LLL and ML correspond to different behavioral models for decision making. Moreover, we demonstrate through an example setup of sensor coverage game that for each of these dynamics, the paths to stochastically stable states exhibit distinctive behaviors. Therefore, we propose multiple criteria to analyze and quantify the differences in the short and medium run behavior of stochastic learning dynamics. We derive and compare upper bounds on the expected hitting time to the set of Nash equilibria for both LLL and ML. For the medium to long-run behavior, we identify a set of tools from the theory of perturbed Markov chains that result in a hierarchical decomposition of the state space into collections of states called cycles. We compare LLL and ML based on the proposed criteria and develop invaluable insights into the comparative behavior of the two dynamics.
Chat View PDF

Distributed Submodular Minimization And Motion Coordination Over Discrete State Space

2017-09-21
Hassan Jaleel , Jeff S. Shamma
We develop a framework for the distributed minimization of submodular functions. Submodular functions are a discrete analog of convex functions and are extensively used in large-scale combinatorial optimization problems. While … We develop a framework for the distributed minimization of submodular functions. Submodular functions are a discrete analog of convex functions and are extensively used in large-scale combinatorial optimization problems. While there has been significant interest in the distributed formulations of convex optimization problems, distributed minimization of submodular functions has received relatively little research attention. Our framework relies on an equivalent convex reformulation of a submodular minimization problem, which is efficiently computable. We then use this relaxation to exploit methods for the distributed optimization of convex functions. The proposed framework is applicable to submodular set functions as well as to a wider class of submodular functions defined over certain lattices. We also propose an approach for solving distributed motion coordination problems in discrete state space based on submodular function minimization. We establish through a challenging setup of capture the flag game that submodular functions over lattices can be used to design artificial potential fields over discrete state space in which the agents are attracted towards their goals and are repulsed from obstacles and from each other for collision avoidance.
Chat View PDF

Global Games With Noisy Information Sharing

2017-09-07
Hessam Mahdavifar , Ahmad Beirami , Behrouz Touri +1 more
Global games form a subclass of games with incomplete information, where a set of agents decide actions against a regime with an underlying fundamental θ representing its power. Each agent … Global games form a subclass of games with incomplete information, where a set of agents decide actions against a regime with an underlying fundamental θ representing its power. Each agent has access to an independent noisy observation of θ. In order to capture the behavior of agents in a social network of information exchange, we assume that agents share their observation in a noisy environment prior to making their decisions. We show that global games with noisy sharing of information do not admit an intuitive type of threshold policy, which only depends on agents' belief about the underlying θ. This is in contrast to the existing results on the threshold policy for the conventional setup of global games. Motivated by this result, we investigate the existence of equilibrium strategies in a more general collection of threshold-type policies and show that such equilibrium strategies exist and are unique if the sharing of information happens over a sufficiently noisy environment.
Chat View PDF

Common Coauthors

Coauthor Papers Together
Magnus Egerstedt 11
Doha Hamza 8
Sebastian F. Ruf 7
Lichun Li 7
Ceyhun Eksin 6
Jason R. Marden 6
Na Li 6
Joshua S. Weitz 6
Mohamed‐Slim Alouini 6
Behrouz Touri 6
Hassan Jaleel 6
Nuno C. Martins 5
Shinkyu Park 5
Hajar El Hammouti 5
Giacomo Como 4
Luca Schenato 4
Luca Ballotta 4
Cédric Langbort 4
Éric Féron 4
Aya Hamed 4
Mohamed A. Mabrok 3
Ketan Savla 3
Ahmad Beirami 3
Subhro Das 3
Daniel Pickem 3
Georgios C. Chasparis 3
Hassan Abdelraouf 3
Munther A. Dahleh 3
Keith Paarporn 3
Holly Borowski 3
Hessam Mahdavifar 3
Basem Shihada 3
Michael Athans 3
Yingying Li 3
Yasin Yazıcıoğlu 2
Tianpeng Zhang 2
Michael J. Fox 2
Gürdal Arslan 2
Usman A. Fiaz 2
Mohamed Abdelkader 2
Ari Arapostathis 2
Samet Güler 2
Nathan Fitzgerald 1
Nasir Saeed 1
Paulo Rosa 1
Noureddine Toumi 1
G.L. Stüber 1
Heba Almorad 1
Farhan M. Aziz 1
Hayssam Dahrouj 1

Commonly Cited References

Effects of Heterogeneous and Clustered Contact Patterns on Infectious Disease Dynamics

2011-06-02
Erik Volz , Joel C. Miller , Alison P. Galvani +1 more
The spread of infectious diseases fundamentally depends on the pattern of contacts between individuals. Although studies of contact networks have shown that heterogeneity in the number of contacts and the … The spread of infectious diseases fundamentally depends on the pattern of contacts between individuals. Although studies of contact networks have shown that heterogeneity in the number of contacts and the duration of contacts can have far-reaching epidemiological consequences, models often assume that contacts are chosen at random and thereby ignore the sociological, temporal and/or spatial clustering of contacts. Here we investigate the simultaneous effects of heterogeneous and clustered contact patterns on epidemic dynamics. To model population structure, we generalize the configuration model which has a tunable degree distribution (number of contacts per node) and level of clustering (number of three cliques). To model epidemic dynamics for this class of random graph, we derive a tractable, low-dimensional system of ordinary differential equations that accounts for the effects of network structure on the course of the epidemic. We find that the interaction between clustering and the degree distribution is complex. Clustering always slows an epidemic, but simultaneously increasing clustering and the variance of the degree distribution can increase final epidemic size. We also show that bond percolation-based approximations can be highly biased if one incorrectly assumes that infectious periods are homogeneous, and the magnitude of this bias increases with the amount of clustering in the network. We apply this approach to model the high clustering of contacts within households, using contact parameters estimated from survey data of social interactions, and we identify conditions under which network models that do not account for household structure will be biased.
Chat View PDF

Game theory of pre-emptive vaccination before bioterrorism or accidental release of smallpox

2015-04-30
Chai Molina , David J. D. Earn
Smallpox was eradicated in the 1970s, but new outbreaks could be seeded by bioterrorism or accidental release. Substantial vaccine-induced morbidity and mortality make pre-emptive mass vaccination controversial, and if vaccination … Smallpox was eradicated in the 1970s, but new outbreaks could be seeded by bioterrorism or accidental release. Substantial vaccine-induced morbidity and mortality make pre-emptive mass vaccination controversial, and if vaccination is voluntary, then there is a conflict between self- and group interests. This conflict can be framed as a tragedy of the commons, in which herd immunity plays the role of the commons, and free-riding (i.e. not vaccinating pre-emptively) is analogous to exploiting the commons. This game has been analysed previously for a particular post-outbreak vaccination scenario. We consider several post-outbreak vaccination scenarios and compare the expected increase in mortality that results from voluntary versus imposed vaccination. Below a threshold level of post-outbreak vaccination effort, expected mortality is independent of the level of response effort. A lag between an outbreak starting and a response being initiated increases the post-outbreak vaccination effort necessary to reduce mortality. For some post-outbreak vaccination scenarios, even modest response lags make it impractical to reduce mortality by increasing post-outbreak vaccination effort. In such situations, if decreasing the response lag is impossible, the only practical way to reduce mortality is to make the vaccine safer (greater post-outbreak vaccination effort leads only to fewer people vaccinating pre-emptively).
Chat View PDF

The Impact of Imitation on Vaccination Behavior in Social Contact Networks

2012-04-12
Martial L. Ndeffo-Mbah , Jingzhou Liu , Chris T. Bauch +4 more
Previous game-theoretic studies of vaccination behavior typically have often assumed that populations are homogeneously mixed and that individuals are fully rational. In reality, there is heterogeneity in the number of … Previous game-theoretic studies of vaccination behavior typically have often assumed that populations are homogeneously mixed and that individuals are fully rational. In reality, there is heterogeneity in the number of contacts per individual, and individuals tend to imitate others who appear to have adopted successful strategies. Here, we use network-based mathematical models to study the effects of both imitation behavior and contact heterogeneity on vaccination coverage and disease dynamics. We integrate contact network epidemiological models with a framework for decision-making, within which individuals make their decisions either based purely on payoff maximization or by imitating the vaccination behavior of a social contact. Simulations suggest that when the cost of vaccination is high imitation behavior may decrease vaccination coverage. However, when the cost of vaccination is small relative to that of infection, imitation behavior increases vaccination coverage, but, surprisingly, also increases the magnitude of epidemics through the clustering of non-vaccinators within the network. Thus, imitation behavior may impede the eradication of infectious diseases. Calculations that ignore behavioral clustering caused by imitation may significantly underestimate the levels of vaccination coverage required to attain herd immunity.
Chat View PDF

The spread of awareness and its impact on epidemic outbreaks

2009-03-31
Sebastian Funk , Erez Gilad , Chris Watkins +1 more
When a disease breaks out in a human population, changes in behavior in response to the outbreak can alter the progression of the infectious agent. In particular, people aware of … When a disease breaks out in a human population, changes in behavior in response to the outbreak can alter the progression of the infectious agent. In particular, people aware of a disease in their proximity can take measures to reduce their susceptibility. Even if no centralized information is provided about the presence of a disease, such awareness can arise through first-hand observation and word of mouth. To understand the effects this can have on the spread of a disease, we formulate and analyze a mathematical model for the spread of awareness in a host population, and then link this to an epidemiological model by having more informed hosts reduce their susceptibility. We find that, in a well-mixed population, this can result in a lower size of the outbreak, but does not affect the epidemic threshold. If, however, the behavioral response is treated as a local effect arising in the proximity of an outbreak, it can completely stop a disease from spreading, although only if the infection rate is below a threshold. We show that the impact of locally spreading awareness is amplified if the social network of potential infection events and the network over which individuals communicate overlap, especially so if the networks have a high level of clustering. These findings suggest that care needs to be taken both in the interpretation of disease parameters, as well as in the prediction of the fate of future outbreaks.

Vaccination and the theory of games

2004-08-25
Chris T. Bauch , David J. D. Earn
Voluntary vaccination policies for childhood diseases present parents with a subtle challenge: if a sufficient proportion of the population is already immune, either naturally or by vaccination, then even the … Voluntary vaccination policies for childhood diseases present parents with a subtle challenge: if a sufficient proportion of the population is already immune, either naturally or by vaccination, then even the slightest risk associated with vaccination will outweigh the risk from infection. As a result, individual self-interest might preclude complete eradication of a vaccine-preventable disease. We show that a formal game theoretical analysis of this problem leads to new insights that help to explain human decision-making with respect to vaccination. Increases in perceived vaccine risk will tend to induce larger declines in vaccine uptake for pathogens that cause more secondary infections (such as measles and pertussis). After a vaccine scare, even if perceived vaccine risk is greatly reduced, it will be relatively difficult to restore prescare vaccine coverage levels.

Strategies for containing Ebola in West Africa

2014-10-31
Abhishek Pandey , Katherine E. Atkins , Jan Medlock +6 more
The ongoing Ebola outbreak poses an alarming risk to the countries of West Africa and beyond. To assess the effectiveness of containment strategies, we developed a stochastic model of Ebola … The ongoing Ebola outbreak poses an alarming risk to the countries of West Africa and beyond. To assess the effectiveness of containment strategies, we developed a stochastic model of Ebola transmission between and within the general community, hospitals, and funerals, calibrated to incidence data from Liberia. We find that a combined approach of case isolation, contact-tracing with quarantine, and sanitary funeral practices must be implemented with utmost urgency in order to reverse the growth of the outbreak. As of 19 September, under status quo, our model predicts that the epidemic will continue to spread, generating a predicted 224 (134 to 358) daily cases by 1 December, 280 (184 to 441) by 15 December, and 348 (249 to 545) by 30 December.
Chat View PDF

Social Factors in Epidemiology

2013-10-03
Chris T. Bauch , Alison P. Galvani
The coupling of social and biological contagion in human populations can have positive or negative outcomes. [Also see Perspective by Kahan ] The coupling of social and biological contagion in human populations can have positive or negative outcomes. [Also see Perspective by Kahan ]
Chat View PDF

Coupled disease–behavior dynamics on complex networks: A review

2015-07-08
Zhen Wang , Michael A. Andrews , Zhi-Xi Wu +2 more

Towards a Characterization of Behavior-Disease Models

2011-08-03
Nicola Perra , Duygu Balcan , Bruno Gonçalves +1 more
The last decade saw the advent of increasingly realistic epidemic models that leverage on the availability of highly detailed census and human mobility data. Data-driven models aim at a granularity … The last decade saw the advent of increasingly realistic epidemic models that leverage on the availability of highly detailed census and human mobility data. Data-driven models aim at a granularity down to the level of households or single individuals. However, relatively little systematic work has been done to provide coupled behavior-disease models able to close the feedback loop between behavioral changes triggered in the population by an individual's perception of the disease spread and the actual disease spread itself. While models lacking this coupling can be extremely successful in mild epidemics, they obviously will be of limited use in situations where social disruption or behavioral alterations are induced in the population by knowledge of the disease. Here we propose a characterization of a set of prototypical mechanisms for self-initiated social distancing induced by local and non-local prevalence-based information available to individuals in the population. We characterize the effects of these mechanisms in the framework of a compartmental scheme that enlarges the basic SIR model by considering separate behavioral classes within the population. The transition of individuals in/out of behavioral classes is coupled with the spreading of the disease and provides a rich phase space with multiple epidemic peaks and tipping points. The class of models presented here can be used in the case of data-driven computational approaches to analyze scenarios of social adaptation and behavioral change.
Chat View PDF

Game Theory of Social Distancing in Response to an Epidemic

2010-05-27
Timothy C. Reluga
Social distancing practices are changes in behavior that prevent disease transmission by reducing contact rates between susceptible individuals and infected individuals who may transmit the disease. Social distancing practices can … Social distancing practices are changes in behavior that prevent disease transmission by reducing contact rates between susceptible individuals and infected individuals who may transmit the disease. Social distancing practices can reduce the severity of an epidemic, but the benefits of social distancing depend on the extent to which it is used by individuals. Individuals are sometimes reluctant to pay the costs inherent in social distancing, and this can limit its effectiveness as a control measure. This paper formulates a differential-game to identify how individuals would best use social distancing and related self-protective behaviors during an epidemic. The epidemic is described by a simple, well-mixed ordinary differential equation model. We use the differential game to study potential value of social distancing as a mitigation measure by calculating the equilibrium behaviors under a variety of cost-functions. Numerical methods are used to calculate the total costs of an epidemic under equilibrium behaviors as a function of the time to mass vaccination, following epidemic identification. The key parameters in the analysis are the basic reproduction number and the baseline efficiency of social distancing. The results show that social distancing is most beneficial to individuals for basic reproduction numbers around 2. In the absence of vaccination or other intervention measures, optimal social distancing never recovers more than 30% of the cost of infection. We also show how the window of opportunity for vaccine development lengthens as the efficiency of social distancing and detection improve.
Chat View PDF

Emergence of Scaling in Random Networks

1999-10-15
Albert‐László Barabási , Réka Albert
Systems as diverse as genetic networks or the World Wide Web are best described as networks with complex topology. A common property of many large networks is that the vertex … Systems as diverse as genetic networks or the World Wide Web are best described as networks with complex topology. A common property of many large networks is that the vertex connectivities follow a scale-free power-law distribution. This feature was found to be a consequence of two generic mechanisms: (i) networks expand continuously by the addition of new vertices, and (ii) new vertices attach preferentially to sites that are already well connected. A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.
Chat View PDF

Repeated Games and Partial Differential Equations

1996-02-01
Bernard De Meyer
Let v n (p) denote the value of the n-times repeated zero-sum game with incomplete information on one side and full monitoring and let u(p) be the value of the … Let v n (p) denote the value of the n-times repeated zero-sum game with incomplete information on one side and full monitoring and let u(p) be the value of the average game G(p). The error term ϵ n (p) = v n (p) − cav(u)(p) is then converging to zero at least as rapidly as 1/√n. In this paper, we analyze the convergence of ψ n (p) = √nϵ n (p) in the games with square payoff matrices such that the optimal strategy of the informed player in the average game G(p) is unique, is completely mixed and does not depend on p. Our main result is that the existence of a solution ψ* to a partial differential equation with appropriate boundary conditions and regularity properties implies the uniform convergence of ψ n to the Fenchel conjugate of ψ*. In particular cases, the P.D.E. problem is linear and its solution ψ* is then related to the multidimensional normal distribution.

Metastability of logit dynamics for coordination games

2012-01-17
Vincenzo Auletta , Diodato Ferraioli , Francesco Pasquale +1 more
Logit Dynamics [Blume, Games and Economic Behavior, 1993] is a randomized best response dynamics for strategic games: at every time step a player is selected uniformly at random and she … Logit Dynamics [Blume, Games and Economic Behavior, 1993] is a randomized best response dynamics for strategic games: at every time step a player is selected uniformly at random and she chooses a new strategy according to a probability distribution biased toward strategies promising higher payoffs. This process defines an ergodic Markov chain, over the set of strategy profiles of the game, whose unique stationary distribution is the long-term equilibrium concept for the game. However, when the mixing time of the chain is large (e.g., exponential in the number of players), the stationary distribution loses its appeal as equilibrium concept, and the transient phase of the Markov chain becomes important. In several cases it happens that on a time-scale shorter than mixing time the chain is quasi-stationary, meaning that it stays close to some small set of the state space, while in a time-scale multiple of the mixing time it jumps from one quasi-stationary configuration to another; this phenomenon is usually called metastability.In this paper we give a quantitative definition of metastable probability distributions for a Markov chain and we study the metastability of the Logit dynamics for some classes of coordination games. In particular, we study no-risk-dominant coordination games on the clique (which is equivalent to the well-known Glauber dynamics for the Ising model) and coordination games on a ring (both the risk-dominant and no-risk-dominant case). We also describe a simple artificial game that highlights the distinctive features of our metastability notion based on distributions.

Structural controllability

1974-06-01
Ching-Tai Lin
The new concepts of "structure" and "structural controllability" for a linear time-invariant control system (described by a pair ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A,b</tex> )) are defined and studied. The physical justification … The new concepts of "structure" and "structural controllability" for a linear time-invariant control system (described by a pair ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A,b</tex> )) are defined and studied. The physical justification of these concepts and examples are also given. The graph of a pair ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A,b</tex> ) is also defined. This gives another way of describing the structure of this pair. The property of structural controllability is reduced to a property of the graph of the pair ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A,b</tex> ). To do this, the basic concept of a "cactus" and the related concept of a "precactus" are introduced. The main result of this paper states that the pair ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A,b</tex> ) is structurally controllable if an only if the graph of ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A,b</tex> ) is "spanned by a cactus." The result is also expressed in a more conventional way, in terms of some properties of the pair ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A,b</tex> ).

Resilient Consensus against Mobile Malicious Agents

2020-01-01
Yuan Wang , Hideaki Ishii , François Bonnet +1 more
This paper addresses consensus problems in the presence of adversaries that can move within the network and induce faulty behaviors in the attacked agents. By employing mobile adversary models from … This paper addresses consensus problems in the presence of adversaries that can move within the network and induce faulty behaviors in the attacked agents. By employing mobile adversary models from the computer science literature, we develop three protocols which can mitigate the influence of malicious agents. The algorithms follow the class of mean subsequence reduced (MSR) algorithms, under which agents ignore the suspicious values received from neighbors during their state updates. Different from the static model, even after the adversaries move away, the infected agents may remain faulty in their values for a short while, which must be taken into account. We develop conditions on the network structures for both the complete and non-complete graph cases, under which the proposed algorithms are guaranteed to attain resilient consensus. An illustrative example is provided to verify the effectiveness of our approach.
Chat View PDF

Resilient Distributed Averaging

2019-07-01
Seyed Mehran Dibaji , Mostafa Safi , Hideaki Ishii
In this paper, a fully distributed averaging algorithm in the presence of adversarial Byzantine agents is proposed. The algorithm is based on a resilient retrieval procedure, where all non-Byzantine nodes … In this paper, a fully distributed averaging algorithm in the presence of adversarial Byzantine agents is proposed. The algorithm is based on a resilient retrieval procedure, where all non-Byzantine nodes send their own initial values and retrieve those of other agents. We establish that the convergence of the proposed algorithm relies on strong robustness of the graph, which is a connectivity notion. Simulation results are provided to verify the effectiveness of the proposed algorithms.
Chat View PDF

Characterizing Trust and Resilience in Distributed Consensus for Cyberphysical Systems

2021-06-29
Michal Yemini , Angelia Nedić , Andrea Goldsmith +1 more
This work considers the problem of resilient consensus, where stochastic values of trust between agents are available. Specifically, we derive a unified mathematical framework to characterize convergence, deviation of the … This work considers the problem of resilient consensus, where stochastic values of trust between agents are available. Specifically, we derive a unified mathematical framework to characterize convergence, deviation of the consensus from the true consensus value, and expected convergence rate, when there exists additional information of trust between agents. We show that under certain conditions on the stochastic trust values and consensus protocol: First, almost sure convergence to a common limit value is possible even when malicious agents constitute more than half of the network connectivity; second, the deviation of the converged limit, from the case where there is no attack, i.e., the true consensus value, can be bounded with probability that approaches 1 exponentially; and third correct classification of malicious and legitimate agents can be attained in finite time almost surely. Furthermore, the expected convergence rate decays exponentially as a function of the quality of the trust observations between agents.
Chat View PDF

Survey on UAV Cellular Communications: Practical Aspects, Standardization Advancements, Regulation, and Security Challenges

2019-01-01
Azade Fotouhi , Haoran Qiang , Ming Ding +4 more
The rapid growth of consumer unmanned aerial vehicles (UAVs) is creating promising new business opportunities for cellular operators. On the one hand, UAVs can be connected to cellular networks as … The rapid growth of consumer unmanned aerial vehicles (UAVs) is creating promising new business opportunities for cellular operators. On the one hand, UAVs can be connected to cellular networks as new types of user equipment, therefore generating significant revenues for the operators that can guarantee their stringent service requirements. On the other hand, UAVs offer the unprecedented opportunity to realize UAV-mounted flying base stations (BSs) that can dynamically reposition themselves to boost coverage, spectral efficiency, and user quality of experience. Indeed, the standardization bodies are currently exploring possibilities for serving commercial UAVs with cellular networks. Industries are beginning to trial early prototypes of flying BSs or user equipments, while academia is in full swing researching mathematical and algorithmic solutions to address interesting new problems arising from flying nodes in cellular networks. In this paper, we provide a comprehensive survey of all of these developments promoting smooth integration of UAVs into cellular networks. Specifically, we survey: 1) the types of consumer UAVs currently available off-the-shelf; 2) the interference issues and potential solutions addressed by standardization bodies for serving aerial users with the existing terrestrial BSs; 3) the challenges and opportunities for assisting cellular communications with UAV-based flying relays and BSs; 4) the ongoing prototyping and test bed activities; 5) the new regulations being developed to manage the commercial use of UAVs; and 6) the cyber-physical security of UAV-assisted cellular communications.
Chat View PDF

On general minimax theorems

1958-03-01
Maurice Sion
Introduction, von Neumann's minimax theorem [10] can be stated as follows : if M and N are finite dimensional simplices and / is a bilinear function on MxN, then / … Introduction, von Neumann's minimax theorem [10] can be stated as follows : if M and N are finite dimensional simplices and / is a bilinear function on MxN, then / has a saddle point, i. e.There have been several generalizations of this theorem.J. Ville [9], A. Wald [11], and others [1] variously extended von Neumann's result to cases where M and N were allowed to be subsets of certain infinite dimensional linear spaces.The functions / they considered, however, were still linear.M. Shiffman [8] seems to have been the first to have considered concave-convex functions in a minimax theorem.H. Kneser [6], K. Fan [3], and C. Berge [2] (using induction and the method of separating two disjoint convex sets in Euclidean space by a hyperplane) got minimax theorems for concave-convex functions that are appropriately semi-continuous in one of the two variables.Although these theorems include the previous results as special cases, they can also be shown to be rather direct consequences of von Neumann's theorem.H. Nikaidό [7], on the other hand, using Brouwer's fixed point theorem, proved the existence of a saddle point for functions satisfying the weaker algebraic condition of being quasi-concave-convex, but the stronger topological condition of being continuous in each variable.Thus, there seem to be essentially two types of argument: one uses some form of separation of disjoint convex sets by a hyperplane and yields the theorem of Kneser-Fan (see 4.2), and the other uses a fixed point theorem and yields Nikaidό's result.ΐn this paper, we unify the two streams of thought by proving a minimax theorem for a function that is quasi-concave-convex and appropriately semi-continuous in each variable.The method of proof differs radically from any used previously.The difficulty lies in the fact that we cannot use a fixed point theorem (due to lack of continuity) nor the separation of disjoint convex sets by a hyperplane (due to lack of convexity).The key tool used is a theorem due to Knaster, Kuratowski, Mazurkiewicz based on Sperner's lemma.It may be of some interest to point out that, in all the minimax theorems, the crucial argument is carried out on spaces M and N that

Which Networks are Least Susceptible to Cascading Failures?

2011-10-01
Lawrence E. Blume , David Easley , Jon Kleinberg +2 more
The spread of a cascading failure through a network is an issue that comes up in many domains - in the contagious failures that spread among financial institutions during a … The spread of a cascading failure through a network is an issue that comes up in many domains - in the contagious failures that spread among financial institutions during a financial crisis, through nodes of a power grid or communication network during a widespread outage, or through a human population during the outbreak of an epidemic disease. Here we study a natural model of threshold contagion: each node v is assigned a numerical threshold ℓ(v) drawn independently from an underlying distribution μ, and v will fail as soon as ℓ(v) of its neighbors fail. Despite the simplicity of the formulation, it has been very challenging to analyze the failure processes that arise from arbitrary threshold distributions; even qualitative questions concerning which graphs are the most resilient to cascading failures in these models have been difficult to resolve. Here we develop a set of new techniques for analyzing the failure probabilities of nodes in arbitrary graphs under this model, and we compare different graphs G according to their μ-risk, defined as the maximum failure probability of any node in G when thresholds are drawn from μ. We find that the space of threshold distributions has a surprisingly rich structure when we consider the risk that these thresholds induce on different graphs: small shifts in the distribution of the thresholds can favor graphs with a maximally clustered structure (i.e., cliques), those with a maximally branching structure (trees), or even intermediate hybrids.
Chat View PDF

Game Theory and Distributed Control****Supported AFOSR/MURI projects #FA9550-09-1-0538 and #FA9530-12-1-0359 and ONR projects #N00014-09-1-0751 and #N0014-12-1-0643.

2014-10-02
Jason R. Marden , Jeff S. Shamma

Competition-Based Resilience in Distributed Quadratic Optimization

2022-12-06
Luca Ballotta , Giacomo Como , Jeff S. Shamma +1 more
We propose a competition-based approach to resilient distributed optimization with quadratic costs in Networked Control Systems (e.g., wireless sensor network, power grid, robotic team) where a fraction of agents may … We propose a competition-based approach to resilient distributed optimization with quadratic costs in Networked Control Systems (e.g., wireless sensor network, power grid, robotic team) where a fraction of agents may misbehave (through, e.g., hacking or power outage). Departing from classical filtering strategies proposed in literature, and inspired by a game-theoretic interpretation of consensus, we propose to introduce competition among normally behaving agents as a mean to enhance resilience against malicious attacks. Our proposal is supported by formal and heuristic results which show that i) there exists a nontrivial trade-off between blind collaboration and full competition and ii) the proposed approach can outperform standard techniques based on the algorithm Mean Subsequence Reduced.
Chat View PDF

A Survey of Channel Modeling for UAV Communications

2018-01-01
Aziz Altaf Khuwaja , Yunfei Chen , Nan Zhao +2 more
Unmanned aerial vehicles (UAVs) have attracted great interest in rapid deployment for both civil and military applications. UAV communication has its own distinctive channel characteristics compared to the widely used … Unmanned aerial vehicles (UAVs) have attracted great interest in rapid deployment for both civil and military applications. UAV communication has its own distinctive channel characteristics compared to the widely used cellular or satellite systems. Accurate channel characterization is crucial for the performance optimization and design of efficient UAV communication. However, several challenges exist in UAV channel modeling. For example, the propagation characteristics of UAV channels are under explored for spatial and temporal variations in non-stationary channels. Additionally, airframe shadowing has not yet been investigated for small size rotary UAVs. This paper provides an extensive survey of the measurement methods proposed for UAV channel modeling that use low altitude platforms and discusses various channel characterization efforts. We also review from a contemporary perspective of UAV channel modeling approaches, and outline future research challenges in this domain.
Chat View PDF

Epidemic spreading in real networks: an eigenvalue viewpoint

2004-03-02
Yang Wang , Deepayan Chakrabarti , Chenxi Wang +1 more
How will a virus propagate in a real network? Does an epidemic threshold exist for a finite graph? How long does it take to disinfect a network given particular values … How will a virus propagate in a real network? Does an epidemic threshold exist for a finite graph? How long does it take to disinfect a network given particular values of infection rate and virus death rate? We answer the first question by providing equations that accurately model virus propagation in any network including real and synthesized network graphs. We propose a general epidemic threshold condition that applies to arbitrary graphs: we prove that, under reasonable approximations, the epidemic threshold for a network is closely related to the largest eigenvalue of its adjacency matrix. Finally, for the last question, we show that infections tend to zero exponentially below the epidemic threshold. We show that our epidemic threshold model subsumes many known thresholds for special-case graphs (e.g., Erdos-Renyi, BA power-law, homogeneous); we show that the threshold tends to zero for infinite power-law graphs. We show that our threshold condition holds for arbitrary graphs.
Chat View PDF

Dynamic Games With Asymmetric Information: Common Information Based Perfect Bayesian Equilibria and Sequential Decomposition

2016-03-22
Yi Ouyang , Hamidreza Tavafoghi , Demosthenis Teneketzis
We formulate and analyze a general class of stochastic dynamic games with asymmetric information arising in dynamic systems. In such games, multiple strategic agents control the system dynamics and have … We formulate and analyze a general class of stochastic dynamic games with asymmetric information arising in dynamic systems. In such games, multiple strategic agents control the system dynamics and have different information about the system over time. Because of the presence of asymmetric information, each agent needs to form beliefs about other agents' private information. Therefore, the specification of the agents' beliefs along with their strategies is necessary to study the dynamic game. We use Perfect Bayesian equilibrium (PBE) as our solution concept. A PBE consists of a pair of strategy profile and belief system. In a PBE, every agent's strategy should be a best response under the belief system, and the belief system depends on agents' strategy profile when there is signaling among agents. Therefore, the circular dependence between strategy profile and belief system makes it difficult to compute PBE. Using the common information among agents, we introduce a subclass of PBE called common information based perfect Bayesian equilibria (CIB-PBE), and provide a sequential decomposition of the dynamic game. Such decomposition leads to a backward induction algorithm to compute CIB-PBE. We illustrate the sequential decomposition with an example of a multiple access broadcast game. We prove the existence of CIB-PBE for a subclass of dynamic games.
Chat View PDF

Survey of Important Issues in UAV Communication Networks

2015-11-03
Lav Gupta , Raj Jain , Gabor Vaszkun
Unmanned Aerial Vehicles (UAVs) have enormous potential in the public and civil domains. These are particularly useful in applications where human lives would otherwise be endangered. Multi-UAV systems can collaboratively … Unmanned Aerial Vehicles (UAVs) have enormous potential in the public and civil domains. These are particularly useful in applications where human lives would otherwise be endangered. Multi-UAV systems can collaboratively complete missions more efficiently and economically as compared to single UAV systems. However, there are many issues to be resolved before effective use of UAVs can be made to provide stable and reliable context-specific networks. Much of the work carried out in the areas of Mobile Ad Hoc Networks (MANETs), and Vehicular Ad Hoc Networks (VANETs) does not address the unique characteristics of the UAV networks. UAV networks may vary from slow dynamic to dynamic; have intermittent links and fluid topology. While it is believed that ad hoc mesh network would be most suitable for UAV networks yet the architecture of multi-UAV networks has been an understudied area. Software Defined Networking (SDN) could facilitate flexible deployment and management of new services and help reduce cost, increase security and availability in networks. Routing demands of UAV networks go beyond the needs of MANETS and VANETS. Protocols are required that would adapt to high mobility, dynamic topology, intermittent links, power constraints and changing link quality. UAVs may fail and the network may get partitioned making delay and disruption tolerance an important design consideration. Limited life of the node and dynamicity of the network leads to the requirement of seamless handovers where researchers are looking at the work done in the areas of MANETs and VANETs, but the jury is still out. As energy supply on UAVs is limited, protocols in various layers should contribute towards greening of the network. This article surveys the work done towards all of these outstanding issues, relating to this new class of networks, so as to spur further research in these areas.
Chat View PDF

The exit path of a Markov chain with rare transitions

1997-01-01
Olivier Catoni , Raphaël Cerf
We study the exit path from a general domain after the last visit to a set of a Markov chain with rare transitions. We prove several large deviation principles for … We study the exit path from a general domain after the last visit to a set of a Markov chain with rare transitions. We prove several large deviation principles for the law of the succession of the cycles visited by the process (the cycle path), the succession of the saddle points gone through to jump from cycle to cycle on the cycle path (the saddle path) and the succession of all the points gone through (the exit path). We estimate the time the process spends in each cycle of the cycle path and how it decomposes into the time spent in each point of the exit path. We describe a systematic method to find the most likely saddle paths. We apply these results to the reversible case of the Metropolis dynamics. We give in appendix the corresponding large deviation estimates in the non homogeneous case, which are corollaries of already published works by Catoni (1992) and Trouvé (1992, 1996a).
Chat View PDF

When individual behaviour matters: homogeneous and network models in epidemiology

2007-07-19
Shweta Bansal , Bryan T. Grenfell , Lauren Ancel Meyers
Heterogeneity in host contact patterns profoundly shapes population-level disease dynamics. Many epidemiological models make simplifying assumptions about the patterns of disease-causing interactions among hosts. In particular, homogeneous-mixing models assume that … Heterogeneity in host contact patterns profoundly shapes population-level disease dynamics. Many epidemiological models make simplifying assumptions about the patterns of disease-causing interactions among hosts. In particular, homogeneous-mixing models assume that all hosts have identical rates of disease-causing contacts. In recent years, several network-based approaches have been developed to explicitly model heterogeneity in host contact patterns. Here, we use a network perspective to quantify the extent to which real populations depart from the homogeneous-mixing assumption, in terms of both the underlying network structure and the resulting epidemiological dynamics. We find that human contact patterns are indeed more heterogeneous than assumed by homogeneous-mixing models, but are not as variable as some have speculated. We then evaluate a variety of methodologies for incorporating contact heterogeneity, including network-based models and several modifications to the simple SIR compartmental model. We conclude that the homogeneous-mixing compartmental model is appropriate when host populations are nearly homogeneous, and can be modified effectively for a few classes of non-homogeneous networks. In general, however, network models are more intuitive and accurate for predicting disease spread through heterogeneous host populations.
Chat View PDF

The influence of altruism on influenza vaccination decisions

2012-04-11
Eunha Shim , Gretchen B. Chapman , Jeffrey P. Townsend +1 more
Game theory is based on the assumption that individuals act according to self-interest and make decisions that maximize their personal payoffs. To test this fundamental assumption, we conducted a survey … Game theory is based on the assumption that individuals act according to self-interest and make decisions that maximize their personal payoffs. To test this fundamental assumption, we conducted a survey study in the context of influenza vaccination decisions. Contrary to the assumption of self-interest, we found that altruism plays an important role in vaccination decisions. Nevertheless, altruistic motivation has not yet been considered in epidemiological models, in predictions of vaccination decisions or in the design of vaccination policies. To determine the impact of altruism on the adherence to optimal vaccination policies and on resulting disease burden, we incorporated altruism into a game-theoretic epidemiological model of influenza vaccination. We found that altruism significantly shifted vaccination decisions away from individual self-interest and towards the community optimum, greatly reducing the total cost, morbidity and mortality for the community. Therefore, promoting altruism could be a potential strategy to improve public health outcomes.

A Few Bad Apples: A Model of Disease Influenced Agent Behaviour in a Heterogeneous Contact Environment

2015-03-03
Jessica Enright , Rowland R. Kao
For diseases that infect humans or livestock, transmission dynamics are at least partially dependent on human activity and therefore human behaviour. However, the impact of human behaviour on disease transmission … For diseases that infect humans or livestock, transmission dynamics are at least partially dependent on human activity and therefore human behaviour. However, the impact of human behaviour on disease transmission is relatively understudied, especially in the context of heterogeneous contact structures such as described by a social network. Here, we use a strategic game, coupled with a simple disease model, to investigate how strategic agent choices impact the spread of disease over a contact network. Using beliefs that are based on disease status and that build up over time, agents choose actions that stochastically determine disease spread on the network. An agent's disease status is therefore a function of both his own and his neighbours actions. The effect of disease on agents is modelled by a heterogeneous payoff structure. We find that the combination of network shape and distribution of payoffs has a non-trivial impact on disease prevalence, even if the mean payoff remains the same. An important scenario occurs when a small percentage (called noncooperators) have little incentive to avoid disease. For diseases that are easily acquired when taking a risk, then even when good behavior can lead to disease eradication, a small increase in the percentage of noncooperators (less than 5%) can yield a large (up to 25%) increase in prevalence.
Chat View PDF

Erratic Flu Vaccination Emerges from Short-Sighted Behavior in Contact Networks

2011-01-27
Daniel M. Cornforth , Timothy C. Reluga , Eunha Shim +3 more
The effectiveness of seasonal influenza vaccination programs depends on individual-level compliance. Perceptions about risks associated with infection and vaccination can strongly influence vaccination decisions and thus the ultimate course of … The effectiveness of seasonal influenza vaccination programs depends on individual-level compliance. Perceptions about risks associated with infection and vaccination can strongly influence vaccination decisions and thus the ultimate course of an epidemic. Here we investigate the interplay between contact patterns, influenza-related behavior, and disease dynamics by incorporating game theory into network models. When individuals make decisions based on past epidemics, we find that individuals with many contacts vaccinate, whereas individuals with few contacts do not. However, the threshold number of contacts above which to vaccinate is highly dependent on the overall network structure of the population and has the potential to oscillate more wildly than has been observed empirically. When we increase the number of prior seasons that individuals recall when making vaccination decisions, behavior and thus disease dynamics become less variable. For some networks, we also find that higher flu transmission rates may, counterintuitively, lead to lower (vaccine-mediated) disease prevalence. Our work demonstrates that rich and complex dynamics can result from the interaction between infectious diseases, human contact patterns, and behavior.
Chat View PDF

On the Existence of Optimal Policies for a Class of Static and Sequential Dynamic Teams

2015-01-01
Abhishek Gupta , Serdar Yüksel , Tamer Başar +1 more
In this paper, we identify sufficient conditions under which static teams and a class of sequential dynamic teams admit team-optimal solutions. We first investigate the existence of optimal solutions in … In this paper, we identify sufficient conditions under which static teams and a class of sequential dynamic teams admit team-optimal solutions. We first investigate the existence of optimal solutions in static teams where the observations of the decision makers are conditionally independent given the state and satisfy certain regularity conditions. Building on these findings and the static reduction method of Witsenhausen, we then extend the analysis to sequential dynamic teams. In particular, we show that a large class of dynamic linear-quadratic-Gaussian (LQG) teams, including the vector version of the well-known Witsenhausen's counterexample and the Gaussian relay channel problem viewed as a dynamic team, admit team-optimal solutions. Results in this paper substantially broaden the class of stochastic control problems with nonclassical information known to have optimal solutions.
Chat View PDF

Optimal Resource Allocation for Network Protection Against Spreading Processes

2014-03-01
Víctor M. Preciado , Michael Zargham , Chinwendu Enyioha +2 more
We study the problem of containing spreading processes in arbitrary directed networks by distributing protection resources throughout the nodes of the network. We consider two types of protection resources are … We study the problem of containing spreading processes in arbitrary directed networks by distributing protection resources throughout the nodes of the network. We consider two types of protection resources are available: (i) Preventive resources able to defend nodes against the spreading (such as vaccines in a viral infection process), and (ii) corrective resources able to neutralize the spreading after it has reached a node (such as antidotes). We assume that both preventive and corrective resources have an associated cost and study the problem of finding the cost-optimal distribution of resources throughout the nodes of the network. We analyze these questions in the context of viral spreading processes in directed networks. We study the following two problems: (i) Given a fixed budget, find the optimal allocation of preventive and corrective resources in the network to achieve the highest level of containment, and (ii) when a budget is not specified, find the minimum budget required to control the spreading process. We show that both resource allocation problems can be solved in polynomial time using Geometric Programming (GP) for arbitrary directed graphs of nonidentical nodes and a wide class of cost functions. Furthermore, our approach allows to optimize simultaneously over both preventive and corrective resources, even in the case of cost functions being node-dependent. We illustrate our approach by designing optimal protection strategies to contain an epidemic outbreak that propagates through an air transportation network.
Chat View PDF

Global analysis of piecewise linear systems using impact maps and surface lyapunov functions

2003-12-01
Jorge Gonçalves , Alexandre Megretski , Munther A. Dahleh
This paper presents an entirely new constructive global analysis methodology for a class of hybrid systems known as piecewise linear systems (PLS). This methodology infers global properties of PLS solely … This paper presents an entirely new constructive global analysis methodology for a class of hybrid systems known as piecewise linear systems (PLS). This methodology infers global properties of PLS solely by studying the behavior at switching surfaces associated with PLS. The main idea is to analyze impact maps, i.e., maps from one switching surface to the next switching surface. Such maps are known to be "unfriendly" maps in the sense that they are highly nonlinear, multivalued, and not continuous. We found, however, that an impact map induced by an linear time-invariant flow between two switching surfaces can be represented as a linear transformation analytically parametrized by a scalar function of the state. This representation of impact maps allows the search for surface Lyapunov functions (SuLF) to be done by simply solving a semidefinite program, allowing global asymptotic stability, robustness, and performance of limit cycles and equilibrium points of PLS to be efficiently checked. This new analysis methodology has been applied to relay feedback, on/off and saturation systems, where it has shown to be very successful in globally analyzing a large number of examples. In fact, it is still an open problem whether there exists an example with a globally stable limit cycle or equilibrium point that cannot be successfully analyzed with this new methodology. Examples analyzed include systems of relative degree larger than one and of high dimension, for which no other analysis methodology could be applied. This success in globally analyzing certain classes of PLS has shown the power of this new methodology, and suggests its potential toward the analysis of larger and more complex PLS.
Chat View PDF

Constrained Consensus and Optimization in Multi-Agent Networks

2010-02-11
A. Nedić , Asuman Ozdaglar , Pablo A. Parrilo
<para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> We present distributed algorithms that can be used by multiple agents to align their estimates with a particular value over a network with time-varying connectivity. Our framework … <para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> We present distributed algorithms that can be used by multiple agents to align their estimates with a particular value over a network with time-varying connectivity. Our framework is general in that this value can represent a consensus value among multiple agents or an optimal solution of an optimization problem, where the global objective function is a combination of local agent objective functions. Our main focus is on constrained problems where the estimates of each agent are restricted to lie in different convex sets. </para>
Chat View PDF

Competing spreading processes on multiplex networks: Awareness and epidemics

2014-07-14
Clara Granell , Sergio Gómez , Àlex Arenas
Epidemic-like spreading processes on top of multilayered interconnected complex networks reveal a rich phase diagram of intertwined competition effects. A recent study by the authors [Granell et al. Phys. Rev. … Epidemic-like spreading processes on top of multilayered interconnected complex networks reveal a rich phase diagram of intertwined competition effects. A recent study by the authors [Granell et al. Phys. Rev. Lett. 111, 128701 (2013)] presented the analysis of the interrelation between two processes accounting for the spreading of an epidemics, and the spreading of information awareness to prevent its infection, on top of multiplex networks. The results in the case in which awareness implies total immunization to the disease, revealed the existence of a metacritical point at which the critical onset of the epidemics starts depending on the reaching of the awareness process. Here we present a full analysis of these critical properties in the more general scenario where the awareness spreading does not imply total immunization, and where infection does not imply immediate awareness of it. We find the critical relation between both competing processes for a wide spectrum of parameters representing the interaction between them. We also analyze the consequences of a massive broadcast of awareness (mass media) on the final outcome of the epidemic incidence. Importantly enough, the mass media makes the metacritical point to disappear. The results reveal that the main finding i.e. existence of a metacritical point, is rooted on the competition principle and holds for a large set of scenarios.
Chat View PDF

Lethality and centrality in protein networks

2001-05-01
Hawoong Jeong , S. P. Mason , Albert‐László Barabási +1 more
Chat View PDF

Minimizing the Social Cost of an Epidemic

2012-01-01
Elizabeth Bodine-Baron , Subhonmesh Bose , Babak Hassibi +1 more

Behavior Changes in SIS STD Models with Selective Mixing

1997-08-01
James M. Hyman , Jia Li
We propose and analyze a heterogeneous, multigroup, susceptible-infective-susceptible (SIS) sexually transmitted disease (STD) model where the desirability and acceptability in partnership formations are functions of the infected individuals. We derive … We propose and analyze a heterogeneous, multigroup, susceptible-infective-susceptible (SIS) sexually transmitted disease (STD) model where the desirability and acceptability in partnership formations are functions of the infected individuals. We derive explicit formulas for the epidemic thresholds, prove the existence and uniqueness of the equilibrium states for the two-group model and provide a complete analysis of their local and global stability. We then investigate the effects of behavior changes on the transmission dynamics and analyze the sensitivity of the epidemic to the magnitude of the behavior changes. We verify that if people modify their behavior to reduce the probability of infection with individuals in highly infected groups, through either reduced contacts, reduced partner formations, or using safe sex, the infection level may be decreased. However, if people continue to have intragroup and intergroup partnerships, then changing the desirability and acceptability formation cannot eradicate the epidemic once it exceeds the epidemic threshold.

The impact of awareness on epidemic spreading in networks

2012-01-03
Qingchu Wu , Xinchu Fu , Michael Small +1 more
We explore the impact of awareness on epidemic spreading through a population represented by a scale-free network. Using a network mean-field approach, a mathematical model for epidemic spreading with awareness … We explore the impact of awareness on epidemic spreading through a population represented by a scale-free network. Using a network mean-field approach, a mathematical model for epidemic spreading with awareness reactions is proposed and analyzed. We focus on the role of three forms of awareness including local, global, and contact awareness. By theoretical analysis and simulation, we show that the global awareness cannot decrease the likelihood of an epidemic outbreak while both the local awareness and the contact awareness can. Also, the influence degree of the local awareness on disease dynamics is closely related with the contact awareness.
Chat View PDF

Distributed Channel Assignment in Cognitive Radio Networks: Stable Matching and Walrasian Equilibrium

2015-03-20
Rami Mochaourab , Bernd Holfeld , Thomas Wirth
We consider a set of secondary transmitter-receiver pairs in a cognitive radio setting. Based on channel sensing and access performances, we consider the problem of assigning channels orthogonally to secondary … We consider a set of secondary transmitter-receiver pairs in a cognitive radio setting. Based on channel sensing and access performances, we consider the problem of assigning channels orthogonally to secondary users through distributed coordination and cooperation algorithms. Two economic models are applied for this purpose: matching markets and competitive markets. In the matching market model, secondary users and channels build two agent sets. We implement a stable matching algorithm in which each secondary user, based on his achievable rate, proposes to the coordinator to be matched with desirable channels. The coordinator accepts or rejects the proposals based on the channel preferences which depend on interference from the secondary user. The coordination algorithm is of low complexity and can adapt to network dynamics. In the competitive market model, channels are associated with prices and secondary users are endowed with monetary budget. Each secondary user, based on his utility function and current channel prices, demands a set of channels. A Walrasian equilibrium maximizes the sum utility and equates the channel demand to their supply. We prove the existence of Walrasian equilibrium and propose a cooperative mechanism to reach it. The performance and complexity of the proposed solutions are illustrated by numerical simulations.
Chat View PDF

On Submodularity and Controllability in Complex Dynamical Networks

2015-07-07
Tyler Summers , Fabrizio L. Cortesi , John Lygeros
Controllability and observability have long been recognized as fundamental structural properties of dynamical systems, but have recently seen renewed interest in the context of large, complex networks of dynamical systems. … Controllability and observability have long been recognized as fundamental structural properties of dynamical systems, but have recently seen renewed interest in the context of large, complex networks of dynamical systems. A basic problem is sensor and actuator placement: choose a subset from a finite set of possible placements to optimize some real-valued controllability and observability metrics of the network. Surprisingly little is known about the structure of such combinatorial optimization problems. In this paper, we show that several important classes of metrics based on the controllability and observability Gramians have a strong structural property that allows for either efficient global optimization or an approximation guarantee by using a simple greedy heuristic for their maximization. In particular, the mapping from possible placements to several scalar functions of the associated Gramian is either a modular or submodular set function. The results are illustrated on randomly generated systems and on a problem of power electronic actuator placement in a model of the European power grid.
Chat View PDF

Markov chains with exponentially small transition probabilities: First exit problem from a general domain. II. The general case

1996-09-01
Enzo Olivieri , Elisabetta Scoppola

Wireless Networks With RF Energy Harvesting: A Contemporary Survey

2014-11-10
Xiao Lu , Ping Wang , Dusit Niyato +2 more
Radio frequency (RF) energy transfer and harvesting techniques have recently become alternative methods to power the next-generation wireless networks. As this emerging technology enables proactive energy replenishment of wireless devices, … Radio frequency (RF) energy transfer and harvesting techniques have recently become alternative methods to power the next-generation wireless networks. As this emerging technology enables proactive energy replenishment of wireless devices, it is advantageous in supporting applications with quality-of-service requirements. In this paper, we present a comprehensive literature review on the research progresses in wireless networks with RF energy harvesting capability, which is referred to as RF energy harvesting networks (RF-EHNs). First, we present an overview of the RF-EHNs including system architecture, RF energy harvesting techniques, and existing applications. Then, we present the background in circuit design as well as the state-of-the-art circuitry implementations and review the communication protocols specially designed for RF-EHNs. We also explore various key design issues in the development of RF-EHNs according to the network types, i.e., single-hop networks, multiantenna networks, relay networks, and cognitive radio networks. Finally, we envision some open research directions.
Chat View PDF

Sign Controllability of a Nonnegative Matrix and a Positive Vector

1993-04-01
Charles R. Johnson , Volker Mehrmann , D.D. Olesky
An n-by-n matrix A and a vector b are controllable if and only if the matrix $[ b,Ab,A^2 b, \ldots ,A^{n - 1} b ]$ has rank n. An array … An n-by-n matrix A and a vector b are controllable if and only if the matrix $[ b,Ab,A^2 b, \ldots ,A^{n - 1} b ]$ has rank n. An array with each entry equal to +, –, or 0 is a sign pattern. If ${\bf A}$ and ${\bf B}$ are sign patterns of orders n-by-n and n-by-1, respectively, then the pair $( {\bf A},{\bf B} )$ is called sign controllable if $( A,b )$ is controllable for all $A \in {\bf A}$ and for all $b \in {\bf B}$ . Sign controllability of a nonnegative sign pattern ${\bf A}$ and a positive sign pattern ${\bf B}$ are characterized, and sufficient conditions for other cases of the sign controllability problem are given.

Structural properties of proportional fairness: Stability and insensitivity

2007-06-01
Laurent Massoulié
In this article we provide a novel characterization of the proportionally fair bandwidth allocation of network capacities, in terms of the Fenchel–Legendre transform of the network capacity region. We use … In this article we provide a novel characterization of the proportionally fair bandwidth allocation of network capacities, in terms of the Fenchel–Legendre transform of the network capacity region. We use this characterization to prove stability (i.e., ergodicity) of network dynamics under proportionally fair sharing, by exhibiting a suitable Lyapunov function. Our stability result extends previously known results to a more general model including Markovian users routing. In particular, it implies that the stability condition previously known under exponential service time distributions remains valid under so-called phase-type service time distributions. We then exhibit a modification of proportional fairness, which coincides with it in some asymptotic sense, is reversible (and thus insensitive), and has explicit stationary distribution. Finally we show that the stationary distributions under modified proportional fairness and balanced fairness, a sharing criterion proposed because of its insensitivity properties, admit the same large deviations characteristics. These results show that proportional fairness is an attractive bandwidth allocation criterion, combining the desirable properties of ease of implementation with performance and insensitivity.
Chat View PDF

A comparison of simulated annealing algorithms for variable selection in principal component analysis and discriminant analysis

2014-03-17
Michael J. Brusco

Controllability of structural brain networks

2015-10-01
Shi Gu , Fabio Pasqualetti , Matthew Cieslak +7 more
Abstract Cognitive function is driven by dynamic interactions between large-scale neural circuits or networks, enabling behaviour. However, fundamental principles constraining these dynamic network processes have remained elusive. Here we use … Abstract Cognitive function is driven by dynamic interactions between large-scale neural circuits or networks, enabling behaviour. However, fundamental principles constraining these dynamic network processes have remained elusive. Here we use tools from control and network theories to offer a mechanistic explanation for how the brain moves between cognitive states drawn from the network organization of white matter microstructure. Our results suggest that densely connected areas, particularly in the default mode system, facilitate the movement of the brain to many easily reachable states. Weakly connected areas, particularly in cognitive control systems, facilitate the movement of the brain to difficult-to-reach states. Areas located on the boundary between network communities, particularly in attentional control systems, facilitate the integration or segregation of diverse cognitive systems. Our results suggest that structural network differences between cognitive circuits dictate their distinct roles in controlling trajectories of brain network function.
Chat View PDF

SARS Transmission, Risk Factors, and Prevention in Hong Kong

2004-04-01
Joseph T. F. Lau , H.T. Tsui , Mason Lau +1 more
Abstract We analyzed information obtained from 1,192 patients with probable severe acute respiratory syndrome (SARS) reported in Hong Kong. Among them, 26.6% were hospital workers, 16.1% were household members of … Abstract We analyzed information obtained from 1,192 patients with probable severe acute respiratory syndrome (SARS) reported in Hong Kong. Among them, 26.6% were hospital workers, 16.1% were household members of SARS patients and had probable secondary infections, 14.3% were Amoy Garden residents, 4.9% were inpatients, and 20.1% were contacts of SARS patients who were not family members. The remaining 347 case-patients (29.1%) did not have “known” sources of infection. Excluding those <16 years of age, 330 patients with cases from “undefined” sources were used in a 1:2 matched case-control study. Multivariate analysis of this case-control study showed that having visited mainland China, hospitals, or the Amoy Gardens were risk factors (odds ratio [OR] 1.95 to 7.63). In addition, frequent mask use in public venues, frequent hand washing, and disinfecting the living quarters were significant protective factors (OR 0.36 to 0.58). In Hong Kong, therefore, community-acquired infection did not make up most transmissions, and public health measures have contributed substantially to the control of the SARS epidemic.
Chat View PDF

Higher order game dynamics

2013-08-12
Rida Laraki , Panayotis Mertikopoulos
Chat View PDF