Budgeted Adversarial Network Resource Utilization Games

This paper studies budgeted adversarial resource utilization game, where one of the player’s (designer) strategy is the utilization of resources while the other player’s (adversary) role is to police the resources for misuse. In this context, we consider routing games where a designer plans routes on a computer network and the adversary intercepts the routes on the network. Another example is in determining adversarial strategies to block access to travel or resources that may be considered to pose a risk to society, e.g. during a pandemic where the population (designer) goal may not be coincide with the societal goal of minimizing accessing a banned resource. We model this as a zero-sum game with constraints on the adversary or designer budgets. While zero-sum games can be solved using linear programs, we illustrate faster combinatorial methods to solve the problem. We first consider the resource access problem game on a bipartite graph where both the designer and the adversary have independent budget constraints and distinct costs and show a fast algorithm to determine a Nash equilibrium. We also consider the situation where the designer would strategize on paths in a general graph. In this application of determining network paths, where the adversary would attack edges in order to block the paths, we also discuss the case of multiple designers and, in particular show faster algorithms when there are 2 designers. These results utilize properties of minimum cuts in 2-commodity flow routing.