To enable the computation of effective randomized patrol routes for single- or multi-robot teams, we present RoSSO, a Python package designed for solving Markov chain optimization problems. We exploit machine-learning techniques such as reverse-mode automatic differentiation and constraint parametrization to achieve superior efficiency compared to general-purpose nonlinear programming solvers. Additionally, we supplement a game-theoretic stochastic surveillance formulation in the literature with a novel greedy algorithm and multi-robot extension. We close with numerical results for a police district in downtown San Francisco that demonstrate RoSSO’s capabilities on our new formulations and the prior work.

The uncertainty held by a system’s users can cause ineffective decision-making. Nowhere is this more apparent than in transportation networks, where drivers’ uncertainty over current road/traffic conditions can negatively alter their routing choices. To alleviate this, an informed system operator may signal information to uninformed users to persuade them into taking more preferable actions (e.g., Google/Apple maps providing live traffic updates). In this work, we study public signalling mechanisms in the context of Bayesian congestion games. We observe the phenomenon that though revealing information can reduce system cost in some settings, in others, it can induce worse performance than not signalling at all. However, we find an important relationship between information signalling and monetary incentives: by utilizing both mechanisms concurrently, the system operator can guarantee that revealing information does not worsen performance. We prove these findings in a general class of Bayesian congestion games. To understand the magnitude at which information signalling can affect system performance, we put a deeper focus in the class of parallel networks with polynomial latency functions and analytically characterize bounds on the change in system cost from signalling. Finally, we consider the problem of solving for optimal signals with and without the concurrent use of monetary incentives. We construct solvable optimization problems whose solutions give optimal signalling policies even when the signalling policy is limited in its support; we then quantify the benefit of these and other signalling mechanisms in numerical examples.

It is well-known that system performance can experience significant degradation from the self-interested choices of human users. Accordingly, in this article, we study the question of how a system operator can exploit system-level knowledge to derive incentives to influence societal behavior and improve system performance. Throughout, we focus on a simple class of routing games where the system operator has uncertainty regarding the network characteristics (i.e., latency functions) and population characteristics (i.e., sensitivity to monetary taxes). Specifically, we address the question of what information can be most effectively exploited in the design of taxation mechanisms to improve system performance. Our main results characterize an optimal marginal-cost taxation mechanism and associated performance guarantee for varying levels of network and population information. The value of a piece of information cannot be known a priori, so we adopt a worst-case interpretation of the value a piece of information is guaranteed to provide. Several interesting observations emerge about the relative value of information, including the fact that the value of population information saturates unless we also acquire more network knowledge.

We consider the problem of designing distribution rules to share `welfare' (cost or revenue) among individually strategic agents. There are many known distribution rules that guarantee the existence of a (pure) Nash equilibrium in this setting, e.g., the Shapley value and its weighted variants; however, a characterization of the space of distribution rules that guarantee the existence of a Nash equilibrium is unknown. Our work provides an exact characterization of this space for a specific class of scalable and separable games, which includes a variety of applications such as facility location, routing, network formation, and coverage games. Given arbitrary local welfare functions $W$, we prove that a distribution rule guarantees equilibrium existence for all games (i.e., all possible sets of resources, agent action sets, etc.) if and only if it is equivalent to a generalized weighted Shapley value on some `ground' welfare functions $W$, which can be distinct from W. However, if budget-balance is required in addition to the existence of a Nash equilibrium, then $W$ must be the same as $W$. We also provide an alternate characterization of this space in terms of `generalized' marginal contributions, which is more appealing from the point of view of computational tractability. A possibly surprising consequence of our result is that, in order to guarantee equilibrium existence in all games with any fixed local welfare functions, it is \textitnecessary to work within the class of potential games.

A game-theoretic framework is introduced for studying selfish user behavior in shared wireless networks. The investigation treats an n-unicast problem in a wireless network that employs a restricted form of network coding called reverse carpooling. Unicast sessions independently choose routes through the network. The cost of a set of unicast routes is the number of wireless transmissions required to establish those connections using those routes. Game theory is employed as a tool for analyzing the impact of cost sharing mechanisms on the global system performance when each unicast independently and selfishly chooses its route to minimize its individual cost. The investigation focuses on the performance of stable solutions, where a stable solution is one in which no single unicast can improve its individual cost by changing its route. The results include bounds on the best- and worst-case stable solutions compared to the best performance that could be found and implemented using a centralized controller. The optimal cost sharing protocol is derived and the worst-case solution is bounded. That worst-case stable performance cannot be improved using cost-sharing protocols that are independent of the network structure.

Load balancing is a common approach for task assignment in distributed architectures. In this paper, we show that the degree of inefficiency in load balancing designs is highly dependent on the scheduling discipline used at each of the back-end servers. Traditionally, the back-end scheduler can be modeled as processor sharing (PS), in which case the degree of inefficiency grows linearly with the number of servers. However, if the back- end scheduler is changed to shortest remaining processing time (SRPT), the degree of inefficiency can be independent of the number of servers, instead depending only on the heterogeneity of the speeds of the servers. Further, switching the back-end scheduler to SRPT can provide significant improvements in the overall mean response time of the system as long as the heterogeneity of the server speeds is small.

We introduce a game theoretic framework for studying a restricted form of network coding in a general wireless network. The network is fixed and known, and the system performance is measured as the number of wireless transmissions required to meet n unicast demands. Game theory is here employed as a tool for improving distributed network coding solutions. We propose a framework that allows each unicast session to independently adjust his routing decision in response to local information. Specifically, we model the unicast sessions as self-interested decision makers in a noncooperative game. This approach involves designing both local cost functions and decision rules for the unicast sessions so that the resulting collective behavior achieves a desirable system performance in a shared network environment. We compare the performance of the resulting distributed algorithms to the best performance that could be found and implemented using a centralized controller. We focus on the performance of stable solutions - where stability here refers to a form of Nash equilibrium defined below. Results include bounds on the best- and worst-case stable solutions as compared to the optimal centralized solution. We show that our bounds on the best- and worst-case stable performance cannot be improved using cost functions that are independent of the network structure. Results in learning in games prove that the best-case stable solution can be learned by self-interested players with probability approaching 1.

We present a view of cooperative control using the language of learning in games. We review the game-theoretic concepts of potential and weakly acyclic games, and demonstrate how several cooperative control problems, such as consensus and dynamic sensor coverage, can be formulated in these settings. Motivated by this connection, we build upon game-theoretic concepts to better accommodate a broader class of cooperative control problems. In particular, we extend existing learning algorithms to accommodate restricted action sets caused by the limitations of agent capabilities and group-based decision making. Furthermore, we also introduce a new class of games called sometimes weakly acyclic games for time-varying objective functions and action sets, and provide distributed algorithms for convergence to an equilibrium.