BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Tamer Basar

Tamer Basar appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Systems and ControlComputer Science and Game Theorymath.OCInformation Theorymath.ITCryptography and Securitymath.DSMultiagent SystemsSocial and Information NetworksDiscrete Mathematicseess.SYMachine LearningDistributed, Parallel, and Cluster Computingmath.PRNetworking and Internet ArchitectureComputational Complexitymath.COMultimediaRobotics

Catalog footprint

What is connected

52works
19topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

52 published item(s)

preprint2022arXiv

A Networked Competitive Multi-Virus SIR Model: Analysis and Observability

This paper proposes a novel discrete-time multi-virus SIR (susceptible-infected-recovered) model that captures the spread of competing SIR epidemics over a population network. First, we provide a sufficient condition for the infection level of all the viruses over the networked model to converge to zero in exponential time. Second, we propose an observation model which captures the summation of all the viruses' infection levels in each node, which represents the individuals who are infected by different viruses but share similar symptoms. We present a sufficient condition for the model to be locally observable. We propose a Luenberger observer for the system state estimation and show via simulations that the estimation error of the Luenberger observer converges to zero before the viruses die out.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Quantization enabled Privacy Protection in Decentralized Stochastic Optimization

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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Rate-Distortion Theory for Strategic Semantic Communication

This paper analyzes the fundamental limit of the strategic semantic communication problem in which a transmitter obtains a limited number of indirect observation of an intrinsic semantic information source and can then influence the receiver's decoding by sending a limited number of messages to an imperfect channel. The transmitter and the receiver can have different distortion measures and can make rational decision about their encoding and decoding strategies, respectively. The decoder can also have some side information (e.g., background knowledge and/or information obtained from previous communications) about the semantic source to assist its interpretation of the semantic information. We focus particularly on the case that the transmitter can commit to an encoding strategy and study the impact of the strategic decision making on the rate distortion of semantic communication. Three equilibrium solutions including the strong Stackelberg equilibrium, weak Stackelberg equilibrium, as well as Nash equilibrium have been studied and compared. The optimal encoding and decoding strategy profiles under various equilibrium solutions have been derived. We prove that committing to an encoding strategy cannot always bring benefit to the encoder. We therefore propose a feasible condition under which committing to an encoding strategy can always reduce the distortion performance of semantic communication.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The H-property of Line Graphons

We explore in this paper sufficient conditions for the $H$-property to hold, with a particular focus on the so-called line graphons. A graphon is a symmetric, measurable function from the unit square $[0,1]^2$ to the closed interval $[0,1]$. Graphons can be used to sample random graphs, and a graphon is said to have the $H$-property if graphs on $n$ nodes sampled from it admit a node-cover by disjoint cycles -- such a cover is called a Hamiltonian decomposition -- almost surely as $n \to \infty$. A step-graphon is a graphon which is piecewise constant over rectangles in the domain. To a step-graphon, we assign two objects: its concentration vector, encoding the areas of the rectangles, and its skeleton-graph, describing their supports. These two objects were used in our earlier work [3] to establish necessary conditions for a step-graphon to have the $H$-property. In this paper, we prove that these conditions are essentially also sufficient for the class of line-graphons, i.e., the step-graphons whose skeleton graphs are line graphs with a self-loop at an ending node. We also investigate borderline cases where neither the necessary nor the sufficient conditions are met.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Analysis, Identification, and Validation of Discrete-Time Epidemic Processes

Models of spread processes over non-trivial networks are commonly motivated by modeling and analysis of biological networks, computer networks, and human contact networks. However, identification of such models has not yet been explored in detail, and the models have not been validated by real data. In this paper, we present several different spread models from the literature and explore their relationships to each other; for one of these processes, we present a sufficient condition for asymptotic stability of the healthy equilibrium, show that the condition is necessary and sufficient for uniqueness of the healthy equilibrium, and present necessary and sufficient conditions for learning the spread parameters. Finally, we employ two real datasets, one from John Snow's seminal work on cholera epidemics in London in the 1850's and the other one from the United States Department of Agriculture, to validate an approximation of a well-studied network-dependent susceptible-infected-susceptible (SIS) model.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Bayesian Persuasion with State-Dependent Quadratic Cost Measures

We address Bayesian persuasion between a sender and a receiver with state-dependent quadratic cost measures for general classes of distributions. The receiver seeks to make mean-square-error estimate of a state based on a signal sent by the sender while the sender signals strategically in order to control the receiver's estimate in a certain way. Such a scheme could model, e.g., deception and privacy, problems in multi-agent systems. Existing solution concepts are not viable since here the receiver has continuous action space. We show that for finite state spaces, optimal signaling strategies can be computed through an equivalent linear optimization problem over the cone of completely positive matrices. We then establish its strong duality to a copositive program. To exemplify the effectiveness of this equivalence result, we adopt sequential polyhedral approximation of completely-positive cones and analyze its performance numerically. We also quantify the approximation error for a quantized version of a continuous distribution and show that a semi-definite program relaxation of the equivalent problem could be a benchmark lower bound for the sender's cost for large state spaces.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Persuasion-based Robust Sensor Design Against Attackers with Unknown Control Objectives

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Zero-Sum Differential Games on the Wasserstein Space

We consider two-player zero-sum differential games (ZSDGs), where the state process (dynamical system) depends on the random initial condition and the state process's distribution, and the objective functional includes the state process's distribution and the random target variable. Unlike ZSDGs studied in the existing literature, the ZSDG of this paper introduces a new technical challenge, since the corresponding (lower and upper) value functions are defined on $\mathcal{P}_2$ (the set of probability measures with finite second moments) or $\mathcal{L}_2$ (the set of random variables with finite second moments), both of which are infinite-dimensional spaces. We show that the (lower and upper) value functions on $\mathcal{P}_2$ and $\mathcal{L}_2$ are equivalent (law invariant) and continuous, satisfying dynamic programming principles. We use the notion of derivative of a function of probability measures in $\mathcal{P}_2$ and its lifted version in $\mathcal{L}_2$ to show that the (lower and upper) value functions are unique viscosity solutions to the associated (lower and upper) Hamilton-Jacobi-Isaacs equations that are (infinite-dimensional) first-order PDEs on $\mathcal{P}_2$ and $\mathcal{L}_2$, where the uniqueness is obtained via the comparison principle. Under the Isaacs condition, we show that the ZSDG has a value.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Approximation Algorithm for the Binary-Preference Capacitated Selfish Replication Game and a Tight Bound on its Price of Anarchy

We consider the capacitated selfish replication (CSR) game with binary preferences, over general undirected networks. We first show that such games have an associated ordinary potential function, and hence always admit a pure-strategy Nash equilibrium (NE). Further, when the minimum degree of the network and the number of resources are of the same order, there exists an exact polynomial time algorithm which can find a NE. Following this, we study the price of anarchy of such games, and show that it is bounded above by 3; we further provide some instances for which the price of anarchy is at least 2. We develop a quasi-polynomial algorithm O(n^2D^{ln n}), where n is the number of players and D is the diameter of the network, which can find, in a distributed manner, an allocation profile that is within a constant factor of the optimal allocation, and hence of any pure-strategy NE of the game. Proof of this result uses a novel potential function.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Convergence Time of Quantized Metropolis Consensus Over Time-Varying Networks

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Information-Theoretic Approach to Strategic Communication as a Hierarchical Game

This paper analyzes the information disclosure problems originated in economics through the lens of information theory. Such problems are radically different from the conventional communication paradigms in information theory since they involve different objectives for the encoder and the decoder, which are aware of this mismatch and act accordingly. This leads, in our setting, to a hierarchical communication game, where the transmitter announces an encoding strategy with full commitment, and its distortion measure depends on a private information sequence whose realization is available at the transmitter. The receiver decides on its decoding strategy that minimizes its own distortion based on the announced encoding map and the statistics. Three problem settings are considered, focusing on the quadratic distortion measures, and jointly Gaussian source and private information: compression, communication, and the simple equilibrium conditions without any compression or communication. The equilibrium strategies and associated costs are characterized. The analysis is then extended to the receiver side information setting and the major changes in the structure of optimal strategies are identified. Finally, an extension of the results to the broader context of decentralized stochastic control is presented.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On a Modified DeGroot-Friedkin Model of Opinion Dynamics

This paper studies the opinion dynamics that result when individuals consecutively discuss a sequence of issues. Specifically, we study how individuals' self-confidence levels evolve via a reflected appraisal mechanism. Motivated by the DeGroot-Friedkin model, we propose a Modified DeGroot-Friedkin model which allows individuals to update their self-confidence levels by only interacting with their neighbors and in particular, the modified model allows the update of self-confidence levels to take place in finite time without waiting for the opinion process to reach a consensus on any particular issue. We study properties of this Modified DeGroot-Friedkin model and compare the associated equilibria and stability with those of the original DeGroot-Friedkin model. Specifically, for the case when the interaction matrix is doubly stochastic, we show that for the modified model, the vector of individuals' self-confidence levels asymptotically converges to a unique nontrivial equilibrium which for each individual is equal to 1/n, where n is the number of individuals. This implies that eventually, individuals reach a democratic state.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Role of Side Information In Strategic Communication

This paper analyzes the fundamental limits of strate- gic communication in network settings. Strategic communication differs from the conventional communication paradigms in in- formation theory since it involves different objectives for the encoder and the decoder, which are aware of this mismatch and act accordingly. This leads to a Stackelberg game where both agents commit to their mappings ex-ante. Building on our prior work on the point-to-point setting, this paper studies the compression and communication problems with the receiver and/or transmitter side information setting. The equilibrium strategies and associated costs are characterized for the Gaussian variables with quadratic cost functions. Several questions on the benefit of side information in source and joint source-channel coding in such strategic settings are analyzed. Our analysis has uncovered an interesting result on optimality of uncoded mappings in strategic source-channel coding in networks.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Structure of Equilibrium Strategies in Dynamic Gaussian Signaling Games

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimal Capacity Allocation for Sampled Networked Systems

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimal Communication Scheduling and Remote Estimation over an Additive Noise Channel

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Price of Transparency in Strategic Machine Learning

Based on the observation that the transparency of an algorithm comes with a cost for the algorithm designer when the users (data providers) are strategic, this paper studies the impact of strategic intent of the users on the design and performance of transparent ML algorithms. We quantitatively study the {\bf price of transparency} in the context of strategic classification algorithms, by modeling the problem as a nonzero-sum game between the users and the algorithm designer. The cost of having a transparent algorithm is measured by a quantity, named here as price of transparency which is the ratio of the designer cost at the Stackelberg equilibrium, when the algorithm is transparent (which allows users to be strategic) to that of the setting where the algorithm is not transparent.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Scalar Quadratic-Gaussian Soft Watermarking Games

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Voltage Graphs and Cluster Consensus with Point Group Symmetries

A cluster consensus system is a multi-agent system in which the autonomous agents communicate to form multiple clusters, with each cluster of agents asymptotically converging to the same clustering point. We introduce in this paper a special class of cluster consensus dynamics, termed the $G$-clustering dynamics for $G$ a point group, whereby the autonomous agents can form as many as $|G|$ clusters, and moreover, the associated $|G|$ clustering points exhibit a geometric symmetry induced by the point group. The definition of a $G$-clustering dynamics relies on the use of the so-called voltage graph. We recall that a $G$-voltage graph is comprised of two elements---one is a directed graph (digraph), and the other is a map assigning elements of a group~$G$ to the edges of the digraph. For example, in the case when $G = \{1, -1\}$, i.e., a cyclic group of order~$2$, a voltage graph is nothing but a signed graph. A $G$-clustering dynamics can then be viewed as a generalization of the so-called Altafini's model, which was originally defined over a signed graph, by defining the dynamics over a voltage graph. One of the main contributions of this paper is to identify a necessary and sufficient condition for the exponential convergence of a $G$-clustering dynamics. Various properties of voltage graphs that are necessary for establishing the convergence result are also investigated, some of which might be of independent interest in topological graph theory.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Complexity of Equilibrium in Diffusion Games on Social Networks

In this paper, we consider the competitive diffusion game, and study the existence of its pure-strategy Nash equilibrium when defined over general undirected networks. We first determine the set of pure-strategy Nash equilibria for two special but well-known classes of networks, namely the lattice and the hypercube. Characterizing the utility of the players in terms of graphical distances of their initial seed placements to other nodes in the network, we show that in general networks the decision process on the existence of pure-strategy Nash equilibrium is an NP-hard problem. Following this, we provide some necessary conditions for a given profile to be a Nash equilibrium. Furthermore, we study players' utilities in the competitive diffusion game over Erdos-Renyi random graphs and show that as the size of the network grows, the utilities of the players are highly concentrated around their expectation, and are bounded below by some threshold based on the parameters of the network. Finally, we obtain a lower bound for the maximum social welfare of the game with two players, and study sub-modularity of the players' utilities.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Consensus with Linear Objective Maps

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Controllability of Formations over Time-varying Graphs

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Distributed Evaluation and Convergence of Self-Appraisals in Social Networks

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Formation Control with Triangulated Laman Graphs

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On Remote Estimation with Multiple Communication Channels

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Optimal Estimation with Limited Measurements and Noisy Communication

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Optimal Sensor Scheduling and Remote Estimation over an Additive Noise Channel

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Privacy Constrained Information Processing

This paper studies communication scenarios where the transmitter and the receiver have different objectives due to privacy concerns, in the context of a variation of the strategic information transfer (SIT) model of Sobel and Crawford. We first formulate the problem as the minimization of a common distortion by the transmitter and the receiver subject to a privacy constrained transmitter. We show the equivalence of this formulation to a Stackelberg equilibrium of the SIT problem. Assuming an entropy based privacy measure, a quadratic distortion measure and jointly Gaussian variables, we characterize the Stackelberg equilibrium. Next, we consider asymptotically optimal compression at the transmitter which inherently provides some level of privacy, and study equilibrium conditions. We finally analyze the impact of the presence of an average power constrained Gaussian communication channel between the transmitter and the receiver on the equilibrium conditions.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Products of Generalized Stochastic Sarymsakov Matrices

In the set of stochastic, indecomposable, aperiodic (SIA) matrices, the class of stochastic Sarymsakov matrices is the largest known subset (i) that is closed under matrix multiplication and (ii) the infinitely long left-product of the elements from a compact subset converges to a rank-one matrix. In this paper, we show that a larger subset with these two properties can be derived by generalizing the standard definition for Sarymsakov matrices. The generalization is achieved either by introducing an "SIA index", whose value is one for Sarymsakov matrices, and then looking at those stochastic matrices with larger SIA indices, or by considering matrices that are not even SIA. Besides constructing a larger set, we give sufficient conditions for generalized Sarymsakov matrices so that their products converge to rank-one matrices. The new insight gained through studying generalized Sarymsakov matrices and their products has led to a new understanding of the existing results on consensus algorithms and will be helpful for the design of network coordination algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Common Information based Markov Perfect Equilibria for Linear-Gaussian Games with Asymmetric Information

We consider a class of two-player dynamic stochastic nonzero-sum games where the state transition and observation equations are linear, and the primitive random variables are Gaussian. Each controller acquires possibly different dynamic information about the state process and the other controller's past actions and observations. This leads to a dynamic game of asymmetric information among the controllers. Building on our earlier work on finite games with asymmetric information, we devise an algorithm to compute a Nash equilibrium by using the common information among the controllers. We call such equilibria common information based Markov perfect equilibria of the game, which can be viewed as a refinement of Nash equilibrium in games with asymmetric information. If the players' cost functions are quadratic, then we show that under certain conditions a unique common information based Markov perfect equilibrium exists. Furthermore, this equilibrium can be computed by solving a sequence of linear equations. We also show through an example that there could be other Nash equilibria in a game of asymmetric information, not corresponding to common information based Markov perfect equilibria.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Convergence Time for Unbiased Quantized Consensus Over Static and Dynamic Networks

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Game-Theoretic Analysis of the Hegselmann-Krause Model for Opinion Dynamics in Finite Dimensions

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

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

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 or 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 LQG team problems, 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 and team problems with non-classical information known to have optimal solutions.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Gaussian Sensor Networks with Adversarial Nodes

This paper studies a particular sensor network model which involves one single Gaussian source observed by many sensors, subject to additive independent Gaussian observation noise. Sensors communicate with the receiver over an additive 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 act as adversary (jammer): they strive to maximize distortion. 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. Depending on the coordination capability of sensors and the receiver, we consider two problem settings. The first setting involves transmitters with coordination capabilities in the sense that all transmitters can use identical realization of randomized encoding for each transmission. In this case, the optimal strategy for the adversary sensors also requires coordination, where they all generate the same realization of independent and identically distributed Gaussian noise. In the second setting, the transmitter sensors are restricted to use fixed, deterministic encoders and this setting, which corresponds to a Stackelberg game, does not admit a saddle-point solution. We show that the the optimal strategy for all sensors is uncoded communications where encoding functions of adversaries and transmitters are in opposite directions. For both settings, digital compression and communication is strictly suboptimal.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On Optimal Jamming Over an Additive Noise Channel

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Lyapunov stochastic stability and control of robust dynamic coalitional games with transferable utilities

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Optimal Strategies for Communication and Remote Estimation with an Energy Harvesting Sensor

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Risk-Sensitive Mean Field Games

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

SODEXO: A System Framework for Deployment and Exploitation of Deceptive Honeybots in Social Networks

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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A Constrained Evolutionary Gaussian Multiple Access Channel Game

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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Evolutionary Games for Multiple Access Control

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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Heterogeneous Learning in Zero-Sum Stochastic Games with Incomplete Information

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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Indices of Power in Optimal IDS Default Configuration: Theory and Examples

Intrusion Detection Systems (IDSs) are becoming essential to protecting modern information infrastructures. The effectiveness of an IDS is directly related to the computational resources at its disposal. However, it is difficult to guarantee especially with an increasing demand of network capacity and rapid proliferation of attacks. On the other hand, modern intrusions often come as sequences of attacks to reach some predefined goals. It is therefore critical to identify the best default IDS configuration to attain the highest possible overall protection within a given resource budget. This paper proposes a game theory based solution to the problem of optimal signature-based IDS configuration under resource constraints. We apply the concepts of indices of power, namely, Shapley value and Banzhaf-Coleman index, from cooperative game theory to quantify the influence or contribution of libraries in an IDS with respect to given attack graphs. Such valuations take into consideration the knowledge on common attack graphs and experienced system attacks and are used to configure an IDS optimally at its default state by solving a knapsack optimization problem.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Prices of Anarchy, Information, and Cooperation in Differential Games

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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Switching Strategies for Linear Feedback Stabilization with Sparsified State Measurements

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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A Distributed Sequential Algorithm for Collaborative Intrusion Detection Networks

Collaborative intrusion detection networks are often used to gain better detection accuracy and cost efficiency as compared to a single host-based intrusion detection system (IDS). Through cooperation, it is possible for a local IDS to detect new attacks that may be known to other experienced acquaintances. In this paper, we present a sequential hypothesis testing method for feedback aggregation for each individual IDS in the net- work. Our simulation results corroborate our theoretical results and demonstrate the properties of cost efficiency and accuracy compared to other heuristic methods. The analytical result on the lower-bound of the average number of acquaintances for consultation is essential for the design and configuration of IDSs in a collaborative environment.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Coalition Formation Games for Collaborative Spectrum Sensing

Collaborative Spectrum Sensing (CSS) between secondary users (SUs) in cognitive networks exhibits an inherent tradeoff between minimizing the probability of missing the detection of the primary user (PU) and maintaining a reasonable false alarm probability (e.g., for maintaining a good spectrum utilization). In this paper, we study the impact of this tradeoff on the network structure and the cooperative incentives of the SUs that seek to cooperate for improving their detection performance. We model the CSS problem as a non-transferable coalitional game, and we propose distributed algorithms for coalition formation. First, we construct a distributed coalition formation (CF) algorithm that allows the SUs to self-organize into disjoint coalitions while accounting for the CSS tradeoff. Then, the CF algorithm is complemented with a coalitional voting game for enabling distributed coalition formation with detection probability guarantees (CF-PD) when required by the PU. The CF-PD algorithm allows the SUs to form minimal winning coalitions (MWCs), i.e., coalitions that achieve the target detection probability with minimal costs. For both algorithms, we study and prove various properties pertaining to network structure, adaptation to mobility and stability. Simulation results show that CF reduces the average probability of miss per SU up to 88.45% relative to the non-cooperative case, while maintaining a desired false alarm. For CF-PD, the results show that up to 87.25% of the SUs achieve the required detection probability through MWC

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Dynamic Interference Minimization Routing Game for On-Demand Cognitive Pilot Channel

In this paper, we introduce a distributed dynamic routing algorithm for secondary users (SUs) to minimize their interference with the primary users (PUs) in multi-hop cognitive radio (CR) networks. We use the medial axis with a relaxation factor as a reference path which is contingent on the states of the PUs. Along the axis, we construct a hierarchical structure for multiple sources to reach cognitive pilot channel (CPC) base stations. We use a temporal and spatial dynamic non-cooperative game to model the interactions among SUs as well as their influences from PUs in the multi-hop structure of the network. A multi-stage fictitious play learning is used for distributed routing in multi-hop CR networks. We obtain a set of mixed (behavioral) Nash equilibrium strategies of the dynamic game in closed form by backward induction. The proposed algorithm minimizes the overall interference and the average packet delay along the routing path from SU nodes to CPC base stations in an optimal and distributed manner

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Hedonic Coalition Formation for Distributed Task Allocation among Wireless Agents

Autonomous wireless agents such as unmanned aerial vehicles or mobile base stations present a great potential for deployment in next-generation wireless networks. While current literature has been mainly focused on the use of agents within robotics or software applications, we propose a novel usage model for self-organizing agents suited to wireless networks. In the proposed model, a number of agents are required to collect data from several arbitrarily located tasks. Each task represents a queue of packets that require collection and subsequent wireless transmission by the agents to a central receiver. The problem is modeled as a hedonic coalition formation game between the agents and the tasks that interact in order to form disjoint coalitions. Each formed coalition is modeled as a polling system consisting of a number of agents which move between the different tasks present in the coalition, collect and transmit the packets. Within each coalition, some agents can also take the role of a relay for improving the packet success rate of the transmission. The proposed algorithm allows the tasks and the agents to take distributed decisions to join or leave a coalition, based on the achieved benefit in terms of effective throughput, and the cost in terms of delay. As a result of these decisions, the agents and tasks structure themselves into independent disjoint coalitions which constitute a Nash-stable network partition. Moreover, the proposed algorithm allows the agents and tasks to adapt the topology to environmental changes such as the arrival/removal of tasks or the mobility of the tasks. Simulation results show how the proposed algorithm improves the performance, in terms of average player (agent or task) payoff, of at least 30.26% (for a network of 5 agents with up to 25 tasks) relatively to a scheme that allocates nearby tasks equally among agents.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Security Games with Decision and Observation Errors

We study two-player security games which can be viewed as sequences of nonzero-sum matrix games played by an Attacker and a Defender. The evolution of the game is based on a stochastic fictitious play process. Players do not have access to each other's payoff matrix. Each has to observe the other's actions up to present and plays the action generated based on the best response to these observations. However, when the game is played over a communication network, there are several practical issues that need to be taken into account: First, the players may make random decision errors from time to time. Second, the players' observations of each other's previous actions may be incorrect. The players will try to compensate for these errors based on the information they have. We examine convergence property of the game in such scenarios, and establish convergence to the equilibrium point under some mild assumptions when both players are restricted to two actions.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Stochastic Games for Security in Networks with Interdependent Nodes

This paper studies a stochastic game theoretic approach to security and intrusion detection in communication and computer networks. Specifically, an Attacker and a Defender take part in a two-player game over a network of nodes whose security assets and vulnerabilities are correlated. Such a network can be modeled using weighted directed graphs with the edges representing the influence among the nodes. The game can be formulated as a non-cooperative zero-sum or nonzero-sum stochastic game. However, due to correlation among the nodes, if some nodes are compromised, the effective security assets and vulnerabilities of the remaining ones will not stay the same in general, which leads to complex system dynamics. We examine existence, uniqueness, and structure of the solution and also provide numerical examples to illustrate our model.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Coalitional Game Theory for Communication Networks: A Tutorial

Game theoretical techniques have recently become prevalent in many engineering applications, notably in communications. With the emergence of cooperation as a new communication paradigm, and the need for self-organizing, decentralized, and autonomic networks, it has become imperative to seek suitable game theoretical tools that allow to analyze and study the behavior and interactions of the nodes in future communication networks. In this context, this tutorial introduces the concepts of cooperative game theory, namely coalitional games, and their potential applications in communication and wireless networks. For this purpose, we classify coalitional games into three categories: Canonical coalitional games, coalition formation games, and coalitional graph games. This new classification represents an application-oriented approach for understanding and analyzing coalitional games. For each class of coalitional games, we present the fundamental components, introduce the key properties, mathematical techniques, and solution concepts, and describe the methodologies for applying these games in several applications drawn from the state-of-the-art research in communications. In a nutshell, this article constitutes a unified treatment of coalitional game theory tailored to the demands of communications and network engineers.

0 citations0 reviewsNo code linkedOpen access