Most models of Stackelberg security games assume that the attacker only knows the defender's mixed strategy, but is not able to observe (even partially) the instantiated pure strategy. Such partial observation of the deployed pure strategy -- an issue we refer to as information leakage -- is a significant concern in practical applications. While previous research on patrolling games has considered the attacker's real-time surveillance, our settings, therefore models and techniques, are fundamentally different. More specifically, after describing the information leakage model, we start with an LP formulation to compute the defender's optimal strategy in the presence of leakage. Perhaps surprisingly, we show that a key subproblem to solve this LP (more precisely, the defender oracle) is NP-hard even for the simplest of security game models. We then approach the problem from three possible directions: efficient algorithms for restricted cases, approximation algorithms, and heuristic algorithms for sampling that improves upon the status quo. Our experiments confirm the necessity of handling information leakage and the advantage of our algorithms.

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.

Cepheus is the first computer program to essentially solve a game of imperfect information that is played competitively by humans. The game it plays is heads-up limit Texas hold'em poker, a game with over 10^14 information sets, and a challenge problem for artificial intelligence for over 10 years. Cepheus was trained using a new variant of Counterfactual Regret Minimization (CFR), called CFR+, using 4800 CPUs running for 68 days. In this paper we describe in detail the engineering details required to make this computation a reality. We also prove the theoretical soundness of CFR+ and its component algorithm, regret-matching+. We further give a hint towards understanding the success of CFR+ by proving a tracking regret bound for this new regret matching algorithm. We present results showing the role of the algorithmic components and the engineering choices to the success of CFR+.

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.

Stackelberg game models of security have received much attention, with a number of approaches for computing Stackelberg equilibria in games with a single defender protecting a collection of targets. In contrast, multi-defender security games have received significantly less attention, particularly when each defender protects more than a single target. We fill this gap by considering a multidefender security game, with a focus on theoretical characterizations of equilibria and the price of anarchy. We present the analysis of three models of increasing generality, two in which each defender protects multiple targets. In all models, we find that the defenders often have the incentive to overprotect the targets, at times significantly. Additionally, in the simpler models, we find that the price of anarchy is unbounded, linearly increasing both in the number of defenders and the number of targets per defender. Surprisingly, when we consider a more general model, this results obtains only in a “corner” case in the space of parameters; in most cases, however, the price of anarchy converges to a constant when the number of defenders increases.

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.

Motivated by a radically new peer review system that the National Science Foundation recently experimented with, we study peer review systems in which proposals are reviewed by PIs who have submitted proposals themselves. An (m,k)-selection mechanism asks each PI to review m proposals, and uses these reviews to select (at most) k proposals. We are interested in impartial mechanisms, which guarantee that the ratings given by a PI to others' proposals do not affect the likelihood of the PI's own proposal being selected. We design an impartial mechanism that selects a k-subset of proposals that is nearly as highly rated as the one selected by the non-impartial (abstract version of) the NSF pilot mechanism, even when the latter mechanism has the "unfair" advantage of eliciting honest reviews.