Search

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.

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

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.

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.

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.

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