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.

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.

We study the tournament fixing problem (TFP), which asks whether a tournament organizer can rig a single-elimination (SE) tournament such that their favorite player wins, simply by adjusting the initial seeding. Prior results give two perspectives of TFP: on the one hand, deciding whether an arbitrary player can win any SE tournament is known to be NP-complete; on the other hand, there are a number of known conditions, under which a player is guaranteed to win some SE tournament. We extend and connect both these lines of work. We show that for a number of structured variants of the problem, where our player is seemingly strong, deciding whether the player can win any tournament is still NP-complete. Dual to this hardness result, we characterize a new set of sufficient conditions for a player to win a tournament. Further, we give an improved exact algorithm for deciding whether a player can win a tournament.

They concluded that UCT quickly finds Self-play Monte Carlo Tree Search (MCTS) has a good but suboptimal policy, while Outcome Sampling initially been successful in many perfect-information twoplayer learns more slowly but converges to the optimal policy games. Although these methods have been over time. In this paper, we address the question whether the extended to imperfect-information games, so far inability of UCT to converge to a Nash equilibrium can be they have not achieved the same level of practical overcome while retaining UCT's fast initial learning rate. We success or theoretical convergence guarantees focus on the full-game MCTS setting, which is an important as competing methods. In this paper we step towards developing sound variants of online MCTS in introduce Smooth UCT, a variant of the established imperfect-information games. Upper Confidence Bounds Applied to Trees In particular, we introduce Smooth UCT, which combines (UCT) algorithm.