Deng, Yuan (Duke University) | Conitzer, Vincent (Duke University)

Much recent work in the AI community concerns algorithms for computing optimal mixed strategies to commit to, as well as the deployment of such algorithms in real security applications. Another possibility is to commit not to play certain actions. If only one player makes such a commitment, then this is generally less powerful than completely committing to a single mixed strategy. However, if players can alternatingly commit not to play certain actions and thereby iteratively reduce their strategy spaces, then desirable outcomes can be obtained that would not have been possible with just a single player committing to a mixed strategy. We refer to such a setting as a disarmament game. In this paper, we study disarmament for two-player normal-form games. We show that deciding whether an outcome can be obtained with disarmament is NP-complete (even for a fixed number of rounds), if only pure strategies can be removed. On the other hand, for the case where mixed strategies can be removed, we provide a folk theorem that shows that all desirable utility profiles can be obtained, and give an efficient algorithm for (approximately) obtaining them.

Albert, Michael (Duke University) | Conitzer, Vincent (Duke University) | Stone, Peter (University of Texas at Austin)

We introduce a new class of mechanisms, robust mechanisms, that is an intermediary between ex-post mechanisms and Bayesian mechanisms. This new class of mechanisms allows the mechanism designer to incorporate imprecise estimates of the distribution over bidder valuations in a way that provides strong guarantees that the mechanism will perform at least as well as ex-post mechanisms, while in many cases performing better. We further extend this class to mechanisms that are with high probability incentive compatible and individually rational, ε-robust mechanisms. Using techniques from automated mechanism design and robust optimization, we provide an algorithm polynomial in the number of bidder types to design robust and ε-robust mechanisms. We show experimentally that this new class of mechanisms can significantly outperform traditional mechanism design techniques when the mechanism designer has an estimate of the distribution and the bidder’s valuation is correlated with an externally verifiable signal.

Albert, Michael (University of Texas at Austin) | Conitzer, Vincent (Duke University) | Lopomo, Giuseppe (Duke University)

In a landmark paper in the mechanism design literature, Cremer and McLean (1985) (CM for short) show that when a bidder’s valuation is correlated with an external signal, a monopolistic seller is able to extract the full social surplus as revenue. In the original paper and subsequent literature, the focus has been on ex-post incentive compatible (or IC) mechanisms, where truth telling is an ex-post Nash equilibrium. In this paper, we explore the implications of Bayesian versus ex-post IC in a correlated valuation setting. We generalize the full extraction result to settings that do not satisfy the assumptions of CM. In particular, we give necessary and sufficient conditions for full extraction that strictly relax the original conditions given in CM. These more general conditions characterize the situations under which requiring ex-post IC leads to a decrease in expected revenue relative to Bayesian IC. We also demonstrate that the expected revenue from the optimal ex-post IC mechanism guarantees at most a (|Θ| + 1)/4 approximation to that of a Bayesian IC mechanism, where |Θ| is the number of bidder types. Finally, using techniques from automated mechanism design, we show that, for randomly generated distributions, the average expected revenue achieved by Bayesian IC mechanisms is significantly larger than that for ex-post IC mechanisms.

Brill, Markus (Duke University) | Freeman, Rupert (Duke University) | Conitzer, Vincent (Duke University)

In many multiagent environments, a designer has some, but limited control over the game being played. In this paper, we formalize this by considering incompletely specified games, in which some entries of the payoff matrices can be chosen from a specified set. We show that it is NP-hard for the designer to make this choices optimally, even in zero-sum games. In fact, it is already intractable to decide whether a given action is (potentially or necessarily) played in equilibrium. We also consider incompletely specified symmetric games in which all completions are required to be symmetric. Here, hardness holds even in weak tournament games (symmetric zero-sum games whose entries are all -1, 0, or 1) and in tournament games (symmetric zero-sum games whose non-diagonal entries are all -1 or 1). The latter result settles the complexity of the possible and necessary winner problems for a social-choice-theoretic solution concept known as the bipartisan set. We finally give a mixed-integer linear programming formulation for weak tournament games and evaluate it experimentally.

Conitzer, Vincent (Duke University) | Freeman, Rupert (Duke University) | Brill, Markus (Duke University) | Li, Yuqian (Duke University)

We study the societal tradeoffs problem, where a set of voters each submit their ideal tradeoff value between each pair of activities (e.g., "using a gallon of gasoline is as bad as creating 2 bags of landfill trash"), and these are then aggregated into the societal tradeoff vector using a rule. We introduce the family of distance-based rules and show that these can be justified as maximum likelihood estimators of the truth. Within this family, we single out the logarithmic distance-based rule as especially appealing based on a social-choice-theoretic axiomatization. We give an efficient algorithm for executing this rule as well as an approximate hill climbing algorithm, and evaluate these experimentally.

Moon, Catherine (Duke University) | Conitzer, Vincent (Duke University)

Standard results on and algorithms for repeated games assume that defections are instantly observable. In reality, it may take some time for the knowledge that a defection has occurred to propagate through the social network. How does this affect the structure of equilibria and algorithms for computing them? In this paper, we consider games with cooperation and defection. We prove that there exists a unique maximal set of forever-cooperating agents in equilibrium and give an efficient algorithm for computing it. We then evaluate this algorithm on random graphs and find experimentally that there appears to be a phase transition between cooperation everywhere and defection everywhere, based on the value of cooperation and the discount factor. Finally, we provide a condition for when the equilibrium found is credible, in the sense that agents are in fact motivated to punish deviating agents. We find that this condition always holds in our experiments, provided the graphs are sufficiently large.

Li, Yuqian (Duke University) | Conitzer, Vincent (Duke University)

In cooperative game theory, it is typically assumed that the value of each coalition is known. We depart from this, assuming that v(S) is only a noisy estimate of the true value V (S), which is not yet known. In this context, we investigate which solution concepts maximize the probability of ex-post stability (after the true values are revealed). We show how various conditions on the noise characterize the least core and the nucleolus as optimal. Modifying some aspects of these conditions to (arguably) make them more realistic, we obtain characterizations of new solution concepts as being optimal, including the partial nucleolus, the multiplicative least core, and the multiplicative nucleolus.

Xu, Haifeng (University of Southern California) | Fang, Fei (University of Southern California) | Jiang, Albert Xin (University of Southern California) | Conitzer, Vincent (Duke University) | Dughmi, Shaddin (University of Southern California) | Tambe, Milind (University of Southern California)

Among the many deployment areas of Stackelberg Security games, a major area involves games played out in space and time, which includes applications in multiple mobile defender resources protecting multiple mobile targets. Previous algorithms for such spatio-temporal security games fail to scale-up and little is known ofthe computational complexity properties of these problems.This paper provides a novel oracle-based algorithmic framework for a systematic study of different problem variants of computing optimal (minimax) strategies in spatio-temporal security games. Our framework enables efficient computation of a minimax strategy when the problem admits a polynomial-time oracle. Furthermore,for the cases in which efficient oracles are difficultto find, we propose approximations or prove hardness results.

Sørensen, Troels Bjerre (IT-University of Copenhagen) | Dalis, Melissa (Duke University) | Letchford, Joshua (Duke University) | Korzhyk, Dmytro (Duke University) | Conitzer, Vincent (Duke University)

Gambles in casinos are usually set up so that the casino makes a profit in expectation -- as long as gamblers play honestly. However, some gamblers are able to cheat, reducing the casino’s profit. How should the casino address this? A common strategy is to selectively kick gamblers out, possibly even without being sure that they were cheating. In this paper, we address the following question: Based solely on a gambler’s track record,when is it optimal for the casino to kick the gambler out? Because cheaters will adapt to the casino’s policy, this is a game-theoretic question. Specifically, we model the problem as a Bayesian game in which the casino is a Stackelberg leader that can commit to a (possibly randomized) policy for when to kick gamblers out, and we provide efficient algorithms for computing the optimal policy. Besides being potentially useful to casinos, we imagine that similar techniques could be useful for addressing related problems -- for example, illegal trades in financial markets.

Li, Yuqian (Duke University) | Conitzer, Vincent (Duke University)

Conventionally, the questions on a test are assumed to be kept secretfrom test takers until the test. However, for tests that are taken ona large scale, particularly asynchronously, this is very hard toachieve. For example, example TOEFL iBT and driver's license test questions are easily found online. This also appears likely to becomean issue for Massive Open Online Courses (MOOCs). In this paper, we take the loss of confidentiality as a fact. Evenso, not all hope is lost as the test taker can memorize only a limitedset of questions' answers, and the tester can randomize which questions appear onthe test. We model this as a Stackelberg game, where the testercommits to a mixed strategy and the follower responds. We provide anexponential-size linear program formulation, prove several NP-hardnessresults, and give efficient algorithms for special cases.