Shubik's (all-pay) dollar auction is a simple yet powerful auction model that aims to shed light on the motives and dynamics of conflict escalation. Common intuition and experimental results suggest that the dollar auction is a trap, inducing conflict by its very design. However, O'Neill proved the surprising fact that, contrary to the experimental results and the intuition, the dollar auction has an immediate solution in pure strategies, i.e., theoretically it should not lead to conflict escalation. In this paper, inspired by the recent literature on spiteful bidders, we ask whether the escalation in the dollar auction can be induced by meanness. Our results confirm this conjecture in various scenarios.

We study the problem of designing envy-free sponsored search auctions, where bidders are budget-constrained. Our primary goal is to design auctions that maximize social welfare and revenue — two classical objectives in auction theory. For this purpose, we characterize envy-freeness with budgets by proving several elementary properties including consistency, monotonicity and transitivity. Based on this characterization, we come up with an envy-free auction, that is both social-optimal and bidder-optimal for a wide class of bidder types. More generally, for all bidder types, we provide two polynomial time approximation schemes (PTASs) for maximizing social welfare or revenue, where the notion of envy-freeness has been relaxed slightly. Finally, in cases where randomization is allowed in designing auctions, we devise similar PTASs for social welfare or revenue maximization problems.

Weighted voting games allow for studying the distribution of power between agents in situations of collective decision making. While the conventional version of these games assumes that any agent is always ready to cooperate with all others, recently, more involved models have been proposed, where cooperation is subject to restrictions. Following Myerson [1977], such restrictions are typically represented by a graph that expresses available communication links among agents. In this paper, we study the time complexity of computing two well-known power indices - the Shapley-Shubik index and the Banzhaf index - in the graph-restricted weighted voting games. We show that both are #P-complete and propose a dedicated dynamic-programming algorithm that runs in pseudo-polynomial time for graphs with the bounded treewidth.

Hedonic games provide a natural model of coalition formation among self-interested agents. The associated problem of finding stable outcomes in such games has been extensively studied. In this paper, we identify simple conditions on expressivity of hedonic games that are sufficient for the problem of checking whether a given game admits a stable outcome to be computationally hard. Somewhat surprisingly, these conditions are very mild and intuitive. Our results apply to a wide range of stability concepts (core stability, individual stability, Nash stability, etc.) and to many known formalisms for hedonic games (additively separable games, games with W-preferences, fractional hedonic games, etc.), and unify and extend known results for these formalisms. They also have broader applicability: for several classes of hedonic games whose computational complexity has not been explored in prior work, we show that our framework immediately implies a number of hardness results for them.

In 1990, Thomas Schwartz proposed the conjecture that every nonempty tournament has a unique minimal TEQ-retentive set (TEQ stands for tournament equilibrium set). A weak variant of Schwartz's Conjecture was recently proposed by Felix Brandt. However, both conjectures were disproved very recently by two counterexamples. In this paper, we prove sufficient conditions for infinite classes of tournaments that satisfy Schwartz's Conjecture and Brandt's Conjecture. Moreover, we prove that TEQ can be calculated in polynomial time in several infinite classes of tournaments. Furthermore, our results reveal some structures that are forbidden in every counterexample to Schwartz's Conjecture.

We study truthful mechanisms in the context of cake cutting when agents not only value their own pieces of cake but also care for the pieces assigned to other agents. In particular, agents derive benefits or costs from the pieces of cake assigned to other agents. This phenomenon is often referred to as positive or negative externalities. We propose and study the following model: given an allocation, externalities of agents are modeled as percentages of the reported values that other agents have for their pieces. We show that even in this restricted class of externalities, under some natural assumptions, no truthful cake cutting mechanisms exist when externalities are either positive or negative. However, when the percentages agents get from each other are small, we show that there exists a truthful cake cutting mechanism with other desired properties.

Our work deals with the important problem of globally characterizing truthful mechanisms where players have multi-parameter, additive valuations, like scheduling unrelated machines or additive combinatorial auctions. Very few mechanisms are known for these settings and the question is: Can we prove that no other truthful mechanisms exist? We characterize truthful mechanisms for n players and 2 tasks or items, as either task-independent, or a player-grouping minimizer, a new class of mechanisms we discover, which generalizes affine minimizers. We assume decisiveness, strong monotonicity and that the truthful payments (The (normalized) payments are uniquely determined by the allocation function of the mechanism; thus the assumptions concern properties of the allocation.) are continuous functions of players' bids.

Allocation games are coalitional games defined in the literature as a way to analyze fair division problems of indivisible goods. The prototypical solution concepts for them are the Shapley value and the Banzhaf value. Unfortunately, their computation is intractable, formally #P-hard. Motivated by this bad news, structural requirements are investigated which can be used to identify islands of tractability. The main result is that, over the class of allocation games, the Shapley value and the Banzhaf value can be computed in polynomial time when interactions among agents can be formalized as graphs of bounded treewidth. This is shown by means of technical tools that are of interest in their own and that can be used for analyzing different kinds of coalitional games. Tractability is also shown for games where each good can be assigned to at most two agents, independently of their interactions.

We study voting games on binary issues, where voters might hold an objective over some issues at stake, while willing to strike deals on the remaining ones, and can influence one another’s voting decision before the vote takes place. We analyse voters’ rational behaviour in the resulting two-phase game, showing under what conditions undesirable equilibria can be removed as an effect of the pre-vote phase.

A key challenge in solving extensive-form games is dealing with large, or even infinite, action spaces. In games of imperfect information, the leading approach is to find a Nash equilibrium in a smaller abstract version of the game that includes only a few actions at each decision point, and then map the solution back to the original game. However, it is difficult to know which actions should be included in the abstraction without first solving the game, and it is infeasible to solve the game without first abstracting it. We introduce a method that combines abstraction with equilibrium finding by enabling actions to be added to the abstraction at run time. This allows an agent to begin learning with a coarse abstraction, and then to strategically insert actions at points that the strategy computed in the current abstraction deems important. The algorithm can quickly add actions to the abstraction while provably not having to restart the equilibrium finding. It enables anytime convergence to a Nash equilibrium of the full game even in infinite games. Experiments show it can outperform fixed abstractions at every stage of the run: early on it improves as quickly as equilibrium finding in coarse abstractions, and later it converges to a better solution than does equilibrium finding in fine-grained abstractions.