SU\G(𝔸)/K·U
Sign Up for free Log In

Author Description

Login to generate an author description

Ask a Question About This Mathematician

Complexity of mechanism design

2002-08-01
Vincent Conitzer , Tüomas 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 … 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 dominantstrategy 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 the agents face additional uncertainty. This comes at no loss, and in some cases at a gain, in the (social) objective.

Justified representation in approval-based committee voting

2017-01-09
Haris Aziz , Markus Brill , Vincent Conitzer +3 more
View PDF Chat

Complexity Results about Nash Equilibria

2002-01-01
Vincent Conitzer , Tüomas Sandholm
Noncooperative game theory provides a normative framework for analyzing strategic interactions. However, for the toolbox to be operational, the solutions it defines will have to be computed. In this paper, … Noncooperative game theory provides a normative framework for analyzing strategic interactions. However, for the toolbox to be operational, the solutions it defines will have to be computed. In this paper, we provide a single reduction that 1) demonstrates NP-hardness of determining whether Nash equilibria with certain natural properties exist, and 2) demonstrates the #P-hardness of counting Nash equilibria (or connected sets of Nash equilibria). We also show that 3) determining whether a pure-strategy Bayes-Nash equilibrium exists is NP-hard, and that 4) determining whether a pure-strategy Nash equilibrium exists in a stochastic (Markov) game is PSPACE-hard even if the game is invisible (this remains NP-hard if the game is finite). All of our hardness results hold even if there are only two players and the game is symmetric. Keywords: Nash equilibrium; game theory; computational complexity; noncooperative game theory; normal form game; stochastic game; Markov game; Bayes-Nash equilibrium; multiagent systems.

Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and Uniqueness

2011-06-21
Dmytro Korzhyk , Zhimin Yin , Christopher Kiekintveld +2 more
There has been significant recent interest in game-theoretic approaches to security, with much of the recent research focused on utilizing the leader-follower Stackelberg game model. Among the major applications are … There has been significant recent interest in game-theoretic approaches to security, with much of the recent research focused on utilizing the leader-follower Stackelberg game model. Among the major applications are the ARMOR program deployed at LAX Airport and the IRIS program in use by the US Federal Air Marshals (FAMS). The foundational assumption for using Stackelberg games is that security forces (leaders), acting first, commit to a randomized strategy; while their adversaries (followers) choose their best response after surveillance of this randomized strategy. Yet, in many situations, a leader may face uncertainty about the follower's surveillance capability. Previous work fails to address how a leader should compute her strategy given such uncertainty. We provide five contributions in the context of a general class of security games. First, we show that the Nash equilibria in security games are interchangeable, thus alleviating the equilibrium selection problem. Second, under a natural restriction on security games, any Stackelberg strategy is also a Nash equilibrium strategy; and furthermore, the solution is unique in a class of security games of which ARMOR is a key exemplar. Third, when faced with a follower that can attack multiple targets, many of these properties no longer hold. Fourth, we show experimentally that in most (but not all) games where the restriction does not hold, the Stackelberg strategy is still a Nash equilibrium strategy, but this is no longer true when the attacker can attack multiple targets. Finally, as a possible direction for future research, we propose an extensive-form game model that makes the defender's uncertainty about the attacker's ability to observe explicit.
View PDF Chat

Determining Possible and Necessary Winners Given Partial Orders

2011-05-17
Lirong Xia , Vincent Conitzer
Usually a voting rule requires agents to give their preferences as linear orders. However, in some cases it is impractical for an agent to give a linear order over all … Usually a voting rule requires agents to give their preferences as linear orders. However, in some cases it is impractical for an agent to give a linear order over all the alternatives. It has been suggested to let agents submit partial orders instead. Then, given a voting rule, a profile of partial orders, and an alternative (candidate) c, two important questions arise: first, is it still possible for c to win, and second, is c guaranteed to win? These are the possible winner and necessary winner problems, respectively. Each of these two problems is further divided into two sub-problems: determining whether c is a unique winner (that is, c is the only winner), or determining whether c is a co-winner (that is, c is in the set of winners). We consider the setting where the number of alternatives is unbounded and the votes are unweighted. We completely characterize the complexity of possible/necessary winner problems for the following common voting rules: a class of positional scoring rules (including Borda), Copeland, maximin, Bucklin, ranked pairs, voting trees, and plurality with runoff.
View PDF Chat

Common voting rules as maximum likelihood estimators

2005-07-26
Vincent Conitzer , Tüomas 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 … 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 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 compute the maximum likelihood estimate of the correct outcome. This maximum likelihood estimate constitutes a voting rule. In this paper, we ask the following question: For which common voting rules does there exist a noise model such that the rule is the maximum likelihood estimate for that noise model? We require that the votes are drawn independently given the correct outcome (we show that without this restriction, all voting rules have the property). We study the question both for the case where outcomes are winners and for the case where outcomes are rankings. In either case, only some of the common voting rules have the property. Moreover, the sets of rules that satisfy the property are incomparable between the two cases (satisfying the property in the one case does not imply satisfying it in the other case).

Fair Public Decision Making

2017-06-20
Vincent Conitzer , Rupert Freeman , Nisarg Shah
We generalize the classic problem of fairly allocating indivisible goods to the problem of fair public decision making, in which a decision must be made on several social issues simultaneously, … We generalize the classic problem of fairly allocating indivisible goods to the problem of fair public decision making, in which a decision must be made on several social issues simultaneously, and, unlike the classic setting, a decision can provide positive utility to multiple players. We extend the popular fairness notion of proportionality (which is not guaranteeable) to our more general setting, and introduce three novel relaxations --- proportionality up to one issue, round robin share, and pessimistic proportional share --- that are also interesting in the classic goods allocation setting. We show that the Maximum Nash Welfare solution, which is known to satisfy appealing fairness properties in the classic setting, satisfies or approximates all three relaxations in our framework. We also provide polynomial time algorithms and hardness results for finding allocations satisfying these axioms, with or without insisting on Pareto optimality.
View PDF Chat

Eliciting Single-Peaked Preferences Using Comparison Queries

2009-06-16
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 … 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. In 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 show that using a sublinear number of queries does not suffice. We also consider the case of cardinally single-peaked preferences. For this case, we show that if the alternatives' cardinal positions are known, then an agent's preferences can be elicited using only a logarithmic number of queries; however, we also show that if the cardinal positions are not known, then a sublinear number of queries does not suffice. We present experimental results for all elicitation algorithms. We also consider the problem of only eliciting enough information to determine the aggregate ranking, and show that even for this more modest objective, a sublinear number of queries per agent does not suffice for known ordinal or unknown cardinal positions. Finally, we discuss whether and how these techniques can be applied when preferences are almost single-peaked.
View PDF Chat

Adapting a kidney exchange algorithm to align with human values

2020-03-24
Rachel Freedman , Jana Schaich Borg , Walter Sinnott‐Armstrong +2 more
View PDF Chat

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

2003-06-20
Vincent Conitzer , Jérôme Lang , Tüomas 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 … 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.
View PDF Chat

Dominating Manipulations in Voting with Partial Information

2011-01-01
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 … 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.
View PDF Chat

Dominating Manipulations in Voting with Partial Information

2011-08-04
Vincent Conitzer , Toby Walsh , Lirong Xia
We consider manipulation problems when the manipulator only has partial information about the votes of the non-manipulators. Such partial information is described by an {\em information set}, which is the … We consider manipulation problems when the manipulator only has partial information about the votes of the non-manipulators. Such partial information is described by an {\em information set}, which is the set of profiles of the non-manipulators that are indistinguishable to the manipulator. Given such an information set, a {\em 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.
View PDF Chat

Complexity of determining nonemptiness of the core

2003-01-01
Vincent Conitzer , Tüomas Sandholm
Coalition formation is a key problem in automated negotiation among self-interested agents, and other electronic commerce applications. A coalition of agents can sometimes accomplish things that the individual agents cannot, … Coalition formation is a key problem in automated negotiation among self-interested agents, and other electronic commerce 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 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), 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 NP-complete even when the collaborative possibilities are given.
View PDF Chat

Universal Voting Protocol Tweaks to Make Manipulation Hard

2003-07-07
Vincent Conitzer , Tüomas Sandholm
Voting is a general method for preference aggregation in multiagent settings, but seminal results have shown that all (nondictatorial) voting protocols are manipulable. One could try to avoid manipulation by … Voting is a general method for preference aggregation in multiagent settings, but seminal results have shown that all (nondictatorial) voting protocols are manipulable. One could try to avoid manipulation 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 existing 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 protocols become NP-hard, #P-hard, or PSPACE-hard to manipulate, depending on whether the schedule 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 conditions on the protocols for this tweak to introduce the hardness, and show that the most common voting protocols satisfy those conditions. These are the first results in voting settings where manipulation is in a higher complexity class than NP (presuming PSPACE $\neq$ NP).

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

2003-07-01
Vincent Conitzer , Tüomas Sandholm
A satisfactory multiagent learning algorithm should, {\em at a minimum}, learn to play optimally against stationary opponents and converge to a Nash equilibrium in self-play. The algorithm that has come … A satisfactory multiagent learning algorithm should, {\em at a minimum}, learn to play optimally against stationary opponents and converge to a Nash equilibrium in self-play. The algorithm that has come closest, WoLF-IGA, has been proven to have these two properties in 2-player 2-action repeated games--assuming that the opponent's (mixed) strategy is observable. In this paper we present AWESOME, the first algorithm that is guaranteed to have these two properties in {\em all} repeated (finite) games. It requires only that the other players' actual actions (not their strategies) can be observed at each step. It also learns to play optimally against opponents that {\em eventually become} stationary. The basic idea behind AWESOME ({\em Adapt When Everybody is Stationary, Otherwise Move to Equilibrium}) is to try to adapt to the others' strategies when they appear stationary, but otherwise to retreat to a precomputed equilibrium strategy. The techniques used to prove the properties of AWESOME are fundamentally different from those used for previous algorithms, and may help in analyzing other multiagent learning algorithms also.

Computational ethics

2022-03-29
Edmond Awad , Sydney Levine , Michael Anderson +7 more
The past 15 years have seen an increased interest in developing ethical machines; manifested in various interdisciplinary research communities (under the umbrella term 'AI ethics'). Less represented in these interdisciplinary … The past 15 years have seen an increased interest in developing ethical machines; manifested in various interdisciplinary research communities (under the umbrella term 'AI ethics'). Less represented in these interdisciplinary efforts is the perspective of cognitive science.We propose a framework – computational ethics – that specifies how the ethical challenges of AI can be addressed better by incorporating the study of how humans make moral decisions.As the driver of this framework, we propose a computational version of reflective equilibrium.The goal of this framework is twofold: (i) to inform the engineering of ethical AI systems, and (ii) to characterize human moral judgment and decision-making in computational terms.Working jointly towards these two goals may prove to be beneficial in making progress on both fronts. Technological advances are enabling roles for machines that present novel ethical challenges. The study of 'AI ethics' has emerged to confront these challenges, and connects perspectives from philosophy, computer science, law, and economics. Less represented in these interdisciplinary efforts is the perspective of cognitive science. We propose a framework – computational ethics – that specifies how the ethical challenges of AI can be partially addressed by incorporating the study of human moral decision-making. The driver of this framework is a computational version of reflective equilibrium (RE), an approach that seeks coherence between considered judgments and governing principles. The framework has two goals: (i) to inform the engineering of ethical AI systems, and (ii) to characterize human moral judgment and decision-making in computational terms. Working jointly towards these two goals will create the opportunity to integrate diverse research questions, bring together multiple academic communities, uncover new interdisciplinary research topics, and shed light on centuries-old philosophical questions. Technological advances are enabling roles for machines that present novel ethical challenges. The study of 'AI ethics' has emerged to confront these challenges, and connects perspectives from philosophy, computer science, law, and economics. Less represented in these interdisciplinary efforts is the perspective of cognitive science. We propose a framework – computational ethics – that specifies how the ethical challenges of AI can be partially addressed by incorporating the study of human moral decision-making. The driver of this framework is a computational version of reflective equilibrium (RE), an approach that seeks coherence between considered judgments and governing principles. The framework has two goals: (i) to inform the engineering of ethical AI systems, and (ii) to characterize human moral judgment and decision-making in computational terms. Working jointly towards these two goals will create the opportunity to integrate diverse research questions, bring together multiple academic communities, uncover new interdisciplinary research topics, and shed light on centuries-old philosophical questions. David Marr set out to describe vision in computational terms by integrating insights and methods from psychology, neuroscience, and engineering [1.Marr D. Vision: A Computational Investigation into the Human Representation and Processing of Visual Information. W.H. Freeman, 1982Google Scholar]. His revolutionary approach to the study of vision offered a model for the field of cognitive science. The key to Marr's innovation was his emphasis on explaining visual perception as an algorithmic (see Glossary) process – a process that transforms one type of information (an input) into another type of information (the output). The goal was to understand the input–output transformation with a sufficiently high degree of precision that it could be captured in mathematical terms. The result of this algorithm-focused pursuit was an account of visual perception that characterized the richness of the human mind in a way that could be programmed into a machine. This approach had two important consequences. The first was that it has become increasingly possible to build machines with a human-like capacity for visual perception. For example, convolutional neural networks (CNNs), the engine underlying most of the recent progress in computer vision, learn internal multi-level representations analogous to the human visual hierarchy [2.Kriegeskorte N. Deep neural networks: a new framework for modeling biological vision and brain information processing.Annu. Rev. Vis. Sci. 2015; 1: 417-446Crossref PubMed Google Scholar]. Given these advances, we now have machines that can detect whether a skin cancer is malignant or benign [3.Esteva A. et al.Dermatologist-level classification of skin cancer with deep neural networks.Nature. 2017; 542: 115-118Crossref PubMed Scopus (54) Google Scholar], can detect street signs in naturalistic settings [4.Zhu Z. et al.Traffic-sign detection and classification in the wild.in: IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2016: 2110-2117Crossref Scopus (403) Google Scholar], and can classify objects into a thousand categories at better than human performance levels [5.Krizhevsky A. et al.ImageNet classification with deep convolutional neural networks.Commun. ACM. 2017; 60: 84-90Crossref Scopus (7838) Google Scholar]. The second was that the mechanisms of human vision were studied and understood in more precise terms than ever before. For example, various aspects of visual perception and decoding (specifically, inference of selected objects) can be understood as a Bayesian inference [6.Zhaoping L. Li Z. Understanding Vision: Theory, Models, and Data. Oxford University Press, 2014Crossref Google Scholar,7.Weiss Y. et al.Motion illusions as optimal percepts.Nat. Neurosci. 2002; 5: 598-604Crossref PubMed Scopus (699) Google Scholar]. Moreover, there was a positive feedback loop between the machine-centric and human-centric research lines. The algorithms developed in studying the cognitive science of human vision were used to program machines that both matched and extended what the human mind is capable of. Conversely, the challenge of trying to program machines with the capacity for vision generated new hypotheses for how vision might work in the mind (and the brain). The key to this success was thinking about vision computationally – that is, in algorithmic terms. Inspired by Marr's success, we propose that a computationally grounded approach could be similarly valuable for the study of ethics [8.Mikhail J. Elements of Moral Cognition: Rawls' Linguistic Analogy and the Cognitive Science of Moral and Legal Judgment. Cambridge University Press, 2011Crossref Scopus (234) Google Scholar]. By analogy to Marr's 'computational vision', we characterize this approach as 'computational ethics'. As we conceive it, computational ethics includes scholarly work that aims to formalize descriptive ethics and normative ethics in algorithmic terms, as well as work that uses this formalization to help to both (i) engineer ethical AI systems, and (ii) better understand human moral decisions and judgments (the relationship between our proposed framework and other interdisciplinary efforts that tackle the challenges of AI ethics is discussed in Box 1).Box 1Relationship to current interdisciplinary effortsFifteen years ago the fields of machine ethics (implementing ethical decision-making in machines) [56.Anderson M. Anderson S.L. Machine Ethics. Cambridge University Press, 2011Crossref Google Scholar,132.Anderson M. Anderson S.L. Guest editors' introduction: machine ethics.IEEE Intell. Syst. 2006; 21: 10-11Crossref Scopus (33) Google Scholar] and roboethics (how humans design, use, and treat robots) [133.Veruggio G. A proposal for a roboethics.in: 1st International Symposium on Roboethics: The Ethics, Social, Humanitarian, and Ecological Aspects of Robotics. Roboethics.org, 2004Google Scholar,134.Tzafestas S.G. Roboethics: A Navigating Overview. Springer, 2015Google Scholar] emerged to bring the perspective of ethics to AI development. Since then 'AI ethics' has emerged as an umbrella term to describe work concerning both AI and ethics. New research directions for AI ethics include algorithmic accountability (the obligation to be able to explain and/or justify algorithmic decisions) [135.Wieringa M. What to account for when accounting for algorithms.in: Hildebrandt M. Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency. Association for Computing Machinery, 2020: 1-18Crossref Scopus (66) Google Scholar], algorithmic transparency (openness about the purpose, structure, and actions of algorithms) [136.Weller A. Transparency: motivations and challenges.in: Samek W. Explainable AI: Interpreting, Explaining and Visualizing Deep Learning. Springer, 2019: 23-40Crossref Scopus (32) Google Scholar], algorithmic fairness/bias (attempts to design algorithms that make fair/unbiased decisions) [137.Mehrabi N. et al.A survey on bias and fairness in machine learning.ACM Comput. Surv. 2019; 54: 1-35Crossref Scopus (87) Google Scholar], and AI for (social) good (ensuring that AI algorithms have a positive impact) [138.Tomašev N. et al.AI for social good: unlocking the opportunity for positive impact.Nat. Commun. 2020; 11: 2468Crossref PubMed Scopus (26) Google Scholar]. Similarly, new multidisciplinary fields of research have been initiated, including responsible AI (RAI; the development of guidelines, regulations, laws, and certifications regarding how AI should be researched, developed, and used) [139.Dignum V. Responsible Artificial Intelligence: How to Develop and Use AI in a Responsible Way. Springer, 2019Crossref Google Scholar], explainable AI (XAI; the development and study of automatically generated explanations for algorithmic decisions) [140.Wachter S. et al.Transparent, explainable, and accountable AI for robotics. Science.Robotics. 2017; 2: eaan6080Crossref Scopus (99) Google Scholar,141.Wachter S. et al.Counterfactual explanations without opening the black box: automated decisions and the GDPR.Harv. J. Law Technol. 2017; 31: 841-887Google Scholar], and machine behavior (the study of machines as a new class of actors with their unique behavioral patterns and ecology) [31.Rahwan I. et al.Machine behaviour.Nature. 2019; 568: 477-486Crossref PubMed Scopus (301) Google Scholar].These fields and communities have already begun to communicate via academic conferences including AIES (Artificial Intelligence, Ethics, and Society), supported by the Association for the Advancement of AI (AAAI) and the Association for Computing Machinery (ACM), and FAT/ML (Fairness, Accountability, and Transparency in Machine Learning), as well as workshops such as FATES (Fairness, Accountability, Transparency, Ethics, and Society on the Web), FACTS-IR (Fairness, Accountability, Confidentiality, Transparency, and Safety in Information Retrieval), and HWB (Handling Web Bias). There are also governmental and global initiatives such as the AI for Good Global Summit, AI for Good initiative, and Partnership on AI. Other organizations – such as the Organization for Economic Co-operation and Development (OECD) AI Policy Observatory, UNESCO, the World Economic Forum, and the Institute of Electrical and Electronics Engineers (IEEE) – have convened a wide range of stakeholders to lay out ethical principles for the development and implementation of AI.Often missing from these pursuits is the perspective of cognitive science that studies how humans (as individuals or as groups) think about, learn, and make moral decisions. The aim of the computational ethics framework is to complement and supplement the work being done in these communities by reviewing the ongoing research and providing a new structure that helps to focus work toward both building ethical machines and better understanding human ethics. Fifteen years ago the fields of machine ethics (implementing ethical decision-making in machines) [56.Anderson M. Anderson S.L. Machine Ethics. Cambridge University Press, 2011Crossref Google Scholar,132.Anderson M. Anderson S.L. Guest editors' introduction: machine ethics.IEEE Intell. Syst. 2006; 21: 10-11Crossref Scopus (33) Google Scholar] and roboethics (how humans design, use, and treat robots) [133.Veruggio G. A proposal for a roboethics.in: 1st International Symposium on Roboethics: The Ethics, Social, Humanitarian, and Ecological Aspects of Robotics. Roboethics.org, 2004Google Scholar,134.Tzafestas S.G. Roboethics: A Navigating Overview. Springer, 2015Google Scholar] emerged to bring the perspective of ethics to AI development. Since then 'AI ethics' has emerged as an umbrella term to describe work concerning both AI and ethics. New research directions for AI ethics include algorithmic accountability (the obligation to be able to explain and/or justify algorithmic decisions) [135.Wieringa M. What to account for when accounting for algorithms.in: Hildebrandt M. Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency. Association for Computing Machinery, 2020: 1-18Crossref Scopus (66) Google Scholar], algorithmic transparency (openness about the purpose, structure, and actions of algorithms) [136.Weller A. Transparency: motivations and challenges.in: Samek W. Explainable AI: Interpreting, Explaining and Visualizing Deep Learning. Springer, 2019: 23-40Crossref Scopus (32) Google Scholar], algorithmic fairness/bias (attempts to design algorithms that make fair/unbiased decisions) [137.Mehrabi N. et al.A survey on bias and fairness in machine learning.ACM Comput. Surv. 2019; 54: 1-35Crossref Scopus (87) Google Scholar], and AI for (social) good (ensuring that AI algorithms have a positive impact) [138.Tomašev N. et al.AI for social good: unlocking the opportunity for positive impact.Nat. Commun. 2020; 11: 2468Crossref PubMed Scopus (26) Google Scholar]. Similarly, new multidisciplinary fields of research have been initiated, including responsible AI (RAI; the development of guidelines, regulations, laws, and certifications regarding how AI should be researched, developed, and used) [139.Dignum V. Responsible Artificial Intelligence: How to Develop and Use AI in a Responsible Way. Springer, 2019Crossref Google Scholar], explainable AI (XAI; the development and study of automatically generated explanations for algorithmic decisions) [140.Wachter S. et al.Transparent, explainable, and accountable AI for robotics. Science.Robotics. 2017; 2: eaan6080Crossref Scopus (99) Google Scholar,141.Wachter S. et al.Counterfactual explanations without opening the black box: automated decisions and the GDPR.Harv. J. Law Technol. 2017; 31: 841-887Google Scholar], and machine behavior (the study of machines as a new class of actors with their unique behavioral patterns and ecology) [31.Rahwan I. et al.Machine behaviour.Nature. 2019; 568: 477-486Crossref PubMed Scopus (301) Google Scholar]. These fields and communities have already begun to communicate via academic conferences including AIES (Artificial Intelligence, Ethics, and Society), supported by the Association for the Advancement of AI (AAAI) and the Association for Computing Machinery (ACM), and FAT/ML (Fairness, Accountability, and Transparency in Machine Learning), as well as workshops such as FATES (Fairness, Accountability, Transparency, Ethics, and Society on the Web), FACTS-IR (Fairness, Accountability, Confidentiality, Transparency, and Safety in Information Retrieval), and HWB (Handling Web Bias). There are also governmental and global initiatives such as the AI for Good Global Summit, AI for Good initiative, and Partnership on AI. Other organizations – such as the Organization for Economic Co-operation and Development (OECD) AI Policy Observatory, UNESCO, the World Economic Forum, and the Institute of Electrical and Electronics Engineers (IEEE) – have convened a wide range of stakeholders to lay out ethical principles for the development and implementation of AI. Often missing from these pursuits is the perspective of cognitive science that studies how humans (as individuals or as groups) think about, learn, and make moral decisions. The aim of the computational ethics framework is to complement and supplement the work being done in these communities by reviewing the ongoing research and providing a new structure that helps to focus work toward both building ethical machines and better understanding human ethics. We first consider how formalizing our normative views and theories of moral cognition can enable progress in engineering ethical AI systems that behave in ways we find morally acceptable [9.Bonnefon J.-F. et al.The moral psychology of AI and the ethical opt-out problem.in: Liao S.M. Ethics of Artificial Intelligence. Oxford University Press, 2020: 109-126Crossref Scopus (9) Google Scholar,10.Russell S. Human Compatible: AI and the Problem of Control. Penguin, UK2019Google Scholar]. Such considerations will yield valuable lessons for machine ethics (Box 2 discusses whether humans should delegate ethics to machines). The following example illustrates the process of developing machine ethics in kidney exchange.Box 2On delegating ethics to machinesShould humans delegate ethics to machines? In opposition to this idea, van Wynsberghe and Robbins propose 'a moratorium on the commercialization of robots claiming to have ethical reasoning skills' [142.van Wynsberghe A. Robbins S. Critiquing the reasons for making artificial moral agents.Sci. Eng. Ethics. 2019; 25: 719-735Crossref PubMed Scopus (44) Google Scholar]. In support of the idea, others have cited several reasons for deploying moral AI. The following considerations are relevant.InevitabilityAdmittedly, moral AI could have unwanted side effects, including abuses and misuses, and these dangers lead critics to oppose the development of moral AI. However, some argue that moral AI is inevitable. Nevertheless, the fact that something is inevitable – like death and taxes – does not make it good. The lesson instead is that people will inevitably develop solutions as needs arise. For example, the global shortage of caregivers in hospitals and nursing homes will lead to more robotic caregivers. Such robots will face moral tradeoffs. If they do less harm and better protect patient autonomy if they are able to reason morally, then there is a reason to try to design robotic caregivers to be moral reasoners [143.Poulsen A. et al.Responses to a critique of artificial moral agents.ArXiv. 2019; (Published online March 17, 2019)https://arxiv.org/abs/1903.07021Google Scholar].TrustAI cannot do much good if the public does not use it, and use requires trust. When AI uses black box methods to instill ethics, this itself undermines trust, which can lead to diminished use and benefits. However, a responsible and transparent development can increase the public's trust in AI, especially if they know that it is sensitive to their rights and other moral concerns [144.Shin D. User perceptions of algorithmic decisions in the personalized AI system: perceptual evaluation of fairness, accountability, transparency, and explainability.J. Broadcast. Electron. Media. 2020; 64: 541-565Crossref Scopus (27) Google Scholar].ComplexityMoral judgment is complex. It is not simply about safety or harm minimization, and includes other factors – including fairness, honesty, autonomy, merit, and roles – that affect what is morally right or wrong. Humans often overlook relevant factors or become confused by complex interactions between conflicting factors. They are also sometimes overcome by emotions, such as dislike of particular groups or fear during military conflicts [145.Arkin R. Governing Lethal Behavior in Autonomous Robots. Chapman and Hall/CRC, 2009Crossref Scopus (300) Google Scholar]. Some researchers hope that sophisticated machines can avoid these problems and then make better moral judgments and decisions than humans. To achieve this goal, robots need to be equipped with broad moral competence for unpredictable problems, through proper and responsible design. However, a potential downside is that over-reliance on moral AI could make humans less likely to develop their own moral reasoning skills [118.Vallor S. Technology and the Virtues: A Philosophical Guide to a Future Worth Wanting. Oxford University Press, 2016Crossref Google Scholar].Of course, all these issues deserve much more careful consideration [146.Vanderelst D. Winfield A. The dark side of ethical robots.in: Furman J. Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society. Association for Computing Machinery, 2018: 317-322Crossref Scopus (11) Google Scholar,147.Cave S. et al.Motivations and risks of machine ethics.Proc. IEEE. 2019; 107: 562-574Crossref Scopus (19) Google Scholar]. It is also crucial to discuss how to govern and regulate moral AI [148.Winfield A.F. et al.Machine ethics: the design and governance of ethical ai and autonomous systems.Proc. IEEE. 2019; 107: 509-517Crossref Scopus (60) Google Scholar,149.Falco G. et al.Governing AI safety through independent audits.Nat. Mach. Intell. 2021; 3: 566-571Crossref Scopus (7) Google Scholar]. Should humans delegate ethics to machines? In opposition to this idea, van Wynsberghe and Robbins propose 'a moratorium on the commercialization of robots claiming to have ethical reasoning skills' [142.van Wynsberghe A. Robbins S. Critiquing the reasons for making artificial moral agents.Sci. Eng. Ethics. 2019; 25: 719-735Crossref PubMed Scopus (44) Google Scholar]. In support of the idea, others have cited several reasons for deploying moral AI. The following considerations are relevant. Inevitability Admittedly, moral AI could have unwanted side effects, including abuses and misuses, and these dangers lead critics to oppose the development of moral AI. However, some argue that moral AI is inevitable. Nevertheless, the fact that something is inevitable – like death and taxes – does not make it good. The lesson instead is that people will inevitably develop solutions as needs arise. For example, the global shortage of caregivers in hospitals and nursing homes will lead to more robotic caregivers. Such robots will face moral tradeoffs. If they do less harm and better protect patient autonomy if they are able to reason morally, then there is a reason to try to design robotic caregivers to be moral reasoners [143.Poulsen A. et al.Responses to a critique of artificial moral agents.ArXiv. 2019; (Published online March 17, 2019)https://arxiv.org/abs/1903.07021Google Scholar]. Trust AI cannot do much good if the public does not use it, and use requires trust. When AI uses black box methods to instill ethics, this itself undermines trust, which can lead to diminished use and benefits. However, a responsible and transparent development can increase the public's trust in AI, especially if they know that it is sensitive to their rights and other moral concerns [144.Shin D. User perceptions of algorithmic decisions in the personalized AI system: perceptual evaluation of fairness, accountability, transparency, and explainability.J. Broadcast. Electron. Media. 2020; 64: 541-565Crossref Scopus (27) Google Scholar]. Complexity Moral judgment is complex. It is not simply about safety or harm minimization, and includes other factors – including fairness, honesty, autonomy, merit, and roles – that affect what is morally right or wrong. Humans often overlook relevant factors or become confused by complex interactions between conflicting factors. They are also sometimes overcome by emotions, such as dislike of particular groups or fear during military conflicts [145.Arkin R. Governing Lethal Behavior in Autonomous Robots. Chapman and Hall/CRC, 2009Crossref Scopus (300) Google Scholar]. Some researchers hope that sophisticated machines can avoid these problems and then make better moral judgments and decisions than humans. To achieve this goal, robots need to be equipped with broad moral competence for unpredictable problems, through proper and responsible design. However, a potential downside is that over-reliance on moral AI could make humans less likely to develop their own moral reasoning skills [118.Vallor S. Technology and the Virtues: A Philosophical Guide to a Future Worth Wanting. Oxford University Press, 2016Crossref Google Scholar]. Of course, all these issues deserve much more careful consideration [146.Vanderelst D. Winfield A. The dark side of ethical robots.in: Furman J. Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society. Association for Computing Machinery, 2018: 317-322Crossref Scopus (11) Google Scholar,147.Cave S. et al.Motivations and risks of machine ethics.Proc. IEEE. 2019; 107: 562-574Crossref Scopus (19) Google Scholar]. It is also crucial to discuss how to govern and regulate moral AI [148.Winfield A.F. et al.Machine ethics: the design and governance of ethical ai and autonomous systems.Proc. IEEE. 2019; 107: 509-517Crossref Scopus (60) Google Scholar,149.Falco G. et al.Governing AI safety through independent audits.Nat. Mach. Intell. 2021; 3: 566-571Crossref Scopus (7) Google Scholar]. Example 1 [kidney exchange]. Thousands of patients are in need of kidney transplants, and thousands of individuals are willing to donate kidneys (sometimes on the condition that kidneys are allocated a certain way). However, kidneys can only be allocated to compatible patients, and there are always more people in need of kidneys than willing donors. How should kidneys be allocated? Can an algorithm help to solve this problem? If so, what is the optimal solution? An initial answer might be: maximize the number of recipients (i.e., matches). However, there are multiple solutions that achieve the maximum number of matches but result in different individuals receiving kidneys. How should we decide among these solutions [11.Roth A.E. et al.Kidney exchange.Q. J. Econ. 2004; 119: 457-488Crossref Scopus (457) Google Scholar, 12.Bertsimas D. et al.Fairness, efficiency, and flexibility in organ allocation for kidney transplantation.Oper. Res. 2013; 61: 73-87Crossref Scopus (42) Google Scholar, 13.Freedman R. et al.Adapting a kidney exchange algorithm to align with human values.Artif. Intell. 2020; 283103261Crossref Scopus (16) Google Scholar]? There are many ways to determine what a fair or justified allocation is and to determine who deserves to get a kidney and who does not. One path forward is to interface with normative ethics and moral psychology and to take inspiration from the factors that have been used by ethicists and by ordinary people when making similar judgments (the question of when and how to integrate the input of these two groups is taken up in the section on normative–descriptive alignment). For the answers to be useful to designing the algorithm, they must be formalized in computational terms. Only following that formalization can algorithmic kidney exchanges be adapted to reflect insights from normative and descriptive human ethics (Box 3 for further discussion).Box 3Extended example – kidney exchangeThis box explores how computational ethics can be used to make progress in a particular ethical challenge: matching kidney donors to compatible patients (example 1).Work relevant to the 'formalize' phase could contribute in several ways. 'Formalizing normative ethics' focuses on representing (perhaps using first-order logic) a set of abstract principles that together form a sound (systematic and consistent) and complete (covering all cases) algorithm. 'Formalizing descriptive ethics' focuses on characterizing (perhaps with computational models) the case-based intuitions of laypersons about which features (e.g., age, critical condition) matter for people when considering different solutions. 'Balancing conflicting values' would formulate this problem as, for example, a combinatorial optimization problem (to maximize the number of recipients, following normative utilitarian views) while adapting weights to reflect the importance of different features (following descriptive preferences for tie breaking), and then applying a computational technique (e.g., an integer program formulation) to solve it.Suppose, as a result, that an algorithm is developed to prioritize patients based on their general health. Although this may seem reasonable at the outset, work relevant to the 'evaluate' phase will help to study the influence of these decisions at the statistical level, and uncover second-order effects on society. For example, the algorithm may end up by discriminating against poorer participants who are likely to have more comorbidities as a result of their economic disadvantage. Work in 'evaluating machine ethical behavior' could use data about patients to evaluate this possibility.Suppose that, upon probing this algorithm with different inputs, we find that patients from poorer socioeconomic backgrounds are indeed being significantly disadvantaged by this algorithm. Moreover, work on 'evaluating human ethical behavior' may uncover how this disadvantage may spill over to human ethical decisions in other domains such as employment (e.g., by disadvantaging job candidates experiencing hindrances in their mental capacity as a consequence of kidney failure). Work under the 'formalize' phase (e.g., 'balancing conflicting values') may then develop technical adaptations to mitigate such bias.Insights about comorbidities may help 'formal descriptive/normative ethics' to realize the considerations implicit in our considered judgments that have not been explicitly articulated. Newly formalized moral principles are then evaluated again, and so on, until formalized moral principles are in c
View PDF Chat

Signaling in Bayesian Stackelberg Games

2016-05-09
Haifeng Xu , Rupert Freeman , Vincent Conitzer +2 more
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 … 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, 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.

Complexity of Manipulating Elections with Few Candidates

2002-01-01
Vincent Conitzer , Tüomas 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 … 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. Especially among computational agents, it is reasonable to measure this hardness by computational complexity. Some earlier work has been done in this area, but it was assumed that the number of voters and candidates is unbounded. We derive hardness results for practical multiagent settings where the number of candidates is small but the number of voters can be large. We show that with complete information about the others' votes, individual manipulation is easy, and coalitional manipulation is easy with unweighted voters. However, constructive coalitional manipulation with weighted voters is intractable for all of the voting protocols under study, except for the nonrandomized Cup. Destructive manipulation tends to be easier. Randomizing over instantiations of the protocols (such as schedules of the Cup protocol) can be used to make manipulation hard. Finally, we show that under weak assumptions, if weighted coalitional manipulation with complete information about the others' votes is hard in some voting protocol, then individual and unweighted manipulation is hard when there is uncertainty about the others' votes.

Pacing Equilibrium in First-Price Auction Markets

2019-06-17
Vincent Conitzer , Christian Kroer , Debmalya Panigrahi +4 more
Mature internet advertising platforms offer high-level campaign management tools to help advertisers run their campaigns, often abstracting away the intricacies of how each ad is placed and focusing on aggregate … Mature internet advertising platforms offer high-level campaign management tools to help advertisers run their campaigns, often abstracting away the intricacies of how each ad is placed and focusing on aggregate metrics of interest to advertisers. On such platforms, advertisers often participate in auctions through a proxy bidder, so the standard incentive analyses that are common in the literature do not apply directly. In this paper, we take the perspective of a budget management system that surfaces aggregated incentives -- instead of individual auctions -- and compare first and second price auctions. We show that theory offers surprising endorsement for using a first price auction to sell individual impressions. In particular, first price auctions guarantee uniqueness of the steady-state equilibrium of the budget management system, monotonicity, and other desirable properties, as well as efficient computation through the solution to the well-studied Eisenberg-Gale convex program. Contrary to what one can expect from first price auctions, we show that incentives issues are not a barrier that undermines the system. Using realistic instances generated from data collected at real-world auction platforms, we show that bidders have small regret with respect to their optimal ex-post strategy, and they do not have a big incentive to misreport when they can influence equilibria directly by giving inputs strategically. Finally, budget-constrained bidders, who have significant prevalence in real-world platforms, tend to have smaller regrets. Our computations indicate that bidder budgets, pacing multipliers and regrets all have a positive association in statistical terms.
View PDF Chat

Complexity of determining nonemptiness of the core

2003-06-09
Vincent Conitzer , Tüomas Sandholm
Coalition formation is a key problem in automated negotiation among self-interested agents, and other electronic commerce applications. A coalition of agents can sometimes accomplish things that the individual agents cannot, … Coalition formation is a key problem in automated negotiation among self-interested agents, and other electronic commerce 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 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), 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 NP-complete even when the collaborative possibilities are given.
View PDF Chat

Prediction Markets, Mechanism Design, and Cooperative Game Theory

2012-01-01
Vincent Conitzer
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; … 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.

Welfare Undominated Groves Mechanisms

2008-01-01
Krzysztof R. Apt , Vincent Conitzer , Mingyu Guo +1 more

Eliciting single-peaked preferences using comparison queries

2007-05-14
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 … 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.
View PDF Chat

Undominated Groves Mechanisms

2013-01-31
Meng Guo , Evangelos Markakis , Krzysztof R. Apt +1 more
The family of Groves mechanisms, which includes the well-known VCG mechanism (also known as the Clarke mechanism), is a family of efficient and strategy-proof mechanisms. Unfortunately, the Groves mechanisms are … The family of Groves mechanisms, which includes the well-known VCG mechanism (also known as the Clarke mechanism), is a family of efficient and strategy-proof mechanisms. Unfortunately, the Groves mechanisms are generally not budget balanced. That is, under such mechanisms, payments may flow into or out of the system of the agents, resulting in deficits or reduced utilities for the agents. We consider the following problem: within the family of Groves mechanisms, we want to identify mechanisms that give the agents the highest utilities, under the constraint that these mechanisms must never incur deficits. We adopt a prior-free approach. We introduce two general measures for comparing mechanisms in prior-free settings. We say that a non-deficit Groves mechanism M individually dominates another non-deficit Groves mechanism M' if for every type profile, every agent's utility under M is no less than that under M', and this holds with strict inequality for at least one type profile and one agent. We say that a non-deficit Groves mechanism M collectively dominates another non-deficit Groves mechanism M' if for every type profile, the agents' total utility under M is no less than that under M', and this holds with strict inequality for at least one type profile. The above definitions induce two partial orders on non-deficit Groves mechanisms. We study the maximal elements corresponding to these two partial orders, which we call the individually undominated mechanisms and the collectively undominated mechanisms, respectively.
View PDF Chat

Complexity of Determining Nonemptiness of the Core

2003-07-07
Vincent Conitzer , Tüomas 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 … 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 $\mathcal{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), 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 $\mathcal{NP}$-complete even when the collaborative possibilities are given.

Multiplicative Pacing Equilibria in Auction Markets

2021-12-13
Vincent Conitzer , Christian Kroer , Eric Sodomka +1 more
Budgets play a significant role in ad markets that implement sequential auctions such as those hosted by internet companies. In “Multiplicative Pacing Equilibria in Auction Markets,” the authors look at … Budgets play a significant role in ad markets that implement sequential auctions such as those hosted by internet companies. In “Multiplicative Pacing Equilibria in Auction Markets,” the authors look at pacing in an ad marketplace using the lens of game theory. The goal is understanding how bids must be shaded to maximize advertiser welfare, at equilibrium. Motivated by the real-world auction mechanism, they construct a game where advertisers in the auctions choose a multiplicative factor not larger than 1 to possibly reduce their bids and best respond to the other advertisers. The article studies the theoretical properties of the game such as existence and uniqueness of equilibria, offers an exact algorithm to compute them, connects the game to well-known abstractions such as Fisher markets, and performs a computational study with real-world-inspired instances. The main insights are that the solutions to the studied game can be used to improve the outcomes achieved by a closer-to-reality dynamic pacing algorithm and that buyers do not have an incentive to misreport bids or budgets when there are enough participants in the auction.
View PDF Chat

Adapting a Kidney Exchange Algorithm to Align with Human Values

2018-12-27
Rachel Freedman , Jana Schaich Borg , Walter Sinnott‐Armstrong +2 more
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 … 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.
View PDF Chat

Justified Representation in Approval-Based Committee Voting

2015-02-16
Haris Aziz , Markus Brill , Vincent Conitzer +3 more
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 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 agree- ment 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.
View PDF Chat

Pacing Equilibrium in First Price Auction Markets

2022-04-06
Vincent Conitzer , Christian Kroer , Debmalya Panigrahi +4 more
Mature internet advertising platforms offer high-level campaign management tools to help advertisers run their campaigns, often abstracting away the intricacies of how each ad is placed and focusing on aggregate … Mature internet advertising platforms offer high-level campaign management tools to help advertisers run their campaigns, often abstracting away the intricacies of how each ad is placed and focusing on aggregate metrics of interest to advertisers. On such platforms, advertisers often participate in auctions through a proxy bidder, so the standard incentive analyses that are common in the literature do not apply directly. In this paper, we take the perspective of a budget management system that surfaces aggregated incentives—instead of individual auctions—and compare first and second price auctions. We show that theory offers surprising endorsement for using a first price auction to sell individual impressions. In particular, first price auctions guarantee uniqueness of the steady-state equilibrium of the budget management system, monotonicity, and other desirable properties, as well as efficient computation through the solution to the well-studied Eisenberg–Gale convex program. Contrary to what one can expect from first price auctions, we show that incentives issues are not a barrier that undermines the system. Using realistic instances generated from data collected at real-world auction platforms, we show that bidders have small regret with respect to their optimal ex post strategy, and they do not have a big incentive to misreport when they can influence equilibria directly by giving inputs strategically. Finally, budget-constrained bidders, who have significant prevalence in real-world platforms, tend to have smaller regrets. Our computations indicate that bidder budgets, pacing multipliers, and regrets all have a positive association in statistical terms. This paper was accepted by Gabriel Weintraub, revenue management and market analytics. Funding: D. Panigrahi was supported in part by the National Science Foundation [Awards CCF 1535972, CCF 1750140, and CCF 1955703]. Supplemental Material: The data files are available at https://doi.org/10.1287/mnsc.2022.4310 .
View PDF Chat

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

2003-01-01
Vincent Conitzer , Jérôme Lang , Tüomas 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 … 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.
View PDF Chat

Multiplicative Pacing Equilibria in Auction Markets

2017-06-22
Vincent Conitzer , Christian Kroer , Eric Sodomka +1 more
Budgets play a significant role in real-world sequential auction markets such as those implemented by Internet companies. To maximize the value provided to auction participants, spending is smoothed across auctions … Budgets play a significant role in real-world sequential auction markets such as those implemented by Internet companies. To maximize the value provided to auction participants, spending is smoothed across auctions so budgets are used for the best opportunities. This paper considers a smoothing procedure that relies on {\em pacing multipliers}: for each bidder, the platform applies a factor between 0 and 1 that uniformly scales the bids across all auctions. Looking at this process as a game between all bidders, we introduce the notion of {\em pacing equilibrium}, and prove that they are always guaranteed to exist. We demonstrate through examples that a market can have multiple pacing equilibria with large variations in several natural objectives. We go on to show that computing either a social-welfare-maximizing or a revenue-maximizing pacing equilibrium is NP-hard. Finally, we develop a mixed-integer program whose feasible solutions coincide with pacing equilibria, and show that it can be used to find equilibria that optimize several interesting objectives. Using our mixed-integer program, we perform numerical simulations on synthetic auction markets that provide evidence that, in spite of the possibility of equilibrium multiplicity, it occurs very rarely across several families of random instances. We also show that solutions from the mixed-integer program can be used to improve the outcomes achieved in a more realistic adaptive pacing setting.

Mitigating Manipulation in Peer Review via Randomized Reviewer Assignments

2020-01-01
Steven Jecmen , Hanrui Zhang , Ryan Liu +3 more
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 … 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. Our algorithms still achieve this similarity while also preventing reviewers with close associations from being assigned to the same paper.

Complexity Results about Nash Equilibria

2002-05-28
Vincent Conitzer , Tüomas Sandholm
Noncooperative game theory provides a normative framework for analyzing strategic interactions. However, for the toolbox to be operational, the solutions it defines will have to be computed. In this paper, … Noncooperative game theory provides a normative framework for analyzing strategic interactions. However, for the toolbox to be operational, the solutions it defines will have to be computed. In this paper, we provide a single reduction that 1) demonstrates NP-hardness of determining whether Nash equilibria with certain natural properties exist, and 2) demonstrates the #P-hardness of counting Nash equilibria (or connected sets of Nash equilibria). We also show that 3) determining whether a pure-strategy Bayes-Nash equilibrium exists is NP-hard, and that 4) determining whether a pure-strategy Nash equilibrium exists in a stochastic (Markov) game is PSPACE-hard even if the game is invisible (this remains NP-hard if the game is finite). All of our hardness results hold even if there are only two players and the game is symmetric. Keywords: Nash equilibrium; game theory; computational complexity; noncooperative game theory; normal form game; stochastic game; Markov game; Bayes-Nash equilibrium; multiagent systems.

Complexity of Scheduling Charging in the Smart Grid

2018-07-01
Mathijs de Weerdt , Michael Albert , Vincent Conitzer +1 more
In the smart grid, the intent is to use flexibility in demand, both to balance demand and supply as well as to resolve potential congestion. A first prominent example of … In the smart grid, the intent is to use flexibility in demand, both to balance demand and supply as well as to resolve potential congestion. A first prominent example of such flexible demand is the charging of electric vehicles, which do not necessarily need to be charged as soon as they are plugged in. 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, we show, using a dynamic programming approach, that the problem is either in P or weakly NP-hard. We also show that about 10 variants of the problem are strongly NP-hard, presenting a potentially significant obstacle to their use in practical situations of scale.
View PDF Chat

Ethical Implementation of Artificial Intelligence to Select Embryos in In Vitro Fertilization

2021-07-21
Michael Anis Mihdi Afnan , Cynthia Rudin , Vincent Conitzer +4 more
AI has the potential to revolutionize many areas of healthcare. Radiology, dermatology, and ophthalmology are some of the areas most likely to be impacted in the near future, and they … AI has the potential to revolutionize many areas of healthcare. Radiology, dermatology, and ophthalmology are some of the areas most likely to be impacted in the near future, and they have received significant attention from the broader research community. But AI techniques are now also starting to be used in in vitro fertilization (IVF), in particular for selecting which embryos to transfer to the woman. The contribution of AI to IVF is potentially significant, but must be done carefully and transparently, as the ethical issues are significant, in part because this field involves creating new people. We first give a brief introduction to IVF and review the use of AI for embryo selection. We discuss concerns with the interpretation of the reported results from scientific and practical perspectives. We then consider the broader ethical issues involved. We discuss in detail the problems that result from the use of black-box methods in this context and advocate strongly for the use of interpretable models. Importantly, there have been no published trials of clinical effectiveness, a problem in both the AI and IVF communities, and we therefore argue that clinical implementation at this point would be premature. Finally, we discuss ways for the broader AI community to become involved to ensure scientifically sound and ethically responsible development of AI in IVF.
View PDF Chat

The Exact Computational Complexity of Evolutionarily Stable Strategies

2013-01-01
Vincent Conitzer
View PDF Chat

On Stackelberg mixed strategies

2015-09-30
Vincent Conitzer
View PDF Chat

Adapting a Kidney Exchange Algorithm to Align With Human Values

2018-04-25
Rachel Freedman , Jana Schaich Borg , Walter Sinnott‐Armstrong +2 more
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 … 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.
View PDF Chat

Classification with Strategically Withheld Data

2021-05-18
A. Krishnaswamy , Haoming Li , David B. Rein +2 more
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 … 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-the-box 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 real-world data sets, and present insights into their relative performance in different settings.
View PDF Chat

Common Voting Rules as Maximum Likelihood Estimators

2012-07-04
Vincent Conitzer , Tüomas 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 … 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

A Dutch book against sleeping beauties who are evidential decision theorists

2015-02-17
Vincent Conitzer
View PDF Chat

Multiplicative Pacing Equilibria in Auction Markets

2017-01-01
Vincent Conitzer , Christian Kroer , Eric Sodomka +1 more
Budgets play a significant role in real-world sequential auction markets such as those implemented by internet companies. To maximize the value provided to auction participants, spending is smoothed across auctions … Budgets play a significant role in real-world sequential auction markets such as those implemented by internet companies. To maximize the value provided to auction participants, spending is smoothed across auctions so budgets are used for the best opportunities. Motivated by a mechanism used in practice by several companies, this paper considers a smoothing procedure that relies on {\em pacing multipliers}: on behalf of each buyer, the auction market applies a factor between 0 and 1 that uniformly scales the bids across all auctions. Reinterpreting this process as a game between buyers, we introduce the notion of {\em pacing equilibrium}, and prove that they are always guaranteed to exist. We demonstrate through examples that a market can have multiple pacing equilibria with large variations in several natural objectives. We show that pacing equilibria refine another popular solution concept, competitive equilibria, and show further connections between the two solution concepts. Although we show that computing either a social-welfare-maximizing or a revenue-maximizing pacing equilibrium is NP-hard, we present a mixed-integer program (MIP) that can be used to find equilibria optimizing several relevant objectives. We use the MIP to provide evidence that: (1) equilibrium multiplicity occurs very rarely across several families of random instances, (2) static MIP solutions can be used to improve the outcomes achieved by a dynamic pacing algorithm with instances based on a real-world auction market, and (3) for the instances we study, buyers do not have an incentive to misreport bids or budgets provided there are enough participants in the auction.
View PDF Chat

A Puzzle about Further Facts

2018-03-07
Vincent Conitzer
In metaphysics, there are a number of distinct but related questions about the existence of "further facts" -- facts that are contingent relative to the physical structure of the universe. … In metaphysics, there are a number of distinct but related questions about the existence of "further facts" -- facts that are contingent relative to the physical structure of the universe. These include further facts about qualia, personal identity, and time. In this article I provide a sequence of examples involving computer simulations, ranging from one in which the protagonist can clearly conclude such further facts exist to one that describes our own condition. This raises the question of where along the sequence (if at all) the protagonist stops being able to soundly conclude that further facts exist.
View PDF Chat

Timeability of Extensive-Form Games

2016-01-05
S. Jakobsen , Troels Bjerre Sørensen , Vincent Conitzer
Extensive-form games constitute the standard representation scheme for games with a temporal component. But do all extensive-form games correspond to protocols that we can implement in the real world? We … Extensive-form games constitute the standard representation scheme for games with a temporal component. But do all extensive-form games correspond to protocols that we can implement in the real world? We often rule out games with imperfect recall, which prescribe that an agent forget something that she knew before. In this paper, we show that even some games with perfect recall can be problematic to implement. Specifically, we show that if the agents have a sense of time passing (say, access to a clock), then some extensive-form games can no longer be implemented; no matter how we attempt to time the game, some information will leak to the agents that they are not supposed to have. We say such a game is not exactly timeable. We provide easy-to-check necessary and sufficient conditions for a game to be exactly timeable. Most of the technical depth of the paper concerns how to approximately time games, which we show can always be done, though it may require large amounts of time. Specifically, we show that some games require time proportional to the power tower of height proportional to the number of players, which in practice would make them untimeable. We hope to convince the reader that timeability should be a standard assumption, just as perfect recall is today. Besides the conceptual contribution to game theory, we show that timeability has implications for onion routing protocols.
View PDF Chat

Definition and Complexity of Some Basic Metareasoning Problems

2003-01-01
Vincent Conitzer , Tüomas 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 … 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 $\mathcal{NP}$-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 $\mathcal{NP}$-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 $\mathcal{NP}$-hard under a natural restriction, and $\mathcal{PSPACE}$-hard in general.

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

2003-01-01
Vincent Conitzer , Tüomas Sandholm
A satisfactory multiagent learning algorithm should, {\em at a minimum}, learn to play optimally against stationary opponents and converge to a Nash equilibrium in self-play. The algorithm that has come … A satisfactory multiagent learning algorithm should, {\em at a minimum}, learn to play optimally against stationary opponents and converge to a Nash equilibrium in self-play. The algorithm that has come closest, WoLF-IGA, has been proven to have these two properties in 2-player 2-action repeated games--assuming that the opponent's (mixed) strategy is observable. In this paper we present AWESOME, the first algorithm that is guaranteed to have these two properties in {\em all} repeated (finite) games. It requires only that the other players' actual actions (not their strategies) can be observed at each step. It also learns to play optimally against opponents that {\em eventually become} stationary. The basic idea behind AWESOME ({\em Adapt When Everybody is Stationary, Otherwise Move to Equilibrium}) is to try to adapt to the others' strategies when they appear stationary, but otherwise to retreat to a precomputed equilibrium strategy. The techniques used to prove the properties of AWESOME are fundamentally different from those used for previous algorithms, and may help in analyzing other multiagent learning algorithms also.
View PDF Chat

Artificial Artificial Intelligence

2020-02-05
Lok-Hei Chan , Kenzie Doyle , Duncan C. McElfresh +4 more
Given AI's growing role in modeling and improving decision-making, how and when to present users with feedback is an urgent topic to address. We empirically examined the effect of feedback … Given AI's growing role in modeling and improving decision-making, how and when to present users with feedback is an urgent topic to address. We empirically examined the effect of feedback from false AI on moral decision-making about donor kidney allocation. We found some evidence that judgments about whether a patient should receive a kidney can be influenced by feedback about participants' own decision-making perceived to be given by AI, even if the feedback is entirely random. We also discovered different effects between assessments presented as being from human experts and assessments presented as being from AI.
View PDF Chat

Fair Public Decision Making

2016-11-12
Vincent Conitzer , Rupert Freeman , Nisarg Shah
We generalize the classic problem of fairly allocating indivisible goods to the problem of \emph{fair public decision making}, in which a decision must be made on several social issues simultaneously, … We generalize the classic problem of fairly allocating indivisible goods to the problem of \emph{fair public decision making}, in which a decision must be made on several social issues simultaneously, and, unlike the classic setting, a decision can provide positive utility to multiple players. We extend the popular fairness notion of proportionality (which is not guaranteeable) to our more general setting, and introduce three novel relaxations --- \emph{proportionality up to one issue, round robin share, and pessimistic proportional share} --- that are also interesting in the classic goods allocation setting. We show that the Maximum Nash Welfare solution, which is known to satisfy appealing fairness properties in the classic setting, satisfies or approximates all three relaxations in our framework. We also provide polynomial time algorithms and hardness results for finding allocations satisfying these axioms, with or without insisting on Pareto optimality.

A Dataset on Malicious Paper Bidding in Peer Review

2023-04-26
Steven Jecmen , Minji Yoon , Vincent Conitzer +2 more
In conference peer review, reviewers are often asked to provide "bids" on each submitted paper that express their interest in reviewing that paper. A paper assignment algorithm then uses these … In conference peer review, reviewers are often asked to provide "bids" on each submitted paper that express their interest in reviewing that paper. A paper assignment algorithm then uses these bids (along with other data) to compute a high-quality assignment of reviewers to papers. However, this process has been exploited by malicious reviewers who strategically bid in order to unethically manipulate the paper assignment, crucially undermining the peer review process. For example, these reviewers may aim to get assigned to a friend's paper as part of a quid-pro-quo deal. A critical impediment towards creating and evaluating methods to mitigate this issue is the lack of any publicly-available data on malicious paper bidding. In this work, we collect and publicly release a novel dataset to fill this gap, collected from a mock conference activity where participants were instructed to bid either honestly or maliciously. We further provide a descriptive analysis of the bidding behavior, including our categorization of different strategies employed by participants. Finally, we evaluate the ability of each strategy to manipulate the assignment, and also evaluate the performance of some simple algorithms meant to detect malicious bidding. The performance of these detection algorithms can be taken as a baseline for future research on detecting malicious bidding.
View PDF Chat

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

2016-01-05
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 … 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.
View PDF Chat

Multi-Agent Risks from Advanced AI

2025-02-19
Lewis Hammond , Alan Chan , Jesse Clifton +7 more
The rapid development of advanced AI agents and the imminent deployment of many instances of these agents will give rise to multi-agent systems of unprecedented complexity. These systems pose novel … The rapid development of advanced AI agents and the imminent deployment of many instances of these agents will give rise to multi-agent systems of unprecedented complexity. These systems pose novel and under-explored risks. In this report, we provide a structured taxonomy of these risks by identifying three key failure modes (miscoordination, conflict, and collusion) based on agents' incentives, as well as seven key risk factors (information asymmetries, network effects, selection pressures, destabilising dynamics, commitment problems, emergent agency, and multi-agent security) that can underpin them. We highlight several important instances of each risk, as well as promising directions to help mitigate them. By anchoring our analysis in a range of real-world examples and experimental evidence, we illustrate the distinct challenges posed by multi-agent systems and their implications for the safety, governance, and ethics of advanced AI.
View PDF Chat

An Interpretable Automated Mechanism Design Framework with Large Language Models

2025-02-16
Jiayuan Liu , Mingyu Guo , Vincent Conitzer
Mechanism design has long been a cornerstone of economic theory, with traditional approaches relying on mathematical derivations. Recently, automated approaches, including differentiable economics with neural networks, have emerged for designing … Mechanism design has long been a cornerstone of economic theory, with traditional approaches relying on mathematical derivations. Recently, automated approaches, including differentiable economics with neural networks, have emerged for designing payments and allocations. While both analytical and automated methods have advanced the field, they each face significant weaknesses: mathematical derivations are not automated and often struggle to scale to complex problems, while automated and especially neural-network-based approaches suffer from limited interpretability. To address these challenges, we introduce a novel framework that reformulates mechanism design as a code generation task. Using large language models (LLMs), we generate heuristic mechanisms described in code and evolve them to optimize over some evaluation metrics while ensuring key design criteria (e.g., strategy-proofness) through a problem-specific fixing process. This fixing process ensures any mechanism violating the design criteria is adjusted to satisfy them, albeit with some trade-offs in performance metrics. These trade-offs are factored in during the LLM-based evolution process. The code generation capabilities of LLMs enable the discovery of novel and interpretable solutions, bridging the symbolic logic of mechanism design and the generative power of modern AI. Through rigorous experimentation, we demonstrate that LLM-generated mechanisms achieve competitive performance while offering greater interpretability compared to previous approaches. Notably, our framework can rediscover existing manually designed mechanisms and provide insights into neural-network based solutions through Programming-by-Example. These results highlight the potential of LLMs to not only automate but also enhance the transparency and scalability of mechanism design, ensuring safe deployment of the mechanisms in society.
View PDF Chat

Computing Game Symmetries and Equilibria That Respect Them

2025-01-15
Emanuel Tewolde , Brian Hu Zhang , Caspar Oesterheld +2 more
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 … 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.
View PDF Chat

The Value of Recall in Extensive-Form Games

2024-12-27
Ratip Emin Berker , Emanuel Tewolde , Ioannis Anagnostides +2 more
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 … 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.
View PDF Chat

Observation Interference in Partially Observable Assistance Games

2024-12-23
Scott Emmons , Caspar Oesterheld , Vincent Conitzer +1 more
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 … 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.
View PDF Chat

Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation

2024-12-22
Hanrui Zhang , Yu Cheng , Vincent Conitzer
We study equilibrium computation with extensive-form correlation in two-player turn-taking stochastic games. Our main results are two-fold: (1) We give an algorithm for computing a Stackelberg extensive-form correlated equilibrium (SEFCE), … We study equilibrium computation with extensive-form correlation in two-player turn-taking stochastic games. Our main results are two-fold: (1) We give an algorithm for computing a Stackelberg extensive-form correlated equilibrium (SEFCE), which runs in time polynomial in the size of the game, as well as the number of bits required to encode each input number. (2) We give an efficient algorithm for approximately computing an optimal extensive-form correlated equilibrium (EFCE) up to machine precision, i.e., the algorithm achieves approximation error $\varepsilon$ in time polynomial in the size of the game, as well as $\log(1 / \varepsilon)$. Our algorithm for SEFCE is the first polynomial-time algorithm for equilibrium computation with commitment in such a general class of stochastic games. Existing algorithms for SEFCE typically make stronger assumptions such as no chance moves, and are designed for extensive-form games in the less succinct tree form. Our algorithm for approximately optimal EFCE is, to our knowledge, the first algorithm that achieves 3 desiderata simultaneously: approximate optimality, polylogarithmic dependency on the approximation error, and compatibility with stochastic games in the more succinct graph form. Existing algorithms achieve at most 2 of these desiderata, often also relying on additional technical assumptions.
View PDF Chat

Characterising Simulation-Based Program Equilibria

2024-12-19
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 … 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) 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) $\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.
View PDF Chat

Testing for reviewer anchoring in peer review: A randomized controlled trial

2024-11-18
Ryan Liu , Steven Jecmen , Vincent Conitzer +2 more
Objective Peer review frequently follows a process where reviewers first provide initial reviews, authors respond to these reviews, then reviewers update their reviews based on the authors’ response. There is … Objective Peer review frequently follows a process where reviewers first provide initial reviews, authors respond to these reviews, then reviewers update their reviews based on the authors’ response. There is mixed evidence regarding whether this process is useful, including frequent anecdotal complaints that reviewers insufficiently update their scores. In this study, we aim to investigate whether reviewers anchor to their original scores when updating their reviews, which serves as a potential explanation for the lack of updates in reviewer scores. Design We design a novel randomized controlled trial to test if reviewers exhibit anchoring. In the experimental condition, participants initially see a flawed version of a paper that is corrected after they submit their initial review, while in the control condition, participants only see the correct version. We take various measures to ensure that in the absence of anchoring, reviewers in the experimental group should revise their scores to be identically distributed to the scores from the control group. Furthermore, we construct the reviewed paper to maximize the difference between the flawed and corrected versions, and employ deception to hide the true experiment purpose. Results Our randomized controlled trial consists of 108 researchers as participants. First, we find that our intervention was successful at creating a difference in perceived paper quality between the flawed and corrected versions: Using a permutation test with the Mann-Whitney U statistic, we find that the experimental group’s initial scores are lower than the control group’s scores in both the Evaluation category (Vargha-Delaney A = 0.64, p = 0.0096) and Overall score ( A = 0.59, p = 0.058). Next, we test for anchoring by comparing the experimental group’s revised scores with the control group’s scores. We find no significant evidence of anchoring in either the Overall ( A = 0.50, p = 0.61) or Evaluation category ( A = 0.49, p = 0.61). The Mann-Whitney U represents the number of individual pairwise comparisons across groups in which the value from the specified group is stochastically greater, while the Vargha-Delaney A is the normalized version in [0, 1].
View PDF Chat

Can CDT rationalise the ex ante optimal policy via modified anthropics?

2024-11-07
Emery Cooper , Caspar Oesterheld , Vincent Conitzer
In Newcomb's problem, causal decision theory (CDT) recommends two-boxing and thus comes apart from evidential decision theory (EDT) and ex ante policy optimisation (which prescribe one-boxing). However, in Newcomb's problem, … In Newcomb's problem, causal decision theory (CDT) recommends two-boxing and thus comes apart from evidential decision theory (EDT) and ex ante policy optimisation (which prescribe one-boxing). However, in Newcomb's problem, you should perhaps believe that with some probability you are in a simulation run by the predictor to determine whether to put a million dollars into the opaque box. If so, then causal decision theory might recommend one-boxing in order to cause the predictor to fill the opaque box. In this paper, we study generalisations of this approach. That is, we consider general Newcomblike problems and try to form reasonable self-locating beliefs under which CDT's recommendations align with an EDT-like notion of ex ante policy optimisation. We consider approaches in which we model the world as running simulations of the agent, and an approach not based on such models (which we call 'Generalised Generalised Thirding', or GGT). For each approach, we characterise the resulting CDT policies, and prove that under certain conditions, these include the ex ante optimal policies.
View PDF Chat

Game Theory with Simulation in the Presence of Unpredictable Randomisation

2024-10-18
Vojtěch Kovařík , Nathaniel Sauerberg , Lewis Hammond +1 more
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 … 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 game-theoretic 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.
View PDF Chat

Aggregating Quantitative Relative Judgments: From Social Choice to Ranking Prediction

2024-10-07
Yixuan Even Xu , Hanrui Zhang , Yu Cheng +1 more
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 … 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.
View PDF Chat

On The Stability of Moral Preferences: A Problem with Computational Elicitation Methods

2024-08-05
Kyle Boerstler , Vijay Keswani , Lok-Hei Chan +4 more
Preference elicitation frameworks feature heavily in the research on participatory ethical AI tools and provide a viable mechanism to enquire and incorporate the moral values of various stakeholders. As part … Preference elicitation frameworks feature heavily in the research on participatory ethical AI tools and provide a viable mechanism to enquire and incorporate the moral values of various stakeholders. As part of the elicitation process, surveys about moral preferences, opinions, and judgments are typically administered only once to each participant. This methodological practice is reasonable if participants' responses are stable over time such that, all other relevant factors being held constant, their responses today will be the same as their responses to the same questions at a later time. However, we do not know how often that is the case. It is possible that participants' true moral preferences change, are subject to temporary moods or whims, or are influenced by environmental factors we don't track. If participants' moral responses are unstable in such ways, it would raise important methodological and theoretical issues for how participants' true moral preferences, opinions, and judgments can be ascertained. We address this possibility here by asking the same survey participants the same moral questions about which patient should receive a kidney when only one is available ten times in ten different sessions over two weeks, varying only presentation order across sessions. We measured how often participants gave different responses to simple (Study One) and more complicated (Study Two) repeated scenarios. On average, the fraction of times participants changed their responses to controversial scenarios was around 10-18% across studies, and this instability is observed to have positive associations with response time and decision-making difficulty. We discuss the implications of these results for the efficacy of moral preference elicitation, highlighting the role of response instability in causing value misalignment between stakeholders and AI tools trained on their moral judgments.
View PDF Chat

Computing Optimal Equilibria in Repeated Games with Restarts

2024-07-26
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 … 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.
View PDF Chat

Game Transformations That Preserve Nash Equilibria or Best-Response Sets

2024-07-26
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 … 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.
View PDF Chat

Imperfect-Recall Games: Equilibrium Concepts and Their Complexity

2024-07-26
Emanuel Tewolde , Brian Hu Zhang , Caspar Oesterheld +4 more
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 … 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.
View PDF Chat

On the Pros and Cons of Active Learning for Moral Preference Elicitation

2024-07-26
Vijay Keswani , Vincent Conitzer , Hoda Heidari +2 more
Computational preference elicitation methods are tools used to learn people's preferences quantitatively in a given context. Recent works on preference elicitation advocate for active learning as an efficient method to … Computational preference elicitation methods are tools used to learn people's preferences quantitatively in a given context. Recent works on preference elicitation advocate for active learning as an efficient method to iteratively construct queries (framed as comparisons between context-specific cases) that are likely to be most informative about an agent's underlying preferences. In this work, we argue that the use of active learning for moral preference elicitation relies on certain assumptions about the underlying moral preferences, which can be violated in practice. Specifically, we highlight the following common assumptions (a) preferences are stable over time and not sensitive to the sequence of presented queries, (b) the appropriate hypothesis class is chosen to model moral preferences, and (c) noise in the agent's responses is limited. While these assumptions can be appropriate for preference elicitation in certain domains, prior research on moral psychology suggests they may not be valid for moral judgments. Through a synthetic simulation of preferences that violate the above assumptions, we observe that active learning can have similar or worse performance than a basic random query selection method in certain settings. Yet, simulation results also demonstrate that active learning can still be viable if the degree of instability or noise is relatively small and when the agent's preferences can be approximately represented with the hypothesis class used for learning. Our study highlights the nuances associated with effective moral preference elicitation in practice and advocates for the cautious use of active learning as a methodology to learn moral preferences.
View PDF Chat

Imperfect-Recall Games: Equilibrium Concepts and Their Complexity

2024-06-22
Emanuel Tewolde , Brian Hu Zhang , Caspar Oesterheld +4 more
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 … 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 P, PPAD, PLS, $\Sigma_2^P$ , $\exists$R, and $\exists \forall$R.
View PDF Chat

Computing Optimal Equilibria in Repeated Games with Restarts

2024-06-02
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 … 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.
View PDF Chat

Social Choice for AI Alignment: Dealing with Diverse Human Feedback

2024-04-15
Vincent Conitzer , Rachel A. Freedman , Jobst Heitzig +7 more
Foundation models such as GPT-4 are fine-tuned to avoid unsafe or otherwise problematic behavior, so that, for example, they refuse to comply with requests for help with committing crimes or … Foundation models such as GPT-4 are fine-tuned to avoid unsafe or otherwise problematic behavior, so that, for example, they refuse to comply with requests for help with committing crimes or with 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.
View PDF Chat

Now, Later, and Lasting: Ten Priorities for AI Research, Policy, and Practice

2024-04-06
Eric Horvitz , Vincent Conitzer , Sheila A. McIlraith +1 more
Advances in artificial intelligence (AI) will transform many aspects of our lives and society, bringing immense opportunities but also posing significant risks and challenges. The next several decades may well … Advances in artificial intelligence (AI) will transform many aspects of our lives and society, bringing immense opportunities but also posing significant risks and challenges. The next several decades may well be a turning point for humanity, comparable to the industrial revolution. We write to share a set of recommendations for moving forward from the perspective of the founder and leaders of the One Hundred Year Study on AI. Launched a decade ago, the project is committed to a perpetual series of studies by multidisciplinary experts to evaluate the immediate, longer-term, and far-reaching effects of AI on people and society, and to make recommendations about AI research, policy, and practice. As we witness new capabilities emerging from neural models, it is crucial that we engage in efforts to advance our scientific understanding of these models and their behaviors. We must address the impact of AI on people and society through technical, social, and sociotechnical lenses, incorporating insights from a diverse range of experts including voices from engineering, social, behavioral, and economic disciplines. By fostering dialogue, collaboration, and action among various stakeholders, we can strategically guide the development and deployment of AI in ways that maximize its potential for contributing to human flourishing. Despite the growing divide in the field between focusing on short-term versus long-term implications, we think both are of critical importance. As Alan Turing, one of the pioneers of AI, wrote in 1950, "We can only see a short distance ahead, but we can see plenty there that needs to be done." We offer ten recommendations for action that collectively address both the short- and long-term potential impacts of AI technologies.
View PDF Chat

The Complexity of Computing Robust Mediated Equilibria in Ordinal Games

2024-03-24
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 … 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.
View PDF Chat

Non-excludable Bilateral Trade between Groups

2024-03-24
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 … 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.
View PDF Chat

Recursive Joint Simulation in Games

2024-02-12
Vojtěch Kovařík , Caspar Oesterheld , Vincent Conitzer
Game-theoretic dynamics between AI agents could differ from traditional human-human interactions in various ways. One such difference is that it may be possible to accurately simulate an AI agent, for … Game-theoretic dynamics between AI agents could differ from traditional human-human interactions in various ways. One such difference is that it may be possible to accurately simulate an AI agent, for example because its source code is known. Our aim is to explore ways of leveraging this possibility to achieve more cooperative outcomes in strategic settings. In this paper, we study an interaction between AI agents where the agents run a recursive joint simulation. That is, the agents first jointly observe a simulation of the situation they face. This simulation in turn recursively includes additional simulations (with a small chance of failure, to avoid infinite recursion), and the results of all these nested simulations are observed before an action is chosen. We show that the resulting interaction is strategically equivalent to an infinitely repeated version of the original game, allowing a direct transfer of existing results such as the various folk theorems.
View PDF Chat

Game Theory with Simulation of Other Players

2023-08-01
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 … 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.
View PDF Chat

The Computational Complexity of Single-Player Imperfect-Recall Games

2023-08-01
Emanuel Tewolde , Caspar Oesterheld , Vincent Conitzer +1 more
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 … 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.
View PDF Chat

A Theory of Bounded Inductive Rationality

2023-07-08
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 … 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 π 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 π 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.
View PDF Chat

A Dataset on Malicious Paper Bidding in Peer Review

2023-04-26
Steven Jecmen , Minji Yoon , Vincent Conitzer +2 more
In conference peer review, reviewers are often asked to provide "bids" on each submitted paper that express their interest in reviewing that paper. A paper assignment algorithm then uses these … In conference peer review, reviewers are often asked to provide "bids" on each submitted paper that express their interest in reviewing that paper. A paper assignment algorithm then uses these bids (along with other data) to compute a high-quality assignment of reviewers to papers. However, this process has been exploited by malicious reviewers who strategically bid in order to unethically manipulate the paper assignment, crucially undermining the peer review process. For example, these reviewers may aim to get assigned to a friend's paper as part of a quid-pro-quo deal. A critical impediment towards creating and evaluating methods to mitigate this issue is the lack of any publicly-available data on malicious paper bidding. In this work, we collect and publicly release a novel dataset to fill this gap, collected from a mock conference activity where participants were instructed to bid either honestly or maliciously. We further provide a descriptive analysis of the bidding behavior, including our categorization of different strategies employed by participants. Finally, we evaluate the ability of each strategy to manipulate the assignment, and also evaluate the performance of some simple algorithms meant to detect malicious bidding. The performance of these detection algorithms can be taken as a baseline for future research on detecting malicious bidding.
View PDF Chat

Game Theory with Simulation of Other Players

2023-01-01
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 … 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 formalize games in which one player can simulate another at a cost. We first derive some basic properties of such games and then prove a number of results for them, 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 however (3) there are settings where introducing simulation results in strictly worse outcomes for both players.
View PDF Chat

The Computational Complexity of Single-Player Imperfect-Recall Games

2023-01-01
Emanuel Tewolde , Caspar Oesterheld , Vincent Conitzer +1 more
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 … 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.
View PDF Chat

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

2023-01-01
Brian Hu Zhang , Gabriele Farina , Ioannis Anagnostides +7 more
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 … 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.

Steering No-Regret Learners to Optimal Equilibria

2023-01-01
Brian Hu Zhang , Gabriele Farina , Ioannis Anagnostides +7 more
A mediator observes no-regret learners playing an extensive-form game repeatedly across $T$ rounds. The mediator attempts to steer players toward some desirable predetermined equilibrium by giving (nonnegative) payments to players. … A mediator observes no-regret learners playing an extensive-form game repeatedly across $T$ rounds. The mediator attempts to steer players toward some desirable predetermined equilibrium by giving (nonnegative) payments to players. We call this the steering problem. The steering problem captures problems several problems of interest, among them equilibrium selection and information design (persuasion). If the mediator's budget is unbounded, steering is trivial because the mediator can simply pay the players to play desirable actions. We study two bounds on the mediator's payments: a total budget and a per-round budget. If the mediator's total budget does not grow with $T$, we show that steering is impossible. However, we show that it is enough for the total budget to grow sublinearly with $T$, that is, for the average payment to vanish. When players' full strategies are observed at each round, we show that constant per-round budgets permit steering. In the more challenging setting where only trajectories through the game tree are observable, we show that steering is impossible with constant per-round budgets in general extensive-form games, but possible in normal-form games or if the per-round budget may itself depend on $T$. We also show how our results can be generalized to the case when the equilibrium is being computed online while steering is happening. We supplement our theoretical positive results with experiments highlighting the efficacy of steering in large games.
View PDF Chat

Testing for Reviewer Anchoring in Peer Review: A Randomized Controlled Trial

2023-01-01
Ryan Liu , Steven Jecmen , Vincent Conitzer +2 more
Peer review frequently follows a process where reviewers first provide initial reviews, authors respond to these reviews, then reviewers update their reviews based on the authors' response. There is mixed … Peer review frequently follows a process where reviewers first provide initial reviews, authors respond to these reviews, then reviewers update their reviews based on the authors' response. There is mixed evidence regarding whether this process is useful, including frequent anecdotal complaints that reviewers insufficiently update their scores. In this study, we aim to investigate whether reviewers anchor to their original scores when updating their reviews, which serves as a potential explanation for the lack of updates in reviewer scores. We design a novel randomized controlled trial to test if reviewers exhibit anchoring. In the experimental condition, participants initially see a flawed version of a paper that is later corrected, while in the control condition, participants only see the correct version. We take various measures to ensure that in the absence of anchoring, reviewers in the experimental group should revise their scores to be identically distributed to the scores from the control group. Furthermore, we construct the reviewed paper to maximize the difference between the flawed and corrected versions, and employ deception to hide the true experiment purpose. Our randomized controlled trial consists of 108 researchers as participants. First, we find that our intervention was successful at creating a difference in perceived paper quality between the flawed and corrected versions: Using a permutation test with the Mann-Whitney U statistic, we find that the experimental group's initial scores are lower than the control group's scores in both the Evaluation category (Vargha-Delaney A=0.64, p=0.0096) and Overall score (A=0.59, p=0.058). Next, we test for anchoring by comparing the experimental group's revised scores with the control group's scores. We find no significant evidence of anchoring in either the Overall (A=0.50, p=0.61) or Evaluation category (A=0.49, p=0.61).

Non-Excludable Bilateral Trade Between Groups

2023-01-01
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 … 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.

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

2022-10-14
Steven Jecmen , Hanrui Zhang , Ryan Liu +3 more
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 … 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 make several contributions towards answering this question. First, we prove that when the set of papers requiring additional review is unknown, a simplified variant of this problem is NP-hard. Second, we empirically show that across several datasets pertaining to real conference data, dividing reviewers between phases/conditions uniformly at random allows an assignment that is nearly as good as the oracle optimal assignment. This uniformly random choice is practical for both the two-phase and conference experiment design settings. Third, we provide explanations of this phenomenon by providing theoretical bounds on the suboptimality of this random strategy under certain natural conditions. From these easily-interpretable conditions, we provide actionable insights to conference program chairs about whether a random reviewer split is suitable for their conference.
View PDF Chat

Efficient Algorithms for Planning with Participation Constraints

2022-07-12
Hanrui Zhang , Yu Cheng , Vincent Conitzer
We consider the problem of planning with participation constraints introduced in[24]. In this problem, a principal chooses actions in a Markov decision process, resulting in separate utilities for the principal … We consider the problem of planning with participation constraints introduced in[24]. In this problem, a principal chooses actions in a Markov decision process, resulting in separate utilities for the principal and the agent. However, the agent can and will choose to end the process whenever his expected onward utility becomes negative. The principal seeks to compute and commit to a policy that maximizes her expected utility, under the constraint that the agent should always want to continue participating. We provide the first polynomial-time exact algorithm for this problem for finite-horizon settings, where previously only an additive ε-approximation algorithm was known. Our approach can also be extended to the (discounted) infinite-horizon case, for which we give an algorithm that runs in time polynomial in the size of the input and log(1/ε), and returns a policy that is optimal up to an additive error of ε.
View PDF Chat

Pacing Equilibrium in First Price Auction Markets

2022-04-06
Vincent Conitzer , Christian Kroer , Debmalya Panigrahi +4 more
Mature internet advertising platforms offer high-level campaign management tools to help advertisers run their campaigns, often abstracting away the intricacies of how each ad is placed and focusing on aggregate … Mature internet advertising platforms offer high-level campaign management tools to help advertisers run their campaigns, often abstracting away the intricacies of how each ad is placed and focusing on aggregate metrics of interest to advertisers. On such platforms, advertisers often participate in auctions through a proxy bidder, so the standard incentive analyses that are common in the literature do not apply directly. In this paper, we take the perspective of a budget management system that surfaces aggregated incentives—instead of individual auctions—and compare first and second price auctions. We show that theory offers surprising endorsement for using a first price auction to sell individual impressions. In particular, first price auctions guarantee uniqueness of the steady-state equilibrium of the budget management system, monotonicity, and other desirable properties, as well as efficient computation through the solution to the well-studied Eisenberg–Gale convex program. Contrary to what one can expect from first price auctions, we show that incentives issues are not a barrier that undermines the system. Using realistic instances generated from data collected at real-world auction platforms, we show that bidders have small regret with respect to their optimal ex post strategy, and they do not have a big incentive to misreport when they can influence equilibria directly by giving inputs strategically. Finally, budget-constrained bidders, who have significant prevalence in real-world platforms, tend to have smaller regrets. Our computations indicate that bidder budgets, pacing multipliers, and regrets all have a positive association in statistical terms. This paper was accepted by Gabriel Weintraub, revenue management and market analytics. Funding: D. Panigrahi was supported in part by the National Science Foundation [Awards CCF 1535972, CCF 1750140, and CCF 1955703]. Supplemental Material: The data files are available at https://doi.org/10.1287/mnsc.2022.4310 .
View PDF Chat

Computational ethics

2022-03-29
Edmond Awad , Sydney Levine , Michael Anderson +7 more
The past 15 years have seen an increased interest in developing ethical machines; manifested in various interdisciplinary research communities (under the umbrella term 'AI ethics'). Less represented in these interdisciplinary … The past 15 years have seen an increased interest in developing ethical machines; manifested in various interdisciplinary research communities (under the umbrella term 'AI ethics'). Less represented in these interdisciplinary efforts is the perspective of cognitive science.We propose a framework – computational ethics – that specifies how the ethical challenges of AI can be addressed better by incorporating the study of how humans make moral decisions.As the driver of this framework, we propose a computational version of reflective equilibrium.The goal of this framework is twofold: (i) to inform the engineering of ethical AI systems, and (ii) to characterize human moral judgment and decision-making in computational terms.Working jointly towards these two goals may prove to be beneficial in making progress on both fronts. Technological advances are enabling roles for machines that present novel ethical challenges. The study of 'AI ethics' has emerged to confront these challenges, and connects perspectives from philosophy, computer science, law, and economics. Less represented in these interdisciplinary efforts is the perspective of cognitive science. We propose a framework – computational ethics – that specifies how the ethical challenges of AI can be partially addressed by incorporating the study of human moral decision-making. The driver of this framework is a computational version of reflective equilibrium (RE), an approach that seeks coherence between considered judgments and governing principles. The framework has two goals: (i) to inform the engineering of ethical AI systems, and (ii) to characterize human moral judgment and decision-making in computational terms. Working jointly towards these two goals will create the opportunity to integrate diverse research questions, bring together multiple academic communities, uncover new interdisciplinary research topics, and shed light on centuries-old philosophical questions. Technological advances are enabling roles for machines that present novel ethical challenges. The study of 'AI ethics' has emerged to confront these challenges, and connects perspectives from philosophy, computer science, law, and economics. Less represented in these interdisciplinary efforts is the perspective of cognitive science. We propose a framework – computational ethics – that specifies how the ethical challenges of AI can be partially addressed by incorporating the study of human moral decision-making. The driver of this framework is a computational version of reflective equilibrium (RE), an approach that seeks coherence between considered judgments and governing principles. The framework has two goals: (i) to inform the engineering of ethical AI systems, and (ii) to characterize human moral judgment and decision-making in computational terms. Working jointly towards these two goals will create the opportunity to integrate diverse research questions, bring together multiple academic communities, uncover new interdisciplinary research topics, and shed light on centuries-old philosophical questions. David Marr set out to describe vision in computational terms by integrating insights and methods from psychology, neuroscience, and engineering [1.Marr D. Vision: A Computational Investigation into the Human Representation and Processing of Visual Information. W.H. Freeman, 1982Google Scholar]. His revolutionary approach to the study of vision offered a model for the field of cognitive science. The key to Marr's innovation was his emphasis on explaining visual perception as an algorithmic (see Glossary) process – a process that transforms one type of information (an input) into another type of information (the output). The goal was to understand the input–output transformation with a sufficiently high degree of precision that it could be captured in mathematical terms. The result of this algorithm-focused pursuit was an account of visual perception that characterized the richness of the human mind in a way that could be programmed into a machine. This approach had two important consequences. The first was that it has become increasingly possible to build machines with a human-like capacity for visual perception. For example, convolutional neural networks (CNNs), the engine underlying most of the recent progress in computer vision, learn internal multi-level representations analogous to the human visual hierarchy [2.Kriegeskorte N. Deep neural networks: a new framework for modeling biological vision and brain information processing.Annu. Rev. Vis. Sci. 2015; 1: 417-446Crossref PubMed Google Scholar]. Given these advances, we now have machines that can detect whether a skin cancer is malignant or benign [3.Esteva A. et al.Dermatologist-level classification of skin cancer with deep neural networks.Nature. 2017; 542: 115-118Crossref PubMed Scopus (54) Google Scholar], can detect street signs in naturalistic settings [4.Zhu Z. et al.Traffic-sign detection and classification in the wild.in: IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2016: 2110-2117Crossref Scopus (403) Google Scholar], and can classify objects into a thousand categories at better than human performance levels [5.Krizhevsky A. et al.ImageNet classification with deep convolutional neural networks.Commun. ACM. 2017; 60: 84-90Crossref Scopus (7838) Google Scholar]. The second was that the mechanisms of human vision were studied and understood in more precise terms than ever before. For example, various aspects of visual perception and decoding (specifically, inference of selected objects) can be understood as a Bayesian inference [6.Zhaoping L. Li Z. Understanding Vision: Theory, Models, and Data. Oxford University Press, 2014Crossref Google Scholar,7.Weiss Y. et al.Motion illusions as optimal percepts.Nat. Neurosci. 2002; 5: 598-604Crossref PubMed Scopus (699) Google Scholar]. Moreover, there was a positive feedback loop between the machine-centric and human-centric research lines. The algorithms developed in studying the cognitive science of human vision were used to program machines that both matched and extended what the human mind is capable of. Conversely, the challenge of trying to program machines with the capacity for vision generated new hypotheses for how vision might work in the mind (and the brain). The key to this success was thinking about vision computationally – that is, in algorithmic terms. Inspired by Marr's success, we propose that a computationally grounded approach could be similarly valuable for the study of ethics [8.Mikhail J. Elements of Moral Cognition: Rawls' Linguistic Analogy and the Cognitive Science of Moral and Legal Judgment. Cambridge University Press, 2011Crossref Scopus (234) Google Scholar]. By analogy to Marr's 'computational vision', we characterize this approach as 'computational ethics'. As we conceive it, computational ethics includes scholarly work that aims to formalize descriptive ethics and normative ethics in algorithmic terms, as well as work that uses this formalization to help to both (i) engineer ethical AI systems, and (ii) better understand human moral decisions and judgments (the relationship between our proposed framework and other interdisciplinary efforts that tackle the challenges of AI ethics is discussed in Box 1).Box 1Relationship to current interdisciplinary effortsFifteen years ago the fields of machine ethics (implementing ethical decision-making in machines) [56.Anderson M. Anderson S.L. Machine Ethics. Cambridge University Press, 2011Crossref Google Scholar,132.Anderson M. Anderson S.L. Guest editors' introduction: machine ethics.IEEE Intell. Syst. 2006; 21: 10-11Crossref Scopus (33) Google Scholar] and roboethics (how humans design, use, and treat robots) [133.Veruggio G. A proposal for a roboethics.in: 1st International Symposium on Roboethics: The Ethics, Social, Humanitarian, and Ecological Aspects of Robotics. Roboethics.org, 2004Google Scholar,134.Tzafestas S.G. Roboethics: A Navigating Overview. Springer, 2015Google Scholar] emerged to bring the perspective of ethics to AI development. Since then 'AI ethics' has emerged as an umbrella term to describe work concerning both AI and ethics. New research directions for AI ethics include algorithmic accountability (the obligation to be able to explain and/or justify algorithmic decisions) [135.Wieringa M. What to account for when accounting for algorithms.in: Hildebrandt M. Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency. Association for Computing Machinery, 2020: 1-18Crossref Scopus (66) Google Scholar], algorithmic transparency (openness about the purpose, structure, and actions of algorithms) [136.Weller A. Transparency: motivations and challenges.in: Samek W. Explainable AI: Interpreting, Explaining and Visualizing Deep Learning. Springer, 2019: 23-40Crossref Scopus (32) Google Scholar], algorithmic fairness/bias (attempts to design algorithms that make fair/unbiased decisions) [137.Mehrabi N. et al.A survey on bias and fairness in machine learning.ACM Comput. Surv. 2019; 54: 1-35Crossref Scopus (87) Google Scholar], and AI for (social) good (ensuring that AI algorithms have a positive impact) [138.Tomašev N. et al.AI for social good: unlocking the opportunity for positive impact.Nat. Commun. 2020; 11: 2468Crossref PubMed Scopus (26) Google Scholar]. Similarly, new multidisciplinary fields of research have been initiated, including responsible AI (RAI; the development of guidelines, regulations, laws, and certifications regarding how AI should be researched, developed, and used) [139.Dignum V. Responsible Artificial Intelligence: How to Develop and Use AI in a Responsible Way. Springer, 2019Crossref Google Scholar], explainable AI (XAI; the development and study of automatically generated explanations for algorithmic decisions) [140.Wachter S. et al.Transparent, explainable, and accountable AI for robotics. Science.Robotics. 2017; 2: eaan6080Crossref Scopus (99) Google Scholar,141.Wachter S. et al.Counterfactual explanations without opening the black box: automated decisions and the GDPR.Harv. J. Law Technol. 2017; 31: 841-887Google Scholar], and machine behavior (the study of machines as a new class of actors with their unique behavioral patterns and ecology) [31.Rahwan I. et al.Machine behaviour.Nature. 2019; 568: 477-486Crossref PubMed Scopus (301) Google Scholar].These fields and communities have already begun to communicate via academic conferences including AIES (Artificial Intelligence, Ethics, and Society), supported by the Association for the Advancement of AI (AAAI) and the Association for Computing Machinery (ACM), and FAT/ML (Fairness, Accountability, and Transparency in Machine Learning), as well as workshops such as FATES (Fairness, Accountability, Transparency, Ethics, and Society on the Web), FACTS-IR (Fairness, Accountability, Confidentiality, Transparency, and Safety in Information Retrieval), and HWB (Handling Web Bias). There are also governmental and global initiatives such as the AI for Good Global Summit, AI for Good initiative, and Partnership on AI. Other organizations – such as the Organization for Economic Co-operation and Development (OECD) AI Policy Observatory, UNESCO, the World Economic Forum, and the Institute of Electrical and Electronics Engineers (IEEE) – have convened a wide range of stakeholders to lay out ethical principles for the development and implementation of AI.Often missing from these pursuits is the perspective of cognitive science that studies how humans (as individuals or as groups) think about, learn, and make moral decisions. The aim of the computational ethics framework is to complement and supplement the work being done in these communities by reviewing the ongoing research and providing a new structure that helps to focus work toward both building ethical machines and better understanding human ethics. Fifteen years ago the fields of machine ethics (implementing ethical decision-making in machines) [56.Anderson M. Anderson S.L. Machine Ethics. Cambridge University Press, 2011Crossref Google Scholar,132.Anderson M. Anderson S.L. Guest editors' introduction: machine ethics.IEEE Intell. Syst. 2006; 21: 10-11Crossref Scopus (33) Google Scholar] and roboethics (how humans design, use, and treat robots) [133.Veruggio G. A proposal for a roboethics.in: 1st International Symposium on Roboethics: The Ethics, Social, Humanitarian, and Ecological Aspects of Robotics. Roboethics.org, 2004Google Scholar,134.Tzafestas S.G. Roboethics: A Navigating Overview. Springer, 2015Google Scholar] emerged to bring the perspective of ethics to AI development. Since then 'AI ethics' has emerged as an umbrella term to describe work concerning both AI and ethics. New research directions for AI ethics include algorithmic accountability (the obligation to be able to explain and/or justify algorithmic decisions) [135.Wieringa M. What to account for when accounting for algorithms.in: Hildebrandt M. Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency. Association for Computing Machinery, 2020: 1-18Crossref Scopus (66) Google Scholar], algorithmic transparency (openness about the purpose, structure, and actions of algorithms) [136.Weller A. Transparency: motivations and challenges.in: Samek W. Explainable AI: Interpreting, Explaining and Visualizing Deep Learning. Springer, 2019: 23-40Crossref Scopus (32) Google Scholar], algorithmic fairness/bias (attempts to design algorithms that make fair/unbiased decisions) [137.Mehrabi N. et al.A survey on bias and fairness in machine learning.ACM Comput. Surv. 2019; 54: 1-35Crossref Scopus (87) Google Scholar], and AI for (social) good (ensuring that AI algorithms have a positive impact) [138.Tomašev N. et al.AI for social good: unlocking the opportunity for positive impact.Nat. Commun. 2020; 11: 2468Crossref PubMed Scopus (26) Google Scholar]. Similarly, new multidisciplinary fields of research have been initiated, including responsible AI (RAI; the development of guidelines, regulations, laws, and certifications regarding how AI should be researched, developed, and used) [139.Dignum V. Responsible Artificial Intelligence: How to Develop and Use AI in a Responsible Way. Springer, 2019Crossref Google Scholar], explainable AI (XAI; the development and study of automatically generated explanations for algorithmic decisions) [140.Wachter S. et al.Transparent, explainable, and accountable AI for robotics. Science.Robotics. 2017; 2: eaan6080Crossref Scopus (99) Google Scholar,141.Wachter S. et al.Counterfactual explanations without opening the black box: automated decisions and the GDPR.Harv. J. Law Technol. 2017; 31: 841-887Google Scholar], and machine behavior (the study of machines as a new class of actors with their unique behavioral patterns and ecology) [31.Rahwan I. et al.Machine behaviour.Nature. 2019; 568: 477-486Crossref PubMed Scopus (301) Google Scholar]. These fields and communities have already begun to communicate via academic conferences including AIES (Artificial Intelligence, Ethics, and Society), supported by the Association for the Advancement of AI (AAAI) and the Association for Computing Machinery (ACM), and FAT/ML (Fairness, Accountability, and Transparency in Machine Learning), as well as workshops such as FATES (Fairness, Accountability, Transparency, Ethics, and Society on the Web), FACTS-IR (Fairness, Accountability, Confidentiality, Transparency, and Safety in Information Retrieval), and HWB (Handling Web Bias). There are also governmental and global initiatives such as the AI for Good Global Summit, AI for Good initiative, and Partnership on AI. Other organizations – such as the Organization for Economic Co-operation and Development (OECD) AI Policy Observatory, UNESCO, the World Economic Forum, and the Institute of Electrical and Electronics Engineers (IEEE) – have convened a wide range of stakeholders to lay out ethical principles for the development and implementation of AI. Often missing from these pursuits is the perspective of cognitive science that studies how humans (as individuals or as groups) think about, learn, and make moral decisions. The aim of the computational ethics framework is to complement and supplement the work being done in these communities by reviewing the ongoing research and providing a new structure that helps to focus work toward both building ethical machines and better understanding human ethics. We first consider how formalizing our normative views and theories of moral cognition can enable progress in engineering ethical AI systems that behave in ways we find morally acceptable [9.Bonnefon J.-F. et al.The moral psychology of AI and the ethical opt-out problem.in: Liao S.M. Ethics of Artificial Intelligence. Oxford University Press, 2020: 109-126Crossref Scopus (9) Google Scholar,10.Russell S. Human Compatible: AI and the Problem of Control. Penguin, UK2019Google Scholar]. Such considerations will yield valuable lessons for machine ethics (Box 2 discusses whether humans should delegate ethics to machines). The following example illustrates the process of developing machine ethics in kidney exchange.Box 2On delegating ethics to machinesShould humans delegate ethics to machines? In opposition to this idea, van Wynsberghe and Robbins propose 'a moratorium on the commercialization of robots claiming to have ethical reasoning skills' [142.van Wynsberghe A. Robbins S. Critiquing the reasons for making artificial moral agents.Sci. Eng. Ethics. 2019; 25: 719-735Crossref PubMed Scopus (44) Google Scholar]. In support of the idea, others have cited several reasons for deploying moral AI. The following considerations are relevant.InevitabilityAdmittedly, moral AI could have unwanted side effects, including abuses and misuses, and these dangers lead critics to oppose the development of moral AI. However, some argue that moral AI is inevitable. Nevertheless, the fact that something is inevitable – like death and taxes – does not make it good. The lesson instead is that people will inevitably develop solutions as needs arise. For example, the global shortage of caregivers in hospitals and nursing homes will lead to more robotic caregivers. Such robots will face moral tradeoffs. If they do less harm and better protect patient autonomy if they are able to reason morally, then there is a reason to try to design robotic caregivers to be moral reasoners [143.Poulsen A. et al.Responses to a critique of artificial moral agents.ArXiv. 2019; (Published online March 17, 2019)https://arxiv.org/abs/1903.07021Google Scholar].TrustAI cannot do much good if the public does not use it, and use requires trust. When AI uses black box methods to instill ethics, this itself undermines trust, which can lead to diminished use and benefits. However, a responsible and transparent development can increase the public's trust in AI, especially if they know that it is sensitive to their rights and other moral concerns [144.Shin D. User perceptions of algorithmic decisions in the personalized AI system: perceptual evaluation of fairness, accountability, transparency, and explainability.J. Broadcast. Electron. Media. 2020; 64: 541-565Crossref Scopus (27) Google Scholar].ComplexityMoral judgment is complex. It is not simply about safety or harm minimization, and includes other factors – including fairness, honesty, autonomy, merit, and roles – that affect what is morally right or wrong. Humans often overlook relevant factors or become confused by complex interactions between conflicting factors. They are also sometimes overcome by emotions, such as dislike of particular groups or fear during military conflicts [145.Arkin R. Governing Lethal Behavior in Autonomous Robots. Chapman and Hall/CRC, 2009Crossref Scopus (300) Google Scholar]. Some researchers hope that sophisticated machines can avoid these problems and then make better moral judgments and decisions than humans. To achieve this goal, robots need to be equipped with broad moral competence for unpredictable problems, through proper and responsible design. However, a potential downside is that over-reliance on moral AI could make humans less likely to develop their own moral reasoning skills [118.Vallor S. Technology and the Virtues: A Philosophical Guide to a Future Worth Wanting. Oxford University Press, 2016Crossref Google Scholar].Of course, all these issues deserve much more careful consideration [146.Vanderelst D. Winfield A. The dark side of ethical robots.in: Furman J. Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society. Association for Computing Machinery, 2018: 317-322Crossref Scopus (11) Google Scholar,147.Cave S. et al.Motivations and risks of machine ethics.Proc. IEEE. 2019; 107: 562-574Crossref Scopus (19) Google Scholar]. It is also crucial to discuss how to govern and regulate moral AI [148.Winfield A.F. et al.Machine ethics: the design and governance of ethical ai and autonomous systems.Proc. IEEE. 2019; 107: 509-517Crossref Scopus (60) Google Scholar,149.Falco G. et al.Governing AI safety through independent audits.Nat. Mach. Intell. 2021; 3: 566-571Crossref Scopus (7) Google Scholar]. Should humans delegate ethics to machines? In opposition to this idea, van Wynsberghe and Robbins propose 'a moratorium on the commercialization of robots claiming to have ethical reasoning skills' [142.van Wynsberghe A. Robbins S. Critiquing the reasons for making artificial moral agents.Sci. Eng. Ethics. 2019; 25: 719-735Crossref PubMed Scopus (44) Google Scholar]. In support of the idea, others have cited several reasons for deploying moral AI. The following considerations are relevant. Inevitability Admittedly, moral AI could have unwanted side effects, including abuses and misuses, and these dangers lead critics to oppose the development of moral AI. However, some argue that moral AI is inevitable. Nevertheless, the fact that something is inevitable – like death and taxes – does not make it good. The lesson instead is that people will inevitably develop solutions as needs arise. For example, the global shortage of caregivers in hospitals and nursing homes will lead to more robotic caregivers. Such robots will face moral tradeoffs. If they do less harm and better protect patient autonomy if they are able to reason morally, then there is a reason to try to design robotic caregivers to be moral reasoners [143.Poulsen A. et al.Responses to a critique of artificial moral agents.ArXiv. 2019; (Published online March 17, 2019)https://arxiv.org/abs/1903.07021Google Scholar]. Trust AI cannot do much good if the public does not use it, and use requires trust. When AI uses black box methods to instill ethics, this itself undermines trust, which can lead to diminished use and benefits. However, a responsible and transparent development can increase the public's trust in AI, especially if they know that it is sensitive to their rights and other moral concerns [144.Shin D. User perceptions of algorithmic decisions in the personalized AI system: perceptual evaluation of fairness, accountability, transparency, and explainability.J. Broadcast. Electron. Media. 2020; 64: 541-565Crossref Scopus (27) Google Scholar]. Complexity Moral judgment is complex. It is not simply about safety or harm minimization, and includes other factors – including fairness, honesty, autonomy, merit, and roles – that affect what is morally right or wrong. Humans often overlook relevant factors or become confused by complex interactions between conflicting factors. They are also sometimes overcome by emotions, such as dislike of particular groups or fear during military conflicts [145.Arkin R. Governing Lethal Behavior in Autonomous Robots. Chapman and Hall/CRC, 2009Crossref Scopus (300) Google Scholar]. Some researchers hope that sophisticated machines can avoid these problems and then make better moral judgments and decisions than humans. To achieve this goal, robots need to be equipped with broad moral competence for unpredictable problems, through proper and responsible design. However, a potential downside is that over-reliance on moral AI could make humans less likely to develop their own moral reasoning skills [118.Vallor S. Technology and the Virtues: A Philosophical Guide to a Future Worth Wanting. Oxford University Press, 2016Crossref Google Scholar]. Of course, all these issues deserve much more careful consideration [146.Vanderelst D. Winfield A. The dark side of ethical robots.in: Furman J. Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society. Association for Computing Machinery, 2018: 317-322Crossref Scopus (11) Google Scholar,147.Cave S. et al.Motivations and risks of machine ethics.Proc. IEEE. 2019; 107: 562-574Crossref Scopus (19) Google Scholar]. It is also crucial to discuss how to govern and regulate moral AI [148.Winfield A.F. et al.Machine ethics: the design and governance of ethical ai and autonomous systems.Proc. IEEE. 2019; 107: 509-517Crossref Scopus (60) Google Scholar,149.Falco G. et al.Governing AI safety through independent audits.Nat. Mach. Intell. 2021; 3: 566-571Crossref Scopus (7) Google Scholar]. Example 1 [kidney exchange]. Thousands of patients are in need of kidney transplants, and thousands of individuals are willing to donate kidneys (sometimes on the condition that kidneys are allocated a certain way). However, kidneys can only be allocated to compatible patients, and there are always more people in need of kidneys than willing donors. How should kidneys be allocated? Can an algorithm help to solve this problem? If so, what is the optimal solution? An initial answer might be: maximize the number of recipients (i.e., matches). However, there are multiple solutions that achieve the maximum number of matches but result in different individuals receiving kidneys. How should we decide among these solutions [11.Roth A.E. et al.Kidney exchange.Q. J. Econ. 2004; 119: 457-488Crossref Scopus (457) Google Scholar, 12.Bertsimas D. et al.Fairness, efficiency, and flexibility in organ allocation for kidney transplantation.Oper. Res. 2013; 61: 73-87Crossref Scopus (42) Google Scholar, 13.Freedman R. et al.Adapting a kidney exchange algorithm to align with human values.Artif. Intell. 2020; 283103261Crossref Scopus (16) Google Scholar]? There are many ways to determine what a fair or justified allocation is and to determine who deserves to get a kidney and who does not. One path forward is to interface with normative ethics and moral psychology and to take inspiration from the factors that have been used by ethicists and by ordinary people when making similar judgments (the question of when and how to integrate the input of these two groups is taken up in the section on normative–descriptive alignment). For the answers to be useful to designing the algorithm, they must be formalized in computational terms. Only following that formalization can algorithmic kidney exchanges be adapted to reflect insights from normative and descriptive human ethics (Box 3 for further discussion).Box 3Extended example – kidney exchangeThis box explores how computational ethics can be used to make progress in a particular ethical challenge: matching kidney donors to compatible patients (example 1).Work relevant to the 'formalize' phase could contribute in several ways. 'Formalizing normative ethics' focuses on representing (perhaps using first-order logic) a set of abstract principles that together form a sound (systematic and consistent) and complete (covering all cases) algorithm. 'Formalizing descriptive ethics' focuses on characterizing (perhaps with computational models) the case-based intuitions of laypersons about which features (e.g., age, critical condition) matter for people when considering different solutions. 'Balancing conflicting values' would formulate this problem as, for example, a combinatorial optimization problem (to maximize the number of recipients, following normative utilitarian views) while adapting weights to reflect the importance of different features (following descriptive preferences for tie breaking), and then applying a computational technique (e.g., an integer program formulation) to solve it.Suppose, as a result, that an algorithm is developed to prioritize patients based on their general health. Although this may seem reasonable at the outset, work relevant to the 'evaluate' phase will help to study the influence of these decisions at the statistical level, and uncover second-order effects on society. For example, the algorithm may end up by discriminating against poorer participants who are likely to have more comorbidities as a result of their economic disadvantage. Work in 'evaluating machine ethical behavior' could use data about patients to evaluate this possibility.Suppose that, upon probing this algorithm with different inputs, we find that patients from poorer socioeconomic backgrounds are indeed being significantly disadvantaged by this algorithm. Moreover, work on 'evaluating human ethical behavior' may uncover how this disadvantage may spill over to human ethical decisions in other domains such as employment (e.g., by disadvantaging job candidates experiencing hindrances in their mental capacity as a consequence of kidney failure). Work under the 'formalize' phase (e.g., 'balancing conflicting values') may then develop technical adaptations to mitigate such bias.Insights about comorbidities may help 'formal descriptive/normative ethics' to realize the considerations implicit in our considered judgments that have not been explicitly articulated. Newly formalized moral principles are then evaluated again, and so on, until formalized moral principles are in c
View PDF Chat

Welfare-Preserving $$\varepsilon $$-BIC to BIC Transformation with Negligible Revenue Loss

2022-01-01
Vincent Conitzer , Zhe Feng , David C. Parkes +1 more
View PDF Chat

A Dataset on Malicious Paper Bidding in Peer Review

2022-01-01
Steven Jecmen , Minji Yoon , Vincent Conitzer +2 more
In conference peer review, reviewers are often asked to provide "bids" on each submitted paper that express their interest in reviewing that paper. A paper assignment algorithm then uses these … In conference peer review, reviewers are often asked to provide "bids" on each submitted paper that express their interest in reviewing that paper. A paper assignment algorithm then uses these bids (along with other data) to compute a high-quality assignment of reviewers to papers. However, this process has been exploited by malicious reviewers who strategically bid in order to unethically manipulate the paper assignment, crucially undermining the peer review process. For example, these reviewers may aim to get assigned to a friend's paper as part of a quid-pro-quo deal. A critical impediment towards creating and evaluating methods to mitigate this issue is the lack of any publicly-available data on malicious paper bidding. In this work, we collect and publicly release a novel dataset to fill this gap, collected from a mock conference activity where participants were instructed to bid either honestly or maliciously. We further provide a descriptive analysis of the bidding behavior, including our categorization of different strategies employed by participants. Finally, we evaluate the ability of each strategy to manipulate the assignment, and also evaluate the performance of some simple algorithms meant to detect malicious bidding. The performance of these detection algorithms can be taken as a baseline for future research on detecting malicious bidding.
View PDF Chat

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

2022-01-01
Scott Emmons , Caspar Oesterheld , Andrew Critch +2 more
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 … 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.
View PDF Chat

Tradeoffs in Preventing Manipulation in Paper Bidding for Reviewer Assignment

2022-01-01
Steven Jecmen , Nihar B. Shah , Fei Fang +1 more
Many conferences rely on paper bidding as a key component of their reviewer assignment procedure. These bids are then taken into account when assigning reviewers to help ensure that each … Many conferences rely on paper bidding as a key component of their reviewer assignment procedure. These bids are then taken into account when assigning reviewers to help ensure that each reviewer is assigned to suitable papers. However, despite the benefits of using bids, reliance on paper bidding can allow malicious reviewers to manipulate the paper assignment for unethical purposes (e.g., getting assigned to a friend's paper). Several different approaches to preventing this manipulation have been proposed and deployed. In this paper, we enumerate certain desirable properties that algorithms for addressing bid manipulation should satisfy. We then offer a high-level analysis of various approaches along with directions for future investigation.

Efficient Algorithms for Planning with Participation Constraints

2022-01-01
Hanrui Zhang , Yu Cheng , Vincent Conitzer
We consider the problem of planning with participation constraints introduced in [Zhang et al., 2022]. In this problem, a principal chooses actions in a Markov decision process, resulting in separate … We consider the problem of planning with participation constraints introduced in [Zhang et al., 2022]. In this problem, a principal chooses actions in a Markov decision process, resulting in separate utilities for the principal and the agent. However, the agent can and will choose to end the process whenever his expected onward utility becomes negative. The principal seeks to compute and commit to a policy that maximizes her expected utility, under the constraint that the agent should always want to continue participating. We provide the first polynomial-time exact algorithm for this problem for finite-horizon settings, where previously only an additive $\varepsilon$-approximation algorithm was known. Our approach can also be extended to the (discounted) infinite-horizon case, for which we give an algorithm that runs in time polynomial in the size of the input and $\log(1/\varepsilon)$, and returns a policy that is optimal up to an additive error of $\varepsilon$.

Similarity-based cooperative equilibrium

2022-01-01
Caspar Oesterheld , Johannes Treutlein , Roger Grosse +2 more
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 … 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.
View PDF Chat

Multiplicative Pacing Equilibria in Auction Markets

2021-12-13
Vincent Conitzer , Christian Kroer , Eric Sodomka +1 more
Budgets play a significant role in ad markets that implement sequential auctions such as those hosted by internet companies. In “Multiplicative Pacing Equilibria in Auction Markets,” the authors look at … Budgets play a significant role in ad markets that implement sequential auctions such as those hosted by internet companies. In “Multiplicative Pacing Equilibria in Auction Markets,” the authors look at pacing in an ad marketplace using the lens of game theory. The goal is understanding how bids must be shaded to maximize advertiser welfare, at equilibrium. Motivated by the real-world auction mechanism, they construct a game where advertisers in the auctions choose a multiplicative factor not larger than 1 to possibly reduce their bids and best respond to the other advertisers. The article studies the theoretical properties of the game such as existence and uniqueness of equilibria, offers an exact algorithm to compute them, connects the game to well-known abstractions such as Fisher markets, and performs a computational study with real-world-inspired instances. The main insights are that the solutions to the studied game can be used to improve the outcomes achieved by a closer-to-reality dynamic pacing algorithm and that buyers do not have an incentive to misreport bids or budgets when there are enough participants in the auction.
View PDF Chat

Ethical Implementation of Artificial Intelligence to Select Embryos in In Vitro Fertilization

2021-07-21
Michael Anis Mihdi Afnan , Cynthia Rudin , Vincent Conitzer +4 more
AI has the potential to revolutionize many areas of healthcare. Radiology, dermatology, and ophthalmology are some of the areas most likely to be impacted in the near future, and they … AI has the potential to revolutionize many areas of healthcare. Radiology, dermatology, and ophthalmology are some of the areas most likely to be impacted in the near future, and they have received significant attention from the broader research community. But AI techniques are now also starting to be used in in vitro fertilization (IVF), in particular for selecting which embryos to transfer to the woman. The contribution of AI to IVF is potentially significant, but must be done carefully and transparently, as the ethical issues are significant, in part because this field involves creating new people. We first give a brief introduction to IVF and review the use of AI for embryo selection. We discuss concerns with the interpretation of the reported results from scientific and practical perspectives. We then consider the broader ethical issues involved. We discuss in detail the problems that result from the use of black-box methods in this context and advocate strongly for the use of interpretable models. Importantly, there have been no published trials of clinical effectiveness, a problem in both the AI and IVF communities, and we therefore argue that clinical implementation at this point would be premature. Finally, we discuss ways for the broader AI community to become involved to ensure scientifically sound and ethically responsible development of AI in IVF.
View PDF Chat

Classification with Strategically Withheld Data

2021-05-18
A. Krishnaswamy , Haoming Li , David B. Rein +2 more
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 … 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-the-box 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 real-world data sets, and present insights into their relative performance in different settings.
View PDF Chat

Automated Mechanism Design for Classification with Partial Verification

2021-05-18
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 … 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 the notion of 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 mechanisms design with partial verification.
View PDF Chat

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

2021-04-29
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 … 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 these 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.

Automated Dynamic Mechanism Design

2021-01-01
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 … 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. 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. Moreover, we show that memoryless mechanisms do not provide a good solution for our problem, in terms of both optimality and computational tractability. These results paint a relatively complete picture for automated dynamic mechanism design in unstructured environments. Finally, 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.

Automated Mechanism Design for Classification with Partial Verification

2021-01-01
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 … 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.
View PDF Chat
Coauthor Papers Together
Tüomas Sandholm 29
Caspar Oesterheld 15
Rupert Freeman 11
Hanrui Zhang 10
Jana Schaich Borg 9
Walter Sinnott‐Armstrong 9
Emanuel Tewolde 8
Fei Fang 8
Steven Jecmen 8
Nihar B. Shah 8
Eric Sodomka 7
Markus Brill 6
John P. Dickerson 6
Vojtěch Kovařík 5
Mingyu Guo 5
Toby Walsh 5
Yu Cheng 5
Christian Kroer 5
Nicolás E. Stier‐Moses 5
Lok-Hei Chan 4
Ryan Liu 4
Paul W. Goldberg 4
Nisarg Shah 4
Krzysztof R. Apt 4
Brian Hu Zhang 4
Lirong Xia 4
Evangelos Markakis 4
David B. Rein 3
Jérôme Lang 3
Ioannis Anagnostides 3
S. Jakobsen 3
Yixuan Even Xu 3
Haoming Li 3
Dmytro Korzhyk 3
Edith Elkind 3
David C. Parkes 3
A. Krishnaswamy 3
Rachel Freedman 3
Ratip Emin Berker 3
Duncan C. McElfresh 3
Kenzie Doyle 3
Hanrui Zhang 3
Haris Aziz 3
Andrea Celli 2
Gabriele Farina 2
Troels Bjerre Sørensen 2
Andreas Haupt 2
Stephen McAleer 2
Jakob Foerster 2
Scott Emmons 2

Settling the complexity of computing two-player Nash equilibria

2009-05-01
Xi Chen , Xiaotie Deng , Shang‐Hua Teng
We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class PPAD (Polynomial Parity Argument, Directed version) introduced by Papadimitriou … We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class PPAD (Polynomial Parity Argument, Directed version) introduced by Papadimitriou in 1991. Our result, building upon the work of Daskalakis et al. [2006a] on the complexity of four-player Nash equilibria, settles a long standing open problem in algorithmic game theory. It also serves as a starting point for a series of results concerning the complexity of two-player Nash equilibria. In particular, we prove the following theorems: —Bimatrix does not have a fully polynomial-time approximation scheme unless every problem in PPAD is solvable in polynomial time. —The smoothed complexity of the classic Lemke-Howson algorithm and, in fact, of any algorithm for Bimatrix is not polynomial unless every problem in PPAD is solvable in randomized polynomial time. Our results also have a complexity implication in mathematical economics: —Arrow-Debreu market equilibria are PPAD -hard to compute.
View PDF Chat

Introduction to Algorithms

1991-09-01
V. J. Rayward‐Smith , Thomas H. Cormen , Charles E. Leiserson +1 more

Determining Possible and Necessary Winners Given Partial Orders

2011-05-17
Lirong Xia , Vincent Conitzer
Usually a voting rule requires agents to give their preferences as linear orders. However, in some cases it is impractical for an agent to give a linear order over all … Usually a voting rule requires agents to give their preferences as linear orders. However, in some cases it is impractical for an agent to give a linear order over all the alternatives. It has been suggested to let agents submit partial orders instead. Then, given a voting rule, a profile of partial orders, and an alternative (candidate) c, two important questions arise: first, is it still possible for c to win, and second, is c guaranteed to win? These are the possible winner and necessary winner problems, respectively. Each of these two problems is further divided into two sub-problems: determining whether c is a unique winner (that is, c is the only winner), or determining whether c is a co-winner (that is, c is in the set of winners). We consider the setting where the number of alternatives is unbounded and the votes are unweighted. We completely characterize the complexity of possible/necessary winner problems for the following common voting rules: a class of positional scoring rules (including Borda), Copeland, maximin, Bucklin, ranked pairs, voting trees, and plurality with runoff.
View PDF Chat

Groves' Scheme on Restricted Domains

1979-09-01
Bengt Holmström
It is proved that Groves’ scheme is unique on restricted domains which are smoothly connected, in particular convex domains. This generalizes earlier uniqueness results by Green and Laffont and Walker. … It is proved that Groves’ scheme is unique on restricted domains which are smoothly connected, in particular convex domains. This generalizes earlier uniqueness results by Green and Laffont and Walker. An example shows that uniqueness may be lost if the domain is not smoothly connected.

Graphical Models for Game Theory

2013-01-01
Michael Kearns , Michael L. Littman , Satinder Singh
In this work, we introduce graphical modelsfor multi-player game theory, and give powerful algorithms for computing their Nash equilibria in certain cases. An n-player game is given by an undirected … In this work, we introduce graphical modelsfor multi-player game theory, and give powerful algorithms for computing their Nash equilibria in certain cases. An n-player game is given by an undirected graph on n nodes and a set of n local matrices. The interpretation is that the payoff to player i is determined entirely by the actions of player i and his neighbors in the graph, and thus the payoff matrix to player i is indexed only by these players. We thus view the global n-player game as being composed of interacting local games, each involving many fewer players. Each player's action may have global impact, but it occurs through the propagation of local influences.Our main technical result is an efficient algorithm for computing Nash equilibria when the underlying graph is a tree (or can be turned into a tree with few node mergings). The algorithm runs in time polynomial in the size of the representation (the graph and theassociated local game matrices), and comes in two related but distinct flavors. The first version involves an approximation step, and computes a representation of all approximate Nash equilibria (of which there may be an exponential number in general). The second version allows the exact computation of Nash equilibria at the expense of weakened complexity bounds. The algorithm requires only local message-passing between nodes (and thus can be implemented by the players themselves in a distributed manner). Despite an analogy to inference in Bayes nets that we develop, the analysis of our algorithm is more involved than that for the polytree algorithm in, owing partially to the fact that we must either compute, or select from, an exponential number of potential solutions. We discuss a number of extensions, such as the computation of equilibria with desirable global properties (e.g. maximizing global return), and directions for further research.

Complexity of Manipulating Elections with Few Candidates

2002-01-01
Vincent Conitzer , Tüomas 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 … 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. Especially among computational agents, it is reasonable to measure this hardness by computational complexity. Some earlier work has been done in this area, but it was assumed that the number of voters and candidates is unbounded. We derive hardness results for practical multiagent settings where the number of candidates is small but the number of voters can be large. We show that with complete information about the others' votes, individual manipulation is easy, and coalitional manipulation is easy with unweighted voters. However, constructive coalitional manipulation with weighted voters is intractable for all of the voting protocols under study, except for the nonrandomized Cup. Destructive manipulation tends to be easier. Randomizing over instantiations of the protocols (such as schedules of the Cup protocol) can be used to make manipulation hard. Finally, we show that under weak assumptions, if weighted coalitional manipulation with complete information about the others' votes is hard in some voting protocol, then individual and unweighted manipulation is hard when there is uncertainty about the others' votes.

Complexity of mechanism design

2002-08-01
Vincent Conitzer , Tüomas 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 … 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 dominantstrategy 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 the agents face additional uncertainty. This comes at no loss, and in some cases at a gain, in the (social) objective.

Universal Voting Protocol Tweaks to Make Manipulation Hard

2003-07-07
Vincent Conitzer , Tüomas Sandholm
Voting is a general method for preference aggregation in multiagent settings, but seminal results have shown that all (nondictatorial) voting protocols are manipulable. One could try to avoid manipulation by … Voting is a general method for preference aggregation in multiagent settings, but seminal results have shown that all (nondictatorial) voting protocols are manipulable. One could try to avoid manipulation 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 existing 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 protocols become NP-hard, #P-hard, or PSPACE-hard to manipulate, depending on whether the schedule 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 conditions on the protocols for this tweak to introduce the hardness, and show that the most common voting protocols satisfy those conditions. These are the first results in voting settings where manipulation is in a higher complexity class than NP (presuming PSPACE $\neq$ NP).

Toward case-based preference elicitation: similarity measures on preference structures

1998-07-24
Vu Ha , Peter Haddawy
While decision theory provides an appealing normative framework for representing rich preference structures, eliciting utility or value functions typically incurs a large cost. For many applications involving interactive systems this … While decision theory provides an appealing normative framework for representing rich preference structures, eliciting utility or value functions typically incurs a large cost. For many applications involving interactive systems this overhead precludes the use of formal decision-theoretic models of preference. Instead of performing elicitation in a vacuum, it would be useful if we could augment directly elicited preferences with some appropriate default information. In this paper we propose a case-based approach to alleviating the preference elicitation bottleneck. Assuming the existence of a population of users from whom we have elicited complete or incomplete preference structures, we propose eliciting the preferences of a new user interactively and incrementally, using the closest existing preference structures as potential defaults. Since a notion of closeness demands a measure of distance among preference structures, this paper takes the first step of studying various distance measures over fully and partially specified preference structures. We explore the use of Euclidean distance, Spearman's footrule, and define a new measure, the probabilistic distance. We provide computational techniques for all three measures.

Dichotomy for voting systems

2006-10-18
Edith Hemaspaandra , Lane A. Hemaspaandra
View PDF Chat

The complexity of computing the permanent

1979-01-01
Leslie G. Valiant

Paper Matching with Local Fairness Constraints

2019-07-25
Ari Kobren , Barna Saha , Andrew McCallum
Automatically matching reviewers to papers is a crucial step of the peer review process for venues receiving thousands of submissions. Unfortunately, common paper matching algorithms often construct matchings suffering from … Automatically matching reviewers to papers is a crucial step of the peer review process for venues receiving thousands of submissions. Unfortunately, common paper matching algorithms often construct matchings suffering from two critical problems: (1) the group of reviewers assigned to a paper do not collectively possess sufficient expertise, and (2) reviewer workloads are highly skewed. In this paper, we propose a novel local fairness formulation of paper matching that directly addresses both of these issues. Since optimizing our formulation is not always tractable, we introduce two new algorithms, FairIR and FairFlow, for computing fair matchings that approximately optimize the new formulation. FairIR solves a relaxation of the local fairness formulation and then employs a rounding technique to construct a valid matching that provably maximizes the objective and only compromises on fairness with respect to reviewer loads and papers by a small constant. In contrast, FairFlow is not provably guaranteed to produce fair matchings, however it can be 2x as efficient as FairIR and an order of magnitude faster than matching algorithms that directly optimize for fairness. Empirically, we demonstrate that both FairIR and FairFlow improve fairness over standard matching algorithms on real conference data. Moreover, in comparison to state-of-the-art matching algorithms that optimize for fairness only, FairIR achieves higher objective scores, FairFlow achieves competitive fairness, and both are capable of more evenly allocating reviewers.
View PDF Chat

Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and Uniqueness

2011-06-21
Dmytro Korzhyk , Zhimin Yin , Christopher Kiekintveld +2 more
There has been significant recent interest in game-theoretic approaches to security, with much of the recent research focused on utilizing the leader-follower Stackelberg game model. Among the major applications are … There has been significant recent interest in game-theoretic approaches to security, with much of the recent research focused on utilizing the leader-follower Stackelberg game model. Among the major applications are the ARMOR program deployed at LAX Airport and the IRIS program in use by the US Federal Air Marshals (FAMS). The foundational assumption for using Stackelberg games is that security forces (leaders), acting first, commit to a randomized strategy; while their adversaries (followers) choose their best response after surveillance of this randomized strategy. Yet, in many situations, a leader may face uncertainty about the follower's surveillance capability. Previous work fails to address how a leader should compute her strategy given such uncertainty. We provide five contributions in the context of a general class of security games. First, we show that the Nash equilibria in security games are interchangeable, thus alleviating the equilibrium selection problem. Second, under a natural restriction on security games, any Stackelberg strategy is also a Nash equilibrium strategy; and furthermore, the solution is unique in a class of security games of which ARMOR is a key exemplar. Third, when faced with a follower that can attack multiple targets, many of these properties no longer hold. Fourth, we show experimentally that in most (but not all) games where the restriction does not hold, the Stackelberg strategy is still a Nash equilibrium strategy, but this is no longer true when the attacker can attack multiple targets. Finally, as a possible direction for future research, we propose an extensive-form game model that makes the defender's uncertainty about the attacker's ability to observe explicit.
View PDF Chat

Towards a dichotomy for the Possible Winner problem in elections based on scoring rules

2010-04-23
Nadja Betzler , Britta Dorn
View PDF Chat

Uncovering Latent Biases in Text: Method and Application to Peer Review

2021-05-18
Emaad Manzoor , Nihar B. Shah
Quantifying systematic disparities in numerical quantities such as employment rates and wages between population subgroups provides compelling evidence for the existence of societal biases. However, biases in the text written … Quantifying systematic disparities in numerical quantities such as employment rates and wages between population subgroups provides compelling evidence for the existence of societal biases. However, biases in the text written for members of different subgroups (such as in recommendation letters for male and non-male candidates), though widely reported anecdotally, remain challenging to quantify. In this work, we introduce a novel framework to quantify bias in text caused by the visibility of subgroup membership indicators. We develop a nonparametric estimation and inference procedure to estimate this bias. We then formalize an identification strategy to causally link the estimated bias to the visibility of subgroup membership indicators, provided observations from time periods both before and after an identity-hiding policy change. We identify an application wherein “ground truth” bias can be inferred to evaluate our framework, instead of relying on synthetic or secondary data. Specifically, we apply our framework to quantify biases in the text of peer reviews from a reputed machine-learning conference before and after the conference adopted a double-blind reviewing policy. We show evidence of biases in the review ratings that serves as “ground truth”, and show that our proposed framework accurately detects the presence (and absence) of these biases from the review text without having access to the review ratings.
View PDF Chat

Exact analysis of Dodgson elections

1997-11-01
Edith Hemaspaandra , Lane A. Hemaspaandra , Jörg Rothe
In 1876, Lewis Carroll proposed a voting system in which the winner is the candidate who with the fewest changes in voters' preferences becomes a Condorcet winner—a candidate who beats … In 1876, Lewis Carroll proposed a voting system in which the winner is the candidate who with the fewest changes in voters' preferences becomes a Condorcet winner—a candidate who beats all other candidates in pairwise majority-rule elections. Bartholdi, Tovey, and Trick provided a lower bound—NP-hardness—on the computational complexity of determining the election winner in Carroll's system. We provide a stronger lower bound and an upper bound that matches our lower bound. In particular, determining the winner in Carroll's system is complete for parallel access to NP, that is, it is complete for Theta_ 2 p for which it becomes the most natural complete problem known. It follows that determining the winner in Carroll's elections is not NP-complete unless the polynomial hierarchy collapses.
View PDF Chat

Exact Complexity of the Winner Problem for Young Elections

2003-02-07
Jörg Rothe , Holger Spakowski , Jörg Vogel

Convex Program Duality, Fisher Markets, and Nash Social Welfare

2017-06-20
Richard Cole , Nikhil R. Devanur , Vasilis Gkatzelis +4 more
No abstract available. No abstract available.
View PDF Chat

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

2003-01-01
Vincent Conitzer , Jérôme Lang , Tüomas 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 … 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.
View PDF Chat

On Revenue Maximization in Second-Price Ad Auctions

2009-01-01
Yossi Azar , Benjamin Birnbaum , Anna R. Karlin +1 more

Structure in Dichotomous Preferences

2015-05-02
Edith Elkind , Martin Lackner
Many hard computational social choice problems are known to become tractable when voters' preferences belong to a restricted domain, such as those of single-peaked or single-crossing preferences. However, to date, … Many hard computational social choice problems are known to become tractable when voters' preferences belong to a restricted domain, such as those of single-peaked or single-crossing preferences. However, to date, all algorithmic results of this type have been obtained for the setting where each voter's preference list is a total order of candidates. The goal of this paper is to extend this line of research to the setting where voters' preferences are dichotomous, i.e., each voter approves a subset of candidates and disapproves the remaining candidates. We propose several analogues of the notions of single-peaked and single-crossing preferences for dichotomous profiles and investigate the relationships among them. We then demonstrate that for some of these notions the respective restricted domains admit efficient algorithms for computationally hard approval-based multi-winner rules.

A framework for optimizing paper matching

2011-07-14
Laurent Charlin , Richard S. Zemel , Craig Boutilier
At the heart of many scientific conferences is the problem of matching submitted papers to suitable reviewers. Arriving at a good assignment is a major and important challenge for any … At the heart of many scientific conferences is the problem of matching submitted papers to suitable reviewers. Arriving at a good assignment is a major and important challenge for any conference organizer. In this paper we propose a framework to optimize paper-to-reviewer assignments. Our framework uses suitability scores to measure pairwise affinity between papers and reviewers. We show how learning can be used to infer suitability scores from a small set of provided scores, thereby reducing the burden on reviewers and organizers. We frame the assignment problem as an integer program and propose several variations for the paper-to-reviewer matching domain. We also explore how learning and matching interact. Experiments on two conference data sets examine the performance of several learning methods as well as the effectiveness of the matching formulations.

Strategic Classification

2016-01-05
Moritz Hardt , Nimrod Megiddo , Christos H. Papadimitriou +1 more
Machine learning relies on the assumption that unseen test instances of a classification problem follow the same distribution as observed training data. However, this principle can break down when machine … Machine learning relies on the assumption that unseen test instances of a classification problem follow the same distribution as observed training data. However, this principle can break down when machine learning is used to make important decisions about the welfare (employment, education, health) of strategic individuals. Knowing information about the classifier, such individuals may manipulate their attributes in order to obtain a better classification outcome. As a result of this behavior -- often referred to as gaming -- the performance of the classifier may deteriorate sharply. Indeed, gaming is a well-known obstacle for using machine learning methods in practice; in financial policy-making, the problem is widely known as Goodhart's law. In this paper, we formalize the problem, and pursue algorithms for learning classifiers that are robust to gaming.
View PDF Chat

Strategyproof linear regression in high dimensions

2019-05-07
Yiling Chen , Chara Podimata , Ariel D. Procaccia +1 more
In this letter, we outline some of the results from our recent work, which is part of an emerging line of research at the intersection of machine learning and mechanism … In this letter, we outline some of the results from our recent work, which is part of an emerging line of research at the intersection of machine learning and mechanism design aiming to avoid noise in training data by correctly aligning the incentives of data sources. Specifically, we focus on the ubiquitous problem of linear regression, where strategyproof mechanisms have previously been identified in two dimensions. In our setting, agents have single-peaked preferences and can manipulate only their response variables. Our main contribution is the discovery of a family of group strategyproof linear regression mechanisms in any number of dimensions, which we call generalized resistant hyperplane mechanisms. The game-theoretic properties of these mechanisms --- and, in fact, their very existence --- are established through a connection to a discrete version of the Ham Sandwich Theorem.
View PDF Chat

On the NP-completeness of finding an optimal strategy in games with common payoffs

2001-09-01
Francis C. Chu , Joseph Y. Halpern

Complexity Results about Nash Equilibria

2002-01-01
Vincent Conitzer , Tüomas Sandholm
Noncooperative game theory provides a normative framework for analyzing strategic interactions. However, for the toolbox to be operational, the solutions it defines will have to be computed. In this paper, … Noncooperative game theory provides a normative framework for analyzing strategic interactions. However, for the toolbox to be operational, the solutions it defines will have to be computed. In this paper, we provide a single reduction that 1) demonstrates NP-hardness of determining whether Nash equilibria with certain natural properties exist, and 2) demonstrates the #P-hardness of counting Nash equilibria (or connected sets of Nash equilibria). We also show that 3) determining whether a pure-strategy Bayes-Nash equilibrium exists is NP-hard, and that 4) determining whether a pure-strategy Nash equilibrium exists in a stochastic (Markov) game is PSPACE-hard even if the game is invisible (this remains NP-hard if the game is finite). All of our hardness results hold even if there are only two players and the game is symmetric. Keywords: Nash equilibrium; game theory; computational complexity; noncooperative game theory; normal form game; stochastic game; Markov game; Bayes-Nash equilibrium; multiagent systems.

Estimating Approximate Incentive Compatibility

2019-06-17
Maria-Florina Balcan , Tüomas Sandholm , Ellen Vitercik
In practice, most mechanisms for selling, buying, matching, voting, and so on are not incentive compatible. We present techniques for estimating how far a mechanism is from incentive compatible. Given … In practice, most mechanisms for selling, buying, matching, voting, and so on are not incentive compatible. We present techniques for estimating how far a mechanism is from incentive compatible. Given samples from the agents' type distribution, we show how to estimate the extent to which an agent can improve his utility by misreporting his type. We do so by first measuring the maximum utility an agent can gain by misreporting his type on average over the samples, assuming his true and reported types are from a finite subset---which our technique constructs---of the type space. The challenge is that by measuring utility gains over a finite subset of the type space, we might miss pairs of types t and t' where an agent with type t can greatly improve his utility by reporting the type t'. Our technique discretizes the type space by constructing a learning-theoretic cover in a higher-dimensional space. The key technical contribution is proving that the maximum utility gain over this finite subset nearly matches the maximum utility gain overall, despite the volatility of the utility functions we study. We apply our tools to the single-item and combinatorial first-price auctions, generalized second-price auction, discriminatory auction, uniform-price auction, and second-price auction with spiteful bidders. To our knowledge, these are the first guarantees for estimating approximate incentive compatibility from the mechanism designer's perspective.
View PDF Chat

Strategyproof Linear Regression in High Dimensions

2018-06-11
Yiling Chen , Chara Podimata , Ariel D. Procaccia +1 more
This paper is part of an emerging line of work at the intersection of machine learning and mechanism design, which aims to avoid noise in training data by correctly aligning … This paper is part of an emerging line of work at the intersection of machine learning and mechanism design, which aims to avoid noise in training data by correctly aligning the incentives of data sources. Specifically, we focus on the ubiquitous problem of linear regression, where strategyproof mechanisms have previously been identified in two dimensions. In our setting, agents have single-peaked preferences and can manipulate only their response variables. Our main contribution is the discovery of a family of group strategyproof linear regression mechanisms in any number of dimensions, which we call generalized resistant hyperplane mechanisms. The game-theoretic properties of these mechanisms --- and, in fact, their very existence --- are established through a connection to a discrete version of the Ham Sandwich Theorem.
View PDF Chat

The social dilemma of autonomous vehicles

2016-06-24
Jean‐François Bonnefon , Azim Shariff , Iyad Rahwan
Autonomous vehicles (AVs) should reduce traffic accidents, but they will sometimes have to choose between two evils, such as running over pedestrians or sacrificing themselves and their passenger to save … Autonomous vehicles (AVs) should reduce traffic accidents, but they will sometimes have to choose between two evils, such as running over pedestrians or sacrificing themselves and their passenger to save the pedestrians. Defining the algorithms that will help AVs make these moral decisions is a formidable challenge. We found that participants in six Amazon Mechanical Turk studies approved of utilitarian AVs (that is, AVs that sacrifice their passengers for the greater good) and would like others to buy them, but they would themselves prefer to ride in AVs that protect their passengers at all costs. The study participants disapprove of enforcing utilitarian regulations for AVs and would be less willing to buy such an AV. Accordingly, regulating for utilitarian algorithms may paradoxically increase casualties by postponing the adoption of a safer technology.
View PDF Chat

Position-Indexed Formulations for Kidney Exchange

2016-07-21
John P. Dickerson , David F. Manlove , Benjamin Plaut +2 more
A kidney exchange is an organized barter market where patients in need of a kidney swap willing but incompatible donors. Determining an optimal set of exchanges is theoretically and empirically … A kidney exchange is an organized barter market where patients in need of a kidney swap willing but incompatible donors. Determining an optimal set of exchanges is theoretically and empirically hard. Traditionally, exchanges took place in cycles, with each participating patient-donor pair both giving and receiving a kidney. The recent introduction of chains, where a donor without a paired patient triggers a sequence of donations without requiring a kidney in return, increased the efficacy of fielded kidney exchanges---while also dramatically raising the empirical computational hardness of clearing the market in practice. While chains can be quite long, unbounded-length chains are not desirable: planned donations can fail before transplant for a variety of reasons, and the failure of a single donation causes the rest of that chain to fail, so parallel shorter chains are better in practice.
View PDF Chat

Clinching auctions with online supply

2015-12-18
Gagan Goel , Vahab Mirrokni , Renato Paes Leme
View PDF Chat

Mathematics without Numbers

1993-11-25
Geoffrey Hellman
Abstract Develops a structuralist understanding of mathematics, as an alternative to set‐ or type‐theoretic foundations, that respects classical mathematical truth while minimizing Platonist commitments to abstract entities. Modal logic is … Abstract Develops a structuralist understanding of mathematics, as an alternative to set‐ or type‐theoretic foundations, that respects classical mathematical truth while minimizing Platonist commitments to abstract entities. Modal logic is combined with notions of part/whole (mereology) enabling a systematic interpretation of ordinary mathematical statements as asserting what would be the case in any (suitable) structure there (logically) might be, e.g. for number theory, functional analysis, algebra, pure geometry, etc. Structures are understood as comprising objects, whatever their nature, standing in suitable relations as given by axioms or defining conditions in mathematics proper. The characterization of structures is aided by the addition of plural quantifiers, e.g. ‘Any objects of sort F’ corresponding to arbitrary collections of Fs, achieving the expressive power of second‐order logic, hence a full logic of relations. (See the author's ‘Structuralism without Structures’, Philosophia Mathematica4 (1996): 100–123.) Claims of absolute existence of structures are replaced by claims of (logical) possibility of enough structurally interrelated objects (modal‐existence postulates). The vast bulk of ordinary mathematics, and scientific applications, can thus be recovered on the basis of the possibility of a countable infinity of atoms. As applied to set theory itself, these ideas lead to a ‘many worlds’—– as opposed to the standard ‘fixed universe’—view, inspired by Zermelo (1930), respecting the unrestricted, indefinite extendability of models of the Zermelo–Fraenkel axioms. Natural motivation for (‘small’) large cardinal axioms is thus provided. In sum, the vast bulk of abstract mathematics is respected as objective, while literal reference to abstracta and related problems with Platonism are eliminated.

Online Stochastic Matching: Beating 1-1/e

2009-10-01
Jon Feldman , Aranyak Mehta , Vahab Mirrokni +1 more
We study the online stochastic bipartite matching problem, in a form motivated by display ad allocation on the Internet. In the online, but adversarial case, the celebrated result of Karp, … We study the online stochastic bipartite matching problem, in a form motivated by display ad allocation on the Internet. In the online, but adversarial case, the celebrated result of Karp, Vazirani and Vazirani gives an approximation ratio of 1- 1/e ¿ 0.632, a very familiar bound that holds for many online problems; further, the bound is tight in this case. In the online, stochastic case when nodes are drawn repeatedly from a known distribution, the greedy algorithm matches this approximation ratio, but still, no algorithm is known that beats the 1 - 1/e bound. Our main result is a 0.67-approximation online algorithm for stochastic bipartite matching, breaking this 1 - ¿ barrier. Furthermore, we show that no online algorithm can produce a 1 - ¿ approximation for an arbitrarily small e for this problem. Our algorithms are based on computing an optimal offline solution to the expected instance, and using this solution as a guideline in the process of online allocation. We employ a novel application of the idea of the power of two choices from load balancing: we compute two disjoint solutions to the expected instance, and use both of them in the online algorithm in a prescribed preference order. To identify these two disjoint solutions, we solve a max flow problem in a boosted flow graph, and then carefully decompose this maximum flow to two edge-disjoint (near-)matchings. In addition to guiding the online decision making, these two offline solutions are used to characterize an upper bound for the optimum in any scenario. This is done by identifying a cut whose value we can bound under the arrival distribution. At the end, we discuss extensions of our results to more general bipartite allocations that are important in a display ad application.
View PDF Chat

Approximation of barter exchanges with cycle length constraints

2016-01-01
Suiqian Luo , Pingzhong Tang , Chenggang Wu +1 more
We explore the clearing problem in the barter exchange market. The problem, described in the terminology of graph theory, is to find a set of vertex-disjoint, length-restricted cycles that maximize … We explore the clearing problem in the barter exchange market. The problem, described in the terminology of graph theory, is to find a set of vertex-disjoint, length-restricted cycles that maximize the total weight in a weighted digraph. The problem has previously been shown to be NP-hard. We advance the understanding of this problem by the following contributions. We prove three constant inapproximability results for this problem. For the weighted graphs, we prove that it is NP-hard to approximate the clearing problem within a factor of 14/13 under general length constraints and within a factor of 434/433 when the cycle length is not longer than 3. For the unweighted graphs, we prove that this problem is NP-hard to approximate within a factor of 698/697. For the unweighted graphs when the cycle length is not longer than 3, we design and implement two simple and practical algorithms. Experiments on simulated data suggest that these algorithms yield excellent performances.

Design and Analysis of the NIPS 2016 Review Process

2017-01-01
Nihar B. Shah , Behzad Tabibian , Krikamol Muandet +2 more
Neural Information Processing Systems (NIPS) is a top-tier annual conference in machine learning. The 2016 edition of the conference comprised more than 2,400 paper submissions, 3,000 reviewers, and 8,000 attendees. … Neural Information Processing Systems (NIPS) is a top-tier annual conference in machine learning. The 2016 edition of the conference comprised more than 2,400 paper submissions, 3,000 reviewers, and 8,000 attendees. This represents a growth of nearly 40% in terms of submissions, 96% in terms of reviewers, and over 100% in terms of attendees as compared to the previous year. The massive scale as well as rapid growth of the conference calls for a thorough quality assessment of the peer-review process and novel means of improvement. In this paper, we analyze several aspects of the data collected during the review process, including an experiment investigating the efficacy of collecting ordinal rankings from reviewers. Our goal is to check the soundness of the review process, and provide insights that may be useful in the design of the review process of subsequent conferences.
View PDF Chat

Budget optimization in search-based advertising auctions

2007-06-11
Jon Feldman , S. Muthukrishnan , Martin Pál +1 more
Internet search companies sell advertisement slots based on users' search queries via an auction. While there has been previous work onthe auction process and its game-theoretic aspects, most of it … Internet search companies sell advertisement slots based on users' search queries via an auction. While there has been previous work onthe auction process and its game-theoretic aspects, most of it focuses on the Internet company. In this work, we focus on the advertisers, who must solve a complex optimization problem to decide how to place bids on keywords to maximize their return (the number of user clicks on their ads) for a given budget. We model the entire process and study this budget optimization problem. While most variants are NP-hard, we show, perhaps surprisingly, that simply randomizing between two uniform strategies that bid equally on all the keywordsworks well. More precisely, this strategy gets at least a 1-1/e fraction of the maximum clicks possible. As our preliminary experiments show, such uniform strategies are likely to be practical. We also present inapproximability results, and optimal algorithms for variants of the budget optimization problem.
View PDF Chat

Polyhedral Clinching Auctions and the AdWords Polytope

2015-06-30
Gagan Goel , Vahab Mirrokni , Renato Paes Leme
A central issue in applying auction theory in practice is the problem of dealing with budget-constrained agents. A desirable goal in practice is to design incentive compatible, individually rational, and … A central issue in applying auction theory in practice is the problem of dealing with budget-constrained agents. A desirable goal in practice is to design incentive compatible, individually rational, and Pareto optimal auctions while respecting the budget constraints. Achieving this goal is particularly challenging in the presence of nontrivial combinatorial constraints over the set of feasible allocations. Toward this goal and motivated by AdWords auctions, we present an auction for polymatroidal environments satisfying these properties. Our auction employs a novel clinching technique with a clean geometric description and only needs an oracle access to the submodular function defining the polymatroid. As a result, this auction not only simplifies and generalizes all previous results, it applies to several new applications including AdWords Auctions, bandwidth markets, and video on demand. In particular, our characterization of the AdWords auction as polymatroidal constraints might be of independent interest. This allows us to design the first mechanism for Ad Auctions taking into account simultaneously budgets, multiple keywords and multiple slots. We show that it is impossible to extend this result to generic polyhedral constraints. This also implies an impossibility result for multiunit auctions with decreasing marginal utilities in the presence of budget constraints.
View PDF Chat

Complexity of combinatorial market makers

2008-07-08
Yiling Chen , Lance Fortnow , Nicolas Lambert +2 more
We analyze the computational complexity of market maker pricing algorithms for combinatorial prediction markets. We focus on Hanson's popular logarithmic market scoring rule market maker (LMSR). Our goal is to … We analyze the computational complexity of market maker pricing algorithms for combinatorial prediction markets. We focus on Hanson's popular logarithmic market scoring rule market maker (LMSR). Our goal is to implicitly maintain correct LMSR prices across an exponentially large outcome space. We examine both permutation combinatorics, where outcomes are permutations of objects, and Boolean combinatorics, where outcomes are combinations of binary events. We look at three restrictive languages that limit what traders can bet on. Even with severely limited languages, we find that LMSR pricing is #P-hard, even when the same language admits polynomial-time matching without the market maker. We then propose an approximation technique for pricing permutation markets based on an algorithm for online permutation learning. The connections we draw between LMSR pricing and the literature on online learning with expert advice may be of independent interest.
View PDF Chat

A Numbers-on-Foreheads Game

2015-01-01
S. Jakobsen

Achieving fully proportional representation: Approximability results

2015-01-30
Piotr Skowron , Piotr Faliszewski , Arkadii Slinko
View PDF Chat

Voting for committees in agreeable societies

2014-01-01
Matt Davis , Michael E. Orrison , Francis Edward Su
We examine the following voting situation. A committee of $k$ people is to be formed from a pool of n candidates. The voters selecting the committee will submit a list … We examine the following voting situation. A committee of $k$ people is to be formed from a pool of n candidates. The voters selecting the committee will submit a list of $j$ candidates that they would prefer to be on the committee. We assume that $j \leq k < n$. For a chosen committee, a given voter is said to be satisfied by that committee if her submitted list of $j$ candidates is a subset of that committee. We examine how popular is the most popular committee. In particular, we show there is always a committee that satisfies a certain fraction of the voters and examine what characteristics of the voter data will increase that fraction.
View PDF Chat

APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items

2015-07-05
Euiwoong Lee
We study the problem of allocating a set of indivisible items to agents with additive utilities to maximize the Nash social welfare. Cole and Gkatzelis recently proved that this problem … We study the problem of allocating a set of indivisible items to agents with additive utilities to maximize the Nash social welfare. Cole and Gkatzelis recently proved that this problem admits a constant factor approximation. We complement their result by showing that this problem is APX-hard.

Polynomial algorithms in linear programming

1980-01-01
Leonid Khachiyan

Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation

2015-02-18
Piotr Skowron , Piotr Faliszewski , Jérôme Lang
We consider the following problem: There is a set of items (e.g., movies) and a group of agents (e.g., passengers on a plane); each agent has some intrinsic utility for … We consider the following problem: There is a set of items (e.g., movies) and a group of agents (e.g., passengers on a plane); each agent has some intrinsic utility for each of the items. Our goal is to pick a set of K items that maximize the total derived utility of all the agents (i.e., in our example we are to pick K movies that we put on the plane's entertainment system). However, the actual utility that an agent derives from a given item is only a fraction of its intrinsic one, and this fraction depends on how the agent ranks the item among the chosen, available, ones. We provide a formal specification of the model and provide concrete examples and settings where it is applicable. We show that the problem is hard in general, but we show a number of tractability results for its natural special cases.
View PDF Chat

Fixed-point and Minimax Theorems in Locally Convex Topological Linear Spaces

1952-02-01
Ky Fan
Emotions coordinate our behavior and physiological states during survival-salient events and pleasurable interactions. Even though we are often consciously aware of our current emotional state, such as anger or happiness, … Emotions coordinate our behavior and physiological states during survival-salient events and pleasurable interactions. Even though we are often consciously aware of our current emotional state, such as anger or happiness, the mechanisms giving ...Emotions are often felt in the body, and somatosensory feedback has been proposed to trigger conscious emotional experiences. Here we reveal maps of bodily sensations associated with different emotions using a unique topographical self-report method. In ...
View PDF Chat

Welfare Undominated Groves Mechanisms

2008-01-01
Krzysztof R. Apt , Vincent Conitzer , Mingyu Guo +1 more

Problem-focused incremental elicitation of multi-attribute tility models

1997-08-01
Vu Ha , Peter Haddawy
Decision theory has become widely accepted in the AI community as a useful framework for planning and decision making. Applying the framework typically requires elicitation of some form of probability … Decision theory has become widely accepted in the AI community as a useful framework for planning and decision making. Applying the framework typically requires elicitation of some form of probability and utility information. While much work in AI has focused on providing representations and tools for elicitation of probabilities, relatively little work has addressed the elicitation of utility models. This imbalance is not particularly justified considering that probability models are relatively stable across problem instances, while utility models may be different for each instance. Spending large amounts of time on elicitation can be undesirable for interactive systems used in low-stakes decision making and in time-critical decision making. In this paper we investigate the issues of reasoning with incomplete utility models. We identify patterns of problem instances where plans can be proved to be suboptimal if the (unknown) utility function satisfies certain conditions. We present an approach to planning and decision making that performs the utility elicitation incrementally and in a way that is informed by the domain model.

A Puzzle about Further Facts

2018-03-07
Vincent Conitzer
In metaphysics, there are a number of distinct but related questions about the existence of "further facts" -- facts that are contingent relative to the physical structure of the universe. … In metaphysics, there are a number of distinct but related questions about the existence of "further facts" -- facts that are contingent relative to the physical structure of the universe. These include further facts about qualia, personal identity, and time. In this article I provide a sequence of examples involving computer simulations, ranging from one in which the protagonist can clearly conclude such further facts exist to one that describes our own condition. This raises the question of where along the sequence (if at all) the protagonist stops being able to soundly conclude that further facts exist.
View PDF Chat

Consensus of Subjective Probabilities: The Pari-Mutuel Method

1959-03-01
E. Eisenberg , David Gale
Abstract : Under the pari-mutuel system of betting on horse races the final track's odds are in some sense a consensus of the 'subjective odds' of the individual bettors weighted … Abstract : Under the pari-mutuel system of betting on horse races the final track's odds are in some sense a consensus of the 'subjective odds' of the individual bettors weighted by the amounts of their bets. The properties which this consensus must possess and prove that there always exists a unique set of odds having the required properties are formulated. (Author)
View PDF Chat

Graph Implementations for Nonsmooth Convex Programs

2007-12-01
Michael C. Grant , Stephen Boyd
View PDF Chat