[PATH]
HOME
> Accepted Papers + Abstracts 
SAGT2010List of
Accepted Papers (ordered by submission numbers, with
abstracts)
[Hide Abstracts]
 Elchanan Mossel and Omer Tamuz.
Truthful Fair Division
Abstract:
We address the problem of fair division, or cake cutting, with the goal of finding truthful mechanisms. In the case of a general measure space ("cake") and nonatomic, additive individual preference measures  or utilities  we show that there exists a truthful "mechanism" which ensures that each of the k players gets at least 1/k of the cake. This mechanism also minimizes risk for truthful players. Furthermore, in the case where there exist at least two different measures we present a different truthful mechanism which ensures that each of the players gets more than 1/k of the cake. We then turn our attention to partitions of indivisible goods with bounded utilities and a large number of goods. Here we provide similar mechanisms, but with slightly weaker guarantees. These guarantees converge to those obtained in the nonatomic case as the number of goods goes to infinity.
Abstract:
Given a set of alternatives and a single player, we introduce the notion of a {\em responsive lottery}. These mechanisms receive as input from the player a reported utility function, specifying a value for each one of the alternatives, and use a lottery to produce as output a probability distribution over the alternatives. Thereafter, exactly one alternative wins (is given to the player) with the respective probability. Assuming that the player is not indifferent to which of the alternatives wins, a lottery rule is called {\em truthful dominant} if reporting his true utility function (up to affine transformations) is the unique report that maximizes the expected payoff for the player. We design truthful dominant responsive lotteries. We also discuss their relations with scoring rules and with VCG mechanisms.
Abstract:
A key solution concept in cooperative game theory is the core. The core of an expense sharing game contains stable allocations of the total cost to the participating players, such that each subset of players pays at most what it would pay if acting on its own. Unfortunately, some expense sharing games have an empty core, meaning that the total cost is too high to be divided in a stable manner. In such cases, an external entity could choose to induce stability using an external subsidy. We call the minimal subsidy required to make the core of a game nonempty the Cost of Stability (CoS), adopting a recently coined term for surplus sharing games. We provide bounds on the CoS for general, subadditive and anonymous games, discuss the special case of Facility Games, and consider the complexity of computing the CoS.
Abstract:
We study "logit dynamics" for strategic games. At every stage of the game a player is selected uniformly at random and she plays according to a "noisy" bestresponse dynamics where the noise level is tuned by a parameter $\beta$. Such a dynamics defines a family of ergodic Markov chains, indexed by $\beta$, over the set of strategy profiles. Our aim is twofold: On the one hand, we are interested in the expected social welfare when the strategy profiles are random according to the stationary distribution of the Markov chain, because we believe it gives a meaningful description of the longterm behavior of the system. On the other hand, we want to estimate how long it takes, for a system starting at an arbitrary profile and running the logit dynamics, to get close to the stationary distribution; i.e., the mixing time of the chain. In this paper we study the stationary expected social welfare for the 3player CKgame, for 2player coordination games (the same class of games studied in~\cite{blumeGEB93}), 2player anticoordination games, and for a simple nplayer game. For all these games, we give almosttight upper and lower bounds on the mixing time of logit dynamics.
Abstract:
Fictitious play is a simple learning algorithm for strategic games that proceeds in rounds. In each round, the players play a best response to a mixed strategy that is given by the empirical frequencies of actions played in previous rounds. There is a close relationship between fictitious play and the Nash equilibria of a game: if the empirical frequencies of fictitious play converge to a strategy profile, this strategy profile is a Nash equilibrium. While fictitious play does not converge in general, it is known to do so for certain restricted classes of games, such as constantsum games, nondegenerate 2 by n games, and potential games. We study the rate of convergence of fictitious play and show that, in all the classes of games mentioned above, fictitious play may require an exponential number of rounds (in the size of the representation of the game) before some equilibrium action is eventually played. In particular, we show the above statement for symmetric constantsum winlosetie games.
Abstract:
We consider network congestion games in which a finite number of noncooperative users select paths. The aim is to mitigate the inefficiency caused by the selfish users by introducing taxes on the network edges. A tax vector is strongly (weakly)optimal if all (at least one of) the equilibria in the resulting game minimize(s) the total latency. The issue of designing optimal tax vectors for selfish
routing games has been studied extensively in the literature. We study for the first time taxation for networks with atomic users which have unsplittable traffic demands and are heterogeneous, i.e., have different sensitivity to taxes. On the positive side, we show the existence of weaklyoptimal taxes for singlesource network games. On the negative side, we show that the cases of homogeneous and heterogeneous users differ sharply as far as the existence of stronglyoptimal taxes is concerned: there are parallellink games with linear latencies and heterogeneous users that do not admit stronglyoptimal taxes.

Chinmay Karande
, Gagan Goel and Lei Wang.
SingleParameter Combinatorial Auctions with Partially Public Valuations
Abstract:
We consider the problem of designing truthful auctions, when the bidders' valuations have a public and a private component. In particular, we consider combinatorial auctions where the valuation of an agent $i$ for a set $S$ of items can be expressed as $v_if(S)$, where $v_i$ is a private single parameter of the agent, and the function $f$ is publicly known. Our motivation behind studying this problem is twofold: (a) Such valuation functions arise naturally in the case of adslots in broadcast media such as Television and Radio. For an ad shown in a set $S$ of adslots, $f(S)$ is, say, the number of {\em unique} audience members reached by the ad, and $v_i$ is the valuation peruniqueviewer. (b) From a theoretical point of view, this factorization of the valuation function simplifies the bidding language, and renders the combinatorial auction more amenable to better approximation factors. We present a very general technique, based on maximalinrange mechanisms, that converts any $\alpha$approximation nontruthful algorithm ($\alpha \leq 1$)\footnote{We use the convention that an approximation algorithm for a maximization problem is $\alpha$approximate if the solution has value at least $\alpha$ times the optimal for $\alpha \leq 1$. Hence, all our approximation factors are fractional.} into $\Omega(\frac{\alpha}{\log{n}})$ and $\Omega(\alpha)$approximate truthful mechanisms which run in polynomial time and quasipolynomial time, respectively.
Abstract:
Much work has been done on the computation of market equilibria. However due to strategic play by buyers, it is not clear whether these are actually observed in the market. Motivated by the observation that a buyer may derive a better payoff by feigning a different utility function and thereby manipulating the Fisher market equilibrium, we formulate the {\em Fisher market game} in which buyers strategize by posing different utility functions. We show that existence of a {\em conflictfree allocation} is a necessary condition for the Nash equilibria (NE) and also sufficient for the symmetric NE in this game. There are many NE with very different payoffs, and the Fisher equilibrium payoff is captured at a symmetric NE. We provide a complete polyhedral characterization of all the NE for the twobuyer market game. Surprisingly, all the NE of this game turn out to be symmetric and the corresponding payoffs constitute a piecewise linear concave curve. We also study the correlated equilibria of this game and show that thirdparty mediation does not help to achieve a better payoff than NE payoffs.

Yonatan Aumann
and Yair Dombb.
Pareto Efficiency and Approximate Pareto Efficiency in Routing and Load Balancing Games
Abstract:
We analyze the Pareto efficiency, or inefficiency, of solutions to routing games and load balancing games, focusing on Nash equilibria and greedy solutions to these games. For some settings, we show that the solutions are necessarily Pareto optimal. When this is not the case, we provide a measure to quantify the distance of the solution from Pareto efficiency. Using this measure, we provide upper and lower bounds on the “Pareto inefficiency” of the different solutions. The settings we consider include load balancing games on identical, uniformlyrelated, and unrelated machines, both using pure and mixed strategies, and nonatomic routing in general and some specific networks.
Abstract:
We consider the computational complexity of coalitional solution concepts in scenarios related to load balancing such as anonymous and congestion games. In congestion games, Paretooptimal Nash and strong equilibria, which are resilient to coalitional deviations, have recently been shown to yield significantly smaller inefficiency. Unfortunately, we show that several problems regarding existence, recognition, and computation of these concepts are hard, even in seemingly special classes of games. In anonymous games with constant number of strategies, we can efficiently recognize a state as Paretooptimal Nash or strong equilibrium, but deciding existence for a game remains hard. In the case of playerspecific singleton congestion games, we show that recognition and computation of both concepts can be done efficiently. In addition, in these games there are always short sequences of coalitional improvement moves to Paretooptimal Nash and strong equilibria that can be computed efficiently.
Abstract:
We investigate the computational aspects of {\em safe manipulation}, a new model of coalitional manipulation that was recently put forward by Slinko and White. In this model, a potential manipulator $v$ announces how he intends to vote, and some of the other voters whose preferences coincide with those of $v$ may follow suit. Depending on the number of followers, the outcome could be better or worse for $v$ than the outcome of truthful voting. A manipulative vote is called safe if for some number of followers it improves the outcome from $v$'s perspective, and can never lead to a worse outcome. In this paper, we study the complexity of finding a safe manipulative vote for a number of common voting rules, including Plurality, Borda, $k$approval, and Bucklin, providing algorithms and hardness results for both weighted and unweighted voters. We also propose two ways to extend the notion of safe manipulation to the setting where the followers' preferences may differ from those of the leader, and study the computational properties of the resulting extensions.
Abstract:
Can learning algorithms ﬁnd a Nash equilibrium? This is a natural question for several reasons. Learning algorithms resemble the behavior of players in many naturally arising games, and thus results on the convergence or nonconvergence properties of such dynamics may inform our understanding of the applicability of Nash equilibria as a plausible solution concept in some settings. A second reason for asking this question is in the hope of being able to prove an impossibility result, not dependent on complexity assumptions, for computing Nash equilibria via a restricted class of reasonable algorithms. In this work, we begin to answer this question by considering the dynamics of the standard multiplicative weights update learning algorithms (which are known to converge to a Nash equilibrium for zerosum games). We revisit a 3 × 3 game deﬁned by Shapley [10] in the 1950s in order to establish that ﬁctitious play does not converge in general games. For this simple game, we show via a potential function argument that in a variety of settings the multiplicative updates algorithm impressively fails to ﬁnd the unique Nash equilibrium, in that the cumulative distributions of players produced by learning dynamics actually drift away from the equilibrium.
 Pranjal Awasthi, MariaFlorina Balcan,
Avrim Blum
, Or Sheffet and
Santosh Vempala
.
On NashEquilibria of ApproximationStable Games
Abstract:
One of the main reasons for wanting to compute a Nash equilibrium of a game is to predict how players will play. However, if the game has multiple equilibria that are far apart, or epsilonequilibria that are far in variation distance from the true Nash equilibrium strategies, then this prediction may not be possible even in principle. In this paper, we define the notion of games that are {\em approximation stable}, meaning that all epsilonapproximate equilibria are contained inside a small ball of radius Delta around a true equilibrium, and investigate a number of their properties. We show there exist 2player nbyn approximationstable games in which the Nash equilibrium and all approximate equilibria have support Omega(log n). On the other hand, we show all (epsilon,Delta)approximationstable games must have an epsilonequilibrium of support O((Delta^{2o(1)}/epsilon^2)log n), yielding an immediate n^{O((Delta^{2o(1)}/epsilon^2)log n)}time algorithm, improving over the bound of [LMM03] for games satisfying this condition. We in addition give improved bounds for the case that Delta and epsilon are sufficiently close together. We also consider an inverse property, namely that all {\em non}approximate equilibria are {\em far} from some true equilibrium, and give an efficient algorithm for games satisfying that condition.

Uriel Feige
and Inbal Talgam.
A Direct Reduction from kPlayer to 2Player Approximate Nash
Abstract:
We present a direct reduction from kplayer games to 2player games that preserves approximate Nash equilibrium. Previously, the computational equivalence of computing approximate Nash equilibrium in kplayer and 2player games was established via an indirect reduction. This included a sequence of works defining the complexity class PPAD, identifying complete problems for this class, showing that computing approximate Nash equilibrium for kplayer games is in PPAD, and reducing a PPADcomplete problem to computing approximate Nash equilibrium for 2player games. Our direct reduction makes no use of the concept of PPAD, thus eliminating some of the difficulties involved in following the known indirect reduction.
Abstract:
We study the computational complexity of finding stable outcomes in additivelyseparable symmetric hedonic games. These coalition formation games are specified by an undirected edgeweighted graph: nodes are players, an outcome of the game is a partition of the nodes into coalitions, and the utility of a node is the sum of incident edge weights in the same coalition. We consider several natural stability requirements defined in the economics literature. For all of them the existence of a stable outcome is guaranteed by a potential function argument, and local improvements will converge to a stable outcome. The different stability requirements correspond to different local search neighbourhoods. For different neighbourhood structures, our findings comprise positive results in the form of polynomialtime algorithms, and negative (PLScompleteness) results.
 Uri Nadav and Georgios Piliouras.
No Regret Learning in Oligopolies: Cournot vs Bertrand
Abstract:
Cournot and Bertrand oligopolies constitute the two most prevalent models of firm competition. The analysis of Nash equilibria in each model reveals a unique prediction about the stable state of the system. Quite alarmingly, despite the similarities of the two models, their projections expose a stark dichotomy. Under the Cournot model, where firms compete by strategically managing their output quantity, firms enjoy positive profits as the resulting market prices exceed that of the marginal costs. On the contrary, the Bertrand model, in which firms compete on price, predicts that a duopoly is enough to push prices down to the marginal cost level. This suggestion that duopoly will result in perfect competition, is commonly referred to in the economics literature as the ``Bertrand paradox''. In this paper, we move away from the safe haven of Nash equilibria as we analyze these models in disequilibrium under minimal behavioral hypotheses. Specifically, we assume that firms adapt their strategies over time, so that in hindsight their average payoffs are not exceeded by any single deviating strategy. Given this noregret guarantee, we show that in the case of Cournot oligopolies, the unique Nash equilibrium fully captures the emergent behavior. Notably, we prove that under natural assumptions the daily market characteristics converge to the unique Nash. In contrast, in the case of Bertrand oligopolies, a wide range of positive average payoff profiles can be sustained. Hence, under the assumption that firms have noregret the Bertrand paradox is resolved and both models arrive to the same conclusion that increased competition is necessary in order to achieve perfect pricing.
Abstract:
The king of refinements of Nash equilibrium is trembling hand perfection. We show that it is NPhard and SQRTSUMhard to decide if a given pure strategy Nash equilibrium of a given threeplayer game in strategic form with integer payoffs is trembling hand perfect. Analogous results are shown for a number of other solution concepts, including proper equilibrium, (the strategy part of) sequential equilbrium, quasiperfect equilibrium and CURB. The proofs all use a reduction from the problem of comparing the minmax value of a threeplayer game in strategic form to a given rational number. This problem was previously shown to be NPhard by Borgs et al., while a SQRTSUM hardness result is given in this paper. The latter proof yields bounds on the algebraic degree of the minmax value of a threeplayer game that may be of independent interest.
Abstract:
We propose a new convex optimization formulation for the Fisher market problem with linear utilities. Like the EisenbergGale formulation, the set of feasible points is a polyhedral convex set while the cost function is nonlinear; however, unlike that, the optimum is always attained at a vertex of this polytope. The convex cost function depends only on the initial endowments of the buyers. This formulation yields an easy simplexlike pivoting algorithm which is provably strongly polynomial for many special cases.

Matus Mihalak
and Jan Christoph Schlegel.
The price of anarchy in network creation games is
(mostly) constant
Abstract:
We study the price of anarchy and the structure of equilibria in network creation games. A network creation game (first defined and studied by Fabrikant et al. [3]) is played by n players {1,2,...,n}, each identified with a vertex of a graph (or network), where the strategy of player i, i = 1,...,n, is to build some edges adjacent to i. The cost of building an edge is á > 0, a fixed parameter of the game. The goal of every player is to minimize its creation cost plus its usage cost. The creation cost of player i is á times the number of built edges. In the SumGame (the original variant of Fabrikant et al. [3]) the usage cost of player i is the sum of distances from i to every node of the resulting graph. In the MaxGame (variant defined and studied by Demaine et al. [2]) the usage cost is the eccentricity of i in the resulting graph of the game. In this paper we improve previously known bounds on price of anarchy of the game (of both variants) for various ranges of á, and give new insights into the structure of equilibria for various values of á. The two main results of the paper show that for á > 249n all equilibria in SumGame are trees and thus the price of anarchy is constant, and that for á > 129 all equilibria in MaxGame are trees and the price of anarchy is constant. For SumGame this (almost) answers one of the arguably most prominent open problems in the field – is price of anarchy of the network creation game constant for all values of á? – in an affirmative way, up to a tiny range of á.
 Vijay Vazirani.
2Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties
Abstract:
The solution to a Nash or a nonsymmetric bargaining game is obtained by maximizing a concave function over a convex set, i.e., it is the solution to a convex program. We show that each 2player game whose convex program has linear constraints, admits a rational solution and such a solution can be found in polynomial time using only an LP solver. If in addition, the game is succinct, i.e., the coefficients in its concave program are ``small'', then its solution can be found in strongly polynomial time. We also give a nonsuccinct linear game whose solution can be found in strongly polynomial time.
 Volodymyr Kuleshov and
Adrian Vetta
.
On the Efficiency of Markets with TwoSided Proportional Allocation Mechanisms
Abstract:
We study the performance of resource allocation mechanisms in which both consumers and suppliers compete. Specifically, we examine a natural extension of Johari and Tsitsiklis' onesided mechanisms for demandcompetitive and supplycompetitive markets. Assuming suppliers have convex marginal costs, we show that the mechanism exhibits a price of anarchy of about $0.5887$, regardless of the number of goods in the market. This welfare ratio is achieved when the demandside is fully competitive and the supplyside is a duopoly. When marginal costs are not concave, the price of anarchy remains bounded and drops smoothly to zero as the marginal costs converge to a constant function. We complement these guarantees by identifying a broad class of mechanisms among which ours achieves the best possible price of anarchy. We present all our results in the context of sharing bandwidth on a network, and show how our mechanism can be used to coordinate the supply and consumption of network capacity.
Abstract:
We consider the existence of Partition Equilibrium in Resource Selection Games. Superstrong equilibrium, where no subset of players has an incentive to change their strategies collectively, does not always exist in such games. We show, however, that partition equilibrium (introduced by Feldman and Tenneholtz to model coalitions arising in a social context) always exists in general resource selection games, as well as how to compute it efficiently. In a partition equilibrium, the set of players has a fixed partition into coalitions, and the only deviations considered are by coalitions that are sets in this partition. Our algorithm to compute a partition equilibrium in any resource selection game (i.e., load balancing game) settles the previously open question about existence of partition equilibrium in general resource selection games. Moreover, we show how to always find a partition equilibrium which is also a Nash equilibrium. This implies that in resource selection games, we do not need to sacrifice the stability of individual players when forming solutions stable against coalitional deviations. In addition, while superstrong equilibrium may not exist in resource selection games, we show that its existence can be decided efficiently, and how to find one if it exists.
 Martin Macko, Kate Larson and Ľuboš Steskal.
Braess's Paradox for Flows Over Time
Abstract:
We study the properties of Braess's paradox in the context of the model of congestion games with flow over time introduced by Koch and Skutella. We compare them to the well known properties of Braess's paradox for Wardrop's model of games with static flows. We show that there are networks which do not admit Braess's paradox in Wardrop's model, but which admit it in the model with flow over time. Moreover, there is a topology that admits a significantly more severe Braess's ratio for this model. Further, despite its symmetry for games with static flow, we show that Braess's paradox is not symmetric for flows over time. We illustrate that there are network topologies which exhibit Braess's paradox, but for which the transpose does not. Finally, we conjecture a necessary and sufficient condition on existence of Braess's paradox in a network, and prove the condition on existence of the paradox either in the network or in its transpose.
Abstract:
Recent results showing PPADcompleteness of the problem of computing an equilibrium for Fisher's market model under additively separable, piecewiselinear, concave utilities dealt a serious blow to the program of obtaining efficient algorithms for computing market equilibria and has prompted a search for alternative models that are realistic as well as amenable to efficient computation. In this paper we show that introducing perfect price discrimination into the model stated above renders its equilibrium polynomial time computable. Moreover, its set of equilibria are captured by a convex program that generalizes the classical EisenbergGale program. Next, we introduce production into our model; our attempt here is to carve out as big a piece of the general production model as possible while still maintaining the attractive property that a single (rational) convex program captures its equilibria, i.e., the program optimizes individually for each buyer and each firm. We show an application of our price discrimination market model to the Internet advertisement market places that have recently emerged.
Abstract:
The class of \emph{weakly acyclic games}, which includes potential games and dominancesolvable games, captures many practical application domains. Informally, a weakly acyclic game is one where natural distributed dynamics, such as betterresponse dynamics, cannot enter \emph{inescapable oscillations}. We establish a novel link between such games and the existence of pure Nash equilibria in subgames. Specifically, we show that the existence of a \emph{unique} pure Nash equilibrium in every \emph{subgame} implies the weak acyclicity of a game. In contrast, we show that the existence of (potentially) \emph{multiple} pure Nash equilibria in every subgame is \emph{insufficient} for weak acyclicity.
Abstract:
Bounding the price of stability of undirected network design games with fair cost allocation is a challenging open problem in the Algorithmic Game Theory research agenda. Even though the generalization of such games in directed networks is well understood in terms of the price of stability (it is exactly $H_n$, the $n$th harmonic number, for games with $n$ players), far less is known for network design games in undirected networks. The upper bound carries over to this case as well while the best known lower bound is $42/23\approx 1.826$. For more restricted but interesting variants of such games such as broadcast and multicast games, sublogarithmic upper bounds are known while the best known lower bound is $12/7\approx 1.714$. In the current paper, we improve the lower bounds as follows. We break the psychological barrier of $2$ by showing that the price of stability of undirected network design games is at least $348/155\approx 2.245$. Our proof uses a recursive construction of a network design game with a simple gadget as the main building block. For broadcast and multicast games, we present new lower bounds of $20/11\approx 1.818$ and $1.862$, respectively.
Abstract:
We study the inefficiency of equilibrium outcomes in \emph{bottleneck congestion games}. These games model situations in which strategic players compete for a limited number of facilities. Each player allocates his weight to a (feasible) subset of the facilities with the goal to minimize the maximum (weightdependent) latency that he experiences on any of these facilities. We derive upper and (asymptotically) matching lower bounds on the (strong) price of anarchy of linear bottleneck congestion games for a natural load balancing social cost objective (i.e., minimize the maximum latency of a facility). We restrict our studies to linear latency functions. Linear bottleneck congestion games still constitute a rich class of games and generalize, for example, load balancing games with identical or uniformly related machines with or without restricted assignments.
 Rajgopal Kannan and
Costas Busch
.
Bottleneck Congestion Games with Logarithmic Price of Anarchy
Abstract:
We study {\em bottleneck congestion games} where the social cost is determined by the worst congestion on any resource. In the literature, bottleneck games assume user utility costs determined by the worst congested resource in their strategy. However, the Nash equilibria of such games are inefficient since the price of anarchy can be very high and proportional to the number of resources. In order to obtain smaller price of anarchy we introduce {\em exponential bottleneck games}, where the utility costs of the players are exponential functions of their congestions. In particular, the delay function for any resource $r$ is $\M^{C_r}$, where $C_r$ denotes the number of players that use $r$, and $\M$ is an integer constant. We find that exponential bottleneck games are very efficient and give the following bound on the price of anarchy: $O(\log R)$, where $R$ is the set of resources. This price of anarchy is tight, since we demonstrate a game with price of anarchy $\Omega(\log R)$. We obtain our tight bounds by using two novel proof techniques: {\em transformation}, which we use to convert arbitrary games to simpler games, and {\em expansion}, which we use to bound the price of anarchy in a simpler game.