Search

We consider the problem of promoting sustainability in production forests wherein a given number of strategic entities are authorized to own or manage concession regions. These entities harvest agricultural commodities and sell them in a market. We study optimal price-shaping in a coupled-activity network game model in which the concession owners (agents) engage in two activities: (a) the sustainable activity of producing a commodity that does not interfere with protected forest resources, and (b) the unsustainable activity of infringing into protected regions to expand their agricultural footprint. We characterize two types of policies in a budget-constrained setting: one that maximally suppresses the aggregate unsustainable activity and another that maximizes social welfare while constraining the aggregate unsustainable activity to remain below a predefined tolerance. Our analysis provides novel insights on the agents' equilibrium effort across the two activities and their influence on others due to intra- and cross-activity network effects. We also identify a measure of node centrality that resembles the Bonacich-Katz centrality and helps us determine pricing incentives that lead to welfare improvement while reducing the aggregate unsustainable activity.

Solving large-scale capacity expansion problems (CEPs) is central to cost-effective decarbonization of regional-scale energy systems. To ensure the intended outcomes of CEPs, modeling uncertainty due to weather-dependent variable renewable energy (VRE) supply and energy demand becomes crucially important. However, the resulting stochastic optimization models are often less computationally tractable than their deterministic counterparts. Here, we propose a learning-assisted approximate solution method to tractably solve two-stage stochastic CEPs. Our method identifies low-cost planning decisions by constructing and solving a sequence of tractable temporally aggregated surrogate problems. We adopt a Bayesian optimization approach to searching the space of time series aggregation hyperparameters and compute approximate solutions that minimize costs on a validation set of supply-demand projections. Importantly, we evaluate solved planning outcomes on a held-out set of test projections. We apply our approach to generation and transmission expansion planning for a joint power-gas system spanning New England. We show that our approach yields an estimated cost savings of up to 3.8% in comparison to benchmark time series aggregation approaches.

We study a planner's provision of information to manage workplace occupancy when strategic workers (agents) face risk of infectious disease transmission. The planner implements an information mechanism to signal information about the underlying risk of infection at the workplace. Agents update their belief over the risk parameter using this information and choose to work in-person or remotely. We address the design of the optimal signaling mechanism that best aligns the workplace occupancy with the planner's preference (i.e., maintaining safe capacity limits and operational efficiency at workplace). For various forms of planner preferences, we show numerical and analytical proof that interval-based information mechanisms are optimal. These mechanisms partition the continuous domain of the risk parameter into disjoint intervals and provision information based on interval-specific probability distributions over a finite set of signals. When the planner seeks to achieve an occupancy that lies in one of finitely many pre-specified ranges independent of the underlying risk, we provide an optimal mechanism that uses at most two intervals. On the other hand, when the preference on the occupancy is risk-dependent, we show that an approximately optimal interval-based mechanism can be computed efficiently. We bound the approximation loss for preferences that are expressed through a Lipschitz continuous function of both occupancy and risk parameter. We provide examples that demonstrate the improvement of proposed signaling mechanisms relative to the common benchmarks in information provision. Our findings suggest that information provision over the risk of disease transmission is an effective intervention for maintaining desirable occupancy levels at the workplace.

Building heat electrification is central to economy-wide decarbonization efforts and directly affects energy infrastructure planning through increasing electricity demand and reducing the building sector's use of gas infrastructure that also serves the power sector. Here, we develop a modeling framework to quantify end-use demand for electricity and gas in the buildings sector under various electrification pathways and evaluate their impact on co-optimized bulk power-gas infrastructure investments and operations under deep decarbonization scenarios. Applying the framework to study the U.S. New England region in 2050 across 20 weather scenarios, we find high electrification of the residential sector can increase sectoral peak and total electricity demands by up to 56-158% and 41-59% respectively relative to business-as-usual projections. Employing demand-side measures like building envelope improvements under high electrification, however, can reduce the magnitude and weather sensitivity of peak load as well as induce overall efficiency gains, reducing the combined residential sector energy demand for power and gas by 28-30% relative to the present day. Notably, a combination of high electrification and envelope improvements yields the lowest bulk power-gas system cost outcomes. We also find that inter-annual weather-driven variations in demand result in up to 33% variation in optimal power sector investments, which highlights the importance of capturing weather sensitivity of demand for planning purposes.

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

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.

Effective investment planning decisions are crucial to ensure cyber-physical infrastructures satisfy performance requirements over an extended time horizon. Computing these decisions often requires solving Capacity Expansion Problems (CEPs). In the context of regional-scale energy systems, these problems are prohibitively expensive to solve due to large network sizes, heterogeneous node characteristics, and a large number of operational periods. To maintain tractability, traditional approaches aggregate network nodes and/or select a set of representative time periods. Often, these reductions do not capture supply-demand variations that crucially impact CEP costs and constraints, leading to suboptimal decisions. Here, we propose a novel graph convolutional autoencoder approach for spatio-temporal aggregation of a generic CEP with heterogeneous nodes (CEPHN). Our architecture leverages graph pooling to identify nodes with similar characteristics and minimizes a multi-objective loss function. This loss function is tailored to induce desirable spatial and temporal aggregations with regard to tractability and optimality. In particular, the output of the graph pooling provides a spatial aggregation while clustering the low-dimensional encoded representations yields a temporal aggregation. We apply our approach to generation expansion planning of a coupled 88-node power and natural gas system in New England. The resulting aggregation leads to a simpler CEPHN with 6 nodes and a small set of representative days selected from one year. We evaluate aggregation outcomes over a range of hyperparameters governing the loss function and compare resulting upper bounds on the original problem with those obtained using benchmark methods. We show that our approach provides upper bounds that are 33% (resp. 10%) lower those than obtained from benchmark spatial (resp. temporal) aggregation approaches.

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)., Comment: 45 pages, 5 figures, NeurIPS 2022

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.

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

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)

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., Comment: 8 pages

Modal split prediction in transportation networks has the potential to support network operators in managing traffic congestion and improving transit service reliability. We focus on the problem of hourly prediction of the fraction of travelers choosing one mode of transportation over another using high-dimensional travel time data. We use logistic regression as base model and employ various regularization techniques for variable selection to prevent overfitting and resolve multicollinearity issues. Importantly, we interpret the prediction accuracy results with respect to the inherent variability of modal splits and travelers' aggregate responsiveness to changes in travel time. By visualizing model parameters, we conclude that the subset of segments found important for predictive accuracy changes from hour-to-hour and include segments that are topologically central and/or highly congested. We apply our approach to the San Francisco Bay Area freeway and rapid transit network and demonstrate superior prediction accuracy and interpretability of our method compared to pre-specified variable selection methods.

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., Comment: Version presented at NeurIPS 2021 AI+HADR workshop

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