Vincent Conitzer

AAAI Conference 2026 Conference Paper

Moral Change or Noise? On Problems of Aligning AI with Temporally Unstable Human Feedback

• Vijay Keswani
• Cyrus Cousins
• Breanna Nguyen
• Vincent Conitzer
• Hoda Heidari
• Jana Schaich Borg
• Walter Sinnott-Armstrong

Alignment methods in moral domains seek to elicit moral preferences of human stakeholders and incorporate them into AI. This presupposes moral preferences as static targets, but such preferences often evolve over time. Proper alignment of AI to dynamic human preferences should ideally account for "legitimate" changes to moral reasoning, while ignoring changes related to attention deficits, cognitive biases, or other arbitrary factors. However, common AI alignment approaches largely neglect temporal changes in preferences, posing serious challenges to proper alignment, especially in high-stakes applications of AI, e.g., in healthcare domains, where misalignment can jeopardize the trustworthiness of the system and yield serious individual and societal harms. This work investigates the extent to which people's moral preferences change over time, and the impact of such changes on AI alignment. Our study is grounded in the kidney allocation domain, where we elicit responses to pairwise comparisons of hypothetical kidney transplant patients from over 400 participants across 3-5 sessions. We find that, on average, participants change their response to the same scenario presented at different times around 6-20% of the time (exhibiting "response instability"). Additionally, we observe significant shifts in several participants' retrofitted decision-making models over time (capturing "model instability"). Predictive performance of simple AI models decreases as a function of both response and model instability. Moreover, predictive performance diminishes over time, highlighting the importance of accounting for temporal changes in preferences during training. These findings raise fundamental normative and technical challenges relevant to AI alignment, highlighting the need to better understand the object of alignment (what to align to) when user preferences change significantly over time, including the mechanisms underlying these changes.

AAAI Conference 2026 Conference Paper

On the Edge of Core (Non-)Emptiness: An Automated Reasoning Approach to Approval-Based Multi-Winner Voting

• Ratip Emin Berker
• Emanuel Tewolde
• Vincent Conitzer
• Mingyu Guo
• Marijn Heule
• Lirong Xia

Core stability is a natural and well-studied notion for group fairness in multi-winner voting, where the task is to select a committee from a pool of candidates. We study the setting where voters either approve or disapprove of each candidate; here, it remains a major open problem whether a core-stable committee always exists. In this work, we develop an approach based on mixed-integer linear programming for deciding whether and when core-stable committees are guaranteed to exist. In contrast to SAT-based approaches popular in computational social choice, our method can produce proofs for a specific number of candidates independent of the number of voters. In addition to these computational gains, our program lends itself to a novel duality-based reformulation of the core stability problem, from which we obtain new existence results in special cases. Further, we use our framework to reveal previously unknown relationships between core stability and other desirable properties, such as notions of priceability.

NeurIPS Conference 2025 Conference Paper

AI Testing Should Account for Sophisticated Strategic Behaviour

• Vojta Kovarik
• Eric Chen
• Sami Petersen
• Alexis Ghersengorin
• Vincent Conitzer

This position paper argues for two claims regarding AI testing and evaluation. First, to remain informative about deployment behaviour, evaluations need account for the possibility that AI systems understand their circumstances and reason strategically. Second, game-theoretic analysis can inform evaluation design by formalising and scrutinising the reasoning in evaluation-based safety cases. Drawing on examples from existing AI systems, a review of relevant research, and formal strategic analysis of a stylised evaluation scenario, we present evidence for these claims and motivate several research directions.

AAAI Conference 2025 Conference Paper

Characterising Simulation-Based Program Equilibria

• Emery Cooper
• Caspar Oesterheld
• Vincent Conitzer

In Tennenholtz’s program equilibrium, players of a game submit programs to play on their behalf. Each program receives the other programs’ source code and outputs an action. This can model interactions involving AI agents, mutually transparent institutions, or commitments. Tennenholtz 2004 (https://doi.org/10.1016/j.geb.2004.02.002) proves a folk theorem for program games, but the equilibria constructed are very brittle. We therefore consider simulation-based programs – i.e., programs that work by running opponents’ programs. These are relatively robust (in particular, two programs that act the same are treated the same) and are more practical than proof-based approaches. Oesterheld’s (2019, https://doi.org/10.1007/s11238-018-9679-3) epsilon-Grounded-pi-Bot is such an approach. Unfortunately, it is not generally applicable to games of three or more players, and only allows for a limited range of equilibria in two player games. In this paper, we propose a generalisation to Oesterheld’s (2019) epsilon-Grounded-pi-Bot. We prove a folk theorem for our programs in a setting with access to a shared source of randomness. We then characterise their equilibria in a setting without shared randomness. Both with and without shared randomness, we achieve a much wider range of equilibria than Oesterheld’s (2019) epsilon-Grounded-pi-Bot. Finally, we explore the limits of simulation-based program equilibrium, showing that the Tennenholtz folk theorem cannot be attained by simulation-based programs without access to shared randomness.

TARK Conference 2025 Conference Paper

Choosing What Game to Play without Selecting Equilibria: Inferring Safe (Pareto) Improvements in Binary Constraint Structures

• Caspar Oesterheld
• Vincent Conitzer

We consider a setting in which a principal gets to choose which game from some given set is played by a group of agents. The principal would like to choose a game that favors one of the players, the social preferences of the players, or the principal's own preferences. Unfortunately, given the potential multiplicity of equilibria, it is conceptually unclear how to tell which of even any two games is better. Oesterheld et al. (2022) propose that we use assumptions about outcome correspondence -- i. e. , about how the outcomes of different games relate -- to allow comparisons in some cases. For example, it seems reasonable to assume that isomorphic games are played isomorphically. From such assumptions we can sometimes deduce that the outcome of one game G' is guaranteed to be better than the outcome of another game G, even if we do not have beliefs about how each of G and G' will be played individually. Following Oesterheld et al. , we then call G' a safe improvement on G. In this paper, we study how to derive safe improvement relations. We first show that if we are given a set of games and arbitrary assumptions about outcome correspondence between these games, deriving safe improvement relations is co-NP-complete. We then study the (in)completeness of a natural set of inference rules for outcome correspondence. We show that in general the inference rules are incomplete. However, we also show that under natural, generally applicable assumptions about outcome correspondence the rules are complete.

AAAI Conference 2025 Conference Paper

Computing Game Symmetries and Equilibria That Respect Them

• Emanuel Tewolde
• Brian Hu Zhang
• Caspar Oesterheld
• Tuomas Sandholm
• Vincent Conitzer

Strategic interactions can be represented more concisely, and analyzed and solved more efficiently, if we are aware of the symmetries within the multiagent system. Symmetries also have conceptual implications, for example for equilibrium selection. We study the computational complexity of identifying and using symmetries. Using the classical framework of normal-form games, we consider game symmetries that can be across some or all players and/or actions. We find a strong connection between game symmetries and graph automorphisms, yielding graph automorphism and graph isomorphism completeness results for characterizing the symmetries present in a game. On the other hand, we also show that the problem becomes polynomial-time solvable when we restrict the consideration of actions in one of two ways. Next, we investigate when exactly game symmetries can be successfully leveraged for Nash equilibrium computation. We show that finding a Nash equilibrium that respects a given set of symmetries is PPAD- and CLS-complete in general-sum and team games respectively---that is, exactly as hard as Brouwer fixed point and gradient descent problems. Finally, we present polynomial-time methods for the special cases where we are aware of a vast number of symmetries, or where the game is two-player zero-sum and we do not even know the symmetries.

ICML Conference 2025 Conference Paper

Expected Variational Inequalities

• Brian Hu Zhang
• Ioannis Anagnostides
• Emanuel Tewolde
• Ratip Emin Berker
• Gabriele Farina
• Vincent Conitzer
• Tuomas Sandholm

Variational inequalities (VIs) encompass many fundamental problems in diverse areas ranging from engineering to economics and machine learning. However, their considerable expressivity comes at the cost of computational intractability. In this paper, we introduce and analyze a natural relaxation—which we refer to as expected variational inequalities (EVIs) —where the goal is to find a distribution that satisfies the VI constraint in expectation. By adapting recent techniques from game theory, we show that, unlike VIs, EVIs can be solved in polynomial time under general (nonmonotone) operators. EVIs capture the seminal notion of correlated equilibria, but enjoy a greater reach beyond games. We also employ our framework to capture and generalize several existing disparate results, including from settings such as smooth games, and games with coupled constraints or nonconcave utilities.

AAMAS Conference 2025 Conference Paper

Game Theory with Simulation in the Presence of Unpredictable Randomisation

• Vojtech Kovarík
• Nathaniel Sauerberg
• Lewis Hammond
• Vincent Conitzer

AI agents will be predictable in certain ways that traditional agents are not. Where and how can we leverage this predictability in order to improve social welfare? We study this question in a gametheoretic setting where one agent can pay a fixed cost to simulate the other in order to learn its mixed strategy. As a negative result, we prove that, in contrast to prior work on pure-strategy simulation, enabling mixed-strategy simulation may no longer lead to improved outcomes for both players in all so-called “generalised trust games”. In fact, mixed-strategy simulation does not help in any game where the simulatee’s action can depend on that of the simulator. We also show that, in general, deciding whether simulation introduces Pareto-improving Nash equilibria in a given game is NP-hard. As positive results, we establish that mixed-strategy simulation can improve social welfare if the simulator has the option to scale their level of trust, if the players face challenges with both trust and coordination, or if maintaining some level of privacy is essential for enabling cooperation.

ICML Conference 2025 Conference Paper

Observation Interference in Partially Observable Assistance Games

• Scott Emmons
• Caspar Oesterheld
• Vincent Conitzer
• Stuart Russell 0001

We study partially observable assistance games (POAGs), a model of the human-AI value alignment problem which allows the human and the AI assistant to have partial observations. Motivated by concerns of AI deception, we study a qualitatively new phenomenon made possible by partial observability: would an AI assistant ever have an incentive to interfere with the human’s observations? First, we prove that sometimes an optimal assistant must take observation-interfering actions, even when the human is playing optimally, and even when there are otherwise-equivalent actions available that do not interfere with observations. Though this result seems to contradict the classic theorem from single-agent decision making that the value of perfect information is nonnegative, we resolve this seeming contradiction by developing a notion of interference defined on entire policies. This can be viewed as an extension of the classic result that the value of perfect information is nonnegative into the cooperative multiagent setting. Second, we prove that if the human is simply making decisions based on their immediate outcomes, the assistant might need to interfere with observations as a way to query the human’s preferences. We show that this incentive for interference goes away if the human is playing optimally, or if we introduce a communication channel for the human to communicate their preferences to the assistant. Third, we show that if the human acts according to the Boltzmann model of irrationality, this can create an incentive for the assistant to interfere with observations. Finally, we use an experimental model to analyze tradeoffs faced by the AI assistant in practice when considering whether or not to take observation-interfering actions.

AAAI Conference 2025 Conference Paper

The Value of Recall in Extensive-Form Games

• Ratip Emin Berker
• Emanuel Tewolde
• Ioannis Anagnostides
• Tuomas Sandholm
• Vincent Conitzer

Imperfect-recall games—in which players may forget previously acquired information—have found many practical applications, ranging from game abstractions to team games and testing AI agents. In this paper, we quantify the utility gain by endowing a player with perfect recall, which we call the value of recall (VoR). While VoR can be unbounded in general, we parameterize it in terms of various game properties, namely the structure of chance nodes and the degree of absentmindedness (the number of successive times a player enters the same information set). Further, we identify several pathologies that arise with VoR, and show how to circumvent them. We also study the complexity of computing VoR, and how to optimally apportion partial recall. Finally, we connect VoR to other previously studied concepts in game theory, including the price of anarchy. We use that connection in conjunction with the celebrated smoothness framework to characterize VoR in a broad class of games.

NeurIPS Conference 2024 Conference Paper

Aggregating Quantitative Relative Judgments: From Social Choice to Ranking Prediction

• Yixuan E. Xu
• Hanrui Zhang
• Yu Cheng
• Vincent Conitzer

Quantitative Relative Judgment Aggregation (QRJA) is a new research topic in (computational) social choice. In the QRJA model, agents provide judgments on the relative quality of different candidates, and the goal is to aggregate these judgments across all agents. In this work, our main conceptual contribution is to explore the interplay between QRJA in a social choice context and its application to ranking prediction. We observe that in QRJA, judges do not have to be people with subjective opinions; for example, a race can be viewed as a ``judgment'' on the contestants' relative abilities. This allows us to aggregate results from multiple races to evaluate the contestants' true qualities. At a technical level, we introduce new aggregation rules for QRJA and study their structural and computational properties. We evaluate the proposed methods on data from various real races and show that QRJA-based methods offer effective and interpretable ranking predictions.

IJCAI Conference 2024 Conference Paper

Computing Optimal Equilibria in Repeated Games with Restarts

• Ratip Emin Berker
• Vincent Conitzer

Infinitely repeated games can support cooperative outcomes that are not equilibria in the one-shot game. The idea is to make sure that any gains from deviating will be offset by retaliation in future rounds. However, this model of cooperation fails in anonymous settings with many strategic agents that interact in pairs. Here, a player can defect and then avoid penalization by immediately switching partners. In this paper, we focus on a specific set of equilibria that avoids this pitfall. In them, agents follow a designated sequence of actions, and restart if their opponent ever deviates. We show that the socially-optimal sequence of actions consists of an infinitely repeating goal value, preceded by a hazing period. We introduce an equivalence relation on sequences and prove that the computational problem of finding a representative from the optimal equivalence class is (weakly) NP-hard. Nevertheless, we present a pseudo-polynomial time dynamic program for this problem, as well as an integer linear program, and show they are efficient in practice. Lastly, we introduce a fully polynomial-time approximation scheme that outputs a hazing sequence with arbitrarily small approximation ratio.

IJCAI Conference 2024 Conference Paper

Game Transformations That Preserve Nash Equilibria or Best-Response Sets

• Emanuel Tewolde
• Vincent Conitzer

In this paper, we investigate under which conditions normal-form games are (guaranteed to be) strategically equivalent. First, we show for N -player games (N >= 3) that (A) it is NP-hard to decide whether a given strategy is a best response to some strategy profile of the opponents, and that (B) it is co-NP-hard to decide whether two games have the same best-response sets. Combining that with known results from the literature, we move our attention to equivalence-preserving game transformations. It is a widely used fact that a positive affine (linear) transformation of the utility payoffs neither changes the best-response sets nor the Nash equilibrium set. We investigate which other game transformations also possess either of the following two properties when being applied to an arbitrary N-player game (N >= 2): (i) The Nash equilibrium set stays the same; (ii) The best-response sets stay the same. For game transformations that operate player-wise and strategy-wise, we prove that (i) implies (ii) and that transformations with property (ii) must be positive affine. The resulting equivalence chain highlights the special status of positive affine transformations among all the transformation procedures that preserve key game-theoretic characteristics.

AAMAS Conference 2024 Conference Paper

Game Transformations That Preserve Nash Equilibria or Best-Response Sets

• Emanuel Tewolde
• Vincent Conitzer

In the full version of this paper, we investigate under which conditions normal-form games are (guaranteed) to be strategically equivalent. First, we show for 𝑁-player games (𝑁 ≥ 3) that (a) it is NP-hard to decide whether a given strategy is a best response to some strategy profile of the opponents, and that (b) it is co-NP-hard to decide whether two games have the same best-response sets. We then turn our attention to equivalence-preserving game transformations. It is a widely used fact that a positive affine (linear) transformation of the utility payoffs neither changes the bestresponse sets nor the Nash equilibrium set. We investigate which other game transformations also possess either of the following two properties when being applied to an arbitrary 𝑁-player game (𝑁 ≥ 2): (i) The Nash equilibrium set stays the same; (ii) The bestresponse sets stay the same. For game transformations that operate player-wise and strategywise, we prove that (i) implies (ii) and that transformations with property (ii) must be positive affine. The resulting equivalence chain highlights the special status of positive affine transformations among all the transformation procedures that preserve key gametheoretic characteristics.

IJCAI Conference 2024 Conference Paper

Imperfect-Recall Games: Equilibrium Concepts and Their Complexity

• Emanuel Tewolde
• Brian Hu Zhang
• Caspar Oesterheld
• Manolis Zampetakis
• Tuomas Sandholm
• Paul Goldberg
• Vincent Conitzer

We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before. An example is the absentminded driver game, as well as team games in which the members have limited communication capabilities. In the framework of extensive-form games with imperfect recall, we analyze the computational complexities of finding equilibria in multiplayer settings across three different solution concepts: Nash, multiselves based on evidential decision theory (EDT), and multiselves based on causal decision theory (CDT). We are interested in both exact and approximate solution computation. As special cases, we consider (1) single-player games, (2) two-player zero-sum games and relationships to maximin values, and (3) games without exogenous stochasticity (chance nodes). We relate these problems to the complexity classes PPAD, PLS, Σ_2^P, ∃R, and ∃∀R.

NeurIPS Conference 2024 Conference Paper

Melting Pot Contest: Charting the Future of Generalized Cooperative Intelligence

• Rakshit S. Trivedi
• Akbir Khan
• Jesse Clifton
• Lewis Hammond
• Edgar A. Duéñez-Guzmán
• John P. Agapiou
• Jayd Matyas
• Sasha Vezhnevets

Multi-agent AI research promises a path to develop human-like and human-compatible intelligent technologies that complement the solipsistic view of other approaches, which mostly do not consider interactions between agents. Aiming to make progress in this direction, the Melting Pot contest 2023 focused on the problem of cooperation among interacting agents and challenged researchers to push the boundaries of multi-agent reinforcement learning (MARL) for mixed-motive games. The contest leveraged the Melting Pot environment suite to rigorously evaluate how well agents can adapt their cooperative skills to interact with novel partners in unforeseen situations. Unlike other reinforcement learning challenges, this challenge focused on social rather than environmental generalization. In particular, a population of agents performs well in Melting Pot when its component individuals are adept at finding ways to cooperate both with others in their population and with strangers. Thus Melting Pot measures cooperative intelligence. The contest attracted over 600 participants across 100+ teams globally and was a success on multiple fronts: (i) it contributed to our goal of pushing the frontiers of MARL towards building more cooperatively intelligent agents, evidenced by several submissions that outperformed established baselines; (ii) it attracted a diverse range of participants, from independent researchers to industry affiliates and academic labs, both with strong background and new interest in the area alike, broadening the field’s demographic and intellectual diversity; and (iii) analyzing the submitted agents provided important insights, highlighting areas for improvement in evaluating agents' cooperative intelligence. This paper summarizes the design aspects and results of the contest and explores the potential of Melting Pot as a benchmark for studying Cooperative AI. We further analyze the top solutions and conclude with a discussion on promising directions for future research.

AAAI Conference 2024 Conference Paper

Non-excludable Bilateral Trade between Groups

• Yixuan Even Xu
• Hanrui Zhang
• Vincent Conitzer

Bilateral trade is one of the most natural and important forms of economic interaction: A seller has a single, indivisible item for sale, and a buyer is potentially interested. The two parties typically have different, privately known valuations for the item, and ideally, they would like to trade if the buyer values the item more than the seller. The celebrated impossibility result by Myerson and Satterthwaite shows that any mechanism for this setting must violate at least one important desideratum. In this paper, we investigate a richer paradigm of bilateral trade, with many self-interested buyers and sellers on both sides of a single trade who cannot be excluded from the trade. We show that this allows for more positive results. In fact, we establish a dichotomy in the possibility of trading efficiently. If in expectation, the buyers value the item more, we can achieve efficiency in the limit. If this is not the case, then efficiency cannot be achieved in general. En route, we characterize trading mechanisms that encourage truth-telling, which may be of independent interest. We also evaluate our trading mechanisms experimentally, and the experiments align with our theoretical results.

ICML Conference 2024 Conference Paper

Position: Social Choice Should Guide AI Alignment in Dealing with Diverse Human Feedback

• Vincent Conitzer
• Rachel Freedman
• Jobst Heitzig
• Wesley H. Holliday
• Bob M. Jacobs
• Nathan O. Lambert
• Milan Mossé
• Eric Pacuit

Foundation models such as GPT-4 are fine-tuned to avoid unsafe or otherwise problematic behavior, such as helping to commit crimes or producing racist text. One approach to fine-tuning, called reinforcement learning from human feedback, learns from humans’ expressed preferences over multiple outputs. Another approach is constitutional AI, in which the input from humans is a list of high-level principles. But how do we deal with potentially diverging input from humans? How can we aggregate the input into consistent data about “collective” preferences or otherwise use it to make collective choices about model behavior? In this paper, we argue that the field of social choice is well positioned to address these questions, and we discuss ways forward for this agenda, drawing on discussions in a recent workshop on Social Choice for AI Ethics and Safety held in Berkeley, CA, USA in December 2023.

AAAI Conference 2024 Conference Paper

The Complexity of Computing Robust Mediated Equilibria in Ordinal Games

• Vincent Conitzer

Usually, to apply game-theoretic methods, we must specify utilities precisely, and we run the risk that the solutions we compute are not robust to errors in this specification. Ordinal games provide an attractive alternative: they require specifying only which outcomes are preferred to which other ones. Unfortunately, they provide little guidance for how to play unless there are pure Nash equilibria; evaluating mixed strategies appears to fundamentally require cardinal utilities. In this paper, we observe that we can in fact make good use of mixed strategies in ordinal games if we consider settings that allow for folk theorems. These allow us to find equilibria that are robust, in the sense that they remain equilibria no matter which cardinal utilities are the correct ones -- as long as they are consistent with the specified ordinal preferences. We analyze this concept and study the computational complexity of finding such equilibria in a range of settings.

TARK Conference 2023 Conference Paper

A Theory of Bounded Inductive Rationality

• Caspar Oesterheld
• Abram Demski
• Vincent Conitzer

The dominant theories of rational choice assume logical omniscience. That is, they assume that when facing a decision problem, an agent can perform all relevant computations and determine the truth value of all relevant logical/mathematical claims. This assumption is unrealistic when, for example, we offer bets on remote digits of pi or when an agent faces a computationally intractable planning problem. Furthermore, the assumption of logical omniscience creates contradictions in cases where the environment can contain descriptions of the agent itself. Importantly, strategic interactions as studied in game theory are decision problems in which a rational agent is predicted by its environment (the other players). In this paper, we develop a theory of rational decision making that does not assume logical omniscience. We consider agents who repeatedly face decision problems (including ones like betting on digits of pi or games against other agents). The main contribution of this paper is to provide a sensible theory of rationality for such agents. Roughly, we require that a boundedly rational inductive agent tests each efficiently computable hypothesis infinitely often and follows those hypotheses that keep their promises of high rewards. We then prove that agents that are rational in this sense have other desirable properties. For example, they learn to value random and pseudo-random lotteries at their expected reward. Finally, we consider strategic interactions between different agents and prove a folk theorem for what strategies bounded rational inductive agents can converge to.

NeurIPS Conference 2023 Conference Paper

Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games

• Brian Zhang
• Gabriele Farina
• Ioannis Anagnostides
• Federico Cacciamani
• Stephen McAleer
• Andreas Haupt
• Andrea Celli
• Nicola Gatti

We introduce a new approach for computing optimal equilibria via learning in games. It applies to extensive-form settings with any number of players, including mechanism design, information design, and solution concepts such as correlated, communication, and certification equilibria. We observe that optimal equilibria are minimax equilibrium strategies of a player in an extensive-form zero-sum game. This reformulation allows to apply techniques for learning in zero-sum games, yielding the first learning dynamics that converge to optimal equilibria, not only in empirical averages, but also in iterates. We demonstrate the practical scalability and flexibility of our approach by attaining state-of-the-art performance in benchmark tabular games, and by computing an optimal mechanism for a sequential auction design problem using deep reinforcement learning.

AAAI Conference 2023 Conference Paper

Foundations of Cooperative AI

• Vincent Conitzer
• Caspar Oesterheld

AI systems can interact in unexpected ways, sometimes with disastrous consequences. As AI gets to control more of our world, these interactions will become more common and have higher stakes. As AI becomes more advanced, these interactions will become more sophisticated, and game theory will provide the tools for analyzing these interactions. However, AI agents are in some ways unlike the agents traditionally studied in game theory, introducing new challenges as well as opportunities. We propose a research agenda to develop the game theory of highly advanced AI agents, with a focus on achieving cooperation.

IJCAI Conference 2023 Conference Paper

Game Theory with Simulation of Other Players

• Vojtěch Kovařík
• Caspar Oesterheld
• Vincent Conitzer

Game-theoretic interactions with AI agents could differ from traditional human-human interactions in various ways. One such difference is that it may be possible to simulate an AI agent (for example because its source code is known), which allows others to accurately predict the agent's actions. This could lower the bar for trust and cooperation. In this paper, we first formally define games in which one player can simulate another at a cost, and derive some basic properties of such games. Then, we prove a number of results for such games, including: (1) introducing simulation into generic-payoff normal-form games makes them easier to solve; (2) if the only obstacle to cooperation is a lack of trust in the possibly-simulated agent, simulation enables equilibria that improve the outcome for both agents; and (3) however, there are settings where introducing simulation results in strictly worse outcomes for both players.

NeurIPS Conference 2023 Conference Paper

Similarity-based cooperative equilibrium

• Caspar Oesterheld
• Johannes Treutlein
• Roger B. Grosse
• Vincent Conitzer
• Jakob Foerster

As machine learning agents act more autonomously in the world, they will increasingly interact with each other. Unfortunately, in many social dilemmas like the one-shot Prisoner’s Dilemma, standard game theory predicts that ML agents will fail to cooperate with each other. Prior work has shown that one way to enable cooperative outcomes in the one-shot Prisoner’s Dilemma is to make the agents mutually transparent to each other, i. e. , to allow them to access one another’s source code (Rubinstein, 1998; Tennenholtz, 2004) – or weights in the case of ML agents. However, full transparency is often unrealistic, whereas partial transparency is commonplace. Moreover, it is challenging for agents to learn their way to cooperation in the full transparency setting. In this paper, we introduce a more realistic setting in which agents only observe a single number indicating how similar they are to each other. We prove that this allows for the same set of cooperative outcomes as the full transparency setting. We also demonstrate experimentally that cooperation can be learned using simple ML methods.

IJCAI Conference 2023 Conference Paper

The Computational Complexity of Single-Player Imperfect-Recall Games

• Emanuel Tewolde
• Caspar Oesterheld
• Vincent Conitzer
• Paul W. Goldberg

We study single-player extensive-form games with imperfect recall, such as the Sleeping Beauty problem or the Absentminded Driver game. For such games, two natural equilibrium concepts have been proposed as alternative solution concepts to ex-ante optimality. One equilibrium concept uses generalized double halving (GDH) as a belief system and evidential decision theory (EDT), and another one uses generalized thirding (GT) as a belief system and causal decision theory (CDT). Our findings relate those three solution concepts of a game to solution concepts of a polynomial maximization problem: global optima, optimal points with respect to subsets of variables and Karush–Kuhn–Tucker (KKT) points. Based on these correspondences, we are able to settle various complexity-theoretic questions on the computation of such strategies. For ex-ante optimality and (EDT, GDH)-equilibria, we obtain NP-hardness and inapproximability, and for (CDT, GT)-equilibria we obtain CLS-completeness results.

ICML Conference 2022 Conference Paper

For Learning in Symmetric Teams, Local Optima are Global Nash Equilibria

• Scott Emmons
• Caspar Oesterheld
• Andrew Critch
• Vincent Conitzer
• Stuart Russell 0001

Although it has been known since the 1970s that a globally optimal strategy profile in a common-payoff game is a Nash equilibrium, global optimality is a strict requirement that limits the result’s applicability. In this work, we show that any locally optimal symmetric strategy profile is also a (global) Nash equilibrium. Furthermore, we show that this result is robust to perturbations to the common payoff and to the local optimum. Applied to machine learning, our result provides a global guarantee for any gradient method that finds a local optimum in symmetric strategy space. While this result indicates stability to unilateral deviation, we nevertheless identify broad classes of games where mixed local optima are unstable under joint, asymmetric deviations. We analyze the prevalence of instability by running learning algorithms in a suite of symmetric games, and we conclude by discussing the applicability of our results to multi-agent RL, cooperative inverse RL, and decentralized POMDPs.

AAAI Conference 2022 Conference Paper

Learning Influence Adoption in Heterogeneous Networks

• Vincent Conitzer
• Debmalya Panigrahi
• Hanrui Zhang

We study the problem of learning influence adoption in networks. In this problem, a communicable entity (such as an infectious disease, a computer virus, or a social media meme) propagates through a network, and the goal is to learn the state of each individual node by sampling only a small number of nodes and observing/testing their states. We study this problem in heterogeneous networks, in which each individual node has a set of distinct features that determine how it is affected by the propagating entity. We give an efficient algorithm with nearly optimal sample complexity for two variants of this learning problem, corresponding to symptomatic and asymptomatic spread. In each case, the optimal sample complexity naturally generalizes both the complexity of learning how nodes are affected in isolation, and the complexity of learning influence adoption in a homogeneous network.

AAMAS Conference 2022 Conference Paper

Near-Optimal Reviewer Splitting in Two-Phase Paper Reviewing and Conference Experiment Design

• Steven Jecmen
• Hanrui Zhang
• Ryan Liu
• Fei Fang
• Vincent Conitzer
• Nihar B. Shah

Many scientific conferences employ a two-phase paper review process, where some papers are assigned additional reviewers after the initial reviews are submitted. Many conferences also design and run experiments on their paper review process, where some papers are assigned reviewers who provide reviews under an experimental condition. In this paper, we consider the question: how should reviewers be divided between phases or conditions in order to maximize total assignment similarity? We show both empirically (on real conference data) and theoretically (under certain natural conditions) that dividing reviewers uniformly at random is near-optimal. The full paper is available at https: //arxiv. org/abs/2108. 06371.

AAAI Conference 2022 Conference Paper

Planning with Participation Constraints

• Hanrui Zhang
• Yu Cheng
• Vincent Conitzer

We pose and study the problem of planning in Markov decision processes (MDPs), subject to participation constraints as studied in mechanism design. In this problem, a planner must work with a self-interested agent on a given MDP. Each action in the MDP provides an immediate reward to the planner and a (possibly different) reward to the agent. The agent has no control in choosing the actions, but has the option to end the entire process at any time. The goal of the planner is to find a policy that maximizes her cumulative reward, taking into consideration the agent’s ability to terminate. We give a fully polynomial-time approximation scheme for this problem. En route, we present polynomial-time algorithms for computing (exact) optimal policies for important special cases of this problem, including when the time horizon is constant, or when the MDP exhibits a “definitive decisions” property. We illustrate our algorithms with two different game-theoretic applications: the problem of assigning rides in ride-sharing and the problem of designing screening policies. Our results imply efficient algorithms for computing (approximately) optimal policies in both applications.

JAAMAS Journal 2022 Journal Article

Safe Pareto improvements for delegated game playing

• Caspar Oesterheld
• Vincent Conitzer

Abstract A set of players delegate playing a game to a set of representatives, one for each player. We imagine that each player trusts their respective representative’s strategic abilities. Thus, we might imagine that per default, the original players would simply instruct the representatives to play the original game as best as they can. In this paper, we ask: are there safe Pareto improvements on this default way of giving instructions? That is, we imagine that the original players can coordinate to tell their representatives to only consider some subset of the available strategies and to assign utilities to outcomes differently than the original players. Then can the original players do this in such a way that the payoff is guaranteed to be weakly higher than under the default instructions for all the original players? In particular, can they Pareto-improve without probabilistic assumptions about how the representatives play games? In this paper, we give some examples of safe Pareto improvements. We prove that the notion of safe Pareto improvements is closely related to a notion of outcome correspondence between games. We also show that under some specific assumptions about how the representatives play games, finding safe Pareto improvements is NP-complete.

NeurIPS Conference 2021 Conference Paper

Automated Dynamic Mechanism Design

• Hanrui Zhang
• Vincent Conitzer

We study Bayesian automated mechanism design in unstructured dynamic environments, where a principal repeatedly interacts with an agent, and takes actions based on the strategic agent's report of the current state of the world. Both the principal and the agent can have arbitrary and potentially different valuations for the actions taken, possibly also depending on the actual state of the world. Moreover, at any time, the state of the world may evolve arbitrarily depending on the action taken by the principal. The goal is to compute an optimal mechanism which maximizes the principal's utility in the face of the self-interested strategic agent. We give an efficient algorithm for computing optimal mechanisms, with or without payments, under different individual-rationality constraints, when the time horizon is constant. Our algorithm is based on a sophisticated linear program formulation, which can be customized in various ways to accommodate richer constraints. For environments with large time horizons, we show that the principal's optimal utility is hard to approximate within a certain constant factor, complementing our algorithmic result. These results paint a relatively complete picture for automated dynamic mechanism design in unstructured environments. We further consider a special case of the problem where the agent is myopic, and give a refined efficient algorithm whose time complexity scales linearly in the time horizon. In the full version of the paper, we show that memoryless mechanisms, which are without loss of generality optimal in Markov decision processes without strategic behavior, do not provide a good solution for our problem, in terms of both optimality and computational tractability. Moreover, we present experimental results where our algorithms are applied to synthetic dynamic environments with different characteristics, which not only serve as a proof of concept for our algorithms, but also exhibit intriguing phenomena in dynamic mechanism design.

AAAI Conference 2021 Conference Paper

Automated Mechanism Design for Classification with Partial Verification

• Hanrui Zhang
• Yu Cheng
• Vincent Conitzer

We study the problem of automated mechanism design with partial verification, where each type can (mis)report only a restricted set of types (rather than any other type), induced by the principal’s limited verification power. We prove hardness results when the revelation principle does not necessarily hold, as well as when types have even minimally different preferences. In light of these hardness results, we focus on truthful mechanisms in the setting where all types share the same preference over outcomes, which is motivated by applications in, e. g. , strategic classification. We present a number of algorithmic and structural results, including an efficient algorithm for finding optimal deterministic truthful mechanisms, which also implies a faster algorithm for finding optimal randomized truthful mechanisms via a characterization based on convexity. We then consider a more general setting, where the principal’s cost is a function of the combination of outcomes assigned to each type. In particular, we focus on the case where the cost function is submodular, and give generalizations of essentially all our results in the classical setting where the cost function is additive. Our results provide a relatively complete picture for automated mechanism design with partial verification.

AAAI Conference 2021 Conference Paper

Classification with Few Tests through Self-Selection

• Hanrui Zhang
• Yu Cheng
• Vincent Conitzer

We study test-based binary classification, where a principal either accepts or rejects agents based on the outcomes they get in a set of tests. The principal commits to a policy, which consists of all sets of outcomes that lead to acceptance. Each agent is modeled by a distribution over the space of possible outcomes. When an agent takes a test, he pays a cost and receives an independent sample from his distribution as the outcome. Agents can always choose between taking another test and stopping. They maximize their expected utility, which is the value of acceptance if the principal’s policy accepts the set of outcomes they have and 0 otherwise, minus the total cost of tests taken. We focus on the case where agents can be either “good” or “bad” (corresponding to their distribution over test outcomes), and the principal’s goal is to accept good agents and reject bad ones. We show, roughly speaking, that as long as the good and bad agents have different distributions (which can be arbitrarily close to each other), the principal can always achieve perfect accuracy, meaning good agents are accepted with probability 1, and bad ones are rejected with probability 1. Moreover, there is a policy achieving perfect accuracy under which the maximum number of tests any agent needs to take is constant — in sharp contrast to the case where the principal directly observes samples from agents’ distributions. The key technique is to choose the policy so that agents self-select into taking tests.

AAAI Conference 2021 Conference Paper

Classification with Strategically Withheld Data

• Anilesh K. Krishnaswamy
• Haoming Li
• David Rein
• Hanrui Zhang
• Vincent Conitzer

Machine learning techniques can be useful in applications such as credit approval and college admission. However, to be classified more favorably in such contexts, an agent may decide to strategically withhold some of her features, such as bad test scores. This is a missing data problem with a twist: which data is missing depends on the chosen classifier, because the specific classifier is what may create the incentive to withhold certain feature values. We address the problem of training classifiers that are robust to this behavior. We design three classification methods: MINCUT, HILL- CLIMBING (HC) and Incentive-Compatible Logistic Regression (IC-LR). We show that MINCUT is optimal when the true distribution of data is fully known. However, it can produce complex decision boundaries, and hence be prone to overfitting in some cases. Based on a characterization of truthful classifiers (i. e. , those that give no incentive to strategically hide features), we devise a simpler alternative called HC which consists of a hierarchical ensemble of out-of-thebox classifiers, trained using a specialized hill-climbing procedure which we show to be convergent. For several reasons, MINCUT and HC are not effective in utilizing a large number of complementarily informative features. To this end, we present IC-LR, a modification of Logistic Regression that removes the incentive to strategically drop features. We also show that our algorithms perform well in experiments on realworld data sets, and present insights into their relative performance in different settings.

AAAI Conference 2021 Conference Paper

Incentive-Aware PAC Learning

• Hanrui Zhang
• Vincent Conitzer

We study PAC learning in the presence of strategic manipulation, where data points may modify their features in certain predefined ways in order to receive a better outcome. We show that the vanilla ERM principle fails to achieve any nontrivial guarantee in this context. Instead, we propose an incentive-aware version of the ERM principle which has asymptotically optimal sample complexity. We then focus our attention on incentive-compatible classifiers, which provably prevent any kind of strategic manipulation. We give a sample complexity bound that is, curiously, independent of the hypothesis class, for the ERM principle restricted to incentivecompatible classifiers. This suggests that incentive compatibility alone can act as an effective means of regularization. We further show that it is without loss of generality to consider only incentive-compatible classifiers when opportunities for strategic manipulation satisfy a transitivity condition. As a consequence, in such cases, our hypothesis-classindependent sample complexity bound applies even without incentive compatibility. Our results set the foundations of incentive-aware PAC learning.

AAAI Conference 2021 Conference Paper

Indecision Modeling

• Duncan C. McElfresh
• Lok Chan
• Kenzie Doyle
• Walter Sinnott-Armstrong
• Vincent Conitzer
• Jana Schaich Borg
• John P. Dickerson

AI systems are often used to make or contribute to important decisions in a growing range of applications, including criminal justice, hiring, and medicine. Since these decisions impact human lives, it is important that the AI systems act in ways which align with human values. Techniques for preference modeling and social choice help researchers learn and aggregate peoples’ preferences, which are used to guide AI behavior; thus, it is imperative that these learned preferences are accurate. These techniques often assume that people are willing to express strict preferences over alternatives; which is not true in practice. People are often indecisive, and especially so when their decision has moral implications. The philosophy and psychology literature shows that indecision is a measurable and nuanced behavior—and that there are several different reasons people are indecisive. This complicates the task of both learning and aggregating preferences, since most of the relevant literature makes restrictive assumptions on the meaning of indecision. We begin to close this gap by formalizing several mathematical indecision models based on theories from philosophy, psychology, and economics; these models can be used to describe (indecisive) agent decisions, both when they are allowed to express indecision and when they are not. We test these models using data collected from an online survey where participants choose how to (hypothetically) allocate organs to patients waiting for a transplant.

AAMAS Conference 2021 Conference Paper

Safe Pareto Improvements for Delegated Game Playing

• Caspar Oesterheld
• Vincent Conitzer

A set of players delegate playing a game to a set of representatives, one for each player. We imagine that each player trusts their respective representative’s strategic abilities. Thus, we might imagine that per default, the original players would simply instruct the representatives to play the original game as best as they can. In this paper, we ask: are there safe Pareto improvements on this default way of giving instructions? That is, we imagine that the original players can coordinate to tell their representatives to only consider some subset of the available strategies and to assign utilities to outcomes differently than the original players. Then can the original players do this in such a way that the payoff is guaranteed to be weakly higher than under the default instructions for all the original players? In particular, can they Pareto-improve without probabilistic assumptions about how the representatives play games? In this paper, we give some examples of safe Pareto improvements. We prove that the notion of safe Pareto improvements is closely related to a notion of outcome correspondence between games. We also show that under some specific assumptions about how the representatives play games, finding safe Pareto improvements is NP-complete.

AIJ Journal 2020 Journal Article

Adapting a kidney exchange algorithm to align with human values

• Rachel Freedman
• Jana Schaich Borg
• Walter Sinnott-Armstrong
• John P. Dickerson
• Vincent Conitzer

The efficient and fair allocation of limited resources is a classical problem in economics and computer science. In kidney exchanges, a central market maker allocates living kidney donors to patients in need of an organ. Patients and donors in kidney exchanges are prioritized using ad-hoc weights decided on by committee and then fed into an allocation algorithm that determines who gets what—and who does not. In this paper, we provide an end-to-end methodology for estimating weights of individual participant profiles in a kidney exchange. We first elicit from human subjects a list of patient attributes they consider acceptable for the purpose of prioritizing patients (e. g. , medical characteristics, lifestyle choices, and so on). Then, we ask subjects comparison queries between patient profiles and estimate weights in a principled way from their responses. We show how to use these weights in kidney exchange market clearing algorithms. We then evaluate the impact of the weights in simulations and find that the precise numerical values of the weights we computed matter little, other than the ordering of profiles that they imply. However, compared to not prioritizing patients at all, there is a significant effect, with certain classes of patients being (de)prioritized based on the human-elicited value judgments.

ICML Conference 2020 Conference Paper

Learning Opinions in Social Networks

• Vincent Conitzer
• Debmalya Panigrahi
• Hanrui Zhang 0001

We study the problem of learning opinions in social networks. The learner observes the states of some sample nodes from a social network, and tries to infer the states of other nodes, based on the structure of the network. We show that sample-efficient learning is impossible when the network exhibits strong noise, and give a polynomial-time algorithm for the problem with nearly optimal sample complexity when the network is sufficiently stable.

ICML Conference 2020 Conference Paper

Learning the Valuations of a k-demand Agent

• Hanrui Zhang 0001
• Vincent Conitzer

We study problems where a learner aims to learn the valuations of an agent by observing which goods he buys under varying price vectors. More specifically, we consider the case of a $k$-demand agent, whose valuation over the goods is additive when receiving up to $k$ goods, but who has no interest in receiving more than $k$ goods. We settle the query complexity for the active-learning (preference elicitation) version, where the learner chooses the prices to post, by giving a \emph{biased binary search} algorithm, generalizing the classical binary search procedure. We complement our query complexity upper bounds by lower bounds that match up to lower-order terms. We also study the passive-learning version in which the learner does not control the prices, and instead they are sampled from some distribution. We show that in the PAC model for passive learning, any \emph{empirical risk minimizer} has a sample complexity that is optimal up to a factor of $\widetilde{O}(k)$.

NeurIPS Conference 2020 Conference Paper

Mitigating Manipulation in Peer Review via Randomized Reviewer Assignments

• Steven Jecmen
• Hanrui Zhang
• Ryan Liu
• Nihar Shah
• Vincent Conitzer
• Fei Fang

We consider three important challenges in conference peer review: (i) reviewers maliciously attempting to get assigned to certain papers to provide positive reviews, possibly as part of quid-pro-quo arrangements with the authors; (ii) "torpedo reviewing, " where reviewers deliberately attempt to get assigned to certain papers that they dislike in order to reject them; (iii) reviewer de-anonymization on release of the similarities and the reviewer-assignment code. On the conceptual front, we identify connections between these three problems and present a framework that brings all these challenges under a common umbrella. We then present a (randomized) algorithm for reviewer assignment that can optimally solve the reviewer-assignment problem under any given constraints on the probability of assignment for any reviewer-paper pair. We further consider the problem of restricting the joint probability that certain suspect pairs of reviewers are assigned to certain papers, and show that this problem is NP-hard for arbitrary constraints on these joint probabilities but efficiently solvable for a practical special case. Finally, we experimentally evaluate our algorithms on datasets from past conferences, where we observe that they can limit the chance that any malicious reviewer gets assigned to their desired paper to 50% while producing assignments with over 90% of the total optimal similarity.

AAAI Conference 2019 Conference Paper

A Better Algorithm for Societal Tradeoffs

• Hanrui Zhang
• Yu Cheng
• Vincent Conitzer

In the societal tradeoffs problem, each agent perceives certain quantitative tradeoffs between pairs of activities, and the goal is to aggregate these tradeoffs across agents. This is a problem in social choice; specifically, it is a type of quantitative judgment aggregation problem. A natural rule for this problem was axiomatized by Conitzer et al. [AAAI 2016]; they also provided several algorithms for computing the outcomes of this rule. In this paper, we present a significantly improved algorithm and evaluate it experimentally. Our algorithm is based on a tight connection to minimum-cost flow that we exhibit. We also show that our algorithm cannot be improved without breakthroughs on min-cost flow.

AAAI Conference 2019 Conference Paper

A PAC Framework for Aggregating Agents’ Judgments

• Hanrui Zhang
• Vincent Conitzer

Specifying the objective function that an AI system should pursue can be challenging. Especially when the decisions to be made by the system have a moral component, input from multiple stakeholders is often required. We consider approaches that query them about their judgments in individual examples, and then aggregate these judgments into a general policy. We propose a formal learning-theoretic framework for this setting. We then give general results on how to translate classical results from PAC learning into results in our framework. Subsequently, we show that in some settings, better results can be obtained by working directly in our framework. Finally, we discuss how our model can be extended in a variety of ways for future research.

AAAI Conference 2019 Conference Paper

Designing Preferences, Beliefs, and Identities for Artificial Intelligence

• Vincent Conitzer

Research in artificial intelligence, as well as in economics and other related fields, generally proceeds from the premise that each agent has a well-defined identity, well-defined preferences over outcomes, and well-defined beliefs about the world. However, as we design AI systems, we in fact need to specify where the boundaries between one agent and another in the system lie, what objective functions these agents aim to maximize, and to some extent even what belief formation processes they use.The premise of this paper is that as AI is being broadly deployed in the world, we need well-founded theories of, and methodologies and algorithms for, how to design preferences, identities, and beliefs. This paper lays out an approach to address these problems from a rigorous foundation in decision theory, game theory, social choice theory, and the algorithmic and computational aspects of these fields.

NeurIPS Conference 2019 Conference Paper

Distinguishing Distributions When Samples Are Strategically Transformed

• Hanrui Zhang
• Yu Cheng
• Vincent Conitzer

Often, a principal must make a decision based on data provided by an agent. Moreover, typically, that agent has an interest in the decision that is not perfectly aligned with that of the principal. Thus, the agent may have an incentive to select from or modify the samples he obtains before sending them to the principal. In other settings, the principal may not even be able to observe samples directly; instead, she must rely on signals that the agent is able to send based on the samples that he obtains, and he will choose these signals strategically. In this paper, we give necessary and sufficient conditions for when the principal can distinguish between agents of good'' and bad'' types, when the type affects the distribution of samples that the agent has access to. We also study the computational complexity of checking these conditions. Finally, we study how many samples are needed.

AAAI Conference 2019 Conference Paper

Group Fairness for the Allocation of Indivisible Goods

• Vincent Conitzer
• Rupert Freeman
• Nisarg Shah
• Jennifer Wortman Vaughan

We consider the problem of fairly dividing a collection of indivisible goods among a set of players. Much of the existing literature on fair division focuses on notions of individual fairness. For instance, envy-freeness requires that no player prefer the set of goods allocated to another player to her own allocation. We observe that an algorithm satisfying such individual fairness notions can still treat groups of players unfairly, with one group desiring the goods allocated to another. Our main contribution is a notion of group fairness, which implies most existing notions of individual fairness. Group fairness (like individual fairness) cannot be satisfied exactly with indivisible goods. Thus, we introduce two “up to one good” style relaxations. We show that, somewhat surprisingly, certain local optima of the Nash welfare function satisfy both relaxations and can be computed in pseudo-polynomial time by local search. Our experiments reveal faster computation and stronger fairness guarantees in practice.

ICML Conference 2019 Conference Paper

When Samples Are Strategically Selected

• Hanrui Zhang 0001
• Yu Cheng 0002
• Vincent Conitzer

In standard classification problems, the assumption is that the entity making the decision (the principal ) has access to all the samples. However, in many contexts, she either does not have direct access to the samples, or can inspect only a limited set of samples and does not know which are the most relevant ones. In such cases, she must rely on another party (the agent ) to either provide the samples or point out the most relevant ones. If the agent has a different objective, then the principal cannot trust the submitted samples to be representative. She must set a policy for how she makes decisions, keeping in mind the agent’s incentives. In this paper, we introduce a theoretical framework for this problem and provide key structural and computational results.

AAAI Conference 2018 Conference Paper

Adapting a Kidney Exchange Algorithm to Align With Human Values

• Rachel Freedman
• Jana Schaich Borg
• Walter Sinnott-Armstrong
• John Dickerson
• Vincent Conitzer

The efficient allocation of limited resources is a classical problem in economics and computer science. In kidney exchanges, a central market maker allocates living kidney donors to patients in need of an organ. Patients and donors in kidney exchanges are prioritized using ad-hoc weights decided on by committee and then fed into an allocation algorithm that determines who get what—and who does not. In this paper, we provide an end-to-end methodology for estimating weights of individual participant profiles in a kidney exchange. We first elicit from human subjects a list of patient attributes they consider acceptable for the purpose of prioritizing patients (e. g. , medical characteristics, lifestyle choices, and so on). Then, we ask subjects comparison queries between patient profiles and estimate weights in a principled way from their responses. We show how to use these weights in kidney exchange market clearing algorithms. We then evaluate the impact of the weights in simulations and find that the precise numerical values of the weights we computed matter little, other than the ordering of profiles that they imply. However, compared to not prioritizing patients at all, there is a significant effect, with certain classes of patients being (de)prioritized based on the human-elicited value judgments.

AAMAS Conference 2018 Conference Paper

Complexity of Scheduling Charging in the Smart Grid

• Mathijs M. de Weerdt
• Michael Albert
• Vincent Conitzer
• Koos van der Linden

The problem of optimally scheduling the charging demand of electric vehicles within the constraints of the electricity infrastructure is called the charge scheduling problem. The models of the charging speed, horizon, and charging demand determine the computational complexity of the charge scheduling problem. For about 20 variants the problem is either in P or weakly NP-hard and dynamic programs exist to compute optimal solutions. About 10 other variants of the problem are strongly NP-hard, presenting a potentially significant obstacle to their use in practical situations of scale.

IJCAI Conference 2018 Conference Paper

Complexity of Scheduling Charging in the Smart Grid

• Mathijs de Weerdt
• Michael Albert
• Vincent Conitzer
• Koos van der Linden

The problem of optimally scheduling the charging demand of electric vehicles within the constraints of the electricity infrastructure is called the charge scheduling problem. The models of the charging speed, horizon, and charging demand determine the computational complexity of the charge scheduling problem. We show that for about 20 variants the problem is either in P or weakly NP-hard and dynamic programs exist to compute optimal solutions. About 10 other variants of the problem are strongly NP-hard, presenting a potentially significant obstacle to their use in practical situations of scale. An experimental study establishes up to what parameter values the dynamic programs can determine optimal solutions in a couple of minutes.

AAAI Conference 2018 Conference Paper

Disarmament Games With Resource

• Yuan Deng
• Vincent Conitzer

A paper by Deng and Conitzer in AAAI’17 introduces disarmament games, in which players alternatingly commit not to play certain pure strategies. However, in practice disarmament usually does not consist in removing a strategy, but rather in removing a resource (and doing so rules out all the strategies in which that resource is used simultaneously). In this paper, we introduce a model of disarmament games in which resources, rather than strategies, are removed. We prove NP-completeness of several formulations of the problem of achieving desirable outcomes via disarmament. We then study the case where resources can be fractionally removed, and prove a result analogous to the folk theorem that all desirable outcomes can be achieved. We show that we can approximately achieve any desirable outcome in a polynomial number of rounds, though determining whether a given outcome can be obtained in a given number of rounds remains NP-complete.

AAAI Conference 2017 Conference Paper

Automated Design of Robust Mechanisms

• Michael Albert
• Vincent Conitzer
• Peter Stone

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.

AAAI Conference 2017 Conference Paper

Disarmament Games

• Yuan Deng
• Vincent Conitzer

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.

IJCAI Conference 2017 Conference Paper

Fair and Efficient Social Choice in Dynamic Settings

• Rupert Freeman
• Seyed Majid Zahedi
• Vincent Conitzer

We study a dynamic social choice problem in which an alternative is chosen at each round according to the reported valuations of a set of agents. In the interests of obtaining a solution that is both efficient and fair, we aim to maximize the long-term Nash social welfare, which is the product of all agents' utilities. We present and analyze two greedy algorithms for this problem, including the classic Proportional Fair (PF) algorithm. We analyze several versions of the algorithms and how they relate, and provide an axiomatization of PF. Finally, we evaluate the algorithms on data gathered from a computer systems application.

JAIR Journal 2017 Journal Article

Game-Theoretic Question Selection for Tests

• Yuqian Li
• Vincent Conitzer

Conventionally, the questions on a test are assumed to be kept secret from test takers until the test. However, for tests that are taken on a large scale, particularly asynchronously, this is very hard to achieve. For example, TOEFL iBT and driver's license test questions are easily found online. This also appears likely to become an issue for Massive Open Online Courses (MOOCs, as offered for example by Coursera, Udacity, and edX). Specifically, the test result may not reflect the true ability of a test taker if questions are leaked beforehand. In this paper, we take the loss of confidentiality as a fact. Even so, not all hope is lost as the test taker can memorize only a limited set of questions' answers, and the tester can randomize which questions to let appear on the test. We model this as a Stackelberg game, where the tester commits to a mixed strategy and the follower responds. Informally, the goal of the tester is to best reveal the true ability of a test taker, while the test taker tries to maximize the test result (pass probability or score). We provide an exponential-size linear program formulation that computes the optimal test strategy, prove several NP-hardness results on computing optimal test strategies in general, and give efficient algorithms for special cases (scored tests and single-question tests). Experiments are also provided for those proposed algorithms to show their scalability and the increase of the tester's utility relative to that of the uniform-at-random strategy. The increase is quite significant when questions have some correlation---for example, when a test taker who can solve a harder question can always solve easier questions.

AAMAS Conference 2017 Conference Paper

Mechanism Design with Unknown Correlated Distributions: Can We Learn Optimal Mechanisms?

• Michael Albert
• Vincent Conitzer
• Peter Stone

Due to Cremer and McLean (1985), it is well known that in a setting where bidders’ values are correlated, an auction designer can extract the full social surplus as revenue. However, this result strongly relies on the assumption of a common prior distribution between the mechanism designer and the bidders. A natural question to ask is, can a mechanism designer distinguish between a set of possible distributions, or failing that, use a finite number of samples from the true distribution to learn enough about the distribution to recover the Cremer and Mclean result? We show that if a bidder’s distribution is one of a countably infinite sequence of potential distributions that converges to an independent private values distribution, then there is no mechanism that can guarantee revenue more than greater than the optimal mechanism over the independent private value mechanism, even with sampling from the true distribution. We also show that any mechanism over this infinite sequence can guarantee at most a (|Θ| + 1)/(2 + ) approximation, where |Θ| is the number of bidder types, to the revenue achievable by a mechanism where the designer knows the bidder’s distribution. Finally, as a positive result, we show that for any distribution where full surplus extraction as revenue is possible, a mechanism exists that guarantees revenue arbitrarily close to full surplus for sufficiently close distributions. Intuitively, our results suggest that a high degree of correlation will be essential in the effective application of correlated mechanism design techniques to settings with uncertain distributions.

AAAI Conference 2017 Conference Paper

Moral Decision Making Frameworks for Artificial Intelligence

• Vincent Conitzer
• Walter Sinnott-Armstrong
• Jana Schaich Borg
• Yuan Deng
• Max Kramer

The generality of decision and game theory has enabled domain-independent progress in AI research. For example, a better algorithm for finding good policies in (PO)MDPs can be instantly used in a variety of applications. But such a general theory is lacking when it comes to moral decision making. For AI applications with a moral component, are we then forced to build systems based on many ad-hoc rules? In this paper we discuss possible ways to avoid this conclusion.

IJCAI Conference 2016 Conference Paper

ATUCAPTS: Automated Tests that a User Cannot Pass Twice Simultaneously

• Garrett Andersen
• Vincent Conitzer

In highly anonymous environments such as the Internet, many applications suffer from the fact that a single user can pose as multiple users. Indeed, presumably many potential applications do not even get off the ground as a result. Consider the example of an online vote. Requiring voters to provide identifying information, to the extent that this is even feasible, can significantly deter participation. On the other hand, not doing so makes it possible for a single individual to vote more than once, so that the result may become almost meaningless. (A quick web search will reveal many examples of Internet polls with bizarre outcomes. ) CAPTCHAs may prevent running a program that votes many times, but they do nothing to prevent a single user from voting many times by hand. In this paper, we propose ATUCAPTS (Automated Tests That a User Cannot Pass Twice Simultaneously) as a solution. ATUCAPTS are automatically generated tests such that it is (1) easy for a user to pass one instance, but (2) extremely difficult for a user to pass two instances at the same time. Thus, if it is feasible to require all users to take such a test at the same time, we can verify that no user holds more than one account. We propose a specific class of ATUCAPTS and present the results of a human subjects study to validate that they satisfy the two properties above. We also introduce several theoretical models of how well an attacker might perform and show that these models still allow for good performance on both (1) and (2) with reasonable test lengths.

IJCAI Conference 2016 Conference Paper

Catcher-Evader Games

• Yuqian Li
• Vincent Conitzer
• Dmytro Korzhyk

Algorithms for computing game-theoretic solutions have recently been applied to a number of security domains. However, many of the techniques developed for compact representations of security games do not extend to Bayesian security games, which allow us to model uncertainty about the attacker's type. In this paper, we introduce a general framework of catcher-evader games that can capture Bayesian security games as well as other game families of interest. We show that computing Stackelberg strategies is NP-hard, but give an algorithm for computing a Nash equilibrium that performs well in experiments. We also prove that the Nash equilibria of these games satisfy the interchangeability property, so that equilibrium selection is not an issue.

AAAI Conference 2016 Conference Paper

Computing Possible and Necessary Equilibrium Actions (and Bipartisan Set Winners)

• Markus Brill
• Rupert Freeman
• Vincent Conitzer

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.

AAMAS Conference 2016 Conference Paper

False-Name-Proof Recommendations in Social Networks

• Markus Brill
• Vincent Conitzer
• Rupert Freeman
• Nisarg Shah

We study the problem of finding a recommendation for an uninformed user in a social network by weighting and aggregating the opinions offered by the informed users in the network. In social networks, an informed user may try to manipulate the recommendation by performing a false-name manipulation, wherein the user submits multiple opinions through fake accounts. To that end, we impose a no harm axiom: false-name manipulations by a user should not reduce the weight of other users in the network. We show that this axiom has deep connections to false-nameproofness. While it is impossible to design a mechanism that is best for every network subject to this axiom, we propose an intuitive mechanism LEGIT +, and show that it is uniquely optimized for small networks. Using real-world datasets, we show that our mechanism performs very well compared to two baseline mechanisms in a number of metrics, even on large networks.

AAAI Conference 2016 Conference Paper

Maximizing Revenue with Limited Correlation: The Cost of Ex-Post Incentive Compatibility

• Michael Albert
• Vincent Conitzer
• Giuseppe Lopomo

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 expost 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.

IJCAI Conference 2016 Conference Paper

Role Assignment for Game-Theoretic Cooperation

• Catherine Moon
• Vincent Conitzer

In multiagent systems, often agents need to be assigned to different roles. Multiple aspects should be taken into account for this, such as agents' skills and constraints posed by existing assignments. In this paper, we focus on another aspect: when the agents are self-interested, careful role assignment is necessary to make cooperative behavior an equilibrium of the repeated game. We formalize this problem and provide an easy-to-check necessary and sufficient condition for a given role assignment to induce cooperation. However, we show that finding whether such a role assignment exists is in general NP-hard. Nevertheless, we give two algorithms for solving the problem. The first is based on a mixed-integer linear program formulation. The second is based on a dynamic program, and runs in pseudopolynomial time if the number of agents is constant. Minor modifications of these algorithms also allow for determination of the minimal subsidy necessary to induce cooperation. In our experiments, the IP performs much, much faster.

AAMAS Conference 2016 Conference Paper

Role Assignment for Game-Theoretic Cooperation (Extended Abstract)

• Catherine Moon
• Vincent Conitzer

In multiagent systems, often agents need to be assigned to different roles. Multiple aspects should be taken into account for this, such as agents’ skills and constraints posed by existing assignments. In this paper, we focus on another aspect: when the agents are self-interested, careful role assignment is necessary to make cooperative behavior an equilibrium of the repeated game. We formalize this problem and provide an easy-to-check necessary and sufficient condition for a given role assignment to induce cooperation. However, we show that finding whether such a role assignment exists is in general NP-hard. Nevertheless, we give two algorithms for solving the problem. The first is based on a mixed-integer linear program formulation. The second is based on a dynamic program, and runs in pseudopolynomial time if the number of agents is constant. Minor modifications of these algorithms also allow for determination of the minimal subsidy necessary to induce cooperation. In our experiments, the IP performs much, much faster.

AAAI Conference 2016 Conference Paper

Rules for Choosing Societal Tradeoffs

• Vincent Conitzer
• Rupert Freeman
• Markus Brill
• Yuqian Li

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.

AAMAS Conference 2016 Conference Paper

Signaling in Bayesian Stackelberg Games

• Haifeng Xu
• Rupert Freeman
• Vincent Conitzer
• Shaddin Dughmi
• Milind Tambe

Algorithms for solving Stackelberg games are used in an ever-growing variety of real-world domains. Previous work has extended this framework to allow the leader to commit not only to a distribution over actions, but also to a scheme for stochastically signaling information about these actions to the follower. This can result in higher utility for the leader. In this paper, we extend this methodology to Bayesian games, in which either the leader or the follower has payoff-relevant private information or both. This leads to novel variants of the model, for example by imposing an incentive compatibility constraint for each type to listen to the signal intended for it. We show that, in contrast to previous hardness results for the case without signaling [5, 16], we can solve unrestricted games in time polynomial in their natural representation. For security games, we obtain hardness results as well as efficient algorithms, depending on the settings. We show the benefits of our approach in experimental evaluations of our algorithms.

AAAI Conference 2015 Conference Paper

Assessing the Robustness of Cremer-McLean with Automated Mechanism Design

• Michael Albert
• Vincent Conitzer
• Giuseppe Lopomo

In a classic result in the mechanism design literature, Cremer and McLean (1985) show that if buyers’ valuations are sufficiently correlated, a mechanism exists that allows the seller to extract the full surplus from efficient allocation as revenue. This result is commonly seen as “too good to be true” (in practice), casting doubt on its modeling assumptions. In this paper, we use an automated mechanism design approach to assess how sensitive the Cremer-McLean result is to relaxing its main technical assumption. That assumption implies that each valuation that a bidder can have results in a unique conditional distribution over the external signal(s). We relax this, allowing multiple valuations to be consistent with the same distribution over the external signal(s). Using similar insights to Cremer-McLean, we provide a highly efficient algorithm for computing the optimal revenue in this more general case. Using this algorithm, we observe that indeed, as the number of valuations consistent with a distribution grows, the optimal revenue quickly drops to that of a reserve-price mechanism. Thus, automated mechanism design allows us to gain insight into the precise sense in which Cremer-McLean is “too good to be true. ”

AAAI Conference 2015 Conference Paper

Cooperative Game Solution Concepts that Maximize Stability under Noise

• Yuqian Li
• Vincent Conitzer

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.

AAAI Conference 2015 Conference Paper

Justified Representation in Approval-Based Committee Voting

• Haris Aziz
• Markus Brill
• Vincent Conitzer
• Edith Elkind
• Rupert Freeman
• Toby Walsh

We consider approval-based committee voting, i. e. , the setting where each voter approves a subset of candidates, and these votes are then used to select a fixed-size set of winners (committee). We propose a natural axiom for this setting, which we call justified representation (JR). This axiom requires that if a large enough group of voters exhibits agreement by supporting the same candidate, then at least one voter in this group has an approved candidate in the winning committee. We show that for every list of ballots it is possible to select a committee that provides JR. We then check if this axiom is fulfilled by well-known approval-based voting rules. We show that the answer is negative for most of the rules we consider, with notable exceptions of PAV (Proportional Approval Voting), an extreme version of RAV (Reweighted Approval Voting), and, for a restricted preference domain, MAV (Minimax Approval Voting). We then introduce a stronger version of the JR axiom, which we call extended justified representation (EJR), and show that PAV satisfies EJR, while other rules do not. We also consider several other questions related to JR and EJR, including the relationship between JR/EJR and unanimity, and the complexity of the associated algorithmic problems.

IJCAI Conference 2015 Conference Paper

Maximal Cooperation in Repeated Games on Social Networks

• Catherine Moon
• Vincent Conitzer

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 forevercooperating 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.

AAAI Conference 2015 Conference Paper

Strategic Voting and Strategic Candidacy

• Markus Brill
• Vincent Conitzer

Models of strategic candidacy analyze the incentives of candidates to run in an election. Most work on this topic assumes that strategizing only takes place among candidates, whereas voters vote truthfully. In this paper, we extend the analysis to also include strategic behavior on the part of the voters. (We also study cases where only candidates or only voters are strategic.) We consider two settings in which strategic voting is well-defined and has a natural interpretation: majorityconsistent voting with single-peaked preferences and voting by successive elimination. In the former setting, we analyze the type of strategic behavior required in order to guarantee desirable voting outcomes. In the latter setting, we determine the complexity of computing the set of potential outcomes if both candidates and voters act strategically.

AAAI Conference 2014 Conference Paper

Beat the Cheater: Computing Game-Theoretic Strategies for When to Kick a Gambler out of a Casino

• Troels Sørensen
• Melissa Dalis
• Joshua Letchford
• Dmytro Korzhyk
• Vincent Conitzer

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.

AIJ Journal 2014 Journal Article

Better redistribution with inefficient allocation in multi-unit auctions

• Mingyu Guo
• Vincent Conitzer

For the problem of allocating one or more items among a group of competing agents, the Vickrey–Clarke–Groves (VCG) mechanism is strategy-proof and efficient. However, the VCG mechanism is not strongly budget balanced: in general, value flows out of the system of agents in the form of VCG payments, which reduces the agents' utilities. In many settings, the objective is to maximize the sum of the agents' utilities (taking payments into account). For this purpose, several VCG redistribution mechanisms have been proposed that redistribute a large fraction of the VCG payments back to the agents, in a way that maintains strategy-proofness and the non-deficit property. Unfortunately, sometimes even the best VCG redistribution mechanism fails to redistribute a substantial fraction of the VCG payments. This results in a low total utility for the agents, even though the items are allocated efficiently. In this paper, we study strategy-proof allocation mechanisms that do not always allocate the items efficiently. It turns out that by allocating inefficiently, more payment can sometimes be redistributed, so that the net effect is an increase in the sum of the agents' utilities. Our objective is to design mechanisms that are competitive against the first-best mechanism in terms of the agents' total utility. We first study multi-unit auctions with unit demand. We characterize the family of linear allocation mechanisms. We propose an optimization technique for simultaneously finding a linear allocation mechanism and a payment redistribution rule, which together are optimal. With the help of this technique, we also analytically characterize several competitive mechanisms, which are based on burning units and partitioning the agents into groups. Finally, we extend the definition of linear allocation mechanisms and the optimization technique to general multi-unit auctions.

AAAI Conference 2014 Conference Paper

Mechanism Design for Scheduling with Uncertain Execution Time

• Vincent Conitzer
• Angelina Vidali

We study the problem where a task (or multiple unrelated tasks) must be executed, there are multiple machines/agents that can potentially perform the task, and our objective is to minimize the expected sum of the agents’ processing times. Each agent does not know exactly how long it will take him to finish the task; he only knows the distribution from which this time is drawn. These times are independent across agents and the distributions fulfill the monotone hazard rate condition. Agents are selfish and will lie about their distributions if this increases their expected utility. We study different variations of the Vickrey mechanism that take as input the agents’ reported distributions and the players’ realized running times and that output a schedule that minimizes the expected sum of processing times, as well as payments that make it an ex-post equilibrium for the agents to both truthfully report their distributions and exert full effort to complete the task. We devise the ChPE mechanism, which is uniquely tailored to our problem, and has many desirable properties including: not rewarding agents that fail to finish the task and having non-negative payments.

AAAI Conference 2014 Conference Paper

On the Axiomatic Characterization of Runoff Voting Rules

• Rupert Freeman
• Markus Brill
• Vincent Conitzer

Runoff voting rules such as single transferable vote (STV) and Baldwin’s rule are of particular interest in computational social choice due to their recursive nature and hardness of manipulation, as well as in (human) practice because they are relatively easy to understand. However, they are not known for their compliance with desirable axiomatic properties, which we attempt to rectify here. We characterize runoff rules that are based on scoring rules using two axioms: a weakening of local independence of irrelevant alternatives and a variant of population-consistency. We then show, as our main technical result, that STV is the only runoff scoring rule satisfying an independence-of-clones property. Furthermore, we provide axiomatizations of Baldwin’s rule and Coombs’ rule.

AAAI Conference 2014 Conference Paper

Solving Zero-Sum Security Games in Discretized Spatio-Temporal Domains

• Haifeng Xu
• Fei Fang
• Albert Jiang
• Vincent Conitzer
• Shaddin Dughmi
• Milind Tambe

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 of the 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 difficult to find, we propose approximations or prove hardness results.

AAAI Conference 2013 Conference Paper

Fast Equilibrium Computation for Infinitely Repeated Games

• Garrett Andersen
• Vincent Conitzer

It is known that an equilibrium of an infinitely repeated two-player game (with limit average payoffs) can be computed in polynomial time, as follows: according to the folk theorem, we compute minimax strategies for both players to calculate the punishment values, and subsequently find a mixture over outcomes that exceeds these punishment values. However, for very large games, even computing minimax strategies can be prohibitive. In this paper, we propose an algorithmic framework for computing equilibria of repeated games that does not require linear programming and that does not necessarily need to inspect all payoffs of the game. This algorithm necessarily sometimes fails to compute an equilibrium, but we mathematically demonstrate that most of the time it succeeds quickly on uniformly random games, and experimentally demonstrate this for other classes of games. This also holds for games with more than two players, for which no efficient general algorithms are known.

IJCAI Conference 2013 Conference Paper

Game-Theoretic Question Selection for Tests

• Yuqian Li
• Vincent Conitzer

Conventionally, the questions on a test are assumed to be kept secret from test takers until the test. However, for tests that are taken on a large scale, particularly asynchronously, this is very hard to achieve. For example, example TOEFL iBT and driver’s license test questions are easily found online. This also appears likely to become an issue for Massive Open Online Courses (MOOCs). In this paper, we take the loss of confidentiality as a fact. Even so, not all hope is lost as the test taker can memorize only a limited set of questions’ answers, and the tester can randomize which questions appear on the test. We model this as a Stackelberg game, where the tester commits to a mixed strategy and the follower responds. We provide an exponential-size linear program formulation, prove several NP-hardness results, and give efficient algorithms for special cases.

JAAMAS Journal 2013 Journal Article

On the value of commitment

• Joshua Letchford
• Dmytro Korzhyk
• Vincent Conitzer

Abstract In game theory, it is well known that being able to commit to a strategy before other players move can be beneficial. In this paper, we analyze how much benefit a player can derive from commitment in various types of games, in a quantitative sense that is similar to concepts such as the value of mediation and the price of anarchy. Specifically, we introduce and study the value of pure commitment (the benefit of committing to a pure strategy), the value of mixed commitment (the benefit of committing to a mixed strategy), and the mixed versus pure commitment ratio (how much can be gained by committing to a mixed strategy rather than a pure one). In addition to theoretical results about how large these values are in the extreme case in various classes of games, we also give average-case results based on randomly drawn normal-form games.

AAAI Conference 2013 Conference Paper

Solving Security Games on Graphs via Marginal Probabilities

• Joshua Letchford
• Vincent Conitzer

Security games involving the allocation of multiple security resources to defend multiple targets generally have an exponential number of pure strategies for the defender. One method that has been successful in addressing this computational issue is to instead directly compute the marginal probabilities with which the individual resources are assigned (first pursued by Kiekintveld et al. (2009)). However, in sufficiently general settings, there exist games where these marginal solutions are not implementable, that is, they do not correspond to any mixed strategy of the defender. In this paper, we examine security games where the defender tries to monitor the vertices of a graph, and we show how the type of graph, the type of schedules, and the type of defender resources affect the applicability of this approach. In some settings, we show the approach is applicable and give a polynomial-time algorithm for computing an optimal defender strategy; in other settings, we give counterexample games that demonstrate that the approach does not work, and prove NP-hardness results for computing an optimal defender strategy.

AAAI Conference 2012 Conference Paper

Computing Game-Theoretic Solutions and Applications to Security

• Vincent Conitzer

The multiagent systems community has adopted game theory as a framework for the design of systems of multiple self-interested agents. For this to be effective, efficient algorithms must be designed to compute the solutions that game theory prescribes. In this paper, I summarize some of the state of the art on this topic, focusing particularly on how this line of work has contributed to several highly visible deployed security applications, developed at the University of Southern California.

AAAI Conference 2012 Conference Paper

Computing Optimal Strategies to Commit to in Stochastic Games

• Joshua Letchford
• Liam MacDermed
• Vincent Conitzer
• Ronald Parr
• Charles Isbell

Significant progress has been made recently in the following two lines of research in the intersection of AI and game theory: (1) the computation of optimal strategies to commit to (Stackelberg strategies), and (2) the computation of correlated equilibria of stochastic games. In this paper, we unite these two lines of research by studying the computation of Stackelberg strategies in stochastic games. We provide theoretical results on the value of being able to commit and the value of being able to correlate, as well as complexity results about computing Stackelberg strategies in stochastic games. We then modify the QPACE algorithm (MacDermed et al. 2011) to compute Stackelberg strategies, and provide experimental results.

AAAI Conference 2012 Conference Paper

Evaluating Resistance to False-Name Manipulations in Elections

• Bo Waggoner
• Lirong Xia
• Vincent Conitzer

In many mechanisms (especially online mechanisms), a strategic agent can influence the outcome by creating multiple false identities. We consider voting settings where the mechanism designer cannot completely prevent false-name manipulation, but may use false-name-limiting methods such as CAPTCHAs to influence the amount and characteristics of such manipulation. Such a designer would prefer, first, a high probability of obtaining the “correct” outcome, and second, a statistical method for evaluating the correctness of the outcome. In this paper, we focus on settings with two alternatives. We model voters as independently drawing a number of identities from a distribution that may be influenced by the choice of the false-name-limiting method. We give a criterion for the evaluation and comparison of these distributions. Then, given the results of an election in which false-name manipulation may have occurred, we propose and justify a statistical test for evaluating the outcome.

KR Conference 2012 Conference Paper

Paradoxes of Multiple Elections: An Approximation Approach

• Vincent Conitzer
• Lirong Xia

When agents need to make decisions on multiple issues, applying common voting rules becomes computationally hard due to the exponentially large number of alternatives. One computationally efficient solution is to vote on the issues sequentially. In this paper, we investigate how well the winner under the sequential voting process approximates the winners under some common voting rules that admit natural scoring functions that can serve as a basis for approximation results. We focus on multi-issue domains where each issue is binary and the agents’ preferences are O-legal, separable, represented by LP-trees, or lexicographic. We show some generalized paradoxes of multiple elections: Sequential voting does not approximate many common voting rules well even when the preferences are O-legal or separable. However, these paradoxes are much alleviated or even completely avoided when the preferences are lexicographic or represented by LP-trees. Our results thus draw a border for conditions under which sequential voting rules, which have extremely low computational and communicational cost, are good approximations of some common voting rules w. r. t. their corresponding scoring functions.

AAMAS Conference 2011 Conference Paper

A Double Oracle Algorithm for Zero-Sum Security Games on Graphs

• Manish Jain
• Dmytro Korzhyk
• Ond
• #X159; ej Van
• #X11b; k
• Vincent Conitzer
• Michal P
• #X11b; chou

In response to the Mumbai attacks of 2008, the Mumbai police have started to schedule a limited number of inspection checkpoints on the road network throughout the city. Algorithms for similar security-related scheduling problems have been proposed in recent literature, but security scheduling in networked domains when targets have varying importance remains an open problem at large. In this paper, we cast the network security problem as an attackerdefender zero-sum game. The strategy spaces for both players are exponentially large, so this requires the development of novel, scalable techniques. We first show that existing algorithms for approximate solutions can be arbitrarily bad in general settings. We present RUGGED (Randomization in Urban Graphs by Generating strategies for Enemy and Defender), the first scalable optimal solution technique for such network security games. Our technique is based on a double oracle approach and thus does not require the enumeration of the entire strategy space for either of the players. It scales up to realistic problem sizes, as is shown by our evaluation of maps of southern Mumbai obtained from GIS data.

IJCAI Conference 2011 Conference Paper

A Maximum Likelihood Approach towards Aggregating Partial Orders

• Lirong Xia
• Vincent Conitzer

In many of the possible applications as well as the theoretical models of computational social choice, the agents' preferences are represented as partialorders. In this paper, we extend the maximum likelihood approach for defining "optimal" voting rules to this setting. We consider distributions in which the pairwise comparisons / incomparabilities between alternatives are drawn i. i. d. We call suchmodels pairwise-independentmodels and show that they correspond to a class of voting rules that we call pairwise scoring rules. This generalizes rulessuch as Kemeny and Borda. Moreover, we show that Borda is the only pairwise scoring rule that satisfies neutrality, when the outcome space is the set of all alternatives. We then study which voting rules defined for linear orders can be extended to partial orders via our MLE model. We show that any weakly neutral outcome scoring rule (includingany ranking/candidate scoring rule) based onthe weighted majority graph can be represented as the MLE of a weakly neutral pairwise-independent model. Therefore, all such rules admit natural extensionsto profiles of partial orders. Finally, we propose a specific MLE model π k for generating a set of k winning alternatives, and study the computational complexity of winner determination for the MLE of π k.

AAAI Conference 2011 Conference Paper

Commitment to Correlated Strategies

• Vincent Conitzer
• Dmytro Korzhyk

The standard approach to computing an optimal mixed strategy to commit to is based on solving a set of linear programs, one for each of the follower’s pure strategies. We show that these linear programs can be naturally merged into a single linear program; that this linear program can be interpreted as a formulation for the optimal correlated strategy to commit to, giving an easy proof of a result by von Stengel and Zamir that the leader’s utility is at least the utility she gets in any correlated equilibrium of the simultaneous-move game; and that this linear program can be extended to compute optimal correlated strategies to commit to in games of three or more players. (Unlike in two-player games, in games of three or more players, the notions of optimal mixed and correlated strategies to commit to are truly distinct.) We give examples, and provide experimental results that indicate that for 50 × 50 games, this approach is usually significantly faster than the multiple-LPs approach.

AAAI Conference 2011 Conference Paper

Dominating Manipulations in Voting with Partial Information

• Vincent Conitzer
• Toby Walsh
• Lirong Xia

We consider manipulation problems when the manipulator only has partial information about the votes of the nonmanipulators. Such partial information is described by an information set, which is the set of profiles of the nonmanipulators that are indistinguishable to the manipulator. Given such an information set, a dominating manipulation is a non-truthful vote that the manipulator can cast which makes the winner at least as preferable (and sometimes more preferable) as the winner when the manipulator votes truthfully. When the manipulator has full information, computing whether or not there exists a dominating manipulation is in P for many common voting rules (by known results). We show that when the manipulator has no information, there is no dominating manipulation for many common voting rules. When the manipulator’s information is represented by partial orders and only a small portion of the preferences are unknown, computing a dominating manipulation is NP-hard for many common voting rules. Our results thus throw light on whether we can prevent strategic behavior by limiting information about the votes of other voters.

AIJ Journal 2011 Journal Article

Expressive markets for donating to charities

• Vincent Conitzer
• Tuomas Sandholm

When donating money to a (say, charitable) cause, it is possible to use the contemplated donation as a bargaining chip to induce other parties interested in the charity to donate more. Such negotiation is usually done in terms of matching offers, where one party promises to pay a certain amount if others pay a certain amount. However, in their current form, matching offers allow for only limited negotiation. For one, it is not immediately clear how multiple parties can make matching offers at the same time without creating circular dependencies. Also, it is not immediately clear how to make a donation conditional on other donations to multiple charities when the donor has different levels of appreciation for the different charities. In both these cases, the limited expressiveness of matching offers causes economic loss: it may happen that an arrangement that all parties (donors as well as charities) would have preferred cannot be expressed in terms of matching offers and will therefore not occur. In this paper, we introduce a bidding language for expressing very general types of matching offers over multiple charities. We formulate the corresponding clearing problem (deciding how much each bidder pays, and how much each charity receives), and show that it cannot be approximated to any ratio in polynomial time unless P=NP, even in very restricted settings. We give a mixed integer program formulation of the clearing problem, and show that for concave bids, the program reduces to a linear program. We then show that the clearing problem for a subclass of concave bids is at least as hard as the decision variant of linear programming. We also consider the case where each charity has a target amount, and biddersʼ willingness-to-pay functions are concave. Here, we show that the optimal surplus can be approximated to a ratio m, the number of charities, in polynomial time (and no significantly better approximation is possible in polynomial time unless P=NP); no polynomial-time approximation ratio is possible for maximizing the total donated, unless P=NP. Subsequently, we show that the clearing problem is much easier when bids are quasilinear—for maximizing surplus, the problem decomposes across charities, and for maximizing the total donated, a greedy approach is optimal if the bids are concave (although this latter problem is weakly NP-hard when the bids are not concave). For the quasilinear setting, we study the mechanism design question. We show that an ex-post efficient mechanism is impossible even with only one charity and a very restricted class of bids. We also show that there can be benefits to linking the charities from a mechanism design standpoint. Finally, we discuss an experiment in which we used this methodology to collect money for victims of the 2004 Indian Ocean Tsunami.

IJCAI Conference 2011 Conference Paper

Hypercubewise Preference Aggregation in Multi-Issue Domains

• Vincent Conitzer
• J
• eacute; r
• ocirc; me Lang
• Lirong Xia

We consider a framework for preference aggregation on multiple binary issues, where agents' preferences are represented by (possibly cyclic) CP-nets. We focus on the majority aggregation of the individual CP-nets, which is the CP-net where the direction of each edge of the hypercube is decided according to the majority rule. First we focus on hypercube Condorcet winners (HCWs); in particular, we show that, assuming a uniform distribution for the CP-nets, the probability that there exists at least one HCW is at least 1-1/e, and the expected number of HCWs is 1. Our experimental results confirm these results. We also show experimental results under the Impartial Culture assumption. We then generalize a few tournament solutions to select winners from (weighted) majoritarian CP-nets, namely Copeland, maximin, and Kemeny. For each of these, we address some social choice theoretic and computational issues.

IJCAI Conference 2011 Conference Paper

Security Games with Multiple Attacker Resources

• Dmytro Korzhyk
• Vincent Conitzer
• Ronald Parr

Algorithms for finding game-theoretic solutions are now used in several real-world security applications. This work has generally assumed a Stackelberg model where the defender commits to a mixed strategy first. In general two-player normal-form games, Stackelberg strategies are easier to compute than Nash equilibria, though it has recently been shown that in many security games, Stackelberg strategies are also Nash strategies for the defender. However, the work on security games so far assumes that the attacker attacks only a single target. In this paper, we generalize to the case where the attacker attacks multiple targets simultaneously. Here, Stackelberg and Nash strategies for the defender can be truly different. We provide a polynomial-time algorithm for finding a Nash equilibrium. The algorithm gradually increases the number of defender resources and maintains an equilibrium throughout this process. Moreover, we prove that Nash equilibria in security games with multiple attackers satisfy the interchange property, which resolves the problem of equilibrium selection in such games. On the other hand, we show that Stackelberg strategies are actually NP-hard to compute in this context. Finally, we provide experimental results.

AAMAS Conference 2011 Conference Paper

Solving Stackelberg Games with Uncertain Observability

• Dmytro Korzhyk
• Vincent Conitzer
• Ronald Parr

Recent applications of game theory in security domains use algorithms to solve a Stackelberg model, in which one player (the leader) first commits to a mixed strategy and then the other player (the follower) observes that strategy and best-responds to it. However, in real-world applications, it is hard to determine whether the follower is actually able to observe the leader's mixed strategy before acting. In this paper, we model the uncertainty about whether the follower is able to observe the leader's strategy as part of the game (as proposed in the extended version of Yin et al. [17]). We describe an iterative algorithm for solving these games. This algorithm alternates between calling a Nash equilibrium solver and a Stackelberg solver as subroutines. We prove that the algorithm finds a solution in a finite number of steps and show empirically that it runs fast on games of reasonable size. We also discuss other properties of this methodology based on the experiments.

AAMAS Conference 2010 Conference Paper

Aggregating Preferences in Multi-Issue Domains by Using Maximum Likelihood Estimators

• Lirong Xia
• Vincent Conitzer
• Jerome Lang

In this paper, we study a maximum likelihood estimation (MLE)approach to voting when the set of alternatives has a multi-issuestructure, and the voters' preferences are represented by CP-nets. We first consider general multi-issue domains, and study whetherand how issue-by-issue voting rules and sequential voting rulescan be represented by MLEs. We first show that issue-by-issuevoting rules in which each local rule is itself an MLE (resp. acandidate scoring rule) can be represented by MLEs with a weak(resp. strong) decomposability property. Then, we prove two theorems that state that if the noise model satisfies a very weak decomposability property, then no sequential voting rule that satisfiesunanimity can be represented by an MLE, unless the number ofvoters is bounded. We then consider multi-issue domains in which each issue isbinary; for these, we propose a general family of distance-basednoise models, of which give an axiomatic characterization. Wethen propose a more specific family of natural distance-based noisemodels that are parameterized by a threshold. We identify the complexity of winner determination for the corresponding MLE votingrule in the two most important subcases of this framework.

AAAI Conference 2010 Conference Paper

Compilation Complexity of Common Voting Rules

• Lirong Xia
• Vincent Conitzer

In computational social choice, one important problem is to take the votes of a subelectorate (subset of the voters), and summarize them using a small number of bits. This needs to be done in such a way that, if all that we know is the summary, as well as the votes of voters outside the subelectorate, we can conclude which of the m alternatives wins. This corresponds to the notion of compilation complexity, the minimum number of bits required to summarize the votes for a particular rule, which was introduced by Chevaleyre et al. [IJCAI- 09]. We study three different types of compilation complexity. The first, studied by Chevaleyre et al. , depends on the size of the subelectorate but not on the size of the complement (the voters outside the subelectorate). The second depends on the size of the complement but not on the size of the subelectorate. The third depends on both. We first investigate the relations among the three types of compilation complexity. Then, we give upper and lower bounds on all three types of compilation complexity for the most prominent voting rules. We show that for l-approval (when l ≤ m/2), Borda, and Bucklin, the bounds for all three types are asymptotically tight, up to a multiplicative constant; for l-approval (when l > m/2), plurality with runoff, all Condorcet consistent rules that are based on unweighted majority graphs (including Copeland and voting trees), and all Condorcet consistent rules that are based on the order of pairwise elections (including ranked pairs and maximin), the bounds for all three types are asymptotically tight up to a multiplicative constant when the sizes of the subelectorate and its complement are both larger than m1+ for some > 0.

AAAI Conference 2010 Conference Paper

Complexity of Computing Optimal Stackelberg Strategies in Security Resource Allocation Games

• Dmytro Korzhyk
• Vincent Conitzer
• Ronald Parr

Recently, algorithms for computing game-theoretic solutions have been deployed in real-world security applications, such as the placement of checkpoints and canine units at Los Angeles International Airport. These algorithms assume that the defender (security personnel) can commit to a mixed strategy, a so-called Stackelberg model. As pointed out by Kiekintveld et al. (2009), in these applications, generally, multiple resources need to be assigned to multiple targets, resulting in an exponential number of pure strategies for the defender. In this paper, we study how to compute optimal Stackelberg strategies in such games, showing that this can be done in polynomial time in some cases, and is NP-hard in others.

AAAI Conference 2010 Conference Paper

Computationally Feasible Automated Mechanism Design: General Approach and Case Studies

• Mingyu Guo
• Vincent Conitzer

AAMAS Conference 2010 Conference Paper

False-Name-Proofness with Bid Withdrawal

• Mingyu Guo
• Vincent Conitzer

We study a more powerful variant of false-name manipulation in Internet auctions: an agent can submit multiple false-name bids, butthen, once the allocation and payments have been decided, withdraw some of her false-name identities (have some of her false-name identities refuse to pay). While these withdrawn identitieswill not obtain the items they won, their initial presence may havebeen beneficial to the agent's other identities. We define a mechanism to be false-name-proof with withdrawal (FNPW) if the aforementioned manipulation is never beneficial. FNPW is a strongercondition than false-name-proofness (FNP). We discuss the relation between FNP and FNPW in general combinatorial auction settings. We also propose the maximum marginalvalue item pricing (MMVIP) mechanism, which we prove is FNPW. (The full version contains a number of other results. )

SODA Conference 2010 Conference Paper

Incentive Compatible Budget Elicitation in Multi-unit Auctions

• Sayan Bhattacharya
• Vincent Conitzer
• Kamesh Munagala
• Lirong Xia

AIJ Journal 2010 Journal Article

Optimal-in-expectation redistribution mechanisms

• Mingyu Guo
• Vincent Conitzer

Many important problems in multiagent systems involve the allocation of multiple resources among the agents. If agents are self-interested, they will lie about their valuations for the resources if they perceive this to be in their interest. The well-known VCG mechanism allocates the items efficiently, is strategy-proof (agents have no incentive to lie), and never runs a deficit. Nevertheless, the agents may have to make large payments to a party outside the system of agents, leading to decreased utility for the agents. Recent work has investigated the possibility of redistributing some of the payments back to the agents, without violating the other desirable properties of the VCG mechanism. Previous research on redistribution mechanisms has resulted in a worst-case optimal redistribution mechanism, that is, a mechanism that maximizes the fraction of VCG payments redistributed in the worst case. In contrast, in this paper, we assume that a prior distribution over the agents' valuations is available, and our goal is to maximize the expected total redistribution. In the first part of this paper, we study multi-unit auctions with unit demand. We analytically solve for a mechanism that is optimal among linear redistribution mechanisms. We also propose discretized redistribution mechanisms. We show how to automatically solve for the optimal discretized redistribution mechanism for a given discretization step size, and show that the resulting mechanisms converge to optimality as the step size goes to zero. We present experimental results showing that for auctions with many bidders, the optimal linear redistribution mechanism redistributes almost everything, whereas for auctions with few bidders, we can solve for the optimal discretized redistribution mechanism with a very small step size. In the second part of this paper, we study multi-unit auctions with nonincreasing marginal values. We extend the notion of linear redistribution mechanisms, previously defined only in the unit demand setting, to this more general setting. We introduce a linear program for finding the optimal linear redistribution mechanism. This linear program is unwieldy, so we also introduce one simplified linear program that produces relatively good linear redistribution mechanisms. We conjecture an analytical solution for the simplified linear program.

AAAI Conference 2010 Conference Paper

Stackelberg Voting Games: Computational Aspects and Paradoxes

• Lirong Xia
• Vincent Conitzer

We consider settings in which voters vote in sequence, each voter knows the votes of the earlier voters and the preferences of the later voters, and voters are strategic. This can be modeled as an extensive-form game of perfect information, which we call a Stackelberg voting game. We first propose a dynamic-programming algorithm for finding the backward-induction outcome for any Stackelberg voting game when the rule is anonymous; this algorithm is efficient if the number of alternatives is no more than a constant. We show how to use compilation functions to further reduce the time and space requirements. Our main theoretical results are paradoxes for the backwardinduction outcomes of Stackelberg voting games. We show that for any n ≥ 5 and any voting rule that satisfies nonimposition and with a low domination index, there exists a profile consisting of n voters, such that the backwardinduction outcome is ranked somewhere in the bottom two positions in almost every voter’s preferences. Moreover, this outcome loses all but one of its pairwise elections. Furthermore, we show that many common voting rules have a very low (= 1) domination index, including all majorityconsistent voting rules. For the plurality and nomination rules, we show even stronger paradoxes. Finally, using our dynamic-programming algorithm, we run simulations to compare the backward-induction outcome of the Stackelberg voting game to the winner when voters vote truthfully, for the plurality and veto rules. Surprisingly, our experimental results suggest that on average, more voters prefer the backward-induction outcome.

AAMAS Conference 2010 Conference Paper

Stackelberg vs. Nash in Security Games: Interchangeability, Equivalence, and Uniqueness

• Zhengyu Yin
• Dmytro Korzhyk
• Christopher Kiekintveld
• Vincent Conitzer
• Milind Tambe

There has been significant recent interest in game theoretic approaches to security, with much of the recent research focused onutilizing the leader-follower Stackelberg game model; for example, these games are at the heart of major applications such asthe ARMOR program deployed for security at the LAX airportsince 2007 and the IRIS program in use by the US Federal AirMarshals (FAMS). The foundational assumption for using Stackelberg games is that security forces (leaders), acting first, commit toa randomized strategy; while their adversaries (followers) choosetheir best response after surveillance of this randomized strategy. Yet, in many situations, the followers may act without observation of the leader's strategy, essentially converting the game intoa simultaneous-move game model. Previous work fails to addresshow a leader should compute her strategy given this fundamentaluncertainty about the type of game faced. Focusing on the complex games that are directly inspired by realworld security applications, the paper provides four contributionsin the context of a general class of security games. First, exploiting the structure of these security games, the paper shows that theNash equilibria in security games are interchangeable, thus alleviating the equilibrium selection problem. Second, resolving theleader's dilemma, it shows that under a natural restriction on security games, any Stackelberg strategy is also a Nash equilibriumstrategy; and furthermore, the solution is unique in a class of realworld security games of which ARMOR is a key exemplar. Third, when faced with a follower that can attack multiple targets, manyof these properties no longer hold. Fourth, our experimental resultsemphasize positive properties of games that do not fit our restrictions. Our contributions have major implications for the real-worldapplications.

AAMAS Conference 2010 Conference Paper

Strategy-proof Allocation of Multiple Items between Two Agents without Payments or Priors

• Mingyu Guo
• Vincent Conitzer

We investigate the problem of allocating items (private goods) amongcompeting agents in a setting that is both prior-free and payment-free. Specifically, we focus on allocating multiple heterogeneousitems between two agents with additive valuation functions. Ourobjective is to design strategy-proof mechanisms that are competitive against the most efficient (first-best) allocation. We introduce the family of linear increasing-price (LIP) mechanisms. TheLIP mechanisms are strategy-proof, prior-free, and payment-free, and they are exactly the increasing-price mechanisms satisfying astrong responsiveness property. We show how to solve for competitive mechanisms within the LIP family. For the case of two items, we find a LIP mechanism whose competitive ratio is near optimal(the achieved competitive ratio is $0. 828$, while any strategy-proofmechanism is at most $0. 841$-competitive). As the number of itemsgoes to infinity, we prove a negative result that any increasing-pricemechanism (linear or nonlinear) has a maximal competitive ratio of$0. 5$. Our results imply that in some cases, it is possible to designgood allocation mechanisms without payments and without priors.

AAMAS Conference 2010 Conference Paper

Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms

• Atsushi Iwasaki
• Vincent Conitzer
• Yoshifusa Omori
• Yuko Sakurai
• Taiki Todo
• Mingyu Guo
• Makoto Yokoo

This paper analyzes the worst-case efficiency ratio of false-name-proofcombinatorial auction mechanisms. False-name-proofness generalizesstrategy-proofness, by assuming that a bidder can submit multiple bidsunder fictitious identifiers. Even the well-known Vickrey-Clarke-Grovesmechanism is not false-name-proof. It has previously been shown thatthere is no false-name-proof mechanism that always achieves a Paretoefficient allocation. Hence, if false-name bids are possible, we need to sacrifice efficiency to some extent. This leaves the natural question of how much surplusmust be sacrificed. To answer this question, this paper focuses on worst-case analysis. Specifically, we consider thefraction of the Pareto-efficient surplus that we obtain, and try tomaximize this fraction in the worst case, under the constraint offalse-name-proofness. As far as we are aware, this is the first attempt to examine theworst-case efficiency of false-name-proof mechanisms. We show that the worst-case efficiency ratio of any false-name-proofmechanism that satisfies some apparently minor assumptions is atmost $2/(m+1)$ for auctions with $m$ different goods. We also observe that the worst-case efficiency ratioof existing false-name-proof mechanisms is generally $1/m$ or 0. Finally, we propose a novel mechanism, called the adaptive reserve price mechanism, which is false-name-proof when all bidders are single-minded, and its worst-case efficiency ratio is $2/(m+1)$, i. e. , optimal.

IJCAI Conference 2009 Conference Paper

• Erik Halvorson
• Vincent Conitzer
• Ronald Parr

We study a multi-step hider-seeker game where the hider is moving on a graph and, in each step, the seeker is able to search c subsets of the graph nodes. We model this game as a zero-sum Bayesian game, which can be solved in weakly polynomial time in the players’ action spaces. The seeker’s action space is exponential in c, and both players’ action spaces are exponential in the game horizon. To manage this intractability, we use a column/constraint generation approach for both players. This approach requires an oracle to determine best responses for each player. However, we show that computing a best response for the seeker is NPhard, even for a single-step game when c is part of the input, and that computing a best response is NPhard for both players for the multi-step game, even if c = 1. An integer programming formulation of the best response for the hider is practical for moderate horizons, but computing an exact seeker best response is impractical due to the exponential dependence on both c and the horizon. We therefore develop an approximate best response oracle with bounded suboptimality for the seeker. We prove performance bounds on the strategy that results when column/constraint generation with approximate best responses converges, and we measure the performance of our algorithm in simulations. In our experimental results, column/constraint generation converges to near-minimax strategies for both players fairly quickly.

IJCAI Conference 2009 Conference Paper

• Vincent Conitzer
• Matthew Rognlie
• Lirong Xia

In social choice, a preference function (PF) takes a set of votes (linear orders over a set of alternatives) as input, and produces one or more rankings (also linear orders over the alternatives) as output. Such functions have many applications, for example, aggregating the preferences of multiple agents, or merging rankings (of, say, webpages) into a single ranking. The key issue is choosing a PF to use. One natural and previously studied approach is to assume that there is an unobserved “correct” ranking, and the votes are noisy estimates of this. Then, we can use the PF that always chooses the maximum likelihood estimate (MLE) of the correct ranking. In this paper, we define simple ranking scoring functions (SRSFs) and show that the class of neutral SRSFs is exactly the class of neutral PFs that are MLEs for some noise model. We also de- fine composite ranking scoring functions (CRSFs) and show a condition under which these coincide with SRSFs. We study key properties such as consistency and continuity, and consider some example PFs. In particular, we study Single Transferable Vote (STV), a commonly used PF, showing that it is a CRSF but not an SRSF, thereby clarifying the extent to which it is an MLE function. This also gives a new perspective on how ties should be broken under STV. We leave some open questions.

IJCAI Conference 2009 Conference Paper

• Vincent Conitzer
• Jérôme Lang
• Lirong Xia

Voting on multiple related issues is an important and difficult problem. The key difficulty is that the number of alternatives is exponential in the number of issues, and hence it is infeasible for the agents to rank all the alternatives. A simple approach is to vote on the issues one at a time, in sequence; however, a drawback is that the outcome may depend on the order in which the issues are voted upon and decided, which gives the chairperson some control over the outcome of the election because she can strategically determine the order. While this is undeniably a negative feature of sequential voting, in this paper we temper this judgment by showing that the chairperson’s control problem is, in most cases, computationally hard.

IJCAI Conference 2009 Conference Paper

• Lirong Xia
• Vincent Conitzer

An important problem in computational social choice concerns whether it is possible to prevent manipulation of voting rules by making it computationally intractable. To answer this, a key question is how frequently voting rules are manipulable. We [Xia and Conitzer, 2008] recently defined the class of generalized scoring rules (GSRs) and characterized the frequency of manipulability for such rules. We showed, by examples, that most common rules seem to fall into this class. However, no natural axiomatic characterization of the class was given, leaving the possibility that there are natural rules to which these results do not apply. In this paper, we characterize the class of GSRs based on two natural properties: it is equal to the class of rules that are anonymous and finitely locally consistent. Generalized scoring rules also have other uses in computational social choice. For these uses, the order of the GSR (the dimension of its score vector) is important. Our characterization result implies that the order of a GSR is related to the minimum number of locally consistent components of the rule. We proceed to bound the minimum number of locally consistent components for some common rules.

IJCAI Conference 2009 Conference Paper

• Lirong Xia
• Michael Zuckerman
• Ariel D. Procaccia
• Vincent Conitzer
• Jeffrey S. Rosenschein

Understanding the computational complexity of manipulation in elections is arguably the most central agenda in Computational Social Choice. One of the influential variations of the the problem involves a coalition of manipulators trying to make a favorite candidate win the election. Although the complexity of the problem is well-studied under the assumption that the voters are weighted, there were very few successful attempts to abandon this strong assumption. In this paper, we study the complexity of the unweighted coalitional manipulation problem (UCM) under several prominent voting rules. Our main result is that UCM is NP-complete under the maximin rule; this resolves an enigmatic open question. We then show that UCM is NP-complete under the ranked pairs rule, even with respect to a single manipulator. Furthermore, we provide an extreme hardness-of-approximation result for an optimization version of UCM under ranked pairs. Finally, we show that UCM under the Bucklin rule is in P.

JAAMAS Journal 2009 Journal Article

Aggregating value ranges: preference elicitation and truthfulness

• Joseph Farfel
• Vincent Conitzer

Abstract We study the case where agents have preferences over ranges (intervals) of values, and we wish to elicit and aggregate these preferences. For example, consider a set of climatologist agents who are asked for their predictions for the increase in temperature between 2009 and 2100. Each climatologist submits a range, and from these ranges we must construct an aggregate range. What rule should we use for constructing the aggregate range? One issue in such settings is that an agent (climatologist) may misreport her range to make the aggregate range coincide more closely with her own (true) most-preferred range. We extend the theory of single-peaked preferences from points to ranges to obtain a rule (the median-of-ranges rule) that is strategy-proof under a condition on preferences. We then introduce and analyze a natural class of algorithms for approximately eliciting a median range from multiple agents. We also show sufficient conditions under which such an approximate elicitation algorithm still incentivizes agents to answer truthfully. Finally, we consider the possibility that ranges can be refined when the topic is more completely specified (for example, the increase in temperature on the North Pole given the failure of future climate pacts). We give a framework and algorithms for selectively specifying the topic further based on queries to agents.

UAI Conference 2009 Conference Paper

Prediction Markets, Mechanism Design, and Cooperative Game Theory

• Vincent Conitzer

ket ensures that agents are rewarded for contributing useful and accurate information. Prediction markets are designed to elicit information from multiple agents in order to predict (obtain probabilities for) future events. A good prediction market incentivizes agents to reveal their information truthfully; such incentive compatibility considerations are commonly studied in mechanism design. While this relation between prediction markets and mechanism design is well understood at a high level, the models used in prediction markets tend to be somewhat different from those used in mechanism design. This paper considers a model for prediction markets that fits more straightforwardly into the mechanism design framework. We consider a number of mechanisms within this model, all based on proper scoring rules. We discuss basic properties of these mechanisms, such as incentive compatibility. We also draw connections between some of these mechanisms and cooperative game theory. Finally, we speculate how one might build a practical prediction market based on some of these ideas. To analyze prediction markets, it is often assumed that agents will act myopically. In a market based on securities, this corresponds to the assumption that an agent will buy if the price is below her current subjective probability (which takes what happened in the market so far into account), and will sell if the price is above her current subjective probability. Even under this assumption, it is theoretically possible that the market converges to a price that does not reflect the full combined information of all the agents. For example, suppose that agent 1 observes x ∈ {0, 1}, and agent 2 observes y ∈ {0, 1}. Let z = 1 if x = y, and z = 0 otherwise; and consider a prediction market that attempts to predict whether z = 1. In principle, the agents collectively have enough information to predict z perfectly. However, if we assume x and y are drawn independently according to a uniform distribution, then each agent’s subjective probability that z = 1 is 0. 5 regardless of the information she receives, so the price will remain stuck at 0. 5. (A similar example is given in [6].) Of course, this is a knife-edge example. If we modify the distribution so that P (y = 1) = 0. 51, then, given an initial price of 0. 5, if agent 1 observes x = 1, she will start buying and drive the price up; whereas if she observes x = 0, she will start selling and drive the price down. From this behavior, agent 2 can infer what agent 1 observed, and as a result knows z, so that the market price will correctly converge to 0 or 1.

AAMAS Conference 2008 Conference Paper

Anonymity-Proof Shapley Value: Extending Shapley Value for Coalitional Games in Open Environments

• Naoki Ohta
• Vincent Conitzer
• Yasufumi Satoh
• Atsushi Iwasaki
• Makoto Yokoo

Coalition formation is an important capability for automated negotiation among self-interested agents. In order for coalitions to be stable, a key question that must be answered is how the gains from cooperation are to be distributed. Coalitional game theory provides a number of solution concepts for this. However, recent research has revealed that these traditional solution concepts are vulnerable to various manipulations in open anonymous environments such as the Internet. To address this, previous work has developed a solution concept called the anonymity-proof core, which is robust against such manipulations. That work also developed a method for compactly representing the anonymity-proof core. However, the required computational and representational costs are still huge. In this paper, we develop a new solution concept which we call the anonymity-proof Shapley value. We show that the anonymity-proof Shapley value is characterized by certain simple axiomatic conditions, always exists, and is uniquely determined. The computational and representational costs of the anonymity-proof Shapley value are drastically smaller than those of existing anonymity-proof solution concepts.

AAMAS Conference 2008 Conference Paper

Optimal-in-Expectation Redistribution Mechanisms

• Mingyu Guo
• Vincent Conitzer

Many important problems in multiagent systems involve the allocation of multiple resources to multiple agents. If agents are selfinterested, they will lie about their valuations for the resources if they perceive this to be in their interest. The well-known VCG mechanism allocates the items efficiently, is incentive compatible (agents have no incentive to lie), and never runs a deficit. Nevertheless, the agents may have to make large payments to a party outside the system of agents, leading to decreased utility for the agents. Recent work has investigated the possibility of redistributing some of the payments back to the agents, without violating the other desirable properties of the VCG mechanism. We study multi-unit auctions with unit demand, for which previously a mechanism has been found that maximizes the worst-case redistribution percentage. In contrast, we assume that a prior distribution over the agents’ valuations is available, and try to maximize the expected total redistribution. We analytically solve for a mechanism that is optimal among linear redistribution mechanisms. The optimal linear mechanism is asymptotically optimal. We also propose discretization redistribution mechanisms. We show how to automatically solve for the optimal discretization redistribution mechanism for a given discretization step size, and show that the resulting mechanisms converge to optimality as the step size goes to zero. We also present experimental results showing that for auctions with many bidders, the optimal linear redistribution mechanism redistributes almost everything, whereas for auctions with few bidders, we can solve for the optimal discretization redistribution mechanism with a very small step size.

AAMAS Conference 2008 Conference Paper

Strategic Betting for Competitive Agents

• Liad Wagman
• Vincent Conitzer

In many multiagent settings, each agent’s goal is to come out ahead of the other agents on some metric, such as the currency obtained by the agent. In such settings, it is not appropriate for an agent to try to maximize its expected score on the metric; rather, the agent should maximize its expected probability of winning. In principle, given this objective, the game can be solved using game-theoretic techniques. However, most games of interest are far too large and complex to solve exactly. To get some intuition as to what an optimal strategy in such games should look like, we introduce a simplified game that captures some of their key aspects, and solve it (and several variants) exactly. Specifically, the basic game that we study is the following: each agent i chooses a lottery over nonnegative numbers whose expectation is equal to its budget bi. The agent with the highest realized outcome wins (and agents only care about winning). We show that there is a unique symmetric equilibrium when budgets are equal. We proceed to study and solve extensions, including settings where agents must obtain a minimum outcome to win; where agents choose their budgets (at a cost); and where budgets are private information.

AAMAS Conference 2008 Conference Paper

Undominated VCG Redistribution Mechanisms

• Mingyu Guo
• Vincent Conitzer

Many important problems in multiagent systems can be seen as resource allocation problems. For such problems, the well-known Vickrey-Clarke-Groves (VCG) mechanism is efficient, incentive compatible, individually rational, and does not incur a deficit. However, the VCG mechanism is not (strongly) budget balanced: generally, the agents’ payments will sum to more than 0. Very recently, several mechanisms have been proposed that redistribute a significant percentage of the VCG payments back to the agents while maintaining the other properties. This increases the agents’ utilities. One redistribution mechanism dominates another if it always redistributes at least as much to each agent (and sometimes more). In this paper, we provide a characterization of undominated redistribution mechanisms. We also propose several techniques that take a dominated redistribution mechanism as input, and produce as output another redistribution mechanism that dominates the original. One technique immediately produces an undominated redistribution mechanism that is not necessarily anonymous. Another technique preserves anonymity, and repeated application results in an undominated redistribution mechanism in the limit. We show experimentally that these techniques improve the known redistribution mechanisms.

IJCAI Conference 2007 Conference Paper

• Tuomas Sandholm
• Vincent Conitzer
• Craig Boutilier

Mechanism design is the study of preference aggregation protocols that work well in the face of self-interested agents. We present the first general-purpose techniques for automatically designing multistage mechanisms. These can reduce elicitation burden by only querying agents for information that is relevant given their answers to previous queries. We first show how to turn a given (e. g. , automatically designed using constrained optimization techniques) single-stage mechanism into the most efficient corresponding multistage mechanism given a specified elicitation tree. We then present greedy and dynamic programming (DP) algorithms that determine the elicitation tree (optimal in the DP case). Next, we show how the query savings inherent in the multistage model can be used to design the underlying single-stage mechanism to maximally take advantage of this approach. Finally, we present negative results on the design of multistage mechanisms that do not correspond to dominant-strategy single-stage mechanisms: an optimal multistage mechanism in general has to randomize over queries to hide information from the agents.

IJCAI Conference 2007 Conference Paper

• Vincent Conitzer
• Tuomas Sandholm

Mechanism design has traditionally focused almost exclusively on the design of truthful mechanisms. There are several drawbacks to this: 1. in certain settings (e. g. voting settings), no desirable strategy-proof mechanisms exist; 2. truthful mechanisms are unable to take advantage of the fact that computationally bounded agents may not be able to find the best manipulation, and 3. when designing mechanisms automatically, this approach leads to constrained optimization problems for which current techniques do not scale to very large instances. In this paper, we suggest an entirely different approach: we start with a naive (manipulable) mechanism, and incrementally make it more strategy-proof over a sequence of iterations. We give examples of mechanisms that (variants of) our approach generate, including the VCG mechanism in general settings with payments, and the plurality-with-runoff voting rule. We also provide several basic algorithms for automatically executing our approach in general settings. Finally, we discuss how computationally hard it is for agents to find any remaining beneficial manipulation.

AAMAS Conference 2007 Conference Paper

Eliciting Single-Peaked Preferences Using Comparison Queries

• Vincent Conitzer

Voting is a general method for aggregating the preferences of multiple agents. Each agent ranks all the possible alternatives, and based on this, an aggregate ranking of the alternatives (or at least a winning alternative) is produced. However, when there are many alternatives, it is impractical to simply ask agents to report their complete preferences. Rather, the agents' preferences, or at least the relevant parts thereof, need to be elicited. This is done by asking the agents a (hopefully small) number of simple queries about their preferences, such as comparison queries, which ask an agent to compare two of the alternatives. Prior work on preference elicitation in voting has focused on the case of unrestricted preferences. It has been shown that in this setting, it is sometimes necessary to ask each agent (almost) as many queries as would be required to determine an arbitrary ranking of the alternatives. By contrast, in this paper, we focus on single-peaked preferences. We show that such preferences can be elicited using only a linear number of comparison queries, if either the order with respect to which preferences are single-peaked is known, or at least one other agent's complete preferences are known. We also show that using a sublinear number of queries will not suffice. Finally, we present experimental results.

TARK Conference 2007 Conference Paper

Limited verification of identities to induce false-name-proofness

• Vincent Conitzer

In open, anonymous environments such as the Internet, mechanism design is complicated by the fact that a single agent can participate in the mechanism under multiple identifiers. One way to address this is to design false-name-proof mechanisms, which choose the outcome in such a way that agents have no incentive to use more than one identifier. Unfortunately, there are inherent limitations on what can be achieved with false-name-proof mechanisms, and at least in some cases, these limitations are crippling. An alternative approach is to verify the identities of all agents. This imposes significant overhead and removes any benefits from anonymity. In this paper, we propose a middle ground. Based on the reported preferences, we check, for various subsets of the reports, whether the reports in the subset were all submitted by different agents. If they were not, then we discard some of them. We characterize when such a limited verification protocol induces false-name-proofness for a mechanism, that is, when the combination of the mechanism and the verification protocol gives the agents no incentive to use multiple identifiers. This characterization leads to various optimization problems for minimizing verification effort. We study how to solve these problems. Throughout, we use combinatorial auctions (using the Clarke mechanism) and majority voting as examples.

AAAI Conference 2006 Conference Paper

A Compact Representation Scheme for Coalitional Games in Open Anonymous Environments

• Naoki Ohta
• Makoto Yokoo
• Vincent Conitzer

Coalition formation is an important capability of automated negotiation among self-interested agents. In order for coalitions to be stable, a key question that must be answered is how the gains from cooperation are to be distributed. Recent research has revealed that traditional solution concepts, such as the Shapley value, core, least core, and nucleolus, are vulnerable to various manipulations in open anonymous environments such as the Internet. These manipulations include submitting false names, collusion, and hiding some skills. To address this, a solution concept called the anonymityproof core, which is robust against such manipulations, was developed. However, the representation size of the outcome function in the anonymity-proof core (and similar concepts) requires space exponential in the number of agents/skills. This paper proposes a compact representation of the outcome function, given that the characteristic function is represented using a recently introduced compact language that explicitly specifies only coalitions that introduce synergy. This compact representation scheme can successfully express the outcome function in the anonymity-proof core. Furthermore, this paper develops a new solution concept, the anonymity-proof nucleolus, that is also expressible in this compact representation. We show that the anonymity-proof nucleolus always exists, is unique, and is in the anonymity-proof core (if the latter is nonempty), and assigns the same value to symmetric skills.

AAMAS Conference 2006 Conference Paper

A Technique for Reducing Normal Form Games to Compute a Nash Equilibrium

• Vincent Conitzer
• Tuomas Sandholm

AIJ Journal 2006 Journal Article

Complexity of constructing solutions in the core based on synergies among coalitions

• Vincent Conitzer
• Tuomas Sandholm

Coalition formation is a key problem in automated negotiation among self-interested agents, and other multiagent applications. A coalition of agents can sometimes accomplish things that the individual agents cannot, or can accomplish them more efficiently. Motivating the agents to abide by a solution requires careful analysis: only some of the solutions are stable in the sense that no group of agents is motivated to break off and form a new coalition. This constraint has been studied extensively in cooperative game theory: the set of solutions that satisfy it is known as the core. The computational questions around the core have received less attention. When it comes to coalition formation among software agents (that represent real-world parties), these questions become increasingly explicit. In this paper we define a concise, natural, general representation for games in characteristic form that relies on superadditivity. In our representation, individual agents' values are given as well as values for those coalitions that introduce synergies. We show that this representation allows for efficient checking of whether a given outcome is in the core. We then show that determining whether the core is nonempty is NP-complete both with and without transferable utility. We demonstrate that what makes the problem hard in both cases is determining the collaborative possibilities (the set of outcomes possible for the grand coalition); we do so by showing that if these are given, the problem becomes solvable in time polynomial in the size of the representation in both cases. However, we then demonstrate that for a hybrid version of the problem, where utility transfer is possible only within the grand coalition, the problem remains NP-complete even when the collaborative possibilities are given. Finally, we show that for convex characteristic functions, a solution in the core can be computed efficiently (in O ( n l 2 ) time, where n is the number of agents and l is the number of synergies), even when the collaborative possibilities are not given in advance.

AAAI Conference 2006 Conference Paper

Computing Slater Rankings Using Similarities among Candidates

• Vincent Conitzer

Voting (or rank aggregation) is a general method for aggregating the preferences of multiple agents. One important voting rule is the Slater rule. It selects a ranking of the alternatives (or candidates) to minimize the number of pairs of candidates such that the ranking disagrees with the pairwise majority vote on these two candidates. The use of the Slater rule has been hindered by a lack of techniques to compute Slater rankings. In this paper, we show how we can decompose the Slater problem into smaller subproblems if there is a set of similar candidates. We show that this technique suffices to compute a Slater ranking in linear time if the pairwise majority graph is hierarchically structured. For the general case, we also give an efficient algorithm for finding a set of similar candidates. We provide experimental results that show that this technique significantly (sometimes drastically) speeds up search algorithms. Finally, we also use the technique of similar sets to show that computing an optimal Slater ranking is NP-hard, even in the absence of pairwise ties.

AAMAS Conference 2006 Conference Paper

Failures of the VCG Mechanism in Combinatorial Auctions and Exchanges

• Vincent Conitzer
• Tuomas Sandholm

AAAI Conference 2006 Conference Paper

Improved Bounds for Computing Kemeny Rankings

• Vincent Conitzer

Voting (or rank aggregation) is a general method for aggregating the preferences of multiple agents. One voting rule of particular interest is the Kemeny rule, which minimizes the number of cases where the final ranking disagrees with a vote on the order of two alternatives. Unfortunately, Kemeny rankings are NP-hard to compute. Recent work on computing Kemeny rankings has focused on producing good bounds to use in search-based methods. In this paper, we extend on this work by providing various improved bounding techniques. Some of these are based on cycles in the pairwise majority graph, others are based on linear programs. We completely characterize the relative strength of all of these bounds and provide some experimental results.

ICML Conference 2006 Conference Paper

Learning algorithms for online principal-agent problems (and selling goods online)

• Vincent Conitzer
• Nikesh Garera

AAAI Conference 2006 Conference Paper

Nonexistence of Voting Rules That Are Usually Hard to Manipulate

• Vincent Conitzer

Aggregating the preferences of self-interested agents is a key problem for multiagent systems, and one general method for doing so is to vote over the alternatives (candidates). Unfortunately, the Gibbard-Satterthwaite theorem shows that when there are three or more candidates, all reasonable voting rules are manipulable (in the sense that there exist situations in which a voter would benefit from reporting its preferences insincerely). To circumvent this impossibility result, recent research has investigated whether it is possible to make finding a beneficial manipulation computationally hard. This approach has had some limited success, exhibiting rules under which the problem of finding a beneficial manipulation is NPhard, #P-hard, or even PSPACE-hard. Thus, under these rules, it is unlikely that a computationally efficient algorithm can be constructed that always finds a beneficial manipulation (when it exists). However, this still does not preclude the existence of an efficient algorithm that often finds a successful manipulation (when it exists). There have been attempts to design a rule under which finding a beneficial manipulation is usually hard, but they have failed. To explain this failure, in this paper, we show that it is in fact impossible to design such a rule, if the rule is also required to satisfy another property: a large fraction of the manipulable instances are both weakly monotone, and allow the manipulators to make either of exactly two candidates win. We argue why one should expect voting rules to have this property, and show experimentally that common voting rules clearly satisfy it. We also discuss approaches for potentially circumventing this impossibility result.

AAAI Conference 2005 Conference Paper

A Generalized Strategy Eliminability Criterion and Computational Methods for Applying It

• Vincent Conitzer

We define a generalized strategy eliminability criterion for bimatrix games that considers whether a given strategy is eliminable relative to given dominator & eliminee subsets of the players’ strategies. We show that this definition spans a spectrum of eliminability criteria from strict dominance (when the sets are as small as possible) to Nash equilibrium (when the sets are as large as possible). We show that checking whether a strategy is eliminable according to this criterion is coNPcomplete (both when all the sets are as large as possible and when the dominator sets each have size 1). We then give an alternative definition of the eliminability criterion and show that it is equivalent using the Minimax Theorem. We show how this alternative definition can be translated into a mixed integer program of polynomial size with a number of (binary) integer variables equal to the sum of the sizes of the eliminee sets, implying that checking whether a strategy is eliminable according to the criterion can be done in polynomial time, given that the eliminee sets are small. Finally, we study using the criterion for iterated elimination of strategies.

IJCAI Conference 2005 Conference Paper

Coalitional Games in Open Anonymous Environments

• Makoto Yokoo
• Vincent Conitzer
• Tuomas Sandholm
• Naoki Ohta
• Atsushi

AAAI Conference 2005 Conference Paper

Combinatorial Auctions with k-wise Dependent Valuations

• Vincent Conitzer

We analyze the computational and communication complexity of combinatorial auctions from a new perspective: the degree of interdependency between the items for sale in the bidders’ preferences. Denoting by Gk the class of valuations displaying up to k-wise dependencies, we consider the hierarchy G1 ⊂ G2 ⊂ · · · ⊂ Gm, where m is the number of items for sale. We show that the minimum non-trivial degree of interdependency (2-wise dependency) is sufficient to render NP-hard the problem of computing the optimal allocation (but we also exhibit a restricted class of such valuations for which computing the optimal allocation is easy). On the other hand, bidders’ preferences can be communicated efficiently (i. e. , exchanging a polynomial amount of information) as long as the interdependencies between items are limited to sets of cardinality up to k, where k is an arbitrary constant. The amount of communication required to transmit the bidders’ preferences becomes super-polynomial (under the assumption that only value queries are allowed) when interdependencies occur between sets of cardinality g(m), where g(m) is an arbitrary function such that g(m) → ∞ as m → ∞. We also consider approximate elicitation, in which the auctioneer learns, asking polynomially many value queries, an approximation of the bidders’ actual preferences.

UAI Conference 2005 Conference Paper

Common Voting Rules as Maximum Likelihood Estimators

• Vincent Conitzer
• Tuomas Sandholm

Voting is a very general method of preference aggregation. A voting rule takes as input every voter's vote (typically, a ranking of the alternatives), and produces as output either just the winning alternative or a ranking of the alternatives. One potential view of voting is the following. There exists a 'correct' outcome (winner/ranking), and each voter's vote corresponds to a noisy perception of this correct outcome. If we are given the noise model, then for any vector of votes, we can

AAAI Conference 2005 Short Paper

Computational Aspects of Mechanism Design

• Vincent Conitzer

In a preference aggregation setting, a group of agents must jointly make a decision, based on the individual agents’ privately known preferences. To do so, the agents need some protocol (or mechanism) that will elicit this information from them, and make the decision. Examples of such mechanisms include voting protocols, auctions, and exchanges. In most real-world settings, preference aggregation is confronted with the following three computational issues. First, there is the complexity of executing the mechanism. Second, when standard mechanisms do not apply to or are suboptimal for the setting at hand, there is the complexity of designing the mechanism. Third, the agents face the complexity of (strategically) participating in the mechanism. My thesis statement is that by studying these computational aspects of the mechanism design process, we can significantly improve the generated mechanisms in a hierarchy of ways, leading to increased economic welfare.

AAAI Conference 2005 Conference Paper

Expressive Negotiation in Settings with Externalities

• Vincent Conitzer

In recent years, certain formalizations of combinatorial negotiation settings, most notably combinatorial auctions, have become an important research topic in the AI community. A pervasive assumption has been that of no externalities: the agents deciding on a variable (such as whether a trade takes place between them) are the only ones affected by how this variable is set. To date, there has been no widely studied formalization of combinatorial negotiation settings with externalities. In this paper, we introduce such a formalization. We show that in a number of key special cases, it is NP-complete to find a feasible nontrivial solution (and therefore the maximum social welfare is completely inapproximable). However, for one important special case, we give an algorithm which converges to the solution with the maximal concession by each agent (in a linear number of rounds for utility functions that decompose into piecewise constant functions). Maximizing social welfare, however, remains NP-complete even in this setting. We also demonstrate a special case which can be solved in polynomial time by linear programming.

AAMAS Conference 2004 Conference Paper

An algorithm for automatically designing deterministic mechanisms without payments

• Vincent Conitzer
• Tuomas Sandholm

AAAI Conference 2004 Conference Paper

Combinatorial Auctions with Structured Item Graphs

• Vincent Conitzer

Combinatorial auctions (CAs) are important mechanisms for allocating interrelated items. Unfortunately, winner determination is NP-complete unless there is special structure. We study the setting where there is a graph (with some desired property), with the items as vertices, and every bid bids on a connected set of items. Two computational problems arise: 1) clearing the auction when given the item graph, and 2) constructing an item graph (if one exists) with the desired property. 1 was previously solved for the case of a tree or a cycle, and 2 for the case of a line graph or a cycle. We generalize the first result by showing that given an item graph with bounded treewidth, the clearing problem can be solved in polynomial time (and every CA instance has some treewidth; the complexity is exponential in only that parameter). We then give an algorithm for constructing an item tree (treewidth 1) if such a tree exists, thus closing a recognized open problem. We show why this algorithm does not work for treewidth greater than 1, but leave open whether item graphs of (say) treewidth 2 can be constructed in polynomial time. We show that finding the item graph with the fewest edges is NP-complete (even when a graph of treewidth 2 exists). Finally, we study how the results change if a bid is allowed to have more than one connected component. Even for line graphs, we show that clearing is hard even with 2 components, and constructing the line graph is hard even with 5.

ICML Conference 2004 Conference Paper

Communication complexity as a lower bound for learning in games

• Vincent Conitzer
• Tuomas Sandholm

AAAI Conference 2004 Conference Paper

Computing Shapley Values, Manipulating Value Division Schemes, and Checking Core Membership in Multi-Issue Domains

• Vincent Conitzer
• Tuomas Sandholm

Coalition formation is a key problem in automated negotiation among self-interested agents. In order for coalition formation to be successful, a key question that must be answered is how the gains from cooperation are to be distributed. Various solution concepts have been proposed, but the computational questions around these solution concepts have received little attention. We study a concise representation of characteristic functions which allows for the agents to be concerned with a number of independent issues that each coalition of agents can address. For example, there may be a set of tasks that the capacity-unconstrained agents could undertake, where accomplishing a task generates a certain amount of value (possibly depending on how well the task is accomplished). Given this representation, we show how to quickly compute the Shapley value—a seminal value division scheme that distributes the gains from cooperation fairly in a certain sense. We then show that in (distributed) marginal-contribution based value division schemes, which are known to be vulnerable to manipulation of the order in which the agents are added to the coalition, this manipulation is NP-complete. Thus, computational complexity serves as a barrier to manipulating the joining order. Finally, we show that given a value division, determining whether some subcoalition has an incentive to break away (in which case we say the division is not in the core) is NP-complete. So, computational complexity serves to increase the stability of the coalition.

ICML Conference 2003 Conference Paper

AWESOME: A General Multiagent Learning Algorithm that Converges in Self-Play and Learns a Best Response Against Stationary Opponents

• Vincent Conitzer
• Tuomas Sandholm

ICML Conference 2003 Conference Paper

BL-WoLF: A Framework For Loss-Bounded Learnability In Zero-Sum Games

• Vincent Conitzer
• Tuomas Sandholm

IJCAI Conference 2003 Conference Paper

Complexity of Determining Nonemptiness of the Core

• Vincent Conitzer
• Tuomas Sandholm

Coalition formation is a key problem in automated negotiation among self-interested agents, and other multiagent applications. A coalition of agents can sometimes accomplish things that the individual agents cannot, or can do things more efficiently. However, motivating the agents to abide to a solution requires careful analysis: only some of the solutions are stable in the sense that no group of agents is motivated to break off and form a new coalition. This constraint has been studied extensively in cooperative game theory. However, the computational questions around this constraint have received less attention. When it comes to coalition formation among software agents (that represent real-world parties), these questions become increasingly explicit. In this paper we define a concise general representation for games in characteristic form that relies on superadditivity, and show that it allows for efficient checking of whether a given outcome is in the core. We then show that determining whether the core is nonempty is -complete both with and without transferable utility. We demonstrate that what makes the problem hard in both cases is determining the collaborative possibilities (the set of outcomes possible for the grand coalition), by showing that if these are given, the problem becomes tractable in both cases. However, we then demonstrate that for a hybrid version of the problem, where utility transfer is possible only within the grand coalition, the problem remains, complete even when the collaborative possibilities are given.

IJCAI Conference 2003 Conference Paper

Complexity Results about Nash Equilibria

• Vincent Conitzer
• Tuomas Sandholm

Noncooperative game theory provides a norma­ tive framework for analyzing strategic interactions. However, for the toolbox to be operational, the so­ lutions it defines will have to be computed. In this paper, we provide a single reduction that 1) demon­ strates -hardness of determining whether Nash equilibria with certain natural properties exist, and 2) demonstrates the -hardness of counting Nash equilibria (or connected sets of Nash equilibria). We also show that 3) determining whether a purestrategy Bayes-Nash equilibrium exists is hard, and that 4) determining whether a purestrategy Nash equilibrium exists in a stochastic (Markov) game is -hard even if the game is invisible (this remains -hard if the game is fi­ nite). All of our hardness results hold even if there are only two players and the game is symmetric.

IJCAI Conference 2003 Conference Paper

Definition and Complexity of Some Basic Metareasoning Problems

• Vincent Conitzer
• Tuomas Sandholm

In most real-world settings, due to limited time or other resources, an agent cannot perform all potentially useful deliberation and information gathering actions. This leads to the metareasoning problem of selecting such actions. Decision-theoretic methods for metareasoning have been studied in AI, but there are few theoretical results on the complexity of metareasoning. We derive hardness results for three settings which most real metareasoning systems would have to encompass as special cases. In the first, the agent has to decide how to allocate its deliberation time across anytime algorithms running on different problem instances. We show this to be ATP-complete. In the second, the agent has to (dynamically) allocate its deliberation or information gathering resources across multiple actions that it has to choose among. We show this to be AfP-hard even when evaluating each individual action is extremely simple. In the third, the agent has to (dynamically) choose a limited number of deliberation or information gathering actions to disambiguate the state of the world. We show that this is AfP-hard under a natural restriction, and hard in general.

TARK Conference 2003 Conference Paper

How many candidates are needed to make elections hard to manipulate?

• Vincent Conitzer
• Jérôme Lang
• Tuomas Sandholm

In multiagent settings where the agents have different preferences, preference aggregation is a central issue. Voting is a general method for preference aggregation, but seminal results have shown that all general voting protocols are manipulable. One could try to avoid manipulation by using voting protocols where determining a beneficial manipulation is hard computationally. The complexity of manipulating realistic elections where the number of candidates is a small constant was recently studied [4], but the emphasis was on the question of whether or not a protocol becomes hard to manipulate for some constant number of candidates. That work, in many cases, left open the question: How many candidates are needed to make elections hard to manipulate? This is a crucial question when comparing the relative manipulability of different voting protocols. In this paper we answer that question for the voting protocols of the earlier study: plurality, Borda, STV, Copeland, maximin, regular cup, and randomized cup. We also answer that question for two voting protocols for which no results on the complexity of manipulation have been derived before: veto and plurality with runoff. It turns out that the voting protocols under study become hard to manipulate at 3 candidates, 4 candidates, 7 candidates, or never.

IJCAI Conference 2003 Conference Paper

Universal Voting Protocol Tweaks to Make Manipulation Hard

• Vincent Conitzer
• Tuomas Sandholm

Voting is a general method for preference aggrega­ tion in multiagent settings, but seminal results have shown that all (nondictatorial) voting protocols are manipulable. One could try to avoid manipula­ tion by using voting protocols where determining a beneficial manipulation is hard computationally. A number of recent papers study the complexity of manipulating existing protocols. This paper is the first work to take the next step of designing new protocols that are especially hard to manipulate. Rather than designing these new protocols from scratch, we instead show how to tweak ex­ isting protocols to make manipulation hard, while leaving much of the original nature of the protocol intact. The tweak studied consists of adding one elimination preround to the election. Surprisingly, this extremely simple and universal tweak makes typical protocols hard to manipulate! The proto­ cols become NP-hard, #P-hard, or PSPACE-hard to manipulate, depending on whether the sched­ ule of the preround is determined before the votes are collected, after the votes are collected, or the scheduling and the vote collecting are interleaved, respectively. We prove general sufficient condi­ tions on the protocols for this tweak to introduce the hardness, and show that the most common vot­ ing protocols satisfy those conditions. These are the first results in voting settings where manipula­ tion is in a higher complexity class than NP (pre­ suming PSPACE NP).

UAI Conference 2002 Conference Paper

Complexity of Mechanism Design

• Vincent Conitzer
• Tuomas Sandholm

The aggregation of conflicting preferences is a central problem in multiagent systems. The key difficulty is that the agents may report their preferences insincerely. Mechanism design is the art of designing the rules of the game so that the agents are motivated to report their preferences truthfully and a (socially) desirable outcome is chosen. We propose an approach where a mechanism is automatically created for the preference aggregation setting at hand. This has several advantages, but the downside is that the mechanism design optimization problem needs to be solved anew each time. Focusing on settings where side payments are not possible, we show that the mechanism design problem is NP-complete for deterministic mechanisms. This holds both for dominant-strategy implementation and for Bayes-Nash implementation. We then show that if we allow randomized mechanisms, the mechanism design problem becomes tractable. In other words, the coordinator can tackle the computational complexity introduced by its uncertainty about the agents preferences BY making the agents face additional uncertainty.This comes at no loss, AND IN SOME cases at a gain, IN the(social) objective.