My research is on understanding and designing networked interactions of multiple agents in social and technological settings. Networked multi-agent systems are at the core of signal processing and control theory. Examples of such complex systems are found in energy systems (microgrid, demand response), public health (infectious diseases), autonomous robot systems, communication (uplink power allocation), cyber-physical systems among many others. In my research I use game theory and distributed optimization tools to model, analyze and design decision making of agents in complex networked systems.

My current research interests can be thematically represented along the following lines:

  • Networked decision-making in multi-agent systems with uncertainty
  • Decentralized energy systems and energy management
  • Social epidemics on networks

Below I overview each research theme.

Networked decision-making in multi-agent systems with uncertainty

In many multi-agent systems -- stock market, teams of robots, devices in a microgrid --, agents in a network want to take actions that maximize their individual payoffs while their payoff values depend on the state of the environment and actions of the rest of the population. When agents have different and incomplete information about the state of the environment, agents are players in a game of incomplete information. I consider repeated play of this incomplete information game while agents acquire new information from their neighbors in the network and possibly from other sources after each time step. Acquiring this information alters agents' beliefs leading to the selection of new actions which become known at the next play prompting further reevaluation of beliefs and corresponding actions [5]. This research on networked multi-agent systems focuses on the interplay between understanding emerging behavior and designing optimal algorithms. It can be divided into two based on whether agents are rational or not.

Rational behavior

The rational individual behavior in a game of incomplete information maximizes expected individual payoff given the rational actions of others. This rational behavior is called the Bayesian Nash equilibrium (BNE) solution concept. The determination of this BNE behavior involves forming Bayesian beliefs about the state and actions of other agents who have different beliefs about the state. We dub these games in which agents repeatedly make stage game rational decisions and acquire new information from their network as Bayesian Network games (BNG). In this context we talk of Bayesian learning because the agents' goal can be reinterpreted as the eventual learning of peers' actions so that expected payoffs coincide with actual payoffs. The question we try to answer in [3] is whether this information is eventually learned or not.

The burden of computing a BNE in repeated games is, in general, overwhelming even for small sized networks. This is an important drawback for the application of network games to the implementation of distributed actions in autonomous teams. Another purpose of this thrust is to develop algorithms to enable computation of rational actions. By focusing on quadratic payoff functions and initial Gaussian beliefs on the state, we derive the Quadratic Network Game (QNG) filter that agents can run locally to maximize their expected payoffs. The individual Bayesian belief forming process is akin to Kalman filter and involves a full network simulation by the individual [4].

Multi-robot system: Gritsbots running the distributed fictitious play algorithm to solve a task assignment problem in the Robotarium. Click here for the video.

Distributed learning and optimization

In many multi-agent systems, a team of autonomous agents want to complete a task but each agent has different and incomplete information about the task. For instance, consider the problem of task assignment where a team of n robots wants to cover n targets. Each robot has a different belief on targets' locations. The goal is to cover all targets by moving on to the target location while minimizing the total distance traversed. The communication limitations of each robot disallows aggregation of information on locations of targets. This problem is a potential game of incomplete information where there exists a state dependent global objective that agents affect through their individual actions.The optimal action profile maximizes this global objective for the realized environment's state with the optimal action of an agent given by the corresponding action in the profile. The problem we address in this work is the determination of suitable actions when the probability distributions that agents have on the state of the environment are possibly different. These not entirely congruous beliefs result in mismatches between the action profiles that different agents deem to be optimal. As a consequence, when a given agent chooses an action to execute, it is important for it to reason about what the beliefs of other agents may be and what are the consequent actions that other agents may take. In this case, even though the interests of the members of the autonomous team are aligned, they have to resort to strategic reasoning and end up playing a game against uncertainty. The solutions that we propose to the problem above are variations of the fictitious play algorithm that take into account the distributed nature of the multi-agent system and the fact that the state of the environment is not perfectly known [1], [2].

Collaborators and References

The project on Bayesian Network Games started and evolved in collaboration with Pooya Molavi. We thank Ali Jadbabaie and Alejandro Ribeiro for their guidance and support. In the recent work on bounded rational algorithms, I was fortunate to collaborate with Brian Swenson and Soummya Kar. Special thanks goes to GritsLab PI Magnus Egerstedt and Daniel Pickem for their open-access testbed Robotarium.

For detailed account of these topics see the journal articles and the review article cited below.

  1. C. Eksin and A. Ribeiro, Distributed Fictitious Play for Optimal Behavior of Multi-Agent Systems with Incomplete Information, IEEE Trans. Autom. Control., vol. (revised), June 2016.
  2. B. Swenson, C. Eksin, S. Kar, A. Ribeiro, Fictitious Play with Inertia Learns Pure Equilibria in Distributed Games with Incomplete Information, (submitted), April 2016.
  3. P. Molavi, C. Eksin, A. Ribeiro and A. Jadbabaie, Learning to Coordinate in Social Networks, Operations Research, vol. 64, no. 3, June 2016.
  4. C. Eksin, P. Molavi, A. Ribeiro and A. Jadbabaie, Bayesian Quadratic Network Game Filters, IEEE Trans. Signal Process., vol. 62, no. 9, pp. 2250 - 2264, May 2014.
  5. C. Eksin, P. Molavi, A. Ribeiro and A. Jadbabaie, Learning in Networks with Incomplete Information, IEEE Signal Process Mag., vol. 30, no. 3, pp. 30-42, May 2013.

Decentralized energy systems and energy management

Energy system: The SO is responsible for matching power production to consumption. Consumers with smart meters and energy consumption schedulers can shift their demand given the right incentives improving system efficiency.

We are currently observing a multi-disciplinary research thrust to re-design the electricity grid. The overarching objective of this thrust is to have an efficient distribution system that is also robust. My research on this topic is primarily involved with the design of the communication among the entities of the grid -- users, operators, suppliers -- that will be supported by the adoption of smart meters and with the design for seamless integration of growing renewable energy generation into the grid.

In this project we consider the problem of matching power production to power consumption. This problem is exacerbated by the introduction of renewable sources, which, by their very nature, exhibit significant output fluctuations. This problem can be mitigated with the introduction of a system of smart meters. Smart meters control the power consumption of customers by managing the energy cycles of various devices while also enabling information exchanges between customers and the system operator as well as between customers themselves. The information flow and control abilities can be combined with sophisticated pricing strategies so as to encourage a better match between power production and consumption. The effort of power providers to regulate the consumption of end users is referred to as demand response management. In our work, we study the rational consumer behavior in a repeated noncooperative game with incomplete information when the power provider employs an adaptive pricing policy. The adaptive price depends on renewable source output and total power consumption, and hence incentivizes customers with heterogeneous preferences to anticipate behavior of others and beware of their influence on price. Given the adaptive pricing strategy, we formulate the power consumption behavior of customers as a repeated noncooperative game with incomplete information. We provide an explicit characterization of unique Bayesian Nash equilibrium strategy when consumers only know their self-preference and the population preference distribution. Comparing the behavior of selfish consumers with the welfare maximizing consumers, selfish consumers tend to put more weight on their self-preference than on the mean population preference. The rational behavior is also characterized in a communication scheme where smart meters exchange consumption levels with neighboring meters. We use the QNG algorithm to compute equilibrium consumption and propagate beliefs. We observe that communication leads consumers to act similar to welfare maximizing individuals. In addition, communication is beneficial for welfare while having negligible effect on price and consumption levels. We further propose an ad-hoc pricing scheme that the operator can use to lower the peak-to-average ratio of total consumption by adjusting its target profit ratio.

Collaborators and References

The work on demand response management in Smart Grids started in collaboration with Hakan Delic when I visited Bogazici University in the summer of 2013. Alejandro Ribeiro continues to provide invaluable help in developing this project. Selected publications on this project are below.

  1. C. Eksin, H. Delic and A. Ribeiro, Demand Response with Cooperating Rational Consumers, IEEE Trans. on Smart Grid, (to appear), September 2016.
  2. C. Eksin, H. Delic and A. Ribeiro, Demand Response Management in Smart Grids with Heterogeneous Consumer Preferences, IEEE Trans. on Smart Grid, vol. 6, no. 6, pp. 3082 - 3094, November 2015.
  3. C. Eksin, A. Hooshmand and R. Sharma, A Decentralized Energy Management System, in Proc. European Control Conference (ECC), pp. 2260 - 2267, Linz, Austria, July 15-17 2015.

Social Epidemics on Networks

Epidemics: Social network influences disease spread. Figure is from (Bauch & Galvani, Science 2013).

Epidemic diseases often spread via a form of contact among individuals. The existing web of interactions among the humans in a population determines the contact network over which the disease dynamics propagate. When a disease breaks out in the population, people that become aware of the disease can take precautionary measures to reduce their risk of getting infected. These measures are behavioral responses that depend on the local information of the individual on its risk of infection. In return, these responses affect the spread of the disease by changing the underlying contact rate among the individuals. In this project, we propose individual behavior response models to the disease prevalence in the population. In [1], we consider a model where individuals distance themselves from their local contacts based on their awareness. An individual forms its awareness based on information from its contacts in the social network. The efficacy of their distancing depends on the "amount of overlap" between their contagion network and their social network. In [2] we consider a game theoretic basis for understanding the rational response of healthy and sick individuals over a network. The starting point for our model is the recognition that healthy individuals are concerned about contracting a disease from their sick contacts and may utilize protective measures. In addition, sick individuals may be concerned with spreading the disease to their healthy contacts and adopt preemptive measures. Yet, in practice both protective and preemptive changes in behavior come with costs. We show using analytical derivations and simulations that the empathy of sick individuals is more important than the risk aversion of healthy individuals in eliminating the disease. More broadly, we hope that the current framework enables a deeper integration of game theory into studies of how behavior is shaped by and shapes disease dynamics. Overall, this research thrust points to potential pitfalls in current state-of-the-art disease forecasting models that neglect change of behavior during disease outbreaks, and to potential opportunities in local interventions.

Collaborators and References

I am grateful to the invaluable support and help from Keith Paarporn, Joshua Weitz and Jeff Shamma in this thread. Below is a selected list of papers on this topic.

  1. C. Eksin, J.S. Shamma, J.S. Weitz, Disease Dynamics on a Network Game: a Little Empathy Goes a Long Way, Nature Scientific Reports, (to appear), February 2017.
  2. J.S. Weitz, C. Eksin, K. Paarporn, S.P. Brown and W.C. Ratcliff, An oscillating tragedy of the commons in replicator dynamics with game-environment feedback, Proceedings of the National Academy of the Sciences USA, vol. 113, no. 47, November 2016.
  3. K. Paarporn, C. Eksin, J.S. Weitz, J.S. Shamma, Networked SIS Epidemics with Awareness, (submitted), July 2016.
  4. K. Paarporn, C. Eksin, J. S. Weitz, and J. S. Shamma, Epidemic Spread Over Networks with Agent Awareness and Social Distancing, In Proc. 53rd Annual Allerton Conference on Communication, Control, and Computing, pp. 51-57, October 2015.

Other interests - Distributed Network Optimization

Herding behavior: Snapshots of herd network structure at times t=0, t = 15, t = 30 and t=45 corresponding to (a)-(d), respectively. Food source is bold circled. Filled circles are color coded to identify each individual animal. Agents move toward food source while trying to even out inter-individual attraction and repulsion forces.

Network optimization problems entail a group of agents with certain underlying connectivity that strive to minimize a global cost through appropriate selection of local variables. Optimal determination of local variables requires, in principle, global coordination of all agents. In distributed network optimization, agent coordination is further restricted to neighboring nodes. The optimization of the global objective is then achieved through iterative application of local optimization rules that update local variables based on information about the state of neighboring agents. Distributed network optimization is a common solution method for estimation and detection problems in wireless sensor networks (WSNs).

My goal in this project is to analyze emerging global behavior when agents are optimal in an average sense only. The expected optimality of an agent may stand for his resort to heuristic behavior, noisy communication with his neighbors or simply his lack of aptness to carry out the optimal action precisely. We define an agent's aspiration to minimize his local cost function but failing to do it precisely as the heuristic rational behavior.

Collaborators and References

This project is done under the supervision of Alejandro Ribeiro. Below is the journal paper on this topic.

  1. C. Eksin and A. Ribeiro, Distributed Network Optimization with Heuristic Rational Agents, IEEE Trans. Signal Process., vol. 60, no. 10, pp. 5396-5411, October 2012.
Page last modified on February 21, 2017, at 03:27 PM