Tamer Basar

Ashutosh Nayyar, Tamer Basar, Demosthenis Teneketzis et al.

We consider a remote estimation problem with an energy harvesting sensor and a remote estimator. The sensor observes the state of a discrete-time source which may be a finite state Markov chain or a multi-dimensional linear Gaussian system. It harvests energy from its environment (say, for example, through a solar cell) and uses this energy for the purpose of communicating with the estimator. Due to the randomness of energy available for communication, the sensor may not be able to communicate all the time. The sensor may also want to save its energy for future communications. The estimator relies on messages communicated by the sensor to produce real-time estimates of the source state. We consider the problem of finding a communication scheduling strategy for the sensor and an estimation strategy for the estimator that jointly minimize an expected sum of communication and distortion costs over a finite time horizon. Our goal of joint optimization leads to a decentralized decision-making problem. By viewing the problem from the estimator's perspective, we obtain a dynamic programming characterization for the decentralized decision-making problem that involves optimization over functions. Under some symmetry assumptions on the source statistics and the distortion metric, we show that an optimal communication strategy is described by easily computable thresholds and that the optimal estimate is a simple function of the most recently received sensor observation.

Hamidou Tembine, Quanyan Zhu, Tamer Basar

In this paper, we study a class of risk-sensitive mean-field stochastic differential games. We show that under appropriate regularity conditions, the mean-field value of the stochastic differential game with exponentiated integral cost functional coincides with the value function described by a Hamilton-Jacobi-Bellman (HJB) equation with an additional quadratic term. We provide an explicit solution of the mean-field best response when the instantaneous cost functions are log-quadratic and the state dynamics are affine in the control. An equivalent mean-field risk-neutral problem is formulated and the corresponding mean-field equilibria are characterized in terms of backward-forward macroscopic McKean-Vlasov equations, Fokker-Planck-Kolmogorov equations, and HJB equations. We provide numerical examples on the mean field behavior to illustrate both linear and McKean-Vlasov dynamics.

Tamer Basar, Quanyan Zhu

The price of anarchy (PoA) has been widely used in static games to quantify the loss of efficiency due to noncooperation. Here, we extend this concept to a general differential games framework. In addition, we introduce the price of information (PoI) to characterize comparative game performances under different information structures, as well as the price of cooperation to capture the extent of benefit or loss a player accrues as a result of altruistic behavior. We further characterize PoA and PoI for a class of scalar linear quadratic differential games under open-loop and closed-loop feedback information structures. We also obtain some explicit bounds on these indices in a large population regime.

Yongqiang Wang, Tamer Basar

By enabling multiple agents to cooperatively solve a global optimization problem in the absence of a central coordinator, decentralized stochastic optimization is gaining increasing attention in areas as diverse as machine learning, control, and sensor networks. Since the associated data usually contain sensitive information, such as user locations and personal identities, privacy protection has emerged as a crucial need in the implementation of decentralized stochastic optimization. In this paper, we propose a decentralized stochastic optimization algorithm that is able to guarantee provable convergence accuracy even in the presence of aggressive quantization errors that are proportional to the amplitude of quantization inputs. The result applies to both convex and non-convex objective functions, and enables us to exploit aggressive quantization schemes to obfuscate shared information, and hence enables privacy protection without losing provable optimization accuracy. In fact, by using a {stochastic} ternary quantization scheme, which quantizes any value to three numerical levels, we achieve quantization-based rigorous differential privacy in decentralized stochastic optimization, which has not been reported before. In combination with the presented quantization scheme, the proposed algorithm ensures, for the first time, rigorous differential privacy in decentralized stochastic optimization without losing provable convergence accuracy. Simulation results for a distributed estimation problem as well as numerical experiments for decentralized learning on a benchmark machine learning dataset confirm the effectiveness of the proposed approach.

Quanyan Zhu, Hamidou Tembine, Tamer Basar

Learning algorithms are essential for the applications of game theory in a networking environment. In dynamic and decentralized settings where the traffic, topology and channel states may vary over time and the communication between agents is impractical, it is important to formulate and study games of incomplete information and fully distributed learning algorithms which for each agent requires a minimal amount of information regarding the remaining agents. In this paper, we address this major challenge and introduce heterogeneous learning schemes in which each agent adopts a distinct learning pattern in the context of games with incomplete information. We use stochastic approximation techniques to show that the heterogeneous learning schemes can be studied in terms of their deterministic ordinary differential equation (ODE) counterparts. Depending on the learning rates of the players, these ODEs could be different from the standard replicator dynamics, (myopic) best response (BR) dynamics, logit dynamics, and fictitious play dynamics. We apply the results to a class of security games in which the attacker and the defender adopt different learning schemes due to differences in their rationality levels and the information they acquire.

Naci Saldi, Tamer Basar, Maxim Raginsky

Establishing the existence of Nash equilibria for partially observed stochastic dynamic games is known to be quite challenging, with the difficulties stemming from the noisy nature of the measurements available to individual players (agents) and the decentralized nature of this information. When the number of players is sufficiently large and the interactions among agents is of the mean-field type, one way to overcome this challenge is to investigate the infinite-population limit of the problem, which leads to a mean-field game. In this paper, we consider discrete-time partially observed mean-field games with infinite-horizon discounted cost criteria. Using the technique of converting the original partially observed stochastic control problem to a fully observed one on the belief space and the dynamic programming principle, we establish the existence of Nash equilibria for these game models under very mild technical conditions. Then, we show that the mean-field equilibrium policy, when adopted by each agent, forms an approximate Nash equilibrium for games with sufficiently many agents.

Xiaobin Gao, Emrah Akyol, Tamer Basar

This paper considers a sequential sensor scheduling and remote estimation problem with one sensor and one estimator. The sensor makes sequential observations about the state of an underlying memoryless stochastic process and makes a decision as to whether or not to send this measurement to the estimator. The sensor and the estimator have the common objective of minimizing expected distortion in the estimation of the state of the process, over a finite time horizon. The sensor is either charged a cost for each transmission or constrained on transmission times. As opposed to the prior work where communication between the sensor and the estimator was assumed to be perfect (noiseless), in this work an additive noise channel with fixed power constraint is considered; hence, the sensor has to encode its message before transmission. Under some technical assumptions, we obtain the optimal encoding and estimation policies in conjunction with the optimal transmission schedule. The impact of the presence of a noisy channel is analyzed numerically based on dynamic programming. This analysis yields some rather surprising results such as a phase transition phenomenon in the number of used transmission opportunities, which was not encountered in the noiseless communication setting.

Yongqiang Wang, Tamer Basar

Privacy protection and nonconvexity are two challenging problems in decentralized optimization and learning involving sensitive data. Despite some recent advances addressing each of the two problems separately, no results have been reported that have theoretical guarantees on both privacy protection and saddle/maximum avoidance in decentralized nonconvex optimization. We propose a new algorithm for decentralized nonconvex optimization that can enable both rigorous differential privacy and saddle/maximum avoiding performance. The new algorithm allows the incorporation of persistent additive noise to enable rigorous differential privacy for data samples, gradients, and intermediate optimization variables without losing provable convergence, and thus circumventing the dilemma of trading accuracy for privacy in differential privacy design. More interestingly, the algorithm is theoretically proven to be able to efficiently { guarantee accuracy by avoiding} convergence to local maxima and saddle points, which has not been reported before in the literature on decentralized nonconvex optimization. The algorithm is efficient in both communication (it only shares one variable in each iteration) and computation (it is encryption-free), and hence is promising for large-scale nonconvex optimization and learning involving high-dimensional optimization parameters. Numerical experiments for both a decentralized estimation problem and an Independent Component Analysis (ICA) problem confirm the effectiveness of the proposed approach.

Xiaobin Gao, Emrah Akyol, Tamer Basar

This paper considers a sequential sensor scheduling and remote estimation problem with multiple communication channels. Departing from the classical remote estimation paradigm, which involves one communication channel (noiseless or noisy), we consider here the more realistic setting of two channels with different characteristics (one is cheap but noisy, the other one is costly but noiseless). We first show, via a counter-example, that the common folklore of applying symmetric threshold-based policy, which is well known to be optimal (for unimodal state densities) in the classical remote estimation problem, can no longer be optimal in our setting. In view of that, and in order to make the problem tractable, we introduce a side channel which signals to the receiver the sign of the underlying state. We show, under some technical assumptions, that a threshold-in-threshold based communication scheduling is optimal. The impact of the results is analyzed numerically based on dynamic programming. This numerical analysis reveals some rather surprising results inheriting known properties from the single channel settings, such as not exhausting all the opportunities available for the noisy channel.

Tamer Basar, Seyed Rasoul Etesami, Alex Olshevsky

We consider the quantized consensus problem on undirected time-varying connected graphs with n nodes, and devise a protocol with fast convergence time to the set of consensus points. Specifically, we show that when the edges of each network in a sequence of connected time-varying networks are activated based on Poisson processes with Metropolis rates, the expected convergence time to the set of consensus points is at most O(n^2 log^2 n), where each node performs a constant number of updates per unit time.

Emrah Akyol, Kenneth Rose, Tamer Basar

This paper considers the problem of optimal zero-delay jamming over an additive noise channel. Early work had already solved this problem for a Gaussian source and channel. Building on a sequence of recent results on conditions for linearity of optimal estimation, and of optimal mappings in source-channel coding, we derive the saddle-point solution to the jamming problem for general sources and channels, without recourse to Gaussian assumptions. We show that linearity conditions play a pivotal role in jamming, in the sense that the optimal jamming strategy is to effectively force both transmitter and receiver to default to linear mappings, i.e., the jammer ensures, whenever possible, that the transmitter and receiver cannot benefit from non-linear strategies. This result is shown to subsume the known result for Gaussian source and channel. We analyze conditions and general settings where such unbeatable strategy can indeed be achieved by the jammer. Moreover, we provide the procedure to approximate optimal jamming in the remaining (source-channel) cases where the jammer cannot impose linearity on the transmitter and the receiver.

Xudong Chen, M. -A. Belabbas, Tamer Basar

We consider the problem of estimating the states of weakly coupled linear systems from sampled measurements. We assume that the total capacity available to the sensors to transmit their samples to a network manager in charge of the estimation is bounded above, and that each sample requires the same amount of communication. Our goal is then to find an optimal allocation of the capacity to the sensors so that the average estimation error is minimized. We show that when the total available channel capacity is large, this resource allocation problem can be recast as a strictly convex optimization problem, and hence there exists a unique optimal allocation of the capacity. We further investigate how this optimal allocation varies as the available capacity increases. In particular, we show that if the coupling among the subsystems is weak, then the sampling rate allocated to each sensor is nondecreasing in the total sampling rate, and is strictly increasing if and only if the total sampling rate exceeds a certain threshold.

Quanyan Zhu, Hamidou Tembine, Tamer Basar

In this paper, we formulate an evolutionary multiple access channel game with continuous-variable actions and coupled rate constraints. We characterize Nash equilibria of the game and show that the pure Nash equilibria are Pareto optimal and also resilient to deviations by coalitions of any size, i.e., they are strong equilibria. We use the concepts of price of anarchy and strong price of anarchy to study the performance of the system. The paper also addresses how to select one specifc equilibrium solution using the concepts of normalized equilibrium and evolutionary stable strategies. We examine the long-run behavior of these strategies under several classes of evolutionary game dynamics such as Brown-von Neumann-Nash dynamics, and replicator dynamics.

Muhammed Sayin, Emrah Akyol, Tamer Basar

This paper analyzes a finite horizon dynamic signaling game motivated by the well-known strategic information transmission problems in economics. The mathematical model involves information transmission between two agents, a sender who observes two Gaussian processes, state and bias, and a receiver who takes an action based on the received message from the sender. The players incur quadratic instantaneous costs as functions of the state, bias and action variables. Our particular focus is on the Stackelberg equilibrium, which corresponds to information disclosure and Bayesian persuasion problems in economics. Prior work solved the static game, and showed that the Stackelberg equilibrium is achieved by pure strategies that are linear functions of the state and the bias variables. The main focus of this work is on the dynamic (multi-stage) setting, where we show that the existence of a pure strategy Stackelberg equilibrium, within the set of linear strategies, depends on the problem parameters. Surprisingly, for most problem parameters, a pure linear strategy does not achieve the Stackelberg equilibrium which implies the existence of a trade-off between exploiting and revealing information, which was also encountered in several other asymmetric information games.

Quanyan Zhu, Hamidou Tembine, Tamer Basar

In this paper, we formulate an evolutionarymultiple access control game with continuousvariable actions and coupled constraints. We characterize equilibria of the game and show that the pure equilibria are Pareto optimal and also resilient to deviations by coalitions of any size, i.e., they are strong equilibria. We use the concepts of price of anarchy and strong price of anarchy to study the performance of the system. The paper also addresses how to select one specific equilibrium solution using the concepts of normalized equilibrium and evolutionarily stable strategies. We examine the long-run behavior of these strategies under several classes of evolutionary game dynamics, such as Brown-von Neumann-Nash dynamics, Smith dynamics and replicator dynamics. In addition, we examine correlated equilibrium for the single-receiver model. Correlated strategies are based on signaling structures before making decisions on rates. We then focus on evolutionary games for hybrid additive white Gaussian noise multiple access channel with multiple users and multiple receivers, where each user chooses a rate and splits it over the receivers. Users have coupled constraints determined by the capacity regions. Building upon the static game, we formulate a system of hybrid evolutionary game dynamics using G-function dynamics and Smith dynamics on rate control and channel selection, respectively. We show that the evolving game has an equilibrium and illustrate these dynamics with numerical examples.

Kang Kang, Sourabh Bhattacharya, Tamer Basar

In this paper, we address the problem of stabilization in continuous time linear dynamical systems using state feedback when compressive sampling techniques are used for state measurement and reconstruction. In [5], we had introduced the concept of using l1 reconstruction technique, commonly used in sparse data reconstruction, for state measurement and estimation in a discrete time linear system. In this work, we extend the previous scenario to analyse continuous time linear systems. We investigate the effect of switching within a set of sparsifiers, introduced in [5], on the stability of a linear plant in continuous time settings. Initially, we analyze the problem of stabilization in low dimensional systems, following which we generalize the results to address the problem of stabilization in systems of arbitrary dimensions.

Dario Bauso, Puduru Viswanadha Reddy, Tamer Basar

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

Navjot Singh, Xuanyu Cao, Suhas Diggavi et al.

We consider a multi-agent network where each node has a stochastic (local) cost function that depends on the decision variable of that node and a random variable, and further the decision variables of neighboring nodes are pairwise constrained. There is an aggregate objective function for the network, composed additively of the expected values of the local cost functions at the nodes, and the overall goal of the network is to obtain the minimizing solution to this aggregate objective function subject to all the pairwise constraints. This is to be achieved at the node level using decentralized information and local computation, with exchanges of only compressed information allowed by neighboring nodes. The paper develops algorithms and obtains performance bounds for two different models of local information availability at the nodes: (i) sample feedback, where each node has direct access to samples of the local random variable to evaluate its local cost, and (ii) bandit feedback, where samples of the random variables are not available, but only the values of the local cost functions at two random points close to the decision are available to each node. For both models, with compressed communication between neighbors, we have developed decentralized saddle-point algorithms that deliver performances no different (in order sense) from those without communication compression; specifically, we show that deviation from the global minimum value and violations of the constraints are upper-bounded by $\mathcal{O}(T^{-\frac{1}{2}})$ and $\mathcal{O}(T^{-\frac{1}{4}})$, respectively, where $T$ is the number of iterations. Numerical examples provided in the paper corroborate these bounds and demonstrate the communication efficiency of the proposed method.

Muhammed O. Sayin, Kaiqing Zhang, David S. Leslie et al.

We study multi-agent reinforcement learning (MARL) in infinite-horizon discounted zero-sum Markov games. We focus on the practical but challenging setting of decentralized MARL, where agents make decisions without coordination by a centralized controller, but only based on their own payoffs and local actions executed. The agents need not observe the opponent's actions or payoffs, possibly being even oblivious to the presence of the opponent, nor be aware of the zero-sum structure of the underlying game, a setting also referred to as radically uncoupled in the literature of learning in games. In this paper, we develop a radically uncoupled Q-learning dynamics that is both rational and convergent: the learning dynamics converges to the best response to the opponent's strategy when the opponent follows an asymptotically stationary strategy; when both agents adopt the learning dynamics, they converge to the Nash equilibrium of the game. The key challenge in this decentralized setting is the non-stationarity of the environment from an agent's perspective, since both her own payoffs and the system evolution depend on the actions of other agents, and each agent adapts her policies simultaneously and independently. To address this issue, we develop a two-timescale learning dynamics where each agent updates her local Q-function and value function estimates concurrently, with the latter happening at a slower timescale.

Tao Li, Guanze Peng, Quanyan Zhu et al.

Recent years have witnessed significant advances in technologies and services in modern network applications, including smart grid management, wireless communication, cybersecurity as well as multi-agent autonomous systems. Considering the heterogeneous nature of networked entities, emerging network applications call for game-theoretic models and learning-based approaches in order to create distributed network intelligence that responds to uncertainties and disruptions in a dynamic or an adversarial environment. This paper articulates the confluence of networks, games and learning, which establishes a theoretical underpinning for understanding multi-agent decision-making over networks. We provide an selective overview of game-theoretic learning algorithms within the framework of stochastic approximation theory, and associated applications in some representative contexts of modern network systems, such as the next generation wireless communication networks, the smart grid and distributed machine learning. In addition to existing research works on game-theoretic learning over networks, we highlight several new angles and research endeavors on learning in games that are related to recent developments in artificial intelligence. Some of the new angles extrapolate from our own research interests. The overall objective of the paper is to provide the reader a clear picture of the strengths and challenges of adopting game-theoretic learning methods within the context of network systems, and further to identify fruitful future research directions on both theoretical and applied studies.

Wesley Suttle, Zhuoran Yang, Kaiqing Zhang et al.

This paper extends off-policy reinforcement learning to the multi-agent case in which a set of networked agents communicating with their neighbors according to a time-varying graph collaboratively evaluates and improves a target policy while following a distinct behavior policy. To this end, the paper develops a multi-agent version of emphatic temporal difference learning for off-policy policy evaluation, and proves convergence under linear function approximation. The paper then leverages this result, in conjunction with a novel multi-agent off-policy policy gradient theorem and recent work in both multi-agent on-policy and single-agent off-policy actor-critic methods, to develop and give convergence guarantees for a new multi-agent off-policy actor-critic algorithm.

Muhammed O. Sayin, Tamer Basar

We introduce deceptive signaling framework as a new defense measure against advanced adversaries in cyber-physical systems. In general, adversaries look for system-related information, e.g., the underlying state of the system, in order to learn the system dynamics and to receive useful feedback regarding the success/failure of their actions so as to carry out their malicious task. To this end, we craft the information that is accessible to adversaries strategically in order to control their actions in a way that will benefit the system, indirectly and without any explicit enforcement. Under the solution concept of game-theoretic hierarchical equilibrium, we arrive at a semi-definite programming problem equivalent to the infinite-dimensional optimization problem faced by the defender while selecting the best strategy when the information of interest is Gaussian and both sides have quadratic cost functions. The equivalence result holds also for the scenarios where the defender can have partial or noisy measurements or the objective of the adversary is not known. We show the optimality of linear signaling rule within the general class of measurable policies in communication scenarios and also compute the optimal linear signaling rule in control scenarios.

Muhammed O. Sayin, Chung-Wei Lin, Eunsuk Kang et al.

In this paper, we propose a game theoretical adversarial intervention detection mechanism for reliable smart road signs. A future trend in intelligent transportation systems is ``smart road signs" that incorporate smart codes (e.g., visible at infrared) on their surface to provide more detailed information to smart vehicles. Such smart codes make road sign classification problem aligned with communication settings more than conventional classification. This enables us to integrate well-established results in communication theory, e.g., error-correction methods, into road sign classification problem. Recently, vision-based road sign classification algorithms have been shown to be vulnerable against (even) small scale adversarial interventions that are imperceptible for humans. On the other hand, smart codes constructed via error-correction methods can lead to robustness against small scale intelligent or random perturbations on them. In the recognition of smart road signs, however, humans are out of the loop since they cannot see or interpret them. Therefore, there is no equivalent concept of imperceptible perturbations in order to achieve a comparable performance with humans. Robustness against small scale perturbations would not be sufficient since the attacker can attack more aggressively without such a constraint. Under a game theoretical solution concept, we seek to ensure certain measure of guarantees against even the worst case (intelligent) attackers that can perturb the signal even at large scale. We provide a randomized detection strategy based on the distance between the decoder output and the received input, i.e., error rate. Finally, we examine the performance of the proposed scheme over various scenarios.

Muhammed O. Sayin, Tamer Basar

In this paper, we introduce a robust sensor design framework to provide "persuasion-based" defense in stochastic control systems against an unknown type attacker with a control objective exclusive to its type. For effective control, such an attacker's actions depend on its belief on the underlying state of the system. We design a robust "linear-plus-noise" signaling strategy to encode sensor outputs in order to shape the attacker's belief in a strategic way and correspondingly to persuade the attacker to take actions that lead to minimum damage with respect to the system's objective. The specific model we adopt is a Gauss-Markov process driven by a controller with a (partially) "unknown" malicious/benign control objective. We seek to defend against the worst possible distribution over control objectives in a robust way under the solution concept of Stackelberg equilibrium, where the sensor is the leader. We show that a necessary and sufficient condition on the covariance matrix of the posterior belief is a certain linear matrix inequality and we provide a closed-form solution for the associated signaling strategy. This enables us to formulate an equivalent tractable problem, indeed a semi-definite program, to compute the robust sensor design strategies "globally" even though the original optimization problem is non-convex and highly nonlinear. We also extend this result to scenarios where the sensor makes noisy or partial measurements. Finally, we analyze the ensuing performance numerically for various scenarios.

Mohammad A. Noureddine, Ahmed Fawaz, Tamer Basar et al.

In this paper, we address the challenges facing the adoption of client puzzles as means to protect the TCP connection establishment channel from state exhaustion DDoS attacks. We model the problem of selecting the puzzle difficulties as a Stackelberg game with the server as the leader and the clients as the followers and obtain the equilibrium solution for the puzzle difficulty. We then present an implementation of client puzzles inside the TCP stack of the Linux 4.13.0 kernel. We evaluate the performance of our implementation and the obtained solution against a range of attacks through experiments on the DETER testbed. Our results show that client puzzles are effective at boosting the tolerance of the TCP handshake channel to state exhaustion DDoS attacks by rate limiting the flood rate of malicious attackers while allocating resources for legitimate clients. Our results illustrate the benefits that the servers and clients amass from the deployment of TCP client puzzles and incentivize their adoption as means to enhance tolerance to multi-vectored DDoS attacks

Naci Saldi, Tamer Basar, Maxim Raginsky

In this paper, we study a class of discrete-time mean-field games under the infinite-horizon risk-sensitive discounted-cost optimality criterion. Risk-sensitivity is introduced for each agent (player) via an exponential utility function. In this game model, each agent is coupled with the rest of the population through the empirical distribution of the states, which affects both the agent's individual cost and its state dynamics. Under mild assumptions, we establish the existence of a mean-field equilibrium in the infinite-population limit as the number of agents ($N$) goes to infinity, and then show that the policy obtained from the mean-field equilibrium constitutes an approximate Nash equilibrium when $N$ is sufficiently large.

Emrah Akyol, Kenneth Rose, Tamer Basar et al.

This paper studies optimal communication and coordination strategies in cyber-physical systems for both defender and attacker within a game-theoretic framework. We model the communication network of a cyber-physical system as a sensor network which involves one single Gaussian source observed by many sensors, subject to additive independent Gaussian observation noises. The sensors communicate with the estimator over a coherent Gaussian multiple access channel. The aim of the receiver is to reconstruct the underlying source with minimum mean squared error. The scenario of interest here is one where some of the sensors are captured by the attacker and they act as the adversary (jammer): they strive to maximize distortion. The receiver (estimator) knows the captured sensors but still cannot simply ignore them due to the multiple access channel, i.e., the outputs of all sensors are summed to generate the estimator input. We show that the ability of transmitter sensors to secretly agree on a random event, that is "coordination", plays a key role in the analysis...

Kivanc Mihcak, Emrah Akyol, Tamer Basar et al.

We introduce the zero-sum game problem of soft watermarking: The hidden information (watermark) comes from a continuum and has a perceptual value; the receiver generates an estimate of the embedded watermark to minimize the expected estimation error (unlike the conventional watermarking schemes where both the hidden information and the receiver output are from a discrete finite set). Applications include embedding a multimedia content into another. We consider in this paper the scalar Gaussian case and use expected mean-squared distortion. We formulate the resulting problem as a zero-sum game between the encoder & receiver pair and the attacker. We show that for the lin- ear encoder, the optimal attacker is Gaussian-affine, derive the optimal system parameters in that case, and discuss the corresponding system behavior. We also provide numerical results to gain further insight and understanding of the system behavior at optimality.

Xudong Chen, Ji Liu, M. -A. Belabbas et al.

We consider in this paper a networked system of opinion dynamics in continuous time, where the agents are able to evaluate their self-appraisals in a distributed way. In the model we formulate, the underlying network topology is described by a rooted digraph. For each ordered pair of agents $(i,j)$, we assign a function of self-appraisal to agent $i$, which measures the level of importance of agent $i$ to agent $j$. Thus, by communicating only with her neighbors, each agent is able to calculate the difference between her level of importance to others and others' level of importance to her. The dynamical system of self-appraisals is then designed to drive these differences to zero. We show that for almost all initial conditions, the trajectory generated by this dynamical system asymptotically converges to an equilibrium point which is exponentially stable.

Xiaobin Gao, Emrah Akyol, Tamer Basar

This paper considers a sequential estimation and sensor scheduling problem in the presence of multiple communication channels. As opposed to the classical remote estimation problem that involves one perfect (noiseless) channel and one extremely noisy channel (which corresponds to not transmitting the observed state), a more realistic additive noise channel with fixed power constraint along with a more costly perfect channel is considered. It is shown, via a counter-example, that the common folklore of applying symmetric threshold policy, which is well known to be optimal (for unimodal state densities) in the classical two-channel remote estimation problem, can be suboptimal for the setting considered. Next, in order to make the problem tractable, a side channel which signals the sign of the underlying state is considered. It is shown that, under some technical assumptions, threshold-in-threshold communication scheduling is optimal for this setting. The impact of the presence of a noisy channel is analyzed numerically based on dynamic programming. This numerical analysis uncovers some rather surprising results inheriting known properties from the noisy and noiseless settings.

Xiaobin Gao, Emrah Akyol, Tamer Basar

We consider a sensor scheduling and remote estimation problem with one sensor and one estimator. At each time step, the sensor makes an observation on the state of a source, and then decides whether to transmit its observation to the estimator or not. The sensor is charged a cost for each transmission. The remote estimator generates a real-time estimate on the state of the source based on the messages received from the sensor. The estimator is charged for estimation error. As compared with previous works from the literature, we further assume that there is an additive communication channel noise. As a consequence, the sensor needs to encode the message before transmitting it to the estimator. For some specific distributions of the underlying random variables, we obtain the optimal solution to the problem of minimizing the expected value of the sum of communication cost and estimation cost over the time horizon.

Xiaobin Gao, Emrah Akyol, Tamer Basar

This paper considers a sequential estimation and sensor scheduling problem with one sensor and one estimator. The sensor makes sequential observations about the state of an underlying memoryless stochastic process, and makes a decision as to whether or not to send this measurement to the estimator. The sensor and the estimator have the common objective of minimizing expected distortion in the estimation of the state of the process, over a finite time horizon, with the constraint that the sensor can transmit its observation only a limited number of times. As opposed to the prior work where communication between the sensor and the estimator was assumed to be perfect (noiseless), in this work an additive noise channel with fixed power constraint is considered; hence, the sensor has to encode its message before transmission. For some specific source and channel noise densities, we obtain the optimal encoding and estimation policies in conjunction with the optimal transmission schedule. The impact of the presence of a noisy channel is analyzed numerically based on dynamic programming. This analysis yields some rather surprising results such as a phase-transition phenomenon in the number of used transmission opportunities, which was not encountered in the noiseless communication setting.

Xudong Chen, M. -A. Belabbas, Tamer Basar

In this paper, we investigate the controllability of a class of formation control systems. Given a directed graph, we assign an agent to each of its vertices and let the edges of the graph describe the information flow in the system. We relate the strongly connected components of this graph to the reachable set of the formation control system. Moreover, we show that the formation control model is approximately path-controllable over a path-connected, open dense subset as long as the graph is weakly connected and satisfies some mild assumption on the numbers of vertices of the strongly connected components.

Xudong Chen, M. -A. Belabbas, Tamer Basar

A consensus system is a linear multi-agent system in which agents communicate to reach a so-called consensus state, defined as the average of the initial states of the agents. Consider a more generalized situation in which each agent is given a positive weight and the consensus state is defined as the weighted average of the initial conditions. We characterize in this paper the weighted averages that can be evaluated in a decentralized way by agents communicating over a directed graph. Specifically, we introduce a linear function, called the objective map, that defines the desired final state as a function of the initial states of the agents. We then provide a complete answer to the question of whether there is a decentralized consensus dynamics over a given digraph which converges to the final state specified by an objective map. In particular, we characterize not only the set of objective maps that are feasible for a given digraph, but also the consensus dynamics that implements the objective map. In addition, we present a decentralized algorithm to design the consensus dynamics.

Xudong Chen, M. -A. Belabbas, Tamer Basar

Formation control deals with the design of decentralized control laws that stabilize agents at prescribed distances from each other. We call any configuration that satisfies the inter-agent distance conditions a target configuration. It is well known that when the distance conditions are defined via a rigid graph, there is a finite number of target configurations modulo rotations and translations. We can thus recast the objective of formation control as stabilizing one or many of the target configurations. A major issue is that such control laws will also have equilibria corresponding to configurations which do not meet the desired inter-agent distance conditions; we refer to these as undesired equilibria. The undesired equilibria become problematic if they are also stable. Designing decentralized control laws whose stable equilibria are all target configurations in the case of a general rigid graph is still an open problem. We propose here a partial solution to this problem by exhibiting a class of rigid graphs and control laws for which all stable equilibria are target configurations.

Seyed Rasoul Etesami, Tamer Basar

We consider the Hegselmann-Krause model for opinion dynamics and study the evolution of the system under various settings. We first analyze the termination time of the synchronous Hegselmann-Krause dynamics in arbitrary finite dimensions and show that the termination time in general only depends on the number of agents involved in the dynamics. To the best of our knowledge, that is the sharpest bound for the termination time of such dynamics that removes dependency of the termination time from the dimension of the ambient space. This answers an open question in [1] on how to obtain a tighter upper bound for the termination time. Furthermore, we study the asynchronous Hegselmann-Krause model from a novel game-theoretic approach and show that the evolution of an asynchronous Hegselmann-Krause model is equivalent to a sequence of best response updates in a well-designed potential game. We then provide a polynomial upper bound for the expected time and expected number of switching topologies until the dynamic reaches an arbitrarily small neighborhood of its equilibrium points, provided that the agents update uniformly at random. This is a step toward analysis of heterogeneous Hegselmann-Krause dynamics. Finally, we consider the heterogeneous Hegselmann-Krause dynamics and provide a necessary condition for the finite termination time of such dynamics. In particular, we sketch some future directions toward more detailed analysis of the heterogeneous Hegselmann-Krause model.

Seyed Rasoul Etesami, Tamer Basar

In this paper, the question of expected time to convergence is addressed for unbiased quantized consensus on undirected connected graphs, and some strong results are obtained. The paper first provides a tight expression for the expected convergence time of the unbiased quantized consensus over general but fixed networks. It is shown that the maximum expected convergence time lies within a constant factor of the maximum hitting time of an appropriate lazy random walk, using the theory of harmonic functions for reversible Markov chains. Following this, and using electric resistance analogy of the reversible Markov chains, the paper provides a tight upper bound for the expected convergence time to consensus based on the parameters of the network. Moreover, the paper identifies a precise order of the maximum expected convergence time for some simple graphs such as line graph and cycle. Finally, the results are extended to bound the expected convergence time of the underlying dynamics in time-varying networks. Modeling such dynamics as the evolution of a time inhomogeneous Markov chain, the paper derives a tight upper bound for expected convergence time of the dynamics using the spectral representation of the networks. This upper bound is significantly better than earlier results for the quantized consensus problem over time-varying graphs.

Garrett Warnell, Sourabh Bhattacharya, Rama Chellappa et al.

We provide two novel adaptive-rate compressive sensing (CS) strategies for sparse, time-varying signals using side information. Our first method utilizes extra cross-validation measurements, and the second one exploits extra low-resolution measurements. Unlike the majority of current CS techniques, we do not assume that we know an upper bound on the number of significant coefficients that comprise the images in the video sequence. Instead, we use the side information to predict the number of significant coefficients in the signal at the next time instant. For each image in the video sequence, our techniques specify a fixed number of spatially-multiplexed CS measurements to acquire, and adjust this quantity from image to image. Our strategies are developed in the specific context of background subtraction for surveillance video, and we experimentally validate the proposed methods on real video sequences.

Quanyan Zhu, Andrew Clark, Radha Poovendran et al.

As social networking sites such as Facebook and Twitter are becoming increasingly popular, a growing number of malicious attacks, such as phishing and malware, are exploiting them. Among these attacks, social botnets have sophisticated infrastructure that leverages compromised users accounts, known as bots, to automate the creation of new social networking accounts for spamming and malware propagation. Traditional defense mechanisms are often passive and reactive to non-zero-day attacks. In this paper, we adopt a proactive approach for enhancing security in social networks by infiltrating botnets with honeybots. We propose an integrated system named SODEXO which can be interfaced with social networking sites for creating deceptive honeybots and leveraging them for gaining information from botnets. We establish a Stackelberg game framework to capture strategic interactions between honeybots and botnets, and use quantitative methods to understand the tradeoffs of honeybots for their deployment and exploitation in social networks. We design a protection and alert system that integrates both microscopic and macroscopic models of honeybots and optimally determines the security strategies for honeybots. We corroborate the proposed mechanism with extensive simulations and comparisons with passive defenses.