This paper introduces algorithm instance games (AIGs) as a conceptual classification applying to games in which outcomes are resolved from joint strategies algorithmically. For such games, a fundamental question asks: How do the details of the algorithm's description influence agents' strategic behavior? We analyze two versions of an AIG based on the set-cover optimization problem. In these games, joint strategies correspond to instances of the set-cover problem, with each subset (of a given universe of elements) representing the strategy of a single agent. Outcomes are covers computed from the joint strategies by a set-cover algorithm. In one variant of this game, outcomes are computed by a deterministic greedy algorithm, and the other variant utilizes a non-deterministic form of the greedy algorithm. We characterize Nash equilibrium strategies for both versions of the game, finding that agents' strategies can vary considerably between the two settings. In particular, we find that the version of the game based on the deterministic algorithm only admits Nash equilibrium in which agents choose strategies (i.e., subsets) containing at most one element, with no two agents picking the same element. On the other hand, in the version of the game based on the non-deterministic algorithm, Nash equilibrium strategies can include agents with zero, one, or every element, and the same element can appear in the strategies of multiple agents.
In this work, we study the degree to which small fluctuations in costs in well-studied potential games can impact the result of natural best-response and improved-response dynamics. We call this the Price of Uncertainty and study it in a wide variety of potential games including fair cost-sharing games, set-cover games, routing games, and job-scheduling games. We show that in certain cases, even extremely small fluctuations can have the ability to cause these dynamics to spin out of control and move to states of much higher social cost, whereas in other cases these dynamics are much more stable even to large degrees of fluctuation. We also consider the resilience of these dynamics to a small number of Byzantine players about which no assumptions are made. We show again a contrast between different games. In certain cases (e.g., fair cost-sharing, set-cover, job-scheduling) even a single Byzantine player can cause best-response dynamics to transition from low-cost states to states of substantially higher cost, whereas in others (e.g., the class of β-nice games, which includes routing, market-sharing and many others) these dynamics are much more resilient. Overall, our work can be viewed as analyzing the inherent resilience or safety of games to different kinds of imperfections in player behavior, player information, or in modeling assumptions made. We consider a general class of non-cooperative games related to combinatorial covering and facility location problems. A game is based on an integer programming formulation of the corresponding optimization problem, and each of the k players wants to satisfy a subset of the constraints. For that purpose, resources available in integer units must be bought, and their cost can be shared arbitrarily between players. We consider the existence and cost of exact and approximate pure-strategy Nash equilibria. In general, the prices of anarchy and stability are in @Q(k) and deciding the existence of a pure Nash equilibrium is NP-hard. Under certain conditions, however, cheap Nash equilibria exist, in particular if the integrality gap of the underlying integer program is 1, or in the case of single constraint players. We also present algorithms that compute simultaneously near-stable and near-optimal approximate Nash equilibria in polynomial time. We consider a cost sharing system where users are selfish and act according to their own interest. There is a set of facilities and each facility provides services to a subset of the users. Each user is interested in purchasing a service, and will buy it from the facility offering it at the lowest cost. The overall system performance is defined to be the total cost of the facilities chosen by the users. A central authority can encourage the purchase of services by offering subsidies that reduce their price, in order to improve the system performance. The subsidies are financed by taxes collected from the users. Specifically, we investigate a non-cooperative game, where users join the system, and act according to their best response. We model the system as an instance of a set cover game, where each element is interested in selecting a cover minimizing its payment. The subsidies are updated dynamically, following the selfish moves of the elements and the taxes collected due to their payments. Our objective is to design a dynamic subsidy mechanism that improves on the overall system performance while collecting as taxes only a small fraction of the sum of the payments of the users. The performance of such a subsidy mechanism is thus defined by two different quality parameters: (i) the price of anarchy, defined as the ratio between the cost of the Nash equilibrium obtained and the cost of an optimal solution; and (ii) the taxation ratio, defined as the fraction of payments collected as taxes from the users. We investigate two different models: (i) an integral model in which each element is covered by a single set; and (ii) a fractional model in which an element can be fractionally covered by several sets. Let f denote the maximum number of sets that an element can belong to. For the fractional model, we provide a subsidy mechanism such that, for any e≤1, the price of anarchy is @math and the taxation ratio is e. For the integral model, we provide a subsidy mechanism such that, for any e≤1, the price of anarchy is @math and the taxation ratio is e, where n is the number of elements. Given a collection @math of weighted subsets of a ground set @math , the set cover problem is to find a minimum weight subset of @math which covers all elements of @math . We study a strategic game defined upon this classical optimization problem. Every element of @math is a player which chooses one set of @math where it appears. Following a public tax function, every player is charged a fraction of the weight of the set that it has selected. Our motivation is to design a tax function having the following features: it can be implemented in a distributed manner, existence of an equilibrium is guaranteed and the social cost for these equilibria is minimized. 