Program – Speakers

Speakers | Itinerary

Plenary Speakers

Randomized Methods in Game Theory with Applications to Network Security

João Hespanha
ECE, University of California, Santa Barbara

Abstract
This talk addresses the solution of large zero-sum matrix games using randomized methods. We formalize a procedure -- termed the Sampled Security Policy (SSP) algorithm -- by which a player can compute policies that, with high probability, guarantees a certain level of performance against an adversary engaged in a random exploration of the game's decision tree. The SSP Algorithm has applications to numerous combinatorial games in which decision makers are faced with a number of possible options that increases exponentially with the size of the problem. In this talk we focus on an applications in the area of network security, where system administrators need to consider multi-stage, multi-host attacks that may consist of long sequences of actions by an attacker in their attempt to circumvent the system defenses. In practice, this leads to policy spaces that grow exponentially with the number of stages involved in an attack.

U.S. Incentive Auction for Repurposing of Electromagnetic Spectrum: A Case Study in Algorithmic Market Design

Ilya Segal
Economics, Stanford University

Abstract
The “Incentive Auction” conducted by the US Federal Communications Commission in 2016–17 reassigned fourteen UHF TV channels to wireless Internet services, generating over $19 billion in revenues, out of which more than $10 billion was paid to TV broadcasters who relinquished their spectrum rights. The auction process respected millions of radio interference constraints and overcame interacting economic and computational challenges. Even though the auction algorithm had to solve hundreds of NP-hard “graph coloring” problems in each round, from bidders’ viewpoint it was a simple clock auction, in which spectrum sellers faced descending prices and spectrum buyers faced ascending prices, and each participant could exit any time its price is adjusted and is no longer acceptable. For single-minded bidders (e.g., individual TV station owners), the auction was obviously strategy-proof, (weakly) group strategy-proof, and preserved the privacy of winning bidders. Due to complementarities among bidders, associated computational challenges, and the need to at least break even, the auction could not guarantee an economically efficient allocation, and used heuristic price adjustment rules instead of explicit optimization. However, simulations on real-life constraints show that the auction provides a good approximation of efficiency if there are limited complementarities and sufficient competition among substitutable bidders.

Invited Speakers

Risk-Sensitive and Robust Mean Field Games

Tamer Başar
ECE, University of Illinois at Urbana–Champaign

Abstract
Mean field games (MFGs) constitute a class of non-cooperative stochastic differential games, where there is a large number of players or agents who interact with each other through a mean field coupling term—also known as the mass behavior or the macroscopic behavior in statistical physics—included in the individual cost functions and/or each agent’s dynamics generated by a controlled stochastic differential equation, capturing the average behavior of all agents. One of the main research issues in MFGs with no hierarchy in decision making is to study (existence, uniqueness and characterization of) Nash equilibria with an infinite population of players under specified information structures and further to study finite-population approximations, that is to explore to what extent an infinite-population Nash equilibrium provides an approximate Nash equilibrium for the finite-population game, and what the relationship is between the level of approximation and the size of the population. Following a general overview of such games, the talk will dwell on two classes of MFGs: those characterized by risk sensitive (that is, exponentiated) objective functions (known as risk-sensitive MFGs) and those that have risk-neutral (RN) objective functions but with an additional adversarial driving term in the dynamics (known as robust MFGs). In stochastic optimal control, it is known that risk-sensitive (RS) cost functions lead to a behavior akin to robustness, leading to establishment of a connection between RS control problems and RN minimax ones. The talk will explore to what extent a similar connection holds between RS MFGs and robust MFGs, particularly in the context of linear-quadratic problems, which will allow for closed-form solutions and explicit comparisons between the two in both infinite- and finite-population regimes and with respect to the approximation of Nash equilibria in going from the former to the latter.
(This is based mostly on joint work with Jun Moon)

The Sharing Economics of Wireless Spectrum

Randal Berry
ECE, Northwestern University

Abstract
The combination of the rising demands for wireless data and the lack of vacant spectrum to support these demands has led to a shift in focus from exclusively licensing spectrum to a single entity to sharing spectrum among multiple entities. The various entities sharing a band of spectrum may in turn compete with each other for customers. This is further complicated due to the congestible nature of the shared spectrum. In this talk we will discuss several game theoretic models for studying how different policies for sharing spectrum may impact the resulting market outcomes.
This talk is based on joint work with M. Honig, T. Nguyen, C. Liu, V. Subramanian, R. Vohra and H. Zhou.

Vision-based Target Tracking Games: New Horizons and Future Challenges

Sourabh Bhattacharya
ME, Iowa State University

Abstract
In the last decade, there has been a widespread deployment of autonomous vehicles for visual surveillance in civilian as well as military applications. In this talk, I will present some new results in target tracking using a team of autonomous agents. In the first part of the talk, I will present a game-theoretic perspective to the problem of target tracking by casting it as a pursuit-evasion game. For a single observer and target, I will present some new necessary and sufficient conditions for tracking using the framework of optimal control theory. In the second part of the talk, I will present deployment, tracking and coordination strategies for multiple observers with guaranteed tracking performance by drawing a connection between multi-robot tracking and multi-robot coverage. The relevant tools are based on ideas from computational geometry, hybrid systems and convex optimization. I will conclude my talk with some future directions and challenges in multi-robot target-tracking.

Simple Mechanisms

Tilman Borgers
Economics, University of Michigan

Abstract
We consider mechanism design under the constraint that the mechanism be "simple." We review some possible definitions of the concept of "simplicity," and then focus on one particular form of strategic simplicity: we define a mechanism to be "simple" if optimal strategy choices can be based on first order beliefs alone, and there is no need for agents to form higher order beliefs because such beliefs are irrelevant to agents' optimal choices. In mechanisms "first order beliefs" are beliefs about other agents' rationality and their utility. "Higher order beliefs" are beliefs about beliefs, beliefs about beliefs about beliefs, etc. In many mechanisms agents who want to make an optimal choice cannot avoid having to form higher order beliefs. But in some mechanisms there is no need for this. These are the mechanisms that we investigate and characterize in this paper. All dominant strategy mechanism are simple. But many more mechanisms are simple. In particular, simple mechanisms may be more flexible than dominant strategy mechanisms in examples such as the bilateral trade problem and the voting problem.

Tie-line Scheduling in Electric Power Systems under Uncertainty: A Multi-Parametric Linear Programming Approach

Subhonmesh Bose
ECE, University of Illinois at Urbana–Champaign

Abstract
Each system operator (SO) controls the grid assets over the power network within its own geographical footprint (area). Multiple SOs coordinate to schedule the power flows over the tie-lines interconnecting such areas. In this work, we seek a tie-line schedule that minimizes the maximum aggregate cost of balancing demand and supply in real-time across multiple areas. It adds to the growing literature on multi-area optimal power flow under uncertainty — a paradigm for coordination motivated by the deepening penetration of renewable resources like wind and solar energy. We consider an approach based on multi-parametric linear programming, and develop an algorithm that requires limited communication between a coordinator and the SOs to reach the optimal robust tie-line schedule. We illustrate the efficacy of our approach empirically.

Avoiding Cascading Failures for Time-of-Use Pricing

Shuchi Chawla
CS, University of Wisconsin

Abstract
For commodities of a temporal nature, such as electricity and computing resources on a cloud platform, demand and supply fluctuate stochastically over time, and time-of-use pricing is an effective way to balance supply and demand. For a single time period in isolation, determining the right price to set is a newsvendor type problem. The optimal solution is to set the price in a way that the system is slightly over provisioned. We study settings where demand can be temporally flexible: when prices are high, consumers with temporally-flexible workloads can move their demand to a lower price period. This movement of demand complicates the relationship between the advertised prices and observed demand. In particular, it is no longer clear that optimizing the price for each individual time period suffices to ensure good system performance. Indeed, excess demand from one time period can move over to another period and cause an overload, which can in turn cause an overload at another time period, and so on. How much should the system be over provisioned in each time period so as to ensure that the loss of efficiency is small? Under what conditions can we guarantee that overload cascades of the sort described above are unlikely? In this work we develop techniques for answering these questions. Our main result is that in a large market setting, i.e. where the total supply in any time period far exceeds any single customer's demand, slightly over provisioning each time period is sufficient to achieve high system efficiency -- overload cascades of the sort described above are few and short lived.

Development of a Game Theoretic Traffic Simulation Environment for Autonomous Vehicle Testing

Anouck Girard
AERO, University of Michigan

Abstract
Significant efforts are being put into the developments of automated driving algorithms, aiming at making self-driving cars a viable option for everyday transportation. Automated cars operate in a traffic environment, interacting with other cars, pedestrians and road infrastructure. To validate the robustness of an automated driving algorithm and calibrate its parameters, hundreds of thousands of miles of driving tests are required to cover an abundance of traffic scenarios. Traffic simulators can facilitate the initial control calibrations before actual road tests and reduce the time and effort needed for the overall algorithm testing. In this talk, we will describe a simulator based on a game theoretic traffic modeling approach. This simulator is based on hierarchical reasoning theory and level-k games.

Persistence and Stability of Traffic Flow in Large Scale Transportation Networks

Vijay Gupta
ECE, University of Notre Dame

Abstract
Fluid-like models, such as the Lighthill- Whitham-Richards (LWR) model and their discretizations like Daganzo’s Cell Transmission Model (CTM), have proven successful in modeling traffic networks. In general, these models are not linear; they employ discontinuous dynamics or nonlinear terms to describe phenomena like shock waves and phantom jams. Given the complexity of the dynamics, it is not surprising that the stability properties of these models are not yet well characterized. Recent results have shown the existence of a unique equilibrium in the free flow regime for certain classes of networks modeled by the CTM; however, these results restrict inflows to the system to be bounded or constant. Further, it is of interest to understand the system behavior in congested regimes, since links in various practical networks are often congested. In this talk, we consider traffic flow on a network modeled by the CTM. We show that the trajectories of the system are persistent in every mode of the system and that if the inflows are constant, the system admits multiple congested equilibria. We then draw upon entropy-like Lyapunov functions used in chemical reaction network theory to show that these equilibria are locally asymptotically stable. With further restrictions on system inflows, these equilibria degenerate to the free flow equilibrium in existing results. In the final part of the talk, we motivate compositional design approaches to mitigate congestion in large-scale transportation networks by describing a design that uses only local information to limit the propagation of congestion in the network.
This work has been done jointly with Sivaranjani Seetharaman.

Analysis and Control of Nonlinear Stochastic Systems via Linear Optimal Control with Semidefinite Constraints

Andy Lamperski
ECE, University of Minnesota

Abstract
Stochastic dynamic systems model phenomena such as chemical reactions, stock prices, and mechanical systems with noise. Important statistical information can be computed from the moments. For example, the mean of a random variable is the first moment, the variance is computed from the first two moments. For many nonlinear stochastic systems, the moments can be described by a system of linear differential equations. A challenge arises when equations of any one moment depend on higher order moments. In this case, we say that the moments are not closed and an infinite number of equations is required. Existing methods mitigate this problem by approximating the higher moments probabilistically, but the true value of the desired moment remains unknown.

This talk will present an alternative approach based on optimal control. Rather than approximating the higher order moments, we treat them as control inputs. The control problem is deterministic and linear, but requires semidefinite constraints. By maximizing and minimizing a moment of interest we obtain upper and lower bounds on its true value. Increasing the size of the control problem leads to a sequence of bounds that converges to the true moment of interest. The methodology for stochastic analysis extends with minimal modification to nonlinear stochastic optimal control problems. The resulting linear optimal control problem gives bounds on the achievable performance of nonlinear controllers. A method to extract nonlinear controllers for the original system will be described. The main ideas will be explained for stochastic differential equations defined by polynomials. Extensions to jump processes and non-polynomial systems will be sketched. We will briefly present applications in chemical physics, power systems, and fishery management.
This is joint work with Khem Raj Ghusinga and Abhyudai Singh at the University of Delaware.

Robust Control for the Analysis and Design of Large-Scale Optimization Algorithms

Laurent Lessard
ECE, University of Wisconsin

Abstract
Most complicated optimization problems, in particular those involving a large number of variables, are solved in practice using iterative algorithms. The problem of selecting a suitable algorithm is currently more of an art than a science; a great deal of expertise is required to know which algorithms to try and how to properly tune them. Moreover, there are seldom performance guarantees. In this talk, I will show how the problem of algorithm selection can be approached using tools from robust control theory. By solving simple semidefinite programs, we can derive robust bounds on convergence rates for popular algorithms such as the gradient method, proximal methods, fast/accelerated methods, and operator-splitting methods such as ADMM. The bounds derived in this manner either match or improve upon the best known bounds from the literature. Finally, our framework can be used to search for algorithms that meet desired performance specifications, thus establishing a new and principled methodology for designing new algorithms.

The Dilemma of the Cypress and the Oak Tree

David Rahman
Economics, University of Minnesota

Abstract
I study repeated games with mediated communication and frequent actions. I derive folk theorems with imperfect public and private monitoring under minimal detectability assumptions. Even in the limit, when noise is driven by Brownian motion and actions are arbitrarily frequent, as long as players are sufficiently patient they can attain virtually efficient equilibrium outcomes, in two ways: secret monitoring and infrequent coordination. Players follow private strategies over discrete blocks of time. A mediator constructs latent Brownian motions to score players on the basis of others' secret monitoring, and gives incentives with these variables at the end of each block to economize on the cost of providing incentives. This brings together the work on repeated games in discrete and continuous time in that, despite actions being continuous, strategic coordination is endogenously discrete. As an application, I show how individual full rank is necessary and sufficient for the folk theorem in the Prisoners' Dilemma regardless of whether monitoring is public or private.

Privacy-Preserving Market Design

Marzena Rostek
Economics, University of Wisconsin

Abstract
Preserving privacy is a common concern in auctions and exchanges. To examine the role of privacy in markets, we formulate a class of mechanism design problems based on the uniform-price market clearing to study the joint design of (i) transparency of auction outcomes (observables); (ii) bid schedules (contingent variables); and (iii) pre-trade communication. Our approach complements that based on differential privacy (Dwork (2006)) in that it suits settings in which design objectives, such as efficiency or revenue, demand that the outcomes of market participants respond strongly to their incentives. We say that a design preserves privacy if the publicly observable outcome (e.g., price, quantities, bids) is not informative about the participants' private information. We show that in some trading environments, this privacy requirement is necessary for equilibrium existence. Designs that do not preserve privacy can increase welfare if traders participate in the market for sufficiently many rounds. Under conditions, dynamic privacy-preserving designs can be efficient.
This is joint work with Mariann Ollar and Ji Hee Yoon.

Latency-Optimal Coding Control and Scheduling for Clouds and Wireless Networks

Ness Shroff
ECE, Ohio State University

Abstract
We are in the midst of a major data revolution. The total data generated by humans from the dawn of civilization until the turn of the new millennium is now being generated every two days. Driven by a wide range of data-intensive devices and applications, this growth is expected to continue its astonishing march, and fuel the development of new and larger data centers. In order to exploit the low-cost services offered by these resource-rich data centers, application developers are pushing computing and storage away from the end-devices and instead deeper into the data-centers. Hence, the end-users’ experience is now dependent on the performance of the algorithms used for data retrieval within the data-centers. In particular, providing low-latency services is critically important to the end-user experience for a wide variety of applications. Our goal has been to develop the analytical foundations and methodologies to enable cloud computing and storage solutions that result in low-latency services. A variety of cloud based and wireless systems can be modeled using multi-server, multi queue queueing systems with data locality constraints. In these systems, replication (or most sophisticated coding schemes) can be used to not only improve reliability but to also reduce latency. However, delay optimality for multi-server queueing systems has been a long-standing open problem, with limited results usually in asymptotic regimes. The key question is can we design resource allocation schemes that are near optimal in distribution for minimizing several different classes of delay metrics that are important in web and cloud based services? In this talk, I will overview some of our recent research efforts at solving this problem, provide some key design principles, and outline a set of what I believe are important open problems.

The Stochastic Multi-Armed Bandit Problem: In Neuroscience, Ecology, and Engineering

Vaibhav Srivatsava
ECE, Michigan State University

Abstract
In the stochastic multi-armed bandit problem, the objective is to optimize accumulated reward over a sequence of choices, which creates a tension between choosing the most rewarding among known options (exploitation) and choosing poorly known but potentially more rewarding options (exploration). I will discuss results from multi-armed bandit experiments with human participants and features of human decision-making captured by a model that relies on Bayesian inference, confidence bounds, and Boltzmann action selection. I will discuss how multi-armed bandit framework bridges macroscopic and microscopic foraging models in ecology. Finally, I will discuss some results on distributed cooperative decision-making in multi-player multi-armed bandit problems.

Design of Player’s Strategies in Pursuit-Evasion Games based on Approximations of Minimum and Maximum Functions

Dušan Stipanović
IE, University of Illinois at Urbana–Champaign

Abstract
In this talk, convergent and differentiable approximations of minimum and maximum functions will be used for deriving explicit strategies for players in pursuit-evasion games when their dynamic models are affine in strategies. Furthermore, Lyapunov-like conditions will be provided for either guaranteed capture or guaranteed evasion for some particular scenarios with multiple non-homogeneous players.

Fragility of the Commons: The Game-Theoretic Impacts of Human Decision-Making on Robustness of Shared Systems

Shreyas Sundaram
ECE, Purdue University

Abstract
The robustness of systems depends critically on the decisions made by the humans who use those systems. Game-theoretic analysis of such settings has traditionally relied on the framework of expected utility theory, with utility functions chosen to model classical notions of risk aversion. However, studies in behavioral psychology and economics have shown that humans consistently deviate from such classical models of behavior. In this talk, we consider the game-theoretic implications of behavioral deviations (captured by Prospect Theory) on the utilization of shared failure-prone systems. We consider a setting where a group of individuals utilize a shared resource; the resource fails with a probability that increases with the amount of utilization, and provides a certain return otherwise. We show that utilization increases as the players deviate from risk neutrality, and that societies with heterogeneous aversions to loss will utilize the resource more than societies with homogeneous aversions to loss. We then consider the use of a taxation policy to mitigate overutilization of the resource, and demonstrate that counter-intuitive outcomes can arise under behavioral decision-making.
Based on joint work with Ashish Hota.

A Common Information Approach to Stochastic Dynamic Games with Asymmetric Information

Demos Teneketzis
ECE, University of Michigan

Abstract
We consider a class of stochastic dynamic games with asymmetric information. In these games, conditioned on the players’ actions, the underlying system has Markovian dynamics. At each time instant the players have some common information and, in addition, each player has private information about the game’s evolution. We use the players’ common information to discover an information state that has a time-invariant domain, and define a common information based (CIB) assessment, consisting of CIB strategies and CIB beliefs, along with appropriate notions of CIB equilibria such as CIB Perfect Bayesian Equilibria ( CIB-PBE ). Based on the above information state we provide a sequential decomposition of the games; this decomposition leads to an algorithm for the determination of CIB-PBE. We prove, in certain instances, the existence of CIB-PBE.

Superlinearly Convergent Asynchronous Distributed Network Newton Method

Ermin Wei
EECS, Northwestern University

Abstract
The problem of minimizing a sum of local convex objective functions over a networked system captures many important applications and has received much attention in the distributed optimization field. Most of existing work focuses on development of fast distributed algorithms under the presence of a central clock. The only known algorithms with convergence guarantees for this setup in asynchronous setup could achieve either sublinear rate under totally asynchronous setting or linear rate under partially asynchronous setting (with bounded delay). In this work, we built upon existing literature to develop and analyze an asynchronous Newton based approach for solving a penalized version of the problem. We show that this algorithm converges almost surely and has superlinear rate in expectation. Numerical studies confirm superior performance against other existing asynchronous methods.