Algorithmic Game Theory

Weakly acyclic games form a natural generalization of the class of games that have the finite improvement property (FIP). In such games one stipulates that from any initial joint strategy some finite improvement path exists. We classify weakly acyclic games using the concept of a scheduler recently introduced in [1].

We study the selfishness level of several well-known strategic games. This allows us to quantify the implicit tension within a game between players’ individual interests and the impact of their decisions on the society as a whole. Our analysis reveals that the selfishness level often provides more refined insights into the game than other measures of inefficiency, such as the price of stability or the price of anarchy.

We consider randomized mechanisms for multi-dimensional scheduling. Following Lavi and Swamy [10], we study a setting with restrictions on the domain, while still preserving multi-dimensionality. In a sense, our setting is the simplest multi-dimensional setting, where each machine holds privately only a single-bit of information.

We prove a separation between truthful-in-expectation and universally truthful mechanisms for makespan minimization: We first show how to design an optimal truthful-in-expectation mechanism, and then prove lower bounds on the approximation guarantee of universally truthful mechanisms.

We revisit the complexity of deciding, given a (finite) strategic game, whether Nash equilibria with certain natural properties exist; such decision problems are well-known to be \(\cal NP\)-complete [2, 6, 10] . We show that this complexity remains unchanged when all utilities are restricted to be 0 or 1; thus, win-lose games are as complex as general games with respect to such decision problems.

For any transferable utility game in coalitional form with a nonempty core, we show that that the number of blocks required to switch from an imputation out of the core to an imputation in the core is at most n − 1, where n is the number of players. This bound exploits the geometry of the core and is optimal. It considerably improves the upper bounds found so far by Kóczy [7], Yang [13, 14] and a previous result by ourselves [2] in which the bound was n(n − 1)/2.

We consider generalized congestion games, a class of games in which players share a set of strategies and the payoff functions depend only on the chosen strategy and the number of players playing the same strategy, in such a way that fewer such players results in greater payoff. In these games we consider improvement paths. As shown by Milchtaich [2] such paths may be infinite. We consider paths in which the players deviate in a specific order, and prove that ordered best response improvement paths are finite, while ordered better response improvement paths may still be infinite.

Network creation games model the creation and usage costs of networks formed by a set of selfish peers. Each peer has the ability to change the network in a limited way, e.g., by creating or deleting incident links. In doing so, a peer can reduce its individual communication cost. Typically, these costs are modeled by the maximum or average distance in the network. We introduce a generalized version of the basic network creation game (BNCG). In the BNCG (by Alon et al., SPAA 2010), each peer may replace one of its incident links by a link to an arbitrary peer. This is done in a selfish way in order to minimize either the maximum or average distance to all other peers. That is, each peer works towards a network structure that allows himself to communicate efficiently with all other peers. However, participants of large networks are seldom interested in all peers. Rather, they want to communicate efficiently with a small subset only. Our model incorporates these (communication) interests explicitly.

Given peers with interests and a communication network forming a tree, we prove several results on the structure and quality of equilibria in our model. We focus on the MAX-version, i.e., each node tries to minimize the maximum distance to nodes it is interested in, and give an upper bound of \({\mathcal O}({\sqrt{n})}\) for the private costs in an equilibrium of n peers. Moreover, we give an equilibrium for a circular interest graph where a node has private cost \(\Omega({\sqrt{n})}\), showing that our bound is tight. This example can be extended such that we get a tight bound of \(\Theta({\sqrt{n})}\) for the price of anarchy. For the case of general networks we show the price of anarchy to be Θ(n). Additionally, we prove an interesting connection between a maximum independent set in the interest graph and the private costs of the peers.

Many puzzling social behaviors, such as avoiding eye contact, using innuendos, and insignificant events that trigger revolutions, seem to relate to common knowledge and coordination, but the exact relationship has yet to be formalized. Herein, we present such a formalization. We state necessary and sufficient conditions for what we call state-dependent equilibria – equilibria where players play different strategies in different states of the world. In particular, if everybody behaves a certain way (e.g. does not revolt) in the usual state of the world, then in order for players to be able to behave a different way (e.g. revolt) in another state of the world, it is both necessary and sufficient for it to be common p-believed that it is not the usual state of the world, where common p-belief is a relaxation of common knowledge introduced by Monderer and Samet [16]. Our framework applies to many player r-coordination games – a generalization of coordination games that we introduce – and common (r,p)-beliefs – a generalization of common p-beliefs that we introduce. We then apply these theorems to two particular signaling structures to obtain novel results.

We consider the problem of approximating the minmax value of a multi-player game in strategic form. We argue that in three-player games with 0-1 payoffs, approximating the minmax value within an additive constant smaller than ξ/2, where \(\xi = \frac{3-\sqrt5}{2} \approx 0.382\), is not possible by a polynomial time algorithm. This is based on assuming hardness of a version of the so-called planted clique problem in Erdős-Rényi random graphs, namely that of detecting a planted clique. Our results are stated as reductions from a promise graph problem to the problem of approximating the minmax value, and we use the detection problem for planted cliques to argue for its hardness. We present two reductions: a randomised many-one reduction and a deterministic Turing reduction. The latter, which may be seen as a derandomisation of the former, may be used to argue for hardness of approximating the minmax value based on a hardness assumption about deterministic algorithms. Our technique for derandomisation is general enough to also apply to related work about ε-Nash equilibria.

In an ε-Nash equilibrium, a player can gain at most ε by changing his behaviour. Recent work has addressed the question of how best to compute ε-Nash equilibria, and for what values of ε a polynomial-time algorithm exists. An ε-well-supported Nash equilibrium (ε-WSNE) has the additional requirement that any strategy that is used with non-zero probability by a player must have payoff at most ε less than a best response. A recent algorithm of Kontogiannis and Spirakis shows how to compute a 2/3-WSNE in polynomial time, for bimatrix games. Here we introduce a new technique that leads to an improvement to the worst-case approximation guarantee.

We study mechanisms for combinatorial auctions that are simultaneously incentive compatible (IC), envy free (EF) and efficient in settings with capacitated valuations — a subclass of subadditive valuations introduced by Cohen et al. [4]. Capacitated agents have valuations which are additive up to a publicly known capacity. The main result of Cohen et al. [4] is the assertion that the Vickrey-Clarke-Groves mechanism with Clarke pivot payments is EF (and clearly IC and efficient) in the case of homogeneous capacities. The main open problem raised by Cohen et al. [4] is whether the existence result extends beyond homogeneous capacities. We resolve the open problem, establishing that no mechanism exists that is simultaneously IC, EF and efficient for capacitated agents with heterogeneous capacities. In addition, we establish the existence of IC, EF, and efficient mechanisms in the special cases of capacitated agents with heterogeneous capacities, where (i) there are only two items; or (ii) the individual item values are binary. Finally, we show that the last existence result does not extend to the stronger notion of Walrasian mechanisms, i.e. mechanisms whose allocation and payments correspond to a Walrasian equilibrium.

We study a capacitated symmetric network design game, where each of n agents wishes to construct a path from a network’s source to its sink, and the cost of each edge is shared equally among its agents. The uncapacitated version of this problem has been introduced by Anshelevich et al. (2003) and has been extensively studied. We find that the consideration of edge capacities entails a significant effect on the quality of the obtained Nash equilibria (NE), under both the utilitarian and the egalitarian objective functions, as well as on the convergence rate to an equilibrium. The following results are established. First, we provide bounds for the price of anarchy (PoA) and the price of stability (PoS) measures with respect to the utilitarian (i.e., sum of costs) and egalitarian (i.e., maximum cost) objective functions. Our main result here is that, unlike the uncapacitated version, the network topology is a crucial factor in the quality of NE. Specifically, a network topology has a bounded PoA if and only if it is series-parallel (SP). Second, we show that the convergence rate of best-response dynamics (BRD) may be super linear (in the number of agents). This is in contrast to the uncapacitated version, where convergence is guaranteed within at most n iterations.

Game theory studies situations in which strategic players can modify the state of a given system, due to the absence of a central authority. Solution concepts, such as Nash equilibrium, are defined to predict the outcome of such situations. In the spirit of the field, we study the computation of solution concepts by means of decentralized dynamics. These are algorithms in which players move in turns to improve their own utility and the hope is that the system reaches an “equilibrium” quickly.

We study these dynamics for the class of opinion games, recently introduced by [1]. These are games, important in economics and sociology, that model the formation of an opinion in a social network. We study best-response dynamics and show that the convergence to Nash equilibria is polynomial in the number of players. We also study a noisy version of best-response dynamics, called logit dynamics, and prove a host of results about its convergence rate as the noise in the system varies. To get these results, we use a variety of techniques developed to bound the mixing time of Markov chains, including coupling, spectral characterizations and bottleneck ratio.

In routing games, the network performance at equilibrium can be significantly improved if we remove some edges from the network. This counterintuitive fact, a.k.a. Braess’s paradox, gives rise to the network design problem, where we seek to recognize routing games suffering from the paradox, and to improve the equilibrium performance by edge removal. In this work, we investigate the computational complexity and the approximability of network design for non-atomic bottleneck routing games, where the individual cost of each player is the bottleneck cost of her path, and the social cost is the bottleneck cost of the network. We first show that bottleneck routing games do not suffer from Braess’s paradox either if the network is series-parallel, or if we consider only subpath-optimal Nash flows. On the negative side, we prove that even for games with strictly increasing linear latencies, it is NP-hard not only to recognize instances suffering from the paradox, but also to distinguish between instances for which the Price of Anarchy (PoA) can decrease to 1 and instances for which the PoA is Ω(n^0.121) and cannot improve by edge removal. Thus, the network design problem for such games is NP-hard to approximate within a factor of O(n^{0.121 − ε}), for any constant ε > 0. On the positive side, we show how to compute an almost optimal subnetwork w.r.t. the bottleneck cost of its worst Nash flow, when the worst Nash flow in the best subnetwork routes a non-negligible amount of flow on all edges. The running time is determined by the total number of paths, and is quasipolynomial if the number of paths is quasipolynomial.

The holy grail of online advertising is to target users with ads matched to their needs with such precision that the users respond to the ads, thereby increasing both advertisers’ and users’ value. The current approach to this challenge utilizes information about the users: their gender, their location, the websites they have visited before, and so on. Incorporating this data in ad auctions poses an economic challenge: can this be done in a way that the auctioneer’s revenue does not decrease (at least on average)? This is the problem we study in this paper. Our main result is that in Myerson’s optimal mechanism, for a general model of data in auctions, additional data leads to additional expected revenue. In the context of ad auctions we show that for the simple and common mechanisms, namely second price auction with reserve prices, there are instances in which additional data decreases the expected revenue, but this decrease is by at most a small constant factor under a standard regularity assumption.

We study set-system auctions whereby a single buyer wants to purchase Q items of some commodity. There are multiple sellers, each of whom has some known number of items, and a private cost for supplying those items. Thus a “feasible set” of sellers (a set that is able to comprise the winning bidders) is any set of sellers whose total quantity sums to at least Q. We show that, even in a limited special case, VCG has a frugality ratio of at least n − 1 (with respect to the NTUmin benchmark) and that this matches the upper bound for any set-system auction. We show a lower bound on the frugality of any truthful mechanism of \(\sqrt{Q}\) in this setting and give a truthful mechanism with a frugality ratio of \(2\sqrt{Q}\). However, we show that similar types of ‘scaling’ mechanism, in the general (integer) case, give a frugality ratio of at least \({{4Qe^{-2}}\over{{\rm In}^2Q}}\) .

We study the problem of computing approximate Nash equilibria, in a setting where players initially know their own payoffs but not the payoffs of other players. In order for a solution of reasonable quality to be found, some amount of communication needs to take place between the players. We are interested in algorithms where the communication is substantially less than the contents of a payoff matrix, for example logarithmic in the size of the matrix. At one extreme is the case where the players do not communicate at all; for this case (with 2 players having n×n matrices) ε-Nash equilibria can be computed for ε = 3/4, while there is a lower bound of slightly more than 1/2 on the lowest ε achievable. When the communication is polylogarithmic in n, we show how to obtain ε = 0.438. For one-way communication we show that ε = 1/2 is the exact answer.

We study a network extension to the Nash bargaining game, as introduced by Kleinberg and Tardos [6], where the set of players corresponds to vertices in a graph G = (V,E) and each edge ij ∈ E represents a possible deal between players i and j. We reformulate the problem as a cooperative game and study the following question: Given a game with an empty core (i.e. an unstable game) is it possible, through minimal changes in the underlying network, to stabilize the game? We show that by removing edges in the network that belong to a blocking set we can find a stable solution in polynomial time. This motivates the problem of finding small blocking sets. While it has been previously shown that finding the smallest blocking set is NP-hard [2], we show that it is possible to efficiently find approximate blocking sets in sparse graphs.

We present our results on Uniform Price Auctions, one of the standard sealed-bid multi-unit auction formats, for selling multiple identical units of a single good to multi-demand bidders. Contrary to the truthful and economically efficient multi-unit Vickrey auction, the Uniform Price Auction encourages strategic bidding and is socially inefficient in general, partly due to a ”Demand Reduction” effect; bidders tend to bid for fewer (identical) units, so as to receive them at a lower uniform price. Despite its inefficiency, the uniform pricing rule is widely popular by its appeal to the natural anticipation, that identical items should be identically priced. Application domains of its variants include sales of U.S. Treasury bonds to investors, trade exchanges over the internet facilitated by popular online brokers, allocation of radio spectrum licenses etc. In this work we study equilibria of the Uniform Price Auction in undominated strategies. We characterize a class of undominated pure Nash equilibria and quantify the social inefficiency of pure and (mixed) Bayes-Nash equilibria by means of bounds on the Price of Anarchy.

We consider strategic games in which each player seeks a mixed strategy to minimize her cost evaluated by a concave valuation V (mapping probability distributions to reals); such valuations are used to model risk. In contrast to games with expectation-optimizer players where mixed equilibria always exist [15, 16], a mixed equilibrium for such games, called a V-equilibrium, may fail to exist, even though pure equilibria (if any) transfer over. What is the impact of such valuations on the existence, structure and complexity of mixed equilibria? We address this fundamental question for a particular concave valuation: expectation plus variance, denoted as RA, which stands for risk-averse; so, variance enters as a measure of risk and it is used as an additive adjustment to expectation. We obtain the following results about RA-equilibria:

Lookahead search is perhaps the most natural and widely used game playing strategy. Given the practical importance of the method, the aim of this paper is to provide a theoretical performance examination of lookahead search in a wide variety of applications. To determine a strategy play using lookahead search, each agent predicts multiple levels of possible re-actions to her move (via the use of a search tree), and then chooses the play that optimizes her future payoff accounting for these re-actions. There are several choices of optimization function the agents can choose, where the most appropriate choice of function will depend on the specifics of the actual game - we illustrate this in our examples. Furthermore, the type of search tree chosen by computationally-constrained agent can vary. We focus on the case where agents can evaluate only a bounded number, k, of moves into the future. That is, we use depth k search trees and call this approach k-lookahead search. We apply our method in five well-known settings: industrial organization (Cournot’s model); AdWord auctions; congestion games; valid-utility games and basic-utility games; cost-sharing network design games. We consider two questions. First, what is the expected social quality of outcome when agents apply lookahead search? Second, what interactive behaviours can be exhibited when players use lookahead search? We demonstrate how the answer depends on the game played.