Search

Self-interested behavior from individuals can collectively lead to poor societal outcomes. These outcomes can seemingly be improved through the actions of altruistic agents, which benefit other agents in the system. However, it is known in specific contexts that altruistic agents can actually induce worse outcomes compared to a fully selfish population -- a phenomenon we term altruistic perversity. This paper provides a holistic investigation into the necessary conditions that give rise to altruistic perversity. In particular, we study the class of two-strategy population games where one sub-population is altruistic and the other is selfish. We find that a population game can admit altruistic perversity only if the associated social welfare function is convex and the altruistic population is sufficiently large. Our results are a first step in establishing a connection between properties of nominal agent interactions and the potential impacts from altruistic behaviors.

Self-interested routing polices from individual users in a system can collectively lead to poor aggregate congestion in routing networks. The introduction of altruistic agents, whose goal is to benefit other agents in the system, can seemingly improve aggregate congestion. However, it is known in that in some network routing problems, altruistic agents can actually worsen congestion compared to that which would arise in the presence of a homogeneously selfish population. This paper provides a thorough investigation into the necessary conditions for altruists to be guaranteed to improve total congestion. In particular, we study the class of series-parallel non-atomic congestion games, where one sub-population is altruistic and the other is selfish. We find that a game is guaranteed to have improved congestion in the presence of altruistic agents (even if only a small part of the total population) compared to the homogeneously selfish version of the game, provided the network is symmetric, where all agents are given access to all paths in the network, and the series-parallel network for the game does not have sub-networks which emulate Braess's paradox -- a phenomenon we refer to as a Braess-resistant network. Our results appear to be the most complete characterization of when behavior that is designed to improve total congestion (which we refer to as altruism) is actually guaranteed to do so., Comment: 7 pages, 2 figures

In this study, we introduce a toll lane framework that optimizes the mixed flow of autonomous and high-occupancy vehicles on freeways, where human-driven and autonomous vehicles of varying commuter occupancy share a segment. Autonomous vehicles, with their ability to maintain shorter headways, boost traffic throughput. Our framework designates a toll lane for autonomous vehicles with high occupancy to use free of charge, while others pay a toll. We explore the lane choice equilibria when all vehicles minimize travel costs, and characterize the equilibria by ranking vehicles by their mobility enhancement potential, a concept we term the mobility degree. Through numerical examples, we demonstrate the framework's utility in addressing design challenges such as setting optimal tolls, determining occupancy thresholds, and designing lane policies, showing how it facilitates the integration of high-occupancy and autonomous vehicles. We also propose an algorithm for assigning rational tolls to decrease total commuter delay and examine the effects of toll non-compliance. Our findings suggest that self-interest-driven behavior mitigates moderate non-compliance impacts, highlighting the framework's resilience. This work presents a pioneering comprehensive analysis of a toll lane framework that emphasizes the coexistence of autonomous and high-occupancy vehicles, offering insights for traffic management improvements and the integration of autonomous vehicles into existing transportation infrastructures.

The discipline of game theory was introduced in the context of economics, and has been applied to study cyber attacker and defender behaviors. While adaptions have been made to accommodate features in the cyber domain, these studies are inherently limited by the root of game theory in economic systems where players (i.e., agents) may be selfish but not malicious. In this SoK, we systematize the major cybersecurity problems that have been studied with the game-theoretic approach, the assumptions that have been made, the models and solution concepts that have been proposed. The systematization leads to a characterization of the technical gaps that must be addressed in order to make game-theoretic cybersecurity models truly useful. We explore bridges to address them., Comment: 21 pages, Finished October 17th, 2023

Vehicle-to-Vehicle (V2V) communication is intended to improve road safety through distributed information sharing; however, this type of system faces a design challenge: it is difficult to predict and optimize how human agents will respond to the introduction of this information. Bayesian games are a standard approach for modeling such scenarios; in a Bayesian game, agents probabilistically adopt various types on the basis of a fixed, known distribution. Agents in such models ostensibly perform Bayesian inference, which may not be a reasonable cognitive demand for most humans. To complicate matters, the information provided to agents is often implicitly dependent on agent behavior, meaning that the distribution of agent types is a function of the behavior of agents (i.e., the type distribution is endogenous). In this paper, we study an existing model of V2V communication, but relax it along two dimensions: first, we pose a behavior model which does not require human agents to perform Bayesian inference; second, we pose an equilibrium model which avoids the challenging endogenous recursion. Surprisingly, we show that the simplified non-Bayesian behavior model yields the exact same equilibrium behavior as the original Bayesian model, which may lend credibility to Bayesian models. However, we also show that the original endogenous equilibrium model is strictly necessary to obtain certain informational paradoxes; these paradoxes do not appear in the simpler exogenous model. This suggests that standard Bayesian game models with fixed type distributions are not sufficient to express certain important phenomena., Comment: 8 pages, 2 figures

Can revealing one's competitive capabilities to an opponent offer strategic benefits? In this paper, we address this question in the context of General Lotto games, a class of two-player competitive resource allocation models. We consider an asymmetric information setting where the opponent is uncertain about the resource budget of the other player, and holds a prior belief on its value. We assume the other player, called the signaler, is able to send a noisy signal about its budget to the opponent. With its updated belief, the opponent then must decide to invest in costly resources that it will deploy against the signaler's resource budget in a General Lotto game. We derive the subgame perfect equilibrium to this extensive-form game. In particular, we identify necessary and sufficient conditions for which a signaling policy improves the signaler's resulting performance in comparison to the scenario where it does not send any signal. Moreover, we provide the optimal signaling policy when these conditions are met. Notably we find that for some scenarios, the signaler can effectively double its performance., Comment: 8 pages

The use of game theoretic methods for control in multiagent systems has been an important topic in recent research. Valid utility games in particular have been used to model real-world problems; such games have the convenient property that the value of any decision set which is a Nash equilibrium of the game is guaranteed to be within 1/2 of the value of the optimal decision set. However, an implicit assumption in this guarantee is that each agent is aware of the decisions of all other agents. In this work, we first describe how this guarantee degrades as agents are only aware of a subset of the decisions of other agents. We then show that this loss can be mitigated by restriction to a relevant subclass of games.

The theory of learning in games has extensively studied situations where agents respond dynamically to each other by optimizing a fixed utility function. However, in real situations, the strategic environment varies as a result of past agent choices. Unfortunately, the analysis techniques that enabled a rich characterization of the emergent behavior in static environment games fail to cope with dynamic environment games. To address this, we develop a general framework using probabilistic couplings to extend the analysis of static environment games to dynamic ones. Using this approach, we obtain sufficient conditions under which traditional characterizations of Nash equilibria with best response dynamics and stochastic stability with log-linear learning can be extended to dynamic environment games. As a case study, we pose a model of cyber threat intelligence sharing between firms and a simple dynamic game-theoretic model of social precautions in an epidemic, both of which feature dynamic environments. For both examples, we obtain conditions under which the emergent behavior is characterized in the dynamic game by performing the traditional analysis on a reference static environment game., Comment: arXiv admin note: text overlap with arXiv:2103.13475

The emerging technology of Vehicle-to-Vehicle (V2V) communication over vehicular ad hoc networks promises to improve road safety by allowing vehicles to autonomously warn each other of road hazards. However, research on other transportation information systems has shown that informing only a subset of drivers of road conditions may have a perverse effect of increasing congestion. In the context of a simple (yet novel) model of V2V hazard information sharing, we ask whether partial adoption of this technology can similarly lead to undesirable outcomes. In our model, drivers individually choose how recklessly to behave as a function of information received from other V2V-enabled cars, and the resulting aggregate behavior influences the likelihood of accidents (and thus the information propagated by the vehicular network). We fully characterize the game-theoretic equilibria of this model using our new equilibrium concept. Our model indicates that for a wide range of the parameter space, V2V information sharing surprisingly increases the equilibrium frequency of accidents relative to no V2V information sharing, and that it may increase equilibrium social cost as well., Comment: arXiv admin note: substantial text overlap with arXiv:2207.05846

The emerging technology of Vehicle-to-Vehicle (V2V) communication over vehicular ad hoc networks promises to improve road safety by allowing vehicles to autonomously warn each other of road hazards. However, research on other transportation information systems has shown that informing only a subset of drivers of road conditions may have a perverse effect of increasing congestion. In the context of a simple (yet novel) model of V2V hazard information sharing, we ask whether partial adoption of this technology can similarly lead to undesirable outcomes. In our model, drivers individually choose how recklessly to behave as a function of information received from other V2V-enabled cars, and the resulting aggregate behavior influences the likelihood of accidents (and thus the information propagated by the vehicular network). We fully characterize the game-theoretic equilibria of this model. Our model indicates that for a wide range of our parameter space, V2V information sharing surprisingly increases the equilibrium frequency of accidents relative to no V2V information sharing, and that it may increase equilibrium social cost as well., Comment: Presented at 2022 American Control Conference

Recent research in the social sciences has identified situations in which small changes in the way that information is provided to consumers can have large aggregate effects on behavior. This has been promoted in popular media in areas of public health and wellness, but its application to other areas has not been broadly studied. This paper presents a simple model which expresses the effect of providing commuters with carefully-curated information regarding aggregate traffic "slowdowns" on the various roads in a transportation network. Much of the work on providing information to commuters focuses specifically on travel-time information. However, the model in the present paper allows a system planner to provide slowdown information as well; that is, commuters are additionally told how much slower each route is as compared to its uncongested state. We show that providing this additional information can improve equilibrium routing efficiency when compared to the case when commuters are only given information about travel time, but that these improvements in congestion are not universal. That is, transportation networks exist on which any provision of slowdown information can harm equilibrium congestion. In addition, this paper illuminates a deep connection between the effects of commuter slowdown-sensitivity and the study of marginal-cost pricing and altruism in congestion games.

A stochastic method is described for estimating Green's functions (GF's), appropriate to linear advection-diffusion-reaction transport problems, evolving in arbitrary geometries. By allowing straightforward construction of approximate, though high-accuracy GF's, within any geometry, the technique solves the central challenge in obtaining Green's function solutions. In contrast to Monte Carlo solutions of individual transport problems, subject to specific sets of conditions and forcing, the proposed technique produces approximate GF's that can be used: a) to obtain (infinite) sets of solutions, subject to any combination of (random and deterministic) boundary, initial, and internal forcing, b) as high fidelity direct models in inverse problems, and c) as high quality process models in thermal and mass transport design, optimization, and process control problems., Comment: 47 pages, 8 figures

When users lack specific knowledge of various system parameters, their uncertainty may lead them to make undesirable deviations in their decision making. To alleviate this, an informed system operator may elect to signal information to uninformed users with the hope of persuading them to take more preferable actions. In this work, we study public and truthful signalling mechanisms in the context of Bayesian congestion games on parallel networks. We provide bounds on the possible benefit a signalling policy can provide with and without the concurrent use of monetary incentives. We find that though revealing information can reduce system cost in some settings, it can also be detrimental and cause worse performance than not signalling at all. However, by utilizing both signalling and incentive mechanisms, the system operator can guarantee that revealing information does not worsen performance while offering similar opportunities for improvement. These findings emerge from the closed form bounds we derive on the benefit a signalling policy can provide. We provide a numerical example which illustrates the phenomenon that revealing more information can degrade performance when incentives are not used and improves performance when incentives are used.

The Philos Marketplace blockchain system is a proposed hierarchical blockchain architecture which allows a large number of individual blockchains to operate in parallel. These parallel chains achieve consensus among one another on a limited set of core operations, while allowing each on-chain application to manage its own data independently of others. This architecture addresses the scalability issues of traditional linear blockchains, but requires novel consensus mechanisms. A central feature of the Philos consensus mechanism is its trust algorithm, which assigns each network node a numerical trust value (or score) indicating the quality of recent past performance. This trust value is then used to determine a node's voting weight at the higher levels of consensus. In this paper, we formally define the Philos trust algorithm, and provide several illustrations of its operation, both theoretically and empirically. We also ask whether a misbehaving node can strategically exploit the algorithm for its personal gain, and show that this type of exploitation can be universally prevented simply by enforcing a mild limit on the number of participants in each of the parallel chains.

Highway on-ramps are regarded as typical bottlenecks in transportation networks. In previous work, mainline vehicles' selfish lane choice behavior at on-ramps is studied and regarded as one cause leading to on-ramp inefficiency. When on-ramp vehicles plan to merge into the mainline of the highway, mainline vehicles choose to either stay steadfast on the current lane or bypass the merging area by switching to a neighboring lane farther from the on-ramp. Selfish vehicles make the decisions to minimize their own travel delay, which compromises the efficiency of the whole on-ramp. Results in previous work have shown that, if we can encourage a proper portion of mainline vehicles to bypass rather than to stay steadfast, the social traffic conditions can be improved. In this work, we consider employing a proportion of altruistic vehicles among the selfish mainline vehicles to improve the efficiency of the on-ramps. The altruistic vehicles are individual optimizers, making decisions whether to stay steadfast or bypass to minimize their own altruistic cost, which is a weighted sum of the travel delay and their negative impact on other vehicles. We first consider the ideal case that altruistic costs can be perfectly measured by altruistic vehicles. We give the conditions for the proportion of altruistic vehicles and the weight configuration of the altruistic costs, under which the social delay can be decreased or reach the optimal. Subsequently, we consider the impact of uncertainty in the measurement of altruistic costs and we give the optimal weight configuration for altruistic vehicles which minimizes the worst-case social delay under such uncertainty.

We consider the scenario where human-driven/autonomous vehicles with low/high occupancy are sharing a segment of highway and autonomous vehicles are capable of increasing the traffic throughput by preserving a shorter headway than human-driven vehicles. We propose a toll lane framework where a lane on the highway is reserved freely for autonomous vehicles with high occupancy, which have the greatest capability to increase social mobility, and the other three classes of vehicles can choose to use the toll lane with a toll or use the other regular lanes freely. All vehicles are assumed to be only interested in minimizing their own travel costs. We explore the resulting lane choice equilibria under the framework and establish desirable properties of the equilibria, which implicitly compare high-occupancy vehicles with autonomous vehicles in terms of their capabilities to increase social mobility. We further use numerical examples in the optimal toll design, the occupancy threshold design, and the policy design problems to clarify the various potential applications of this toll lane framework that unites high-occupancy vehicles and autonomous vehicles. To our best knowledge, this is the first work that systematically studies a toll lane framework that unites autonomous vehicles and high-occupancy vehicles on the roads.

This paper considers coverage games in which a group of agents are tasked with identifying the highest-value subset of resources; in this context, game-theoretic approaches are known to yield Nash equilibria within a factor of 2 of optimal. We consider the case that some of the agents suffer a communication failure and cannot observe the actions of other agents; in this case, recent work has shown that if there are k>0 compromised agents, Nash equilibria are only guaranteed to be within a factor of k+1 of optimal. However, the present paper shows that this worst-case guarantee is fragile; in a sense which we make precise, we show that if a problem instance has a very poor worst-case guarantee, then it is necessarily very "close" to a problem instance with an optimal Nash equilibrium. Conversely, an instance that is far from one with an optimal Nash equilibrium necessarily has relatively good worst-case performance guarantees. To contextualize this fragility, we perform simulations using the log-linear learning algorithm and show that average performance on worst-case instances is considerably better even than our improved analytical guarantees. This suggests that the fragility of the price of anarchy can be exploited algorithmically to compensate for online communication failures., Comment: 6 pages, 4 figures