Algorithmic Game Theory

Consider a model with a finite number of alternatives, and buyers with private values and quasi-linear utility functions. A domain of valuations for a buyer is a monotonicity domain if every finite-valued monotone randomized allocation rule defined on it is implementable, in the sense that there exists a randomized truth-telling direct mechanism, which implements this allocation rule. The domain is a weak monotonicity domain if every deterministic monotone allocation rule defined on it is implementable. I discuss the literature on (weak) monotonicity domain, which includes the early mathematical literature as well as the recent CS/Economics literature.

Equilibria play a central role in game theory and economics. They characterize the possible outcomes in the interaction of rational, optimizing agents: In a game between rational players that want to optimize their payoffs, the only solutions in which no player has any incentive to switch his strategy are the Nash equilibria. Price equilibria in markets give the prices that allow the market to clear (demand matches supply) while the traders optimize their preferences (utilities). Fundamental theorems of Nash [34] and Arrow-Debreu [2] established the existence of the respective equilibria (under suitable conditions in the market case). The proofs in both cases use a fixed point theorem (relying ultimately on a compactness argument), and are non-constructive, i.e., do not yield an algorithm for constructing an equilibrium. We would clearly like to compute these predicted outcomes. This has led to extensive research since the 60’s in the game theory and mathematical economics literature, with the development of several methods for computation of equilibria, and more generally fixed points. More recently, equilibria problems have been studied intensively in the computer science community, from the point of view of modern computation theory. While we still do not know definitely whether equilibria can be computed in general efficiently or not, these investigations have led to a better understanding of the computational complexity of equilibria, the various issues involved, and the relationship with other open problems in computation. In this talk we will discuss some of these aspects and our current understanding of the relevant problems. We outline below the main points and explain some of the related issues.

Roberts’ theorem from 1979 states that the only incentive compatible mechanisms over a full domain and range of at least 3 are weighted variants of the VCG mechanism termed affine maximizers. Roberts’ proof is somewhat “magical” and we provide a new “modular” proof. We hope that this proof will help in future efforts to extend the theorem to non-full domains such as combinatorial auctions or scheduling.

We study implementability in dominant strategies of social choice functions when sets of types are multi-dimensional and convex, sets of outcomes are arbitrary, valuations for outcomes are convex functions in the type, and utilities over outcomes and payments are quasi-linear. Archer and Kleinberg [1] have proven that in case of valuation functions that are linear in the type monotonicity in combination with a local integrability condition are equivalent with implementability. We show that in the case of convex valuation functions one has to require in addition a property called decomposition monotonicity in order to conclude implementability from monotonicity and the integrability condition. Decomposition monotonicity is automatically satisfied in the linear case.

Saks and Yu [9] have shown that for the same setting as in Archer and Kleinberg [1], but finite set of outcomes, monotonicity alone is sufficient for implementability. Later Archer and Kleinberg [1], Monderer [6] and Vohra [10] have given alternative proofs for the same theorem. Using our characterization, we show that the Saks and Yu theorem generalizes to convex valuations. Again, decomposition monotonicity has to be added as a condition.

We prove a general monotonicity result about Nash flows in directed networks, which generalizes earlier results and can be used for the design of

truthful mechanisms

in the setting where each edge of the network is controlled by a different selfish agent, who incurs costs proportional to the usage of her edge. Moreover, we consider a mechanism design setting with

two-parameter agents

, which generalizes the well-known setting of one-parameter agents by allowing a fixed cost component as part of each agent’s private data. We give a complete characterization of the set of output functions that can be turned into truthful mechanisms for two-parameter agents. This characterization also motivates our choice of linear cost functions without fixed costs for the edges in the selfish routing setting.

We introduce partition equilibrium and study its existence in resource selection games (RSG). In partition equilibrium the agents are partitioned into coalitions, and only deviations by the prescribed coalitions are considered. This is in difference to the classical concept of strong equilibrium according to which any subset of the agents may deviate. In resource selection games, each agent selects a resource from a set of resources, and its payoff is an increasing (or non-decreasing) function of the number of agents selecting its resource. While it has been shown that strong equilibrium exists in resource selection games, these games do not possess super-strong equilibrium, in which a fruitful deviation benefits at least one deviator without hurting any other deviator, even in the case of two identical resources with increasing cost functions. Similarly, strong equilibrium does not exist for that restricted two identical resources setting when the game is played repeatedly. We prove that for any given partition there exists a super-strong equilibrium for resource selection games of identical resources with increasing cost functions; we also show similar existence results for a variety of other classes of resource selection games. For the case of repeated games we identify partitions that guarantee the existence of strong equilibrium. Together, our work introduces a natural concept, which turns out to lead to positive and applicable results in one of the basic domains studied in the literature.

A mechanism is manipulable if it is in some agents’ best interest to misrepresent their private information. The

revelation principle

establishes that, roughly, anything that can be accomplished by a manipulable mechanism can also be accomplished with a truthful mechanism. Yet agents often fail to play their optimal manipulations due to computational limitations or various flavors of incompetence and cognitive biases. Thus, manipulable mechanisms in particular should anticipate byzantine play. We study

manipulation-optimal

mechanisms: mechanisms that are undominated by truthful mechanisms when agents act fully rationally, and do better than any truthful mechanism if

any

agent fails to act rationally

in any way

. This enables the mechanism designer to do better than the revelation principle would suggest, and obviates the need to predict byzantine agents’ irrational behavior. We prove a host of possibility and impossibility results for the concept which have the impression of broadly limiting possibility. These results are largely in line with the revelation principle, although the considerations are more subtle and the impossibility not universal.

In this paper we study a large class of resource allocation problems with an important complication, the utilization cost of a given resource is private information of a profit maximizing agent. After reviewing the characterization of the optimal bayesian mechanism, we study the informational cost introduced by the presence of private information. Our main result is to provide an upper bound for the ratio between the cost under asymmetric information and the cost of a fully informed designer, which is independent of the combinatorial nature of the problem and only depend on the statistical distribution of the resource costs. In particular our bounds evaluates to 2 when the utilization cost’s distributions are symmetric and unimodal and this is tight. We also show that this bound holds for a variation of the Vickrey-Clark-Groves mechanism, which always achieves an ex-post efficient allocation. Finally we point out implementation issues of the considered mechanisms.

It is well-known that for several natural decision problems no budget balanced Groves mechanisms exist. This has motivated recent research on designing variants of feasible Groves mechanisms (termed as ‘redistribution of VCG (Vickrey-Clarke-Groves) payments’) that generate reduced deficit. With this in mind, we study sequential mechanisms and consider optimal strategies that could reduce the deficit resulting under the simultaneous mechanism. We show that such strategies exist for the sequential pivotal mechanism of the well-known public project problem. We also exhibit an optimal strategy with the property that a maximal social welfare is generated when each player follows it. Finally, we show that these strategies can be achieved by an implementation in Nash equilibrium. All proofs can be found in the full version posted in Computing Research Repository (CoRR),

http://arxiv.org/abs/0810.1383

Since the pioneering paper of Rosenthal a lot of work has been done in order to determine classes of games that admit a potential. First, we study the existence of potential functions for weighted congestion games. Let

$\mathcal{C}$

be an arbitrary set of locally bounded functions and let

$\mathcal{G}(\mathcal{C})$

be the set of weighted congestion games with cost functions in

$\mathcal{C}$

. We show that every weighted congestion game

$G\in\mathcal{G}(\mathcal{C})$

admits an exact potential if and only if

C

contains only affine functions. We also give a similar characterization for weighted potentials with the difference that here

$\mathcal{C}$

consists either of affine functions or of certain exponential functions. We finally extend our characterizations to weighted congestion games with facility-dependent demands and elastic demands, respectively.

This paper studies a setting where a principal needs to motivate teams of agents whose efforts lead to an outcome that stochastically depends on the combination of agents’ actions, which are not directly observable by the principal. In [1] we suggest and study a basic “combinatorial agency” model for this setting. In this paper we expose a somewhat surprising phenomenon found in this setting: cases where the principal can gain by asking agents to

reduce

their effort level, even when this increased effort comes

for free

. This phenomenon cannot occur in a setting where the principal can observe the agents’ actions, but we show that it can occur in the hidden-actions setting. We prove that for the family of technologies that exhibit “increasing returns to scale” this phenomenon cannot happen, and that in some sense this is a maximal family of technologies for which the phenomenon cannot occur. Finally, we relate our results to a basic question in production design in firms.

A key question in cooperative game theory is that of coalitional stability, usually captured by the notion of the

core

—the set of outcomes such that no subgroup of players has an incentive to deviate. However, some coalitional games have empty cores, and any outcome in such a game is unstable.

In this paper, we investigate the possibility of stabilizing a coalitional game by using external payments. We consider a scenario where an external party, which is interested in having the players work together, offers a supplemental payment to the grand coalition (or, more generally, a particular coalition structure). This payment is conditional on players not deviating from their coalition(s). The sum of this payment plus the actual gains of the coalition(s) may then be divided among the agents so as to promote stability. We define the

cost of stability (CoS)

as the minimal external payment that stabilizes the game.

We provide general bounds on the cost of stability in several classes of games, and explore its algorithmic properties. To develop a better intuition for the concepts we introduce, we provide a detailed algorithmic study of the cost of stability in weighted voting games, a simple but expressive class of games which can model decision-making in political bodies, and cooperation in multiagent settings. Finally, we extend our model and results to games with coalition structures.

In a scheduling game, each player owns a job and chooses a machine to execute it. While the social cost is the maximal load over all machines (makespan), the cost (disutility) of each player is the completion time of its own job. In the game, players may follow selfish strategies to optimize their cost and therefore their behaviors do not necessarily lead the game to an equilibrium. Even in the case there is an equilibrium, its makespan might be much larger than the social optimum, and this inefficiency is measured by the price of anarchy – the worst ratio between the makespan of an equilibrium and the optimum. Coordination mechanisms aim to reduce the price of anarchy by designing scheduling policies that specify how jobs assigned to a same machine are to be scheduled. Typically these policies define the schedule according to the processing times as announced by the jobs. One could wonder if there are policies that do not require this knowledge, and still provide a good price of anarchy. This would make the processing times be private information and avoid the problem of truthfulness. In this paper we study these so-called

non-clairvoyant

policies. In particular, we study the

RANDOM

policy that schedules the jobs in a random order without preemption, and the

EQUI

policy that schedules the jobs in parallel using time-multiplexing, assigning each job an equal fraction of CPU time.

For these models we study two important questions, the existence of Nash equilibria and the price of anarchy. We show under some restrictions that the game under

RANDOM

policy is a potential game for two unrelated machines but it is not for three or more; for uniform machines, we prove that the game under this policy always possesses a Nash equilibrium by using a novel potential function with respect to a refinement of best-response dynamic. Moreover, we show that the game under the

EQUI

policy is a potential game.

Next, we analyze the inefficiency of

EQUI

policy. Interestingly, the (strong) price of anarchy of

EQUI

, a non-clairvoyant policy, is asymptotically the same as that of the best

strongly local

policy – policies in which a machine may look at the processing time of jobs assigned to it. The result also indicates that knowledge of jobs’ characteristics is not necessarily needed.

We consider the balloon popping problem introduced by Immorlica et al. in 2007 [13]. This problem is directly related to the problem of profit maximization in online auctions, where an auctioneer is selling a collection of identical items to anonymous unit-demand bidders. The auctioneer has the full knowledge of bidders’ private valuations for the items and tries to maximize his profit. Compared with the profit of fixed price schemes, the competitive ratio of Immorlica et al.’s algorithm was in the range [1.64, 4.33]. In this paper, we narrow the gap to [1.659, 2].

We consider the loss in social welfare caused by individual rationality in matching scenarios. We give both theoretical and experimental results comparing stable matchings with socially optimal ones, as well as studying the convergence of various natural algorithms to stable matchings. Our main goal is to design mechanisms that incentivize agents to participate in matchings that are socially desirable. We show that theoretically, the loss in social welfare caused by strategic behavior can be substantial. However, under some natural distributions of utilities, we show experimentally that stable matchings attain close to the optimal social welfare. Furthermore, for certain graph structures, simple greedy algorithms for partner-switching (some without convergence guarantees) converge to stability remarkably quickly in expectation. Even when stable matchings are significantly socially suboptimal, slight changes in incentives can provide good solutions. We derive conditions for the existence of approximately stable matchings that are also close to socially optimal, which demonstrates that adding small switching costs can make socially optimal matchings stable.

In both transportation and communication networks we are faced with “selfish flows”, where every agent sending flow over the network desires to get it to its destination as soon as possible. Such flows have been well studied in time-invariant networks in the last few years. A key observation that must be taken into account in defining and studying selfish flow, however, is that a flow can take a non-negligible amount of time to travel across the network from the source to destination, and that network states like traffic load and congestion can vary during this period. Such flows are called dynamic flows (a.k.a. flows over time). This variation in network state as the flow progresses through the network results in the fundamentally different and significantly more complex nature of dynamic flow equilibria, as compared to those defined in static network settings.

In this paper, we study equilibria in dynamic flows, and prove various bounds about their quality, as well as give algorithms on how to compute them. In general, we show that unlike in static flows, Nash equilibria may not exist, and the price of anarchy can be extremely high. If the system obeys FIFO (first-in first-out), however, we show the existence and how to compute an equilibrium for all single-source single-sink networks. In addition, we prove a set of much stronger results about price of anarchy and stability in the case where the delay on an edge is flow-independent.

Congestion control at bottleneck routers on the internet is a long standing problem. Many policies have been proposed for effective ways to drop packets from the queues of these routers so that network endpoints will be inclined to share router capacity fairly and minimize the overflow of packets trying to enter the queues. We study just how effective some of these queuing policies are when each network endpoint is a self-interested player with no information about the other players’ actions or preferences. By employing the adaptive learning model of evolutionary game theory, we study policies such as Droptail, RED, and the greedy-flow-punishing policy proposed by Gao et al. [10] to find the stochastically stable states: the states of the system that will be reached in the long run.

We study the convergence time of Nash dynamics in two classes of congestion games – constant player congestion games and bounded jump congestion games. It was shown by Ackermann and Skopalik [2] that even 3-player congestion games are

PLS

-complete. We design an FPTAS for congestion games with constant number of players. In particular, for any

ε

> 0, we establish a stronger result, namely, any sequence of (1 + 

ε

)-greedy improvement steps converges to a (1 + 

ε

)-approximate equilibrium in a number of steps that is polynomial in

ε

− 1

and the size of the input. As the number of strategies of a player can be exponential in the size of the input, our FPTAS result assumes that a (1 + 

ε

)-greedy improvement step, if it exists, can be computed in polynomial time. This assumption holds in previously studied models of congestion games, including network congestion games [9] and restricted network congestion games [2].

For bounded jump games, where jumps in the delay functions of resources are bounded by

β

, we show that there exists a game with an exponentially long sequence of

α

-greedy best response steps that does not converge to an

α

-approximate equilibrium, for all

α

 ≤ 

β

o

(

n

/log

n

)

, where

n

is the number of players and the size of the game is

O

(

n

). So in the worst case, Nash dynamics may fail to converge in polynomial time to such an approximate equilibrium. We also prove the same result for bounded jump network congestion games. In contrast, we observe that it is easy to show that a

β

2

n

-approximate equilibrium is reached in at most

n

best response steps.

We study the survivable version of the game theoretic network formation model known as the Connection Game, originally introduced in [4]. In this model, players attempt to connect to a common source node in a network by purchasing edges, and sharing their costs with other players. We introduce the

survivable

version of this game, where each player desires 2 edge-disjoint connections between her pair of nodes instead of just a single connecting path, and analyze the quality of exact and approximate Nash equilibria. For the special case where each node represents a player, we show that Nash equilibria are guaranteed to exist and price of stability is 1. For the general version of the Survivable Connection Game, we show that there always exists a 2-approximate Nash equilibrium that is as cheap as the socially optimal solution.

Congestion games—in which players strategically choose from a set of “resources” and derive utilities that depend on the congestion on each resource—are important in a wide range of applications. However, to date, such games have been constrained to use utility functions that are linear sums with respect to resources. To remove this restriction, this paper provides a significant generalisation to the case where a player’s payoff can be given by

any

real-valued function over the set of possible congestion vectors. Under reasonable assumptions on the structure of player strategy spaces, we constructively prove the existence of a pure strategy equilibrium for the very wide class of these generalised games in which player utility functions are

congestion-averse

—i.e., monotonic, submodular and independent of irrelevant alternatives. Although, as we show, these games do not admit a generalised ordinal potential function (and hence—the finite improvement property), any such game does possess a Nash equilibrium in pure strategies. A polynomial time algorithm for computing such an equilibrium is presented.

Let

A

be a randomized, unlimited supply, unit demand, single-item auction, which given a bid-vector

b

 ∈ [

h

]

n

, has expected profit

${\mathbb E}[P(b)]$

. Aggarwal et al. showed that given

A

, there exists a deterministic auction which given a bid-vector

b

, guarantees a profit of

${\mathbb E}[P(b)]/4 - O(h)$

. In this paper we show that given

A

, there exists a deterministic auction which given a bid-vector

b

of length

n

, guarantees a profit of

${\mathbb E}[P(b)]- O(h\sqrt{n \ln hn})$

. As is the case with the construction of Aggarwal et al., our construction is not polynomial time computable.

We continue the recently initiated study of the computational aspects of weak saddles, an ordinal set-valued solution concept proposed by Shapley. Brandt et al. gave a polynomial-time algorithm for computing weak saddles in a subclass of matrix games, and showed that certain problems associated with weak saddles of bimatrix games are NP-complete. The important question of whether weak saddles can be

found

efficiently was left open. We answer this question in the negative by showing that finding weak saddles of bimatrix games is NP-hard, under polynomial-time Turing reductions. We moreover prove that recognizing weak saddles is coNP-complete, and that deciding whether a given action is contained in some weak saddle is hard for parallel access to NP and thus not even in NP unless the polynomial hierarchy collapses. Our hardness results are finally shown to carry over to a natural weakening of weak saddles.

Computing optimal Stackelberg strategies in general two-player Bayesian games (not to be confused with Stackelberg strategies in routing games) is a topic that has recently been gaining attention, due to their application in various security and law enforcement scenarios. Earlier results consider the computation of optimal Stackelberg strategies, given that all the payoffs and the prior distribution over types are known. We extend these results in two different ways. First, we consider

learning

optimal Stackelberg strategies. Our results here are mostly positive. Second, we consider computing

approximately

optimal Stackelberg strategies. Our results here are mostly negative.

We study economic means to improve network performance in the well-known game theoretic traffic model due to Wardrop. We introduce two sorts of spam flow - auxiliary and adversarial flow - that have no intrinsic value. Auxiliary/adversarial flows are a separate commodity with the sole objective to minimize/maximize the latency at the induced Wardrop equilibrium of the selfish flow. By this means a separate access to the edges is not necessary and the latency of the regulating flow does not distort the arising latency cost. We present networks where auxiliary flow is able to improve the network performance. However, we show that the optimal auxiliary flow is

NP

-hard to compute and not approximable within a factor of less then

$\frac 43$

. The minimal amount of auxiliary flow needed to induce the best possible equilibrium is even hard to approximate by any subexponential factor. These hardness results are complemented by proving

NP

-hardness for the optimal adversarial flow. All hardness results hold even for single-commodity networks.

In the

tollbooth problem on trees

, we are given a tree

T

= (

V

,

E

) with

n

edges, and a set of

m

customers, each of whom is interested in purchasing a path on the graph. Each customer has a fixed budget, and the objective is to price the edges of

T

such that the total revenue made by selling the paths to the customers that can afford them is maximized. An important special case of this problem, known as the

highway problem

, is when

T

is restricted to be a line. For the tollbooth problem, we present an

O

(log

n

)-approximation, improving on the current best

O

(log

m

)-approximation. We also study a special case of the tollbooth problem, when all the paths that customers are interested in purchasing go towards a fixed root of

T

. In this case, we present an algorithm that returns a (1 − 

ε

)-approximation, for any

ε

> 0, and runs in quasi-polynomial time. On the other hand, we rule out the existence of an FPTAS by showing that even for the line case, the problem is strongly NP-hard. Finally, we show that in the

discount model

, when we allow some items to be priced below zero to improve the overall profit, the problem becomes even APX-hard.

In game theory, a player’s action is said to be weakly dominated if there exists another action that, with respect to what the other players do, is never worse and sometimes strictly better. We investigate the computational complexity of the process of iteratively eliminating weakly dominated actions (IWD) in two-player constant-sum games, i.e., games in which the interests of both players are diametrically opposed. It turns out that deciding whether an action is eliminable via IWD is feasible in polynomial time whereas deciding whether a given subgame is reachable via IWD is NP-complete. The latter result is quite surprising as we are not aware of other natural computational problems that are intractable in constant-sum games. Furthermore, we slightly improve a result by Conitzer and Sandholm [6] by showing that typical problems associated with IWD in win-lose games with at most one winner are NP-complete.

In voting theory,

bribery

is a form of manipulative behavior in which an external actor (the briber) offers to pay the voters to change their votes in order to get her preferred candidate elected. We investigate a model of bribery where the price of each vote depends on the amount of change that the voter is asked to implement. Specifically, in our model the briber can change a voter’s preference list by paying for a sequence of swaps of consecutive candidates. Each swap may have a different price; the price of a bribery is the sum of the prices of all swaps that it involves. We prove complexity results for this model, which we call

swap bribery

, for a broad class of voting rules, including variants of approval and

k

-approval, Borda, Copeland, and maximin.

We investigate the approximation ratio of the solutions achieved after a one-round walk in linear congestion games. We consider the social functions

${\mathrm{S}\textsc{um}}$

, defined as the sum of the players’ costs, and

${\mathrm{M}\textsc{ax}}$

, defined as the maximum cost per player, as a measure of the quality of a given solution. For the social function

${\mathrm{S}\textsc{um}}$

and one-round walks starting from the empty strategy profile, we close the gap between the upper bound of

$2+\sqrt{5}\approx 4.24$

given in [8] and the lower bound of 4 derived in [4] by providing a matching lower bound whose construction and analysis require non-trivial arguments. For the social function

${\mathrm{M}\textsc{ax}}$

, for which, to the best of our knowledge, no results were known prior to this work, we show an approximation ratio of

$\Theta(\sqrt[4]{n^3})$

(resp.

$\Theta(n\sqrt{n})$

), where

n

is the number of players, for one-round walks starting from the empty (resp. an arbitrary) strategy profile.

We study Nash equilibria in the context of flows over time. Many results on

static

routing games have been obtained over the last ten years. In flows over time (also called

dynamic

flows), flow travels through a network over time and, as a consequence, flow values on edges are time-dependent. This more realistic setting has not been tackled from the viewpoint of algorithmic game theory yet; but there is a rich literature on game theoretic aspects of flows over time in the traffic community.

We present a novel characterization of Nash equilibria for flows over time. It turns out that Nash flows over time can be seen as a concatenation of special static flows. The underlying flow over time model is the so-called

deterministic queuing model

that is very popular in road traffic simulation and related fields. Based upon this, we prove the first known results on the price of anarchy for flows over time.

We study auctions whose bidders are embedded in a social or economic network. As a result, even bidders who do not win the auction themselves might derive utility from the auction, namely, when a friend wins. On the other hand, when an enemy or competitor wins, a bidder might derive negative utility. Such spite and altruism will alter the bidding strategies. A simple and natural model for bidders’ utilities in these settings posits that the utility of a losing bidder

i

as a result of bidder

j

winning is a constant (positive or negative) fraction of bidder

j

’s utility.

We study such auctions under a Bayesian model in which all valuations are distributed independently according to a known distribution, but the actual valuations are private. We describe and analyze Nash Equilibrium bidding strategies in two broad classes: regular friendship networks with arbitrary valuation distributions, and arbitrary friendship networks with identical uniform valuation distributions.

In the ADM minimization problem, the input is a set of arcs along a directed ring. The input arcs need to be partitioned into non-overlapping chains and cycles so as to minimize the total number of endpoints, where a

k

-arc cycle contributes

k

endpoints and a

k

-arc chain contains

k

 + 1 endpoints. We study ADM minimization problem both as a non-cooperative and a cooperative games. In these games, each arc corresponds to a player, and the players share the cost of the ADM switches. We consider two cost allocation models, a model which was considered by Flammini et al., and a new cost allocation model, which is inspired by congestion games. We compare the price of anarchy and price of stability in the two cost allocation models, as well as the strong price of anarchy and the strong price of stability.