#### Introduction to the Special Issue on EC'14

Vincent Conitzer and David Easley#### Do Capacity Constraints Constrain Coalitions?

Michal Feldman; Ofir GeriWe study strong equilibria in symmetric capacitated cost-sharing games.

In these games, a graph with designated source s and sink t is given, and each edge is associated with some cost.

Each agent chooses strategically an s-t path, knowing that the cost of each edge is shared equally between all agents using it.

Two variants of cost-sharing games have been previously studied: (i) games where coalitions can form, and (ii) games where edges are associated with capacities; both variants are inspired by real-life scenarios.

In this work we combine these variants and analyze strong equilibria (profiles where no coalition can deviate) in capacitated games.

This combination gives rise to new phenomena that do not occur in the previous variants.

Our contribution is two-fold.

First, we provide a topological characterization of networks that always admit a strong equilibrium.

Second, we establish tight bounds on the efficiency loss that may be incurred due to strategic behavior, as quantified by the strong price of anarchy (and stability) measures.

Interestingly, our results are qualitatively different than those obtained in the analysis of each variant alone, and the combination of coalitions and capacities entails the introduction of more refined topology classes than previously studied.

#### Computing Dominance-Based Solution Concepts

Felix Brandt; Markus BrillTwo common criticisms of Nash equilibrium are its dependence on very demanding epistemic assumptions and its computational intractability. We study the computational properties of less demanding set-valued solution concepts that are based on varying notions of dominance. These concepts are intuitively appealing, always exist, and admit unique minimal solutions in important subclasses of games. Examples include Shapley's saddles, Harsanyi and Selten's primitive formations, Basu and Weibull's CURB sets, and Dutta and Laslier's minimal covering set. Based on a unifying framework proposed by Duggan and Le Breton, we formulate two generic algorithms for computing these concepts and investigate for which classes of games and which properties of the underlying dominance notion the algorithms are sound and efficient. We identify two sets of conditions that are sufficient for polynomial-time computability and show that the conditions are satisfied, for instance, by saddles and primitive formations in normal-form games, minimal CURB sets in two-player games, and the minimal covering set in symmetric matrix games. Our positive algorithmic results explain regularities observed in the literature, but also apply to several solution concepts whose computational complexity was unknown.

#### A Rational Convex Program for Linear Arrow-Debreu Markets

Nikhil R. Devanur, PhD; Jugal Garg, PhD; Lá szló A. Vé gh, Ph.D.We give a new, flow-type convex program describing equilibrium solutions to linear Arrow-Debreu markets. Whereas convex formulations were previously known ([Nenakov and Primak 1983; Jain 2007; Cornet 1989]), our program exhibits several new features. It gives a simple necessary and sufficient condition and a concise proof of the existence and rationality of equilibria, settling an open question raised by Vazirani [2012]. As a consequence we also obtain a simple new proof of Mertens's [2003] result that the equilibrium prices form a convex polyhedral set.

#### Truthful Mechanisms for Combinatorial Allocation of Electric Power in Alternating Current Electric Systems for Smart Grid

Khaled Elbassioni; Chi-Kin Chau; Majid KhonjiTraditional studies of combinatorial auctions often only consider linear constraints. The rise of smart grid presents a new class of auctions, characterized by quadratic constraints. This paper studies the {\em complex-demand knapsack problem}, in which the demands are complex-valued and the capacity of supplies is described by the magnitude of total complex-valued demand. This naturally captures the power constraints in alternating current (AC) electric systems. In this paper, we provide a more complete study and generalize the problem to the multi-minded version, beyond the previously known $\frac{1}{2}$-approximation algorithm for only a subclass of the problem. More precisely, we give a truthful PTAS for the case $\phi\in[0,\frac{\pi}{2}-\delta]$, and a truthful FPTAS, which {\it fully} optimizes the objective function but violates the capacity constraint by at most $(1+\epsilon)$, for the case $\phi\in(\frac{\pi}{2},\pi-\delta]$, where $\phi$ is the maximum angle between any two complex-valued demands and $\epsilon,\delta>0$ are arbitrarily small constants. We complement these results by showing that, unless P=NP, neither a PTAS can exist for the case $\phi\in(\frac{\pi}{2},\pi-\delta]$ nor any bi-criteria approximation algorithm with polynomial guarantees for the case when $\phi$ is arbitrarily close to $\pi$ (that is, when $\delta$ is arbitrarily close $0$).

#### Risk Sensitivity of Price of Anarchy under Uncertainty

Georgios Piliouras; Evdokia Nikolova; Jeff S. ShammaIn game theory, the price of anarchy framework studies efficiency loss in decentralized environments. Optimization and decision theory, on the other hand, explore tradeoffs between optimality and robustness in the case of single agent decision making under uncertainty. If an agent guards against worst case guarantees, then his actions tend to be suboptimal on average.

We examine connections between the efficiency loss due to decentralization and the efficiency loss due to uncertainty and establish tight performance guarantees for distributed systems in uncertain environments. We present applications of this framework to novel variants of atomic congestion games with uncertain costs, for which we provide tight performance bounds under a wide range of risk attitudes. Our results establish that the individual's attitude towards uncertainty has a critical effect on system performance and therefore should be a subject of close and systematic investigation.

#### Optimal Contests for Simple Agents

Arpita Ghosh; Robert KleinbergIncentives are more likely to elicit desired outcomes when they are designed based on accurate models of agents' strategic behavior. A growing literature, however, suggests that people do not quite behave like standard economic agents in a variety of environments, both online and offline. What consequences might such differences have for the optimal {\em design} of mechanisms in these environments? In this paper, we explore this question in the context of optimal contest design for {\em simple} agents---agents who strategically reason about whether or not to participate in a system, but not about the input they provide to it. Specifically, consider a contest where $n$ potential contestants with types $(q_i,c_i)$ each choose between participating and producing a submission of quality $q_i$ at cost $c_i$, versus not participating at all, to maximize their utilities. How should a principal distribute a total prize $V$ amongst the $n$ ranks to maximize some increasing function of the qualities of elicited submissions in a contest with such simple agents? We first solve the optimal contest design problem for settings where agents have homogenous participation costs $c_i = c$. Here, the contest that maximizes every increasing function of the elicited contributions is always a {\em simple} contest, awarding equal prizes of $V/j^*$ each to the top $j^* =V/c - \Theta(\sqrt{V/(c\ln(V/c))})$ contestants. This is in contrast with the optimal contest structure in comparable models with strategic effort choices, where the optimal contest is either a winner-take-all contest or awards possibly unequal prizes, depending on the curvature of agents' effort cost functions. We next address the general case with heterogenous costs where agents' types $(q_i,c_i)$ are inherently two-dimensional, significantly complicating equilibrium analysis. With heterogenous costs, the optimal contest depends on the objective being maximized: our main result here is that the winner-take-all contest is a 3-approximation of the optimal contest when the principal's objective is to maximize the quality of the best elicited contribution. The proof of this result hinges around a `sub-equilibrium' lemma establishing a stochastic dominance relation between the distribution of qualities elicited in an equilibrium and a {\em sub-equilibrium}---a strategy profile that is a best response for all agents who choose to {\em participate} in that strategy profile; this relation between equilibria and sub-equilibria may be of more general interest.

#### Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries

John Fearnley; Rahul SavaniWe study the deterministic and randomized query complexity of finding approximate equilibria in a $k \times k$ bimatrix game. We show that the deterministic query complexity of finding an $\epsilon$-Nash equilibrium when $\epsilon < \frac{1}{2}$ is $\Omega(k^2)$, even in zero-one constant-sum games. In combination with previous results~\cite{FGGS13}, this provides a complete characterization of the deterministic query complexity of approximate Nash equilibria. We also study randomized querying algorithms. We give a randomized algorithm for finding a $(\frac{3 - \sqrt{5}}{2} + \epsilon)$-Nash equilibrium using $O(\frac{k \cdot \log k}{\epsilon^2})$ payoff queries, which shows that the $\frac{1}{2}$ barrier for deterministic algorithms can be broken by randomization. For well-supported Nash equilibria (WSNE), we first give a randomized algorithm for finding an $\epsilon$-WSNE of a zero-sum bimatrix game using $O(\frac{k \cdot \log k}{\epsilon^4})$ payoff queries, and we then use this to obtain a randomized algorithm for finding a $(\frac{2}{3} + \epsilon)$-WSNE in a general bimatrix game using $O(\frac{k \cdot \log k}{\epsilon^4})$ payoff queries. Finally, we initiate the study of lower bounds against randomized algorithms in the context of bimatrix games, by showing that randomized algorithms require $\Omega(k^2)$ payoff queries in order to find a $\frac{1}{6k}$-Nash equilibrium, even in zero-one constant-sum games. In particular, this rules out query-efficient randomized algorithms for finding exact Nash equilibria.

#### Robust Quantitative Comparative Statics for a Multimarket Paradox

Tobias Harks; Philipp von FalkenhausenWe introduce a quantitative approach to comparative statics that allows to bound the maximum effect of an exogenous parameter change on a system's equilibrium. The motivation for this approach is a well known paradox in multimarket Cournot competition, where a positive price shock on a monopoly market may actually reduce the monopolist's profit. We use our approach to quantify for the first time the worst case profit reduction for multimarket oligopolies exposed to arbitrary positive price shocks. For markets with affine price functions and firms with convex cost technologies, we show that the relative profit loss of \emph{any} firm is at most 25% no matter how many firms compete in the oligopoly. We further investigate the impact of positive price shocks on total profit of all firms as well as on social surplus. We find tight bounds also for these measures showing that total profit and social surplus decreases by at most 25% and 16.6%, respectively.

#### Recency, Records and Recaps: Learning and Non-equilibrium Behavior in a Simple Decision Problem

Alexander Peysakhovich; Drew FudenbergNash equilibrium takes optimization as a primitive, but suboptimal behavior can persist in simple stochastic decision problems. This has motivated the development of other equilibrium concepts such as cursed equilibrium and behavioral equilibrium. We experimentally study a simple adverse selection (or "lemons") problem and find that learning models that heavily discount past information (i.e. display recency bias) explain patterns of behavior better than Nash, cursed or behavioral equilibrium. Providing counterfactual information or a record of past outcomes does little to aid convergence to optimal strategies, but providing sample averages ("recaps") gets individuals most of the way to optimality. Thus recency effects are not solely due to limited memory but stem from some other form of cognitive constraints. Our results show the importance of going beyond static optimization and incorporating features of human learning into economic models.

#### Bounds for the Query Complexity of Approximate Equilibria

Paul Goldberg; Aaron RothWe analyze the number of payoff queries needed to compute approximate equilibria of multi-player games. We find that query complexity is an effective tool for distinguishing the computational difficulty of alternative solution concepts, and we develop new techniques for upper- and lower bounding the query complexity. For binary-choice games, we show logarithmic upper and lower bounds on the query complexity of approximate correlated equilibrium. For {\em well-supported} approximate correlated equilibrium (a restriction where a player's behavior must always be approximately optimal, in the worst case over draws from the distribution) we show a linear lower bound, thus separating the query complexity of well supported approximate correlated equilibrium from the standard notion of approximate correlated equilibrium. Finally, we give a query-efficient reduction from the problem of \emph{computing} an approximate well-supported Nash equilibrium to the problem of verifying a well supported Nash equilibrium, where the additional query overhead is proportional to the description length of the game. This gives a polynomial-query algorithm for computing well supported approximate Nash equilibria (and hence correlated equilibria) in concisely represented games. We identify a class of games (which includes congestion games) in which the reduction can be made not only query efficient, but also computationally efficient.

#### The Complexity of Fairness through Equilibrium

Abraham Othman; Christos Papadimitriou; Aviad RubinsteinCompetitive Equilibrium from Equal Incomes (CEEI) is a well-known fair allocation mechanism with desirable fairness and efficiency properties, but with indivisible resources a CEEI may not exist [Foley 1967; Varian 1974; Thomson and Varian 1985]. It was shown in Budish [2011] that in the case of indivisible resources there is always an allocation, called A-CEEI, that is approximately fair, approximately truthful, and approximately efficient, for some favorable approximation parameters. A heuristic search that attempts to find this approximation is used in practice to assign business school students to courses. In this paper we show that finding the A-CEEI allocation guaranteed to exist by Budish's theorem is PPAD-complete. We further show that finding an approximate equilibrium with better approximation guarantees is even harder: NP-complete.

#### Local Computation Mechanism Design

Avinatah Hassidim; Yishay Mansour; Shai VardiWe introduce the notion of ``local computation mechanism design'' - designing game theoretic mechanisms that run in polylogarithmic time and space. Local computation mechanisms reply to each query in polylogarithmic time and space, and the replies to different queries are consistent with the same global feasible solution. When the mechanism employs payments, the computation of the payments is also done in polylogarithmic time and space. Furthermore, the mechanism needs to maintain incentive compatibility with respect to the allocation and payments. We present local computation mechanisms for a variety of classical game-theoretical problems: (1) stable matching, (2) job scheduling, (3) combinatorial auctions for unit-demand and k-minded bidders, and (4) the housing allocation problem. For stable matching, some of our techniques may have implications to the global (non-LCA) setting. Specifically, we show that when the men's preference lists are bounded, we can achieve an arbitrarily good approximation to the stable matching within a fixed number of iterations of the Gale-Shapley algorithm.

#### On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions

Allan Borodin, Ph.D.; Brendan Lucier, PHDWe study mechanisms for the combinatorial auction (CA) problem, in which $m$ objec

ts are sold to rational agents and the goal is to maximize social welfare.Of particular interest is the special case of $s$-CAs, where agents are interested in sets of size at most $s$, for which a simple greedy algorithm obtains an $s+1$

approximation but no deterministictruthful mechanism is known to attain an approximation ratio better than $O(m/\sqr

t{\log m})$. We view this as an extreme gap not only between

the power of greedy auctions and truthful greedy auctions, but also as

%an apparent

a conjectured largest gap between the known power of truthful and non-truthfulpolynomial time deterministic algorithms. We associate the notion of greediness with a broad class of algorithms, known as priority algorithms, which encapsulates many natural auction methods. This motivates us to ask: how well can a truthful greedy algorithm approximate the optimal social welfare for CA problems? We show that no truthful greedy priority algorithm can obtain an approximation to the CA problem that is sublinear in $m$, even for $s$-CAs with $s \geq 2$. We conclude that any truthful combinatorial auction mechanism with non-trivial approximation fact

or must fall outside the scope of many natural auction methods.

#### When Does Improved Targeting Increase Revenue?

Patrick Hummel; Preston McAfeeIn second-price auctions with symmetric bidders, we find that improved targeting via enhanced information disclosure decreases revenue when there are two bidders and increases revenue if there are at least four bidders. With asymmetries, improved targeting increases revenue if the most frequent winner wins less than 30.4% of the time, but can decrease revenue otherwise. We derive analogous results for position auctions. Finally, we show that revenue can vary non-monotonically with the number of bidders who are able to take advantage of improved targeting.

#### Mechanism Design for Fair Division: Allocating Divisible Items without Payments

Richard Cole; Vasilis Gkatzelis; Gagan GoelWe revisit the classic problem of fair division from a mechanism design perspective, using {\em Proportional Fairness} as a benchmark. In particular, we aim to allocate a collection of divisible items to a set of agents while incentivizing the agents to be truthful in reporting their valuations. For the very large class of homogeneous valuations, we design a truthful mechanism that provides {\em every agent} with at least a $1/e\approx 0.368$ fraction of her Proportionally Fair valuation. To complement this result, we show that no truthful mechanism can guarantee more than a $0.5$ fraction, even for the restricted class of additive linear valuations. We also propose another mechanism for additive linear valuations that works really well when every item is highly demanded. To guarantee truthfulness, our mechanisms discard a carefully chosen fraction of the allocated resources; we conclude by uncovering interesting connections between our mechanisms and known mechanisms that use money instead.

#### The AND-OR Game

Avinatan Hassidim; Haim Kaplan; Yishay Mansour; noam nisanWe consider a simple simultaneous first price auction for two

identical items in a complete information setting. Our goal is to analyze this setting, for a simple, yet highly interesting, AND-OR game, where one agent is single minded and the other is unit demand. We find a mixed equilibrium

of this game, and show that every other equilibrium admits the same expected allocation and payments. In addition, we study the equilibrium, highlighting the change in revenue and social welfare as a function of the players' valuations.

#### Affine Maximizers in Domains with Selfish Valuations

Swaprava Nath, PhD; Arunava Sen, PhDWe consider the domain of selfish and continuous preferences over a ``rich'' allocation space and show that onto, strategyproof and allocation non-bossy social choice functions are affine maximizers. Roberts (1979) proves this result for a finite set of alternatives and an unrestricted valuation space. In this paper, we show that in a sub-domain of the unrestricted valuations with the additional assumption of allocation non-bossiness, using the richness of the allocations, the strategyproof social choice functions can be shown to be affine maximizers. We provide an example to show that allocation non-bossiness is indeed critical for this result. This work shows that an affine maximizer result needs certain amount of richness split across valuations and allocations.