Search

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.

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

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

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 myopic travelers who repeatedly play a routing game on a transportation network with an unknown state. The state impacts cost functions of one or more edges of the network. In each stage, travelers choose their routes according to Wardrop equilibrium based on public belief of the state. This belief is broadcast by an information system that observes the edge loads and realized costs on the used edges, and performs a Bayesian update to the prior stage's belief. We show that the sequence of public beliefs and edge load vectors generated by the repeated play converge almost surely. In any rest point, travelers have no incentive to deviate from the chosen routes and accurately learn the true costs on the used edges. However, the costs on edges that are not used may not be accurately learned. Thus, learning can be incomplete in that the edge load vectors at rest point and complete information equilibrium can be different. We present some conditions for complete learning and illustrate situations when such an outcome is not guaranteed.

We consider an attacker-operator game for monitoring a large-scale network that is comprised on components that differ in their criticality levels. In this zero-sum game, the operator seeks to position a limited number of sensors to monitor the network against an attacker who strategically targets a network component. The operator (resp. attacker) seeks to minimize (resp. maximize) the network loss. To study the properties of mixed-strategy Nash Equilibria of this game, we first study two simple instances: (i) When component sets monitored by individual sensor locations are mutually disjoint; (ii) When only a single sensor is positioned, but with possibly overlapping monitoring component sets. Our analysis reveals new insights on how criticality levels impact the players equilibrium strategies. Next, we extend a previously known approach to obtain an approximate Nash equilibrium for the general case of the game. This approach uses solutions to minimum set cover and maximum set packing problems to construct an approximate Nash equilibrium. Finally, we implement a column generation procedure to improve this solution and numerically evaluate the performance of our approach.

This article poses the following problem: Does there exist a probability distribution over subsets of a finite partially ordered set (poset), such that a set of constraints involving marginal probabilities of the poset's elements and maximal chains is satisfied? We present a combinatorial algorithm to positively resolve this question. The algorithm can be implemented in polynomial time in the special case where maximal chain probabilities are affine functions of their elements. This existence problem is relevant for the equilibrium characterization of a generic strategic interdiction game on a capacitated flow network. The game involves a routing entity that sends its flow through the network while facing path transportation costs, and an interdictor who simultaneously interdicts one or more edges while facing edge interdiction costs. Using our existence result on posets and strict complementary slackness in linear programming, we show that the Nash equilibria of this game can be fully described using primal and dual solutions of a minimum-cost circulation problem. Our analysis provides a new characterization of the critical components in the interdiction game. It also leads to a polynomial-time approach for equilibrium computation.

We study a routing game in an environment with multiple heterogeneous information systems and an uncertain state that affects edge costs of a congested network. Each information system sends a noisy signal about the state to its subscribed traveler population. Travelers make route choices based on their private beliefs about the state and other populations' signals. The question then arises, "How does the presence of asymmetric and incomplete information affect the travelers' equilibrium route choices and costs?'' We develop a systematic approach to characterize the equilibrium structure, and determine the effect of population sizes on the relative value of information (i.e. difference in expected traveler costs) between any two populations. This effect can be evaluated using a population-specific size threshold. One population enjoys a strictly positive value of information in comparison to the other if and only if its size is below the corresponding threshold. We also consider the situation when travelers may choose an information system based on its value, and characterize the set of equilibrium adoption rates delineating the sizes of subscribed traveler populations. The resulting routing strategies are such that all travelers face an identical expected cost and no traveler has the incentive to change her subscription.

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.

Vehicle-to-Infrastructure (V2I) communications are increasingly supporting highway operations such as electronic toll collection, carpooling, and vehicle platooning. In this paper we study the incentives of strategic misbehavior by individual vehicles who can exploit the security vulnerabilities in V2I communications and negatively impact the highway operations. We consider a V2I-enabled highway segment facing two classes of vehicles (agent populations), each with an authorized access to one server (subset of lanes). Vehicles are strategic in that they can misreport their class (type) to the system operator and get an unauthorized access to the server dedicated to the other class. This misbehavior causes additional congestion externality on the compliant vehicles, and thus, needs to be deterred. We focus on an environment where the operator is able to inspect the vehicles for misbehavior. The inspection is costly and successful detection incurs a fine on the misbehaving vehicle. We formulate a signaling game to study the strategic interaction between the vehicle classes and the operator. Our equilibrium analysis provides conditions on the cost parameters that govern the vehicles' incentive to misbehave or not. We also determine the operator's equilibrium inspection strategy.

This article studies a problem of strategic network inspection, in which a defender (agency) is tasked with detecting the presence of multiple attacks in the network. An inspection strategy entails monitoring the network components, possibly in a randomized manner, using a given number of detectors. We formulate the network inspection problem $(\mathcal{P})$ as a large-scale bilevel optimization problem, in which the defender seeks to determine an inspection strategy with minimum number of detectors that ensures a target expected detection rate under worst-case attacks. We show that optimal solutions of $(\mathcal{P})$ can be obtained from the equilibria of a large-scale zero-sum game. Our equilibrium analysis involves both game-theoretic and combinatorial arguments, and leads to a computationally tractable approach to solve $(\mathcal{P})$. Firstly, we construct an approximate solution by utilizing solutions of minimum set cover (MSC) and maximum set packing (MSP) problems, and evaluate its detection performance. In fact, this construction generalizes some of the known results in network security games. Secondly, we leverage properties of the optimal detection rate to iteratively refine our MSC/MSP-based solution through a column generation procedure. Computational results on benchmark water networks demonstrate the scalability, performance, and operational feasibility of our approach. The results indicate that utilities can achieve a high level of protection in large-scale networks by strategically positioning a small number of detectors.

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

This paper considers a 2-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. This game is strategically equivalent to a zero-sum game. Linear programming duality and the max-flow min-cut theorem are applied to obtain properties that are satisfied in any mixed Nash equilibrium. In any equilibrium, both players achieve identical payoffs. While the defender's expected transportation cost decreases in attacker's marginal value of lost flow, the attacker's expected cost of attack increases in defender's marginal value of effective flow. Interestingly, the expected amount of effective flow decreases in both these parameters. These results can be viewed as a generalization of the classical max-flow with minimum transportation cost problem to adversarial environments., Comment: 8 pages, 6 figures, Proceedings of the 53rd Annual Allerton Conference on Communication, Control, and Computing, Urbana, IL, October 2015

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 \emph{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 \emph{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., Comment: To appear in IEEE/ACM Transactions on Networking