Search

We focus on the problem of uncertainty informed allocation of medical resources (vaccines) to heterogeneous populations for managing epidemic spread. We tackle two related questions: (1) For a compartmental ordinary differential equation (ODE) model of epidemic spread, how can we estimate and integrate parameter uncertainty into resource allocation decisions? (2) How can we computationally handle both nonlinear ODE constraints and parameter uncertainties for a generic stochastic optimization problem for resource allocation? To the best of our knowledge current literature does not fully resolve these questions. Here, we develop a data-driven approach to represent parameter uncertainty accurately and tractably in a novel stochastic optimization problem formulation. We first generate a tractable scenario set by estimating the distribution on ODE model parameters using Bayesian inference with Gaussian processes. Next, we develop a parallelized solution algorithm that accounts for scenario-dependent nonlinear ODE constraints. Our scenario-set generation procedure and solution approach are flexible in that they can handle any compartmental epidemiological ODE model. Our computational experiments on two different non-linear ODE models (SEIR and SEPIHR) indicate that accounting for uncertainty in key epidemiological parameters can improve the efficacy of time-critical allocation decisions by 4-8%. This improvement can be attributed to data-driven and optimal (strategic) nature of vaccine allocations, especially in the early stages of the epidemic when the allocation strategy can crucially impact the long-term trajectory of the disease.

The world faces some of its greatest challenges of modern time and how we address them will have a dramatic impact on the life for generations to come. Simultaneously, control systems, consisting of information enriched by various degrees of analytics followed by decision-making, are pervading a variety of sectors, not only in engineering but beyond, into financial services, socio-economic analysis, entertainment and sports, and political and social sciences. Increased levels of automation are sought after in various sectors and being introduced into new domains. All of these advances and transformations urge a shift in the conversation toward how control systems can meet grand societal- scale challenges. The document seeks to chart a roadmap for the evolution of control systems, identifying several areas where our discipline can have an impact over the next decade.

In this paper, we study both multi-armed and contextual bandit problems in censored environments. Our goal is to estimate the performance loss due to censorship in the context of classical algorithms designed for uncensored environments. Our main contributions include the introduction of a broad class of censorship models and their analysis in terms of the effective dimension of the problem -- a natural measure of its underlying statistical complexity and main driver of the regret bound. In particular, the effective dimension allows us to maintain the structure of the original problem at first order, while embedding it in a bigger space, and thus naturally leads to results analogous to uncensored settings. Our analysis involves a continuous generalization of the Elliptical Potential Inequality, which we believe is of independent interest. We also discover an interesting property of decision-making under censorship: a transient phase during which initial misspecification of censorship is self-corrected at an extra cost, followed by a stationary phase that reflects the inherent slowdown of learning governed by the effective dimension. Our results are useful for applications of sequential decision-making models where the feedback received depends on strategic uncertainty (e.g., agents' willingness to follow a recommendation) and/or random uncertainty (e.g., loss or delay in arrival of information)., 45 pages, 5 figures, NeurIPS 2022

We study a market mechanism that sets edge prices to incentivize strategic agents to organize trips that efficiently share limited network capacity. This market allows agents to form groups to share trips, make decisions on departure times and route choices, and make payments to cover edge prices and other costs. We develop a new approach to analyze the existence and computation of market equilibrium, building on theories of combinatorial auctions and dynamic network flows. Our approach tackles the challenges in market equilibrium characterization arising from: (a) integer and network constraints on the dynamic flow of trips in sharing limited edge capacity; (b) heterogeneous and private preferences of strategic agents. We provide sufficient conditions on the network topology and agents' preferences that ensure the existence and polynomial-time computation of market equilibrium. We identify a particular market equilibrium that achieves maximum utilities for all agents, and is equivalent to the outcome of the classical Vickery Clark Grove mechanism. Finally, we extend our results to general networks with multiple populations and apply them to compute dynamic tolls for efficient carpooling in San Francisco Bay Area.

We consider a strategic network monitoring problem involving the operator of a networked system and an attacker. The operator aims to randomize the placement of multiple protected sensors to monitor and protect components that are vulnerable to attacks. We account for the heterogeneity in the components' security levels and formulate a large-scale maximin optimization problem. After analyzing its structure, we propose a three-step approach to approximately solve the problem. First, we solve a generalized covering set problem and run a combinatorial algorithm to compute an approximate solution. Then, we compute approximation bounds by solving a nonlinear set packing problem. To evaluate our solution approach, we implement two classical solution methods based on column generation and multiplicative weights updates, and test them on real-world water distribution and power systems. Our numerical analysis shows that our solution method outperforms the classical methods on large-scale networks, as it efficiently generates solutions that achieve a close to optimal performance and that are simple to implement in practice.

The transition to a deeply decarbonized energy system requires coordinated planning of infrastructure investments and operations serving multiple end-uses while considering technology and policy-enabled interactions across sectors. Electricity and natural gas (NG), which are vital vectors of today's energy system, are likely to be coupled in different ways in the future, resulting from increasing electrification, adoption of variable renewable energy (VRE) generation in the power sector and policy factors such as cross-sectoral emissions trading. This paper develops a least-cost investment and operations model for joint planning of electricity and NG infrastructures that considers a wide range of available and emerging technology options across the two vectors, including carbon capture and storage (CCS) equipped power generation, low-carbon drop-in fuels (LCDF) as well as long-duration energy storage (LDES). The model incorporates the main operational constraints of both systems and allows each system to operate under different temporal resolutions consistent with their typical scheduling timescales. We apply the modeling framework to evaluate power-NG system outcomes for the U.S. New England region under different technology, decarbonization goals, and demand scenarios. Under a global emissions constraint, ranging between 80-95\% emissions reduction compared to 1990 levels, the least-cost solution disproportionately relies on using the available emissions budget to serve non-power NG demand and results in the power sector using only 15-43\% of the emissions budget.

We consider the security-by-design of a signal-free intersection for connected and autonomous vehicles in the face of strategic jamming attacks. We use a fluid model to characterize macroscopic traffic flow through the intersection, where the saturation rate is derived from a vehicle coordination algorithm. We model jamming attacks as sudden increase in communication latency induced on vehicle-to-infrastructure connectivity; such latency triggers the safety mode for vehicle coordination and thus reduces the intersection saturation rate. A strategic attacker selects the attacking rate, while a system operator selects key design parameters, either the saturation rate or the recovery rate. Both players' actions induce technological costs and jointly determine the mean travel delay. By analyzing the equilibrium of the security game, we study the preferable level of investment in the intersection's nominal discharging capability or recovery capability., Comment: Accepted by 2022 IEEE Conference on Decision and Control(CDC)

We study the problem of information provision by a strategic central planner who can publicly signal about an uncertain infectious risk parameter. Signalling leads to an updated public belief over the parameter, and agents then make equilibrium choices on whether to work remotely or in-person. The planner maintains a set of desirable outcomes for each realization of the uncertain parameter and seeks to maximize the probability that agents choose an acceptable outcome for the true parameter. We distinguish between stateless and stateful objectives. In the former, the set of desirable outcomes does not change as a function of the risk parameter, whereas in the latter it does. For stateless objectives, we reduce the problem to maximizing the probability of inducing mean beliefs that lie in intervals computable from the set of desirable outcomes. We derive the optimal signalling mechanism and show that it partitions the parameter domain into at most two intervals with the signals generated according to an interval-specific distribution. For the stateful case, we consider a practically relevant situation in which the planner can enforce in-person work capacity limits that progressively get more stringent as the risk parameter increases. We show that the optimal signalling mechanism for this case can be obtained by solving a linear program. We numerically verify the improvement in achieving desirable outcomes using our information design relative to no information and full information benchmarks.

This paper introduces a "green" routing game between multiple logistic operators (players), each owning a mixed fleet of internal combustion engine vehicle (ICEV) and electric vehicle (EV) trucks. Each player faces the cost of delayed delivery (due to charging requirements of EVs) and a pollution cost levied on the ICEVs. This cost structure models: 1) limited battery capacity of EVs and their charging requirement; 2) shared nature of charging facilities; 3) pollution cost levied by regulatory agency on the use of ICEVs. We characterize Nash equilibria of this game and derive a condition for its uniqueness. We also use the gradient projection method to compute this equilibrium in a distributed manner. Our equilibrium analysis is useful to analyze the trade-off faced by players in incurring higher delay due to congestion at charging locations when the share of EVs increases versus a higher pollution cost when the share of ICEVs increases. A numerical example suggests that to increase marginal pollution cost can dramatically reduce inefficiency of equilibria., 8 pages

A rapid transformation of current electric power and natural gas (NG) infrastructure is imperative to meet the mid-century goal of CO2 emissions reduction requires. This necessitates a long-term planning of the joint power-NG system under representative demand and supply patterns, operational constraints, and policy considerations. Our work is motivated by the computational and practical challenges associated with solving the generation and transmission expansion problem (GTEP) for joint planning of power-NG systems. Specifically, we focus on efficiently extracting a set of representative days from power and NG data in respective networks and using this set to reduce the computational burden required to solve the GTEP. We propose a Graph Autoencoder for Multiple time resolution Energy Systems (GAMES) to capture the spatio-temporal demand patterns in interdependent networks and account for differences in the temporal resolution of available data. The resulting embeddings are used in a clustering algorithm to select representative days. We evaluate the effectiveness of our approach in solving a GTEP formulation calibrated for the joint power-NG system in New England. This formulation accounts for the physical interdependencies between power and NG systems, including the joint emissions constraint. Our results show that the set of representative days obtained from GAMES not only allows us to tractably solve the GTEP formulation, but also achieves a lower cost of implementing the joint planning decisions.

We propose a learning dynamics to model how strategic agents repeatedly play a continuous game while relying on an information platform to learn an unknown payoff-relevant parameter. In each time step, the platform updates a belief estimate of the parameter based on players' strategies and realized payoffs using Bayes's rule. Then, players adopt a generic learning rule to adjust their strategies based on the updated belief. We present results on the convergence of beliefs and strategies and the properties of convergent fixed points of the dynamics. We obtain sufficient and necessary conditions for the existence of globally stable fixed points. We also provide sufficient conditions for the local stability of fixed points. These results provide an approach to analyzing the long-term outcomes that arise from the interplay between Bayesian belief learning and strategy learning in games, and enable us to characterize conditions under which learning leads to a complete information equilibrium., Comment: arXiv admin note: substantial text overlap with arXiv:2109.00719

Aerial images provide important situational awareness for responding to natural disasters such as hurricanes. They are well-suited for providing information for damage estimation and localization (DEL); i.e., characterizing the type and spatial extent of damage following a disaster. Despite recent advances in sensing and unmanned aerial systems technology, much of post-disaster aerial imagery is still taken by handheld DSLR cameras from small, manned, fixed-wing aircraft. However, these handheld cameras lack IMU information, and images are taken opportunistically post-event by operators. As such, DEL from such imagery is still a highly manual and time-consuming process. We propose an approach to both detect damage in aerial images and localize it in world coordinates, with specific focus on detecting and localizing flooding. The approach is based on using structure from motion to relate image coordinates to world coordinates via a projective transformation, using class activation mapping to detect the extent of damage in an image, and applying the projective transformation to localize damage in world coordinates. We evaluate the performance of our approach on post-event data from the 2016 Louisiana floods, and find that our approach achieves a precision of 88%. Given this high precision using limited data, we argue that this approach is currently viable for fast and effective DEL from handheld aerial imagery for disaster response., Version presented at NeurIPS 2021 AI+HADR workshop

This paper presents a modeling approach for probabilistic estimation of hurricane wind-induced damage to infrastructural assets. In our approach, we employ a Nonhomogeneous Poisson Process (NHPP) model for estimating spatially-varying probability distributions of damage as a function of hurricane wind field velocities. Specifically, we consider a physically-based, quadratic NHPP model for failures of overhead assets in electricity distribution systems. The wind field velocities are provided by Forecasts of Hurricanes using Large-Ensemble Outputs (FHLO), a framework for generating probabilistic hurricane forecasts. We use FHLO in conjunction with the NHPP model, such that the hurricane forecast uncertainties represented by FHLO are accounted for in estimating the probability distributions of damage. Furthermore, we evaluate the spatial variability and extent of hurricane damage under key wind field parameters (intensity, size, and asymmetries). By applying our approach to prediction of power outages (loss-of-service) in northwestern Florida due to Hurricane Michael (2018), we demonstrate a statistically significant relationship between outage rate and failure rate. Finally, we formulate parametric models that relate total damage and financial losses to the hurricane parameters of intensity and size. Overall, this paper's findings suggest that our approach is well-suited to jointly account for spatial variability and forecast uncertainty in the damage estimates, and is readily applicable to prediction of system loss-of-service due to the damage., Submitted to Risk Analysis, 21 pages (main text), 17 figures, includes appendix

In this paper, we address the existence and computation of competitive equilibrium in the transportation market for autonomous carpooling first proposed by [Ostrovsky and Schwarz, 2019]. At equilibrium, the market organizes carpooled trips over a transportation network in a socially optimal manner and sets the corresponding payments for individual riders and toll prices on edges. The market outcome ensures individual rationality, stability of carpooled trips, budget balance, and market clearing properties under heterogeneous rider preferences. We show that the question of market's existence can be resolved by proving the existence of an integer optimal solution of a linear programming problem. We characterize conditions on the network topology and riders' disutility for carpooling under which a market equilibrium can be computed in polynomial time. This characterization relies on ideas from the theory of combinatorial auctions and minimum cost network flow problem. Finally, we characterize a market equilibrium that achieves strategyproofness and maximizes welfare of individual riders.

We study learning dynamics induced by strategic agents who repeatedly play a game with an unknown payoff-relevant parameter. In this dynamics, a belief estimate of the parameter is repeatedly updated given players' strategies and realized payoffs using Bayes's rule. Players adjust their strategies by accounting for best response strategies given the belief. We show that, with probability 1, beliefs and strategies converge to a fixed point, where the belief consistently estimates the payoff distribution for the strategy, and the strategy is an equilibrium corresponding to the belief. However, learning may not always identify the unknown parameter because the belief estimate relies on the game outcomes that are endogenously generated by players' strategies. We obtain sufficient and necessary conditions, under which learning leads to a globally stable fixed point that is a complete information Nash equilibrium. We also provide sufficient conditions that guarantee local stability of fixed point beliefs and strategies., Comment: arXiv admin note: text overlap with arXiv:2010.09128

Highway capacity is often subject to stochastic perturbations due to the combined effects of weather, traffic mixture, driver behavior, etc. This paper is motivated by the need of a systematic approach to traffic control with performance guarantees in the face of such perturbations. We develop a novel control-theoretic method for designing perturbation-resilient ramp metering. We consider a cell-transmission model with 1) Markovian cell capacities and 2) buffers representing on-ramps and upstream mainline. Using this model, we analyze the stability of on-ramp queues by constructing piecewise Lyapunov functions that consider the nature of nonlinear traffic dynamics. Then, we design ramp controllers that guarantee bounds for throughput and queue sizes. We also formulate the problem of coordinated ramp metering as a bi-level optimization with non-convex inner sub-problems. To address the computational issue in solving this problem, we also consider localized and partially coordinated reformulations. A case study of a 18.1-km highway in Los Angeles, USA indicates a 8.3\% (resp. 9.9\%) reduction of vehicle-hours-traveled obtained by the localized (resp. partially coordinated) control, both outperforming the classical ALINEA and METALINE controllers.

Error-Correcting Output Codes (ECOCs) offer a principled approach for combining simple binary classifiers into multiclass classifiers. In this paper, we investigate the problem of designing optimal ECOCs to achieve both nominal and adversarial accuracy using Support Vector Machines (SVMs) and binary deep learning models. In contrast to previous literature, we present an Integer Programming (IP) formulation to design minimal codebooks with desirable error correcting properties. Our work leverages the advances in IP solvers to generate codebooks with optimality guarantees. To achieve tractability, we exploit the underlying graph-theoretic structure of the constraint set in our IP formulation. This enables us to use edge clique covers to substantially reduce the constraint set. Our codebooks achieve a high nominal accuracy relative to standard codebooks (e.g., one-vs-all, one-vs-one, and dense/sparse codes). We also estimate the adversarial accuracy of our ECOC-based classifiers in a white-box setting. Our IP-generated codebooks provide non-trivial robustness to adversarial perturbations even without any adversarial training.

We study learning dynamics induced by strategic agents who repeatedly play a game with an unknown payoff-relevant parameter. In each step, an information system estimates a belief distribution of the parameter based on the players' strategies and realized payoffs using Bayes' rule. Players adjust their strategies by accounting for an equilibrium strategy or a best response strategy based on the updated belief. We prove that beliefs and strategies converge to a fixed point with probability 1. We also provide conditions that guarantee local and global stability of fixed points. Any fixed point belief consistently estimates the payoff distribution given the fixed point strategy profile. However, convergence to a complete information Nash equilibrium is not always guaranteed. We provide a sufficient and necessary condition under which fixed point belief recovers the unknown parameter. We also provide a sufficient condition for convergence to complete information equilibrium even when parameter learning is incomplete.

Vehicle platooning is a promising technology that can lead to significant fuel savings and emission reduction. However, the macroscopic impact of vehicle platoons on highway traffic is not yet well understood. In this article, we propose a new fluid queuing model to study the macroscopic interaction between randomly arriving vehicle platoons and the background traffic at highway bottlenecks. This model, viewed as a stochastic switched system, is analyzed for two practically relevant priority rules: proportional (or mixed) and segmented priority. We provide intuitive stability conditions, and obtain bounds on the long-run average length and variance of queues for both priority rules. We use these results to study how platoon-induced congestion varies with the fraction of platooned vehicles, and their characteristics such as intra-platoon spacing and arrival rate. Our analysis reveals a basic tradeoff between congestion induced by the randomness of platoon arrivals, and efficiency gain due to a tighter intra-platoon spacing. This naturally leads to conditions under which the proportional priority is preferred over segmented priority. Somewhat surprisingly, our analytical results are in agreement with the simulation results based on a more sophisticated two-class cell transmission model., National Science Foundation (U.S.) (CAREER Award CNS-1453126), National Science Foundation (U.S.) (CNS-1239054), Singapore. National Research Foundation, Horizon 2020 Framework Programme (European Commission) (Marie Sklodowska-Curie Grant 674875), VINNOVA (Contract 2014- 06200), Swedish Research Council, Knut and Alice Wallenberg Foundation, Swedish Foundation for Strategic Research

The tandem fluid queueing model is a useful tool for performance analysis and control design for a variety of transportation systems. In this article, we study the joint impact of stochastic capacity and spillback on the long-time properties of this model. Our analysis focuses on the system of two fluid queueing links in series. The upstream link has a constant capacity (saturation rate) and an infinite buffer size. The downstream link has a stochastic capacity and a finite buffer size. Queue spillback occurs when the the downstream link is full. We derive a necessary condition and a sufficient condition for the total queue length to be bounded on average. The necessary (resp. sufficient) condition leads to an upper (resp. lower) bound for the throughput of the two-link system. Using our results, we analyze the sensitivity of throughput of the two-link system with respect to the frequency and intensity of capacity disruptions, and to the buffer size. In addition, we discuss how our analysis can be extended to feedback-controlled systems and to networks consisting of merges and splits.

Traffic Management Centers (TMCs) routinely use traffic cameras to provide situational awareness regarding traffic, road, and weather conditions. Camera footage is quite useful for a variety of diagnostic purposes; yet, most footage is kept for only a few days, if at all. This is largely due to the fact that currently, identification of notable footage is done via manual review by human operators---a laborious and inefficient process. In this article, we propose a semantics-oriented approach to analyzing sequential image data, and demonstrate its application for automatic detection of real-world, anomalous events in weather and traffic conditions. Our approach constructs semantic vector representations of image contents from textual labels which can be easily obtained from off-the-shelf, pretrained image labeling software. These semantic label vectors are used to construct semantic topic signals---time series representations of physical processes---using the Latent Dirichlet Allocation (LDA) topic model. By detecting anomalies in the topic signals, we identify notable footage corresponding to winter storms and anomalous traffic congestion. In validation against real-world events, anomaly detection using semantic topic signals significantly outperforms detection using any individual label signal.

In this paper, we study the problem of traffic management in highways facing stochastic perturbations. To model the macroscopic traffic flow under perturbations, we use cell-transmission model with Markovian capacities. The decision variables are: (i) the admissible flow through each on-ramp, and (ii) whether individual on-ramps are metered to prioritize the mainline traffic or not. The objective is to maximize the throughput while ensuring that on-ramp queues remain bounded on average. We develop a computational approach to solving this stability-constrained, throughput-maximization problem. We establish a mixed-integer linear program for throughput maximization and construct an algorithm that gives the optimal solution in particular settings. We illustrate the performance benefits of the proposed approach through a computational study on a segment of Interstate 210 in California, USA., 27 pages

Electricity distribution networks (DNs) in many regions are increasingly subjected to disruptions caused by tropical storms. Distributed Energy Resources (DERs) can act as temporary supply sources to sustain "microgrids" resulting from disruptions. In this paper, we investigate the problem of suitable DER allocation to facilitate more efficient repair operations and faster recovery. First, we estimate the failure probabilities of DN components (lines) using a stochastic model of line failures which parametrically depends on the location-specific storm wind field. Next, we formulate a two-stage stochastic mixed integer program, which models the distribution utility's decision to allocate DERs in the DN (pre-storm stage); and accounts for multi-period decisions on optimal dispatch and line repair scheduling (post-storm stage). A key feature of this formulation is that it jointly optimizes electricity dispatch within the individual microgrids and the line repair schedules to minimize the sum of the cost of DER allocation and cost due to lost load. To illustrate our approach, we use the sample average approximation method to solve our problem for a small-size DN under different storm intensities and DER/crew constraints., Comment: 7 pages, 4 figures, accepted to 2018 IEEE SmartGridComm Conference

In this brief paper we find computable exponential convergence rates for a large class of stochastically ordered Markov processes. We extend the result of Lund, Meyn, and Tweedie (1996), who found exponential convergence rates for stochastically ordered Markov processes starting from a fixed initial state, by allowing for a random initial condition that is also stochastically ordered. Our bounds are formulated in terms of moment-generating functions of hitting times. To illustrate our result, we find an explicit exponential convergence rate for an M/M/1 queue beginning in equilibrium and then experiencing a change in its arrival or departure rates, a setting which has not been studied to our knowledge., Comment: 13 pages

Advances in microgrids powered by Distributed Energy Resources (DERs) make them an attractive response capability for improving the resilience of electricity distribution networks (DNs). This paper presents an approach to evaluate the value of implementing a timely response using microgrid operations and DER dispatch in the aftermath of a disruption event, involving strategic compromise of multiple DN components. Firstly, we extend the resiliency assessment framework in [1] and develop a sequential (bilevel) model of attacker-operator interactions on a radial DN with one or more microgrids. Particularly, the operator response includes microgrid operations under various islanding configurations (regimes), and single- or multi-master operation of DERs in providing grid-forming services as well as frequency and voltage regulation. Secondly, we introduce a restoration problem in which the operator gradually reconnects the disrupted components over multiple periods to restore the nominal performance of the DN. The first problem, formulated as a bilevel mixed-integer problem, is solved using a Benders decomposition method. The second problem, formulated as a multi-period mixed-integer problem, can be solved using a greedy algorithm. Our results illustrate the benefit of using microgrids in reducing the operator's losses, both immediately after the disruption event and during the restoration process.

In this paper, we develop a novel mechanism for reducing volatility of residential demand for electricity. We construct a reward-based (rebate) mechanism that provides consumers with incentives to shift their demand to off-peak time. In contrast to most other mechanisms proposed in the literature, the key feature of our mechanism is its modest requirements on user preferences, i.e., it does not require exact knowledge of user responsiveness to rewards for shifting their demand from the peak to the off-peak time. Specifically, our mechanism utilizes a probabilistic reward structure for users who shift their demand to the off-peak time, and is robust to incomplete information about user demand and/or risk preferences. We approach the problem from the public good perspective, and demonstrate that the mechanism can be implemented via lottery-like schemes. Our mechanism permits to reduce the distribution losses, and thus improve efficiency of electricity distribution. Finally, the mechanism can be readily incorporated into the emerging demand response schemes (e.g., the time-of-day pricing, and critical peak pricing schemes), and has security and privacy-preserving properties., National Science Foundation (U.S.) (Grant CNS-1239166), National Science Foundation (U.S.) (Grant CNS-0910711), National Science Foundation (U.S.) (CCF-0424422)

This article studies the value of information in route choice decisions when a fraction of players have access to high accuracy information about traffic incidents relative to others. To model such environments, we introduce a Bayesian congestion game, in which players have private information about incidents, and each player chooses her route on a network of parallel links. The links are prone to incidents that occur with an ex-ante known probability. The demand is comprised of two player populations: one with access to high accuracy incident information and another with low accuracy information, i.e. the populations differ only by their access to information. The common knowledge includes: (i) the demand and route cost functions, (ii) the fraction of highly-informed players, (iii) the incident probability, and (iv) the marginal type distributions induced by the information structure of the game. We present a full characterization of the Bayesian Wardrop Equilibrium of this game under the assumption that low information players receive no additional information beyond common knowledge. We also compute the cost to individual players and the social cost as a function of the fraction of highly-informed players when they receive perfectly accurate information. Our first result suggests that below a certain threshold of highly-informed players, both populations experience a reduction in individual cost, with the highly-informed players receiving a greater reduction. However, above this threshold, both populations realize the same equilibrium cost. Secondly, there exists another (lower or equal) threshold above which a further increase in the fraction of highly-informed players does not reduce the expected social costs. Thus, once a sufficiently large number of players are highly informed, wider distribution of more accurate information is ineffective at best, and otherwise socially harmful.

This note introduces a piecewise-deterministic queueing (PDQ) model to study the stability of traffic queues in parallel-link transportation systems facing stochastic capacity fluctuations. The saturation rate (capacity) of the PDQ model switches between a finite set of modes according to a Markov chain, and link inflows are controlled by a state-feedback policy. A PDQ system is stable only if a lower bound on the time-average link inflows does not exceed the corresponding time-average saturation rate. Furthermore, a PDQ system is stable if the following two conditions hold: the nominal mode's saturation rate is high enough that all queues vanish in this mode, and a bilinear matrix inequality (BMI) involving an underestimate of the discharge rates of the PDQ in individual modes is feasible. The stability conditions can be strengthened for two-mode PDQs. These results can be used for design of routing policies that guarantee stability of traffic queues under stochastic capacity fluctuations., Comment: 20 pages, 3 figures

This article introduces a model for freeway traffic dynamics under stochastic capacity-reducing incidents, and provides insights for freeway incident management by analyzing long-time (stability) properties of the proposed model. Incidents on a multi-cell freeway are modeled by reduction in capacity at the affected freeway sections, which occur and clear according to a Markov chain. We develop conditions under which the traffic queue induced by stochastic incidents is bounded. A necessary condition is that the demand must not exceed the time-average capacity adjusted for spillback. A sufficient condition, in the form of a set of bilinear inequalities, is also established by constructing a Lyapunov function and applying the classical Foster-Lyapunov drift condition. Both conditions can be easily verified for realistic instances of the stochastic incident model. Our analysis relies on the construction of a globally attracting invariant set, and exploits the properties of the traffic flow dynamics. We use our results to analyze the impact of stochastic capacity fluctuation (frequency, intensity, and spatial correlation) on the throughput of a freeway segment.

This article considers a two-player strategic game for network routing under link disruptions. Player 1 (defender) routes flow through a network to maximize her value of effective flow while facing transportation costs. Player 2 (attacker) simultaneously disrupts one or more links to maximize her value of lost flow but also faces cost of disrupting links. Linear programming duality in zero-sum games and the Max-Flow Min-Cut Theorem are applied to obtain properties that are satisfied in any Nash equilibrium. A characterization of the support of the equilibrium strategies is provided using graph-theoretic arguments. Finally, conditions under which these results extend to budget-constrained environments are also studied. These results extend the classical minimum cost maximum flow problem and the minimum cut problem to a class of security games on flow networks., Comment: The results in this paper only hold under a restrictive assumption on the class of networks (Assumption 1 in page 7). This makes the results inapplicable in practice, and further work is needed

The smart grid refers to the modernization of the power grid infrastructure with new technologies, enabling a more intelligently networked automated system with the goal of improving efficiency, reliability, and security, while providing more transparency and choices to electricity customers. A key technology being widely deployed on the consumption side of the grid is advanced metering infrastructure (AMI)., National Science Foundation (U.S.) (Award CNS-1239054)

We propose a raffle-based scheme for the decongestion of a shared resource. Our scheme builds on ideas from the economic literature on incentivizing contributions to a public good. We formulate a game-theoretic model for the decongestion problem in a setup with a finite number of users, as well as in a setup with an infinite number of non-atomic users. We analyze both setups, and show that the former converges toward the latter when the number of users becomes large. We compare our results to existing results for the public good provision problem. Overall, our results establish that raffle-based schemes are useful in addressing congestion problems., National Science Foundation (U.S.) (Grant CNS-0910711), National Science Foundation (U.S.) (Grant CCF-0424422), United States. Air Force Office of Scientific Research (FA9550-06-1-0244)

International audience

The instrumentation of infrastructure systems by embedded sensors, computation, and communication networks has enabled significant advances in their management. Examples include monitoring of structural health, traffic congestion, environmental hazards, and energy usage. The use of homogeneous (especially, commercially available off-the-shelf) information technology (IT) solutions makes infrastructure systems subject to correlated hardware malfunctions and software bugs. Over the past decade, many concerns have been raised about the vulnerabilities of infrastructure systems to both random failures and security attacks. Cyber-security of Supervisory Control and Data Acquisition (SCADA) systems is especially important, because these systems are employed for sensing and control of large physical infrastructures. So far, the existing research in robust and fault-tolerant control does not account for cyber attacks on networked control system (NCS) components. Also, the existing research in computer security neither considers the attacks targeting NCS components nor accounts for their interactions with the physical system. The goal of this thesis is to bridge this gap by focusing on (1) security threat assessment, (2) model-based attack diagnosis, and (3) resilient control design. First, cyber-security assessment for SCADA systems is performed based on well-defined attacker and defender objectives. The mathematical model of SCADA systems considered in this work has two control levels: regulatory control using distributed proportional-integral (PI) controllers, and supervisory fault diagnosis based on approximate dynamical system models. The performance of a PI control based regulatory scheme and a model-based supervisory diagnostic scheme is studied under a class of deception attacks. In order to test the system resilience, a class of stealthy attacks which can evade detection by SCADA systems is presented. Second, design of attack diagnosis schemes that incorporate the knowledge of physical dynamics of the system is presented. For SCADA systems used to manage water canal networks, an observer-based attack diagnostic scheme, in which each observer estimates the state of a reduced-order flow model, is presented. The observer parameters are computed using a convex optimization method, and the performance of this scheme is tested on a number of attack scenarios. An application of the theoretical results is illustrated by a field operational test performed on the SCADA system of the Gignac water canal system, located in Montpellier, France. A successful experimental cyber-attack on the sensors and actuators of this canal network revealed new vulnerabilities of the current SCADA system implementation. Another illustration includes security analysis of two benchmark scenarios: the Tennessee Eastman process control system (TE-PCS) and a power system state estimator (PSSE). In both these cases, model-based statistical detection schemes are used to study stealthy deception attacks. For the case of TE-PCS, design of practically implementable attack-detection and response mechanisms to maintain operational safety is presented. For the case of PSSE, it is assumed that the attacker only has a partial knowledge of the actual system model. For a set of attacker objectives, the trade-off between the attacker knowledge and possible impact of a successful attack on the performance of false data detection schemes is studied. Third, the stability of linear hyperbolic systems of PDEs when the boundary control actions and the system parameters switch discontinuously between a finite set of modes is studied. Switched PDE models can describe a class of fault and attack scenarios resulting from intermittent withdrawals through offtake nodes and compromise of sensor-control data. Motivated by such scenarios, a new condition for stability of linear hyperbolic systems of PDEs under arbitrary switching of boundary control actions and system parameters is derived. A class of switching attack strategies is presented, which violate the stability condition and result in unstable flow dynamics.Fourth, the problem of controlling stochastic linear systems for networked control settings is considered when the sensor-control data is prone to packet loss and jamming. For a class of packet drop models, feedback control policies which minimize a given objective function subject to safety constraints are synthesized. For marginally stable systems, under mild hypotheses on the noise introduced by the control channel and large enough control authority, the synthesis of a control policy that render the state of the closed-loop system mean-square bounded is presented.Finally, a class of games involving discrete interdependent risks is considered when each player is a NCS, and their security is interdependent due to the exposure to network induced risks. The problem of security decisions of individual players is formulated as a two-stage non-cooperative game defined as follows: in the first stage, the players decide whether to invest in security or not; and in the second stage, they apply control inputs to minimize the average operational costs. The characterization of the equilibria of the game is presented, which includes the determination of the individually optimal security levels. The presence of interdependent security causes a negative externality, and the individual players tend to under invest in security relative to the social optimum. From these results, for a wide parameter range, public policy incentivising higher security investments is desirable.

Infrastructure inspection and maintenance decision making is a stochastic and partially observable problem. This thesis presents a learning and decision-making approach for developing optimal joint inspection and maintenance policies for civil infrastructure facilities under performance model uncertainty and partially observable condition state. Joint inspection and maintenance decision making refers to the cost-effective policies that capture the interactions between the inspections, and the maintenance and rehabilitation decisions. Performance model uncertainty is the uncertainty about the actual facility deterioration model. Partially observation condition states imply that the true or latent condition of the facility is not captured by the measurement technology used for inspecting the facility due to measurement errors. The proposed approach models single facility inspection and maintenance decision-making problem as a partially observable Markov decision process. The data collected during the agency-facility interaction is used to learn the maximum likelihood estimate of performance model using the Baum-Welch algorithm. Both offline and online versions of the learning algorithm are presented. The probing-optimizing dichotomy, also known as exploration-exploitation dilemma, in choosing between the best strategy based on the past knowledge of deterioration and the strategy that provides information leading to better performance model is also illustrated. Once a set of performance models is learned, each of the models is quantitatively compared with the corresponding true model using an information theoretic measure known as asymmetric Kullback-Leibler divergence to determine its goodness. It is also shown that given a set of new observation sequences gathered after the model learning, each of the sequences or the entire set of sequences can be assigned the model that gives the least log-likelihood on that sequence or the set. This can help in classifying the facility deterioration into different deterioration modes like slow, medium, or fast. Finally, an exact algorithm for arriving at optimal inspection and maintenance decision-making policies is described. It is argued that the proposed approach scores over other recently developed adaptive control approaches in that it directly learns the best model from historical data instead of maintaining and updating beliefs over a set of pre-selected models. Furthermore, since the proposed learning approach is model-based, it makes more efficient use of costly data as compared to the model-less learning approaches. Keywords: Infrastructure Inspection and Maintenance, Baum-Welch Algorithm, Kullback-Liebler Divergence, Sequence Classification, Partially Observable Markov Decision Process, Reinforcement Learning.

IEEE This article introduces a Piecewise-Deterministic Queueing (PDQ) model to study the stability of traffic queues in parallel-link transportation systems facing stochastic capacity fluctuations. The saturation rate (capacity) of the PDQ model switches between a finite set of modes according to a Markov chain, and link inflows are controlled by a state-feedback policy. A PDQ system is stable only if a lower bound on the time-average link inflows does not exceed the corresponding time-average saturation rate. Furthermore, a PDQ system is stable if the following two conditions hold: the nominal mode's saturation rate is high enough that all queues vanish in this mode, and a Bilinear Matrix Inequality (BMI) involving an underestimate of the discharge rates of the PDQ in individual modes is feasible. The stability conditions can be strengthened for two-mode PDQs. These results can be used for design of routing policies that guarantee stability of traffic queues under stochastic capacity fluctuations., National Science Foundation (U.S.) (CNS-1239054 CPS Frontiers), National Science Foundation (U.S.). Faculty Early Career Development Program Award (CNS-145312), United States. Air Force Research Laboratory. Lablet-Secure and Resilient Cyber-Physical Systems

Infrastructure systems are increasingly facing new security threats due to the vulnerabilities of cyber-physical components that support their operation. In this article, we investigate how the infrastructure operator (defender) should prioritize the investment in securing a set of facilities in order to reduce the impact of a strategic adversary (attacker) who can target a facility to increase the overall usage cost of the system. We adopt a game-theoretic approach to model the defender-attacker interaction and study two models: normal-form game -- where both players move simultaneously; and sequential game -- where attacker moves after observing the defender's strategy. For each model, we provide a complete characterization of how the set of facilities that are secured by the defender in equilibrium vary with the costs of attack and defense. Importantly, our analysis provides a sharp condition relating the cost parameters for which the defender has the first mover advantage. Specifically, we show that to fully deter the attacker from targeting any facility, the defender needs to proactively secure all "vulnerable facilities" at an appropriate level of effort. We illustrate the outcome of the attacker-defender interaction on a simple transportation network. We also suggest a dynamic learning setup to understand how this outcome can affect the ability of imperfectly informed users to make their decisions about using the system in the post-attack stage.

Mobile data traffic has been steadily rising in the past years. This has generated a significant interest in the deployment of incentive mechanisms to reduce peak-time congestion. Typically, the design of these mechanisms requires information about user demand and sensitivity to prices. Such information is naturally imperfect. In this paper, we propose a fixed-budget rebate mechanism that gives each user a reward proportional to his percentage contribution to the aggregate reduction in peak-time demand. For comparison, we also study a time-of-day pricing mechanism that gives each user a fixed reward per unit reduction of his peak-time demand. To evaluate the two mechanisms, we introduce a game-theoretic model that captures the public good nature of decongestion. For each mechanism, we demonstrate that the socially optimal level of decongestion is achievable for a specific choice of the mechanism's parameter. We then investigate how imperfect information about user demand affects the mechanisms' effectiveness. From our results, the fixed-budget rebate pricing is more robust when the users' sensitivity to congestion is “sufficiently” convex. This feature of the fixed-budget rebate mechanism is attractive for many situations of interest and is driven by its closed-loop property, i.e., the unit reward decreases as the peak-time demand decreases., National Science Foundation (U.S.) (Grant CNS-1239166), National Science Foundation (U.S.) (Grant CNS-0910711), National Science Foundation (U.S.) (CCF-0424422), United States. Air Force Office of Scientific Research (FA9550-06-1-0244)

This paper focuses on the security assessment of electricity distribution networks (DNs) with vulnerable distributed energy resource (DER) nodes. The adversary model is a simultaneous compromise of DER nodes by strategic manipulation of generation setpoints. The loss to the defender (DN operator) includes loss of voltage regulation and cost of induced load control under supply-demand mismatch caused by the attack. A three-stage defender-attacker-defender (DAD) game is formulated: in Stage 1, the defender chooses a security strategy to secure a subset of DER nodes; in Stage 2, the attacker compromises a set of vulnerable DERs and injects false generation setpoints; in Stage 3, the defender responds by controlling loads and non-compromised DERs. Solving this trilevel optimization problem is hard due to nonlinear power flows and mixed-integer decision variables. To address this challenge, the problem is approximated by a tractable formulation based on an ε-linear power-flow model. The set of critical DER nodes and the setpoint manipulations characterizing the optimal attack strategy are computed. An iterative greedy approach to computing attacker-defender strategies for the original nonlinear problem is proposed. These results provide guidelines for optimal security investment and defender response in preattack and postattack conditions, respectively., National Science Foundation (U.S.) (Award CNS-1238959), National Science Foundation (U.S.) (Award CNS-1238962), National Science Foundation (U.S.) (Award CNS- 1239054), National Science Foundation (U.S.) (Award CNS-1239166), Sandia National Laboratories, United States. Air Force. Research Laboratory (Award FA8750-14-2-0180)

Traffic signals were originally standalone hardware devices running on fixed schedules, but by now, they have evolved into complex networked systems. As a consequence, traffic signals have become susceptible to attacks through wireless interfaces or even remote attacks through the Internet. Indeed, recent studies have shown that many traffic lights deployed in practice have easily exploitable vulnerabilities, which allow an attacker to tamper with the configuration of the signal. Due to hardware-based failsafes, these vulnerabilities cannot be used to cause accidents. However, they may be used to cause disastrous traffic congestions. Building on Daganzo's well- known traffic model, we introduce an approach for evaluating vulnerabilities of transportation networks, identifying traffic signals that have the greatest impact on congestion and which, therefore, make natural targets for attacks. While we prove that finding an attack that maximally impacts congestion is NP-hard, we also exhibit a polynomial-time heuristic algorithm for computing approximately optimal attacks. We then use numerical experiments to show that our algorithm is extremely efficient in practice. Finally, we also evaluate our approach using the SUMO traffic simulator with a real-world transportation network, demonstrating vulnerabilities of this network. These simulation results extend the numerical experiments by showing that our algorithm is extremely efficient in a microsimulation model as well., National Science Foundation (U.S.) (Award CNS-1238959), National Science Foundation (U.S.) (Award CNS-1238962), National Science Foundation (U.S.) (Award CNS- 1239054), National Science Foundation (U.S.) (Award CNS-1239166), United States. Air Force. Research Laboratory (Award FA8750-14-2-0180), Sandia National Laboratories

This paper focuses on the optimal sensor placement problem for the identification of pipe failure locations in large-scale urban water systems. The problem involves selecting the minimum number of sensors such that every pipe failure can be uniquely localized. This problem can be viewed as a minimum test cover (MTC) problem, which is NP-hard. We consider two approaches to obtain approximate solutions to this problem. In the first approach, we transform the MTC problem to a minimum set cover (MSC) problem and use the greedy algorithm that exploits the submodularity property of the MSC problem to compute the solution to the MTC problem. In the second approach, we develop a new augmented greedy algorithm for solving the MTC problem. This approach does not require the transformation of the MTC to MSC. Our augmented greedy algorithm provides in a significant computational improvement while guaranteeing the same approximation ratio as the first approach. We propose several metrics to evaluate the performance of the sensor placement designs. Finally, we present detailed computational experiments for a number of real water distribution networks. Keywords: Fault identification; Minimum test cover; Water networks

We consider the initial-boundary value problem governed by systems of linear hyperbolic partial differential equations in the canonical diagonal form and study conditions for exponential stability when the system discontinuously switches between a finite set of modes. The switching system is fairly general in that the system matrix functions as well as the boundary conditions may switch in time. We show how the stability mechanism developed for classical solutions of hyperbolic initial boundary value problems can be generalized to the case in which weaker solutions become necessary due to arbitrary switching. We also provide an explicit dwell-time bound for guaranteeing exponential stability of the switching system when, for each mode, the system is exponentially stable. Our stability conditions only depend on the system parameters and boundary data. These conditions easily generalize to switching systems in the nondiagonal form under a simple commutativity assumption. We present tutorial examples to illustrate the instabilities that can result from switching.

The Internet is plagued with congestion problems of growing severity which are worst at peak periods. In this paper, we compare two schemes that incentivize users to shift part of their usage from the peak-time to the off-peak time. The traditional time-of-day pricing scheme gives a fixed reward per unit of shifted usage. Conversely, the raffle-based scheme provides a random reward distributed in proportion of each user's fraction of the total shifted usage. Using a game-theoretic model, we show that both schemes can achieve an optimal level of decongestion at a unique Nash equilibrium. We provide a comparison of the schemes' sensitivity to uncertainty of the users' utilities., National Science Foundation (U.S.) (Grant CNS-0910711)