Tamer Basar

Tamer Basar
Are you Tamer Basar?

Claim your profile, edit publications, add additional information:

Contact Details

Tamer Basar

Pubs By Year

Pub Categories

Mathematics - Optimization and Control (22)
Computer Science - Computer Science and Game Theory (16)
Computer Science - Information Theory (12)
Mathematics - Information Theory (12)
Mathematics - Dynamical Systems (9)
Computer Science - Multiagent Systems (8)
Computer Science - Discrete Mathematics (4)
Mathematics - Combinatorics (4)
Computer Science - Distributed; Parallel; and Cluster Computing (2)
Computer Science - Cryptography and Security (2)
Mathematics - Probability (2)
Computer Science - Computational Complexity (1)
Computer Science - Robotics (1)
Computer Science - Learning (1)
Physics - Physics and Society (1)
Computer Science - Multimedia (1)

Publications Authored By Tamer Basar

The recently proposed DeGroot-Friedkin model describes the dynamical evolution of individual social power in a social network that holds opinion discussions on a sequence of different issues. This paper revisits that model, and uses nonlinear contraction analysis, among other tools, to establish several novel results. First, we show that for a social network with constant topology, each individual's social power converges to its equilibrium value exponentially fast, whereas previous results only concluded asymptotic convergence. Read More

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. Read More

A Boolean network is a finite state discrete time dynamical system. At each step, each variable takes a value from a binary set. The value update rule for each variable is a local function which depends only on a selected subset of variables. Read More

We show in this paper that a small subset of agents of a formation of n agents in Euclidean space can control the position and orientation of the entire formation. We consider here formations tasked with maintaining inter-agent distances at prescribed values. It is known that when the inter-agent distances specified can be realized as the edges of a rigid graph, there is a finite number of possible configurations of the agents that satisfy the distance constraints, up to rotations and translations of the entire formation. Read More

Wholesale electricity market designs in practice do not provide the market participants with adequate mechanisms to hedge their financial risks. Demanders and suppliers will likely face even greater risks with the deepening penetration of variable renewable resources like wind and solar. This paper explores the design of a centralized cash-settled call option market to mitigate such risks. Read More

This paper studies a recently proposed continuous-time distributed self-appraisal model with time-varying interactions among a network of $n$ individuals which are characterized by a sequence of time-varying relative interaction matrices. The model describes the evolution of the social-confidence levels of the individuals via a reflected appraisal mechanism in real time. We first show by example that when the relative interaction matrices are stochastic (not doubly stochastic), the social-confidence levels of the individuals may not converge to a steady state. Read More

This paper analyses the DeGroot-Friedkin model for evolution of the individuals' social powers in a social network when the network topology varies dynamically (described by dynamic relative interaction matrices). The DeGroot-Friedkin model describes how individual social power (self-appraisal, self-weight) evolves as a network of individuals discuss a sequence of issues. We seek to study dynamically changing relative interactions because interactions may change depending on the issue being discussed. Read More

According to the DeGroot-Friedkin model of a social network, an individual's social power evolves as the network discusses individual opinions over a sequence of issues. Under mild assumptions on the connectivity of the network, the social power of every individual converges to a constant strictly positive value as the number of issues discussed increases. If the network has a special topology, termed "star topology", then all social power accumulates with the individual at the centre of the star. Read More

Epidemic processes are used commonly for modeling and analysis of biological networks, computer networks, and human contact networks. The idea of competing viruses has been explored recently, motivated by the spread of different ideas along different social networks. Previous studies of competitive viruses have focused only on two viruses and on static graph structures. Read More

The use of unmanned aerial vehicles (UAVs) as delivery systems of online goods is rapidly becoming a global norm, as corroborated by Amazon's "Prime Air" and Google's "Project Wing" projects. However, the real-world deployment of such drone delivery systems faces many cyber-physical security challenges. In this paper, a novel mathematical framework for analyzing and enhancing the security of drone delivery systems is introduced. Read More

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. Read More

In a recent paper, a distributed algorithm was proposed for solving linear algebraic equations of the form $Ax = b$ assuming that the equation has at least one solution. The equation is presumed to be solved by $m$ agents assuming that each agent knows a subset of the rows of the matrix $[A \; b]$, the current estimates of the equation's solution generated by each of its neighbors, and nothing more. Neighbor relationships are represented by a time-dependent directed graph $N(t)$ whose vertices correspond to agents and whose arcs characterize neighbor relationships. Read More

In this paper, we consider discrete-time dynamic games of the mean-field type with a finite number $N$ of agents subject to an infinite-horizon discounted-cost optimality criterion. The state space of each agent is a locally compact Polish space. At each time, the agents are coupled through the empirical distribution of their states, which affects both the agents' individual costs and their state transition probabilities. Read More

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. Read More

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. Read More

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. Read More

We construct team-optimal estimation algorithms over distributed networks for state estimation in the finite-horizon mean-square error (MSE) sense. Here, we have a distributed collection of agents with processing and cooperation capabilities. These agents observe noisy samples of a desired state through a linear model and seek to learn this state by interacting with each other. Read More

We analyze in this paper finite horizon hierarchical signaling games between informed senders and decision maker receivers in a dynamic environment. The underlying information evolves in time while sender and receiver interact repeatedly. Different from the classical communication models, however, the sender and the receiver have different objectives and there is a hierarchy between the players such that the sender leads the game by announcing his policies beforehand. Read More

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. Read More

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. Read More

A Boolean network is a finite dynamical system, whose variables take values from a binary set. The value update rule for each variable is a local function, i.e. Read More

Motivated by the spread of opinions on different social networks, we study a distributed continuous-time bi-virus model for a system of groups of individuals. An in-depth stability analysis is performed for more general models than have been previously considered, for the healthy and epidemic states. In addition, we investigate sensitivity properties of some nontrivial equilibria and obtain an impossibility result for distributed feedback control. Read More

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. Read More

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. Read More

This paper considers the discrete-time version of Altafini's model for opinion dynamics in which the interaction among a group of agents is described by a time-varying signed digraph. Prompted by an idea from [1], exponential convergence of the system is studied using a graphical approach. Necessary and sufficient conditions for exponential convergence with respect to each possible type of limit states are provided. Read More

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. Read More

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. Read More

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. Read More

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. Read More

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. Read More

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. Read More

This paper studies a multi-period demand response management problem in the smart grid where multiple utility companies compete among themselves. The user-utility interactions are modeled by a noncooperative game of a Stackelberg type where the interactions among the utility companies are captured through a Nash equilibrium. It is shown that this game has a unique Stackelberg equilibrium at which the utility companies set prices to maximize their revenues (within a Nash game) while the users respond accordingly to maximize their utilities subject to their budget constraints. Read More

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. Read More

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. Read More

In this paper, a novel context-aware approach for resource allocation in two-tier wireless small cell networks~(SCNs) is proposed. In particular, the SCN's users are divided into two types: frequent users, who are regular users of certain small cells, and occasional users, who are one-time or infrequent users of a particular small cell. Given such \emph{context} information, each small cell base station (SCBS) aims to maximize the overall performance provided to its frequent users, while ensuring that occasional users are also well serviced. Read More

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$. Read More

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. Read More

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. Read More

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. Read More

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. Read More

Formation control deals with the design of decentralized control laws that stabilize mobile, autonomous agents at prescribed distances from each other. We call any configuration of the agents a target configuration if it satisfies the inter-agent distance conditions. It is well known that when the distance conditions are defined by a rigid graph, there is a finite number of target configurations modulo rotations and translations of the entire formation. Read More

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. Read More

We study the interaction between a network designer and an adversary over a dynamical network. The network consists of nodes performing continuous-time distributed averaging. The adversary strategically disconnects a set of links to prevent the nodes from reaching consensus. Read More

We study the stability properties of a susceptible-infected-susceptible (SIS) diffusion model, so-called the $n$-intertwined Markov model, over arbitrary directed network topologies. As in the majority of the work on infection spread dynamics, this model exhibits a threshold phenomenon. When the curing rates in the network are high, the disease-free state is the unique equilibrium over the network. Read More

We consider a resource allocation game with binary preferences in which each player as a node of an undirected unweighted network is trying to minimize her cost by caching an appropriate resource. Using an ordinal potential function, we propose a polynomial time algorithm to obtain a pure-strategy Nash equilibrium when the number of resources is limited or the network has a high edge density with respect to the number of resources. Moreover, we provide an algorithm to approximate any pure-strategy Nash equilibrium of the game over general networks, and extend our results to games with arbitrary cache sizes. Read More

In this paper, we identify sufficient conditions under which static teams and a class of sequential dynamic teams admit team-optimal solutions. We first investigate the existence of optimal solutions in 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. Read More

Consider a network whose nodes have some initial values, and it is desired to design an algorithm that builds on neighbor to neighbor interactions with the ultimate goal of convergence to the average of all initial node values or to some value close to that average. Such an algorithm is called generically "distributed averaging," and our goal in this paper is to study the performance of a subclass of deterministic distributed averaging algorithms where the information exchange between neighboring nodes (agents) is subject to uniform quantization. With such quantization, convergence to the precise average cannot be achieved in general, but the convergence would be to some value close to it, called quantized consensus. Read More

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. Read More

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. Read More

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. Read More