Vincent Conitzer

Conference Proceedings of the AAAI Conference on Artificial Intelligence · March 25, 2024 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 it ... Full text Cite

The Complexity of Computing Robust Mediated Equilibria in Ordinal Games

Conference Proceedings of the AAAI Conference on Artificial Intelligence · March 25, 2024 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 w ... Full text Cite

Game Transformations That Preserve Nash Equilibria or Best-Response Sets

Conference Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2024 In the full version of this paper, we investigate under which conditions normal-form games are (guaranteed) to be strategically equivalent. First, we show for N-player games (N ≥ 3) that (a) it is NP-hard to decide whether a given strategy is a best respon ... Cite

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

Conference Proceedings of Machine Learning Research · January 1, 2024 Foundation models such as GPT-4 are fine-tuned to avoid unsafe or otherwise problematic behavior, such as helping to commit crimes or producing racist text. One approach to fine-tuning, called reinforcement learning from human feedback, learns from humans' ... Cite

Game Transformations That Preserve Nash Equilibria or Best-Response Sets

Conference IJCAI International Joint Conference on Artificial Intelligence · January 1, 2024 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 ... Cite

Imperfect-Recall Games: Equilibrium Concepts and Their Complexity

Conference IJCAI International Joint Conference on Artificial Intelligence · January 1, 2024 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. I ... Cite

Computing Optimal Equilibria in Repeated Games with Restarts

Conference IJCAI International Joint Conference on Artificial Intelligence · January 1, 2024 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 anonym ... Cite

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

Journal Article PloS one · January 2024 ObjectivePeer 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 p ... Full text Cite

Aggregating Quantitative Relative Judgments: From Social Choice to Ranking Prediction

Conference Advances in Neural Information Processing Systems · January 1, 2024 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 ... Cite

Melting Pot Contest: Charting the Future of Generalized Cooperative Intelligence

Conference Advances in Neural Information Processing Systems · January 1, 2024 Multi-agent AI research promises a path to develop human-like and human-compatible intelligent technologies that complement the solipsistic view of other approaches, which mostly do not consider interactions between agents. Aiming to make progress in this ... Cite

A Theory of Bounded Inductive Rationality

Conference Electronic Proceedings in Theoretical Computer Science, EPTCS · July 11, 2023 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 as ... Full text Cite

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

Conference EC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation · July 9, 2023 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 ti ... Full text Cite

Foundations of Cooperative AI

Conference Proceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023 · June 27, 2023 AI systems can interact in unexpected ways, sometimes with disastrous consequences. As AI gets to control more of our world, these interactions will become more common and have higher stakes. As AI becomes more advanced, these interactions will become more ... Full text Cite

A Dataset on Malicious Paper Bidding in Peer Review

Conference ACM Web Conference 2023 - Proceedings of the World Wide Web Conference, WWW 2023 · April 30, 2023 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 assignmen ... Full text Cite

The Computational Complexity of Single-Player Imperfect-Recall Games

Conference IJCAI International Joint Conference on Artificial Intelligence · January 1, 2023 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 optimali ... Full text Cite

Game Theory with Simulation of Other Players

Conference IJCAI International Joint Conference on Artificial Intelligence · January 1, 2023 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 ... Full text Cite

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

Conference Advances in Neural Information Processing Systems · January 1, 2023 We introduce a new approach for computing optimal equilibria and mechanisms 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, c ... Cite

Similarity-based cooperative equilibrium

Conference Advances in Neural Information Processing Systems · January 1, 2023 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 ... Cite

Pacing Equilibrium in First Price Auction Markets

Journal Article Management Science · December 1, 2022 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 aggregatemetrics of interest to advertisers. On such p ... Full text Cite

Safe Pareto improvements for delegated game playing

Journal Article Autonomous Agents and Multi-Agent Systems · October 1, 2022 A set of players delegate playing a game to a set of representatives, one for each player. We imagine that each player trusts their respective representative’s strategic abilities. Thus, we might imagine that per default, the original players would simply ... Full text Cite

Efficient Algorithms for Planning with Participation Constraints

Conference EC 2022 - Proceedings of the 23rd ACM Conference on Economics and Computation · July 12, 2022 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 wil ... Full text Cite

Data solidarity for machine learning for embryo selection: a call for the creation of an open access repository of embryo data.

Journal Article Reproductive biomedicine online · July 2022 The last decade has seen an explosion of machine learning applications in healthcare, with mixed and sometimes harmful results despite much promise and associated hype. A significant reason for the reversal in the reported benefit of these applications is ... Full text Cite

Learning Influence Adoption in Heterogeneous Networks

Conference Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022 · June 30, 2022 We study the problem of learning influence adoption in networks. In this problem, a communicable entity (such as an infectious disease, a computer virus, or a social media meme) propagates through a network, and the goal is to learn the state of each indiv ... Full text Cite

Planning with Participation Constraints

Conference Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022 · June 30, 2022 We pose and study the problem of planning in Markov decision processes (MDPs), subject to participation constraints as studied in mechanism design. In this problem, a planner must work with a self-interested agent on a given MDP. Each action in the MDP pro ... Full text Cite

Computational ethics.

Journal Article Trends in cognitive sciences · May 2022 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 represent ... Full text Cite

Multiplicative Pacing Equilibria in Auction Markets

Journal Article Operations Research · March 1, 2022 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 opportun ... Full text Cite

Which features of patients are morally relevant in ventilator triage? A survey of the UK public.

Journal Article BMC medical ethics · March 2022 BackgroundIn the early stages of the COVID-19 pandemic, many health systems, including those in the UK, developed triage guidelines to manage severe shortages of ventilators. At present, there is an insufficient understanding of how the public vie ... Full text Cite

Mechanism Design for Correlated Valuations: Efficient Methods for Revenue Maximization

Journal Article Operations Research · January 1, 2022 Traditionally, the mechanism design literature has been primarily focused on settings where the bidders' valuations are independent. However, in settings where valuations are correlated, much stronger results are possible. For example, the entire surplus o ... Full text Cite

Welfare-Preserving ε -BIC to BIC Transformation with Negligible Revenue Loss

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2022 In this paper, we provide a transform from an ε -BIC mechanism into an exactly BIC mechanism without any loss of social welfare and with additive and negligible revenue loss. This is the first ε -BIC to BIC transformation that preserves welfare and provide ... Full text Cite

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

Conference Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2022 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 pap ... Cite

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

Conference Proceedings of Machine Learning Research · January 1, 2022 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 opti ... Cite

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

Conference Proceedings of the AAAI Conference on Human Computation and Crowdsourcing · January 1, 2022 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 pap ... Full text Cite

Why should we ever automate moral decision making?

Conference CEUR Workshop Proceedings · January 1, 2022 While people generally trust AI to make decisions in various aspects of their lives, concerns arise when AI is involved in decisions with significant moral implications. The absence of a precise mathematical framework for moral reasoning intensifies these ... Cite

Extracting Money from Causal Decision Theorists

Conference Philosophical Quarterly · October 1, 2021 Newcomb s problem has spawned a debate about which variant of expected utility maximisation (if any) should guide rational choice. In this paper, we provide a new argument against what is probably the most popular variant: causal decision theory (CDT). In ... Full text Cite

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

Conference AIES 2021 - Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society · July 21, 2021 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. ... Full text Cite

The Revelation Principle for Mechanism Design with Signaling Costs

Journal Article ACM Transactions on Economics and Computation · March 1, 2021 The revelation principle is a key tool in mechanism design. It allows the designer to restrict attention to truthful mechanisms, greatly facilitating analysis. This is also borne out algorithmically, allowing certain computational problems in mechanism des ... Full text Cite

Indecision Modeling

Journal Article 35th AAAI Conference on Artificial Intelligence, AAAI 2021 · January 1, 2021 AI systems are often used to make or contribute to important decisions in a growing range of applications, including criminal justice, hiring, and medicine. Since these decisions impact human lives, it is important that the AI systems act in ways which ali ... Full text Cite

Safe pareto improvements for delegated game playing

Conference Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2021 A set of players delegate playing a game to a set of representatives, one for each player. We imagine that each player trusts their respective representative’s strategic abilities. Thus, we might imagine that per default, the original players would simply ... Cite

Automated Mechanism Design for Classification with Partial Verification

Conference 35th AAAI Conference on Artificial Intelligence, AAAI 2021 · January 1, 2021 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 ... Full text Cite

Classification with Few Tests through Self-Selection

Conference 35th AAAI Conference on Artificial Intelligence, AAAI 2021 · January 1, 2021 We study test-based binary classification, where a principal either accepts or rejects agents based on the outcomes they get in a set of tests. The principal commits to a policy, which consists of all sets of outcomes that lead to acceptance. Each agent is ... Full text Cite

Classification with Strategically Withheld Data^∗

Conference 35th AAAI Conference on Artificial Intelligence, AAAI 2021 · January 1, 2021 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. ... Full text Cite

Incentive-Aware PAC Learning

Conference 35th AAAI Conference on Artificial Intelligence, AAAI 2021 · January 1, 2021 We study PAC learning in the presence of strategic manipulation, where data points may modify their features in certain predefined ways in order to receive a better outcome. We show that the vanilla ERM principle fails to achieve any nontrivial guarantee i ... Full text Cite

Interpretable, not black-box, artificial intelligence should be used for embryo selection.

Journal Article Human reproduction open · January 2021 Artificial intelligence (AI) techniques are starting to be used in IVF, in particular for selecting which embryos to transfer to the woman. AI has the potential to process complex data sets, to be better at identifying subtle but important patterns, and to ... Full text Cite

Automated Dynamic Mechanism Design

Conference Advances in Neural Information Processing Systems · January 1, 2021 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 a ... Cite

How Much Moral Status Could Artificial Intelligence Ever Achieve?

Chapter · January 1, 2021 Philosophers often argue about whether fetuses, animals, or AI systems do or do not have moral status. We will suggest instead that different entities have different degrees of moral status with respect to different moral reasons in different circumstances ... Full text Cite

Crying about a strategic wolf: A theory of crime and warning

Journal Article Journal of Economic Theory · September 1, 2020 We analyze cheap talk warnings about a strategic adversary, with applications to cybersecurity and national security. Each period an expert receives a noisy private signal about whether an attack by the adversary is feasible. The expert wants to warn a dec ... Full text Cite

Combinatorial Ski Rental and Online Bipartite Matching

Conference EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation · July 13, 2020 We consider a combinatorial variant of the classical ski rental problem - - which we call combinatorial ski rental - - where multiple resources are available to purchase and to rent, and are demanded online. Moreover, the costs of purchasing and renting ar ... Full text Cite

Adapting a kidney exchange algorithm to align with human values

Journal Article Artificial Intelligence · June 1, 2020 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 excha ... Full text Cite

Artificial artificial intelligence: Measuring influence of AI 'Assessments' on moral decision-making

Journal Article AIES 2020 - Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society · February 7, 2020 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 allocatio ... Full text Cite

AI Methods in Bioethics.

Journal Article AJOB empirical bioethics · January 2020 Full text Cite

Minimum-Regret Contracts for Principal-Expert Problems

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2020 We consider a principal-expert problem in which a principal contracts one or more experts to acquire and report decision-relevant information. The principal never finds out what information is available to which expert, at what costs that information is av ... Full text Cite

Bayesian Repeated Zero-Sum Games with Persistent State, with Application to Security Games

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2020 We study infinitely-repeated two-player zero-sum games with one-sided private information and a persistent state. Here, only one of the two players learns the state of the repeated game. We consider two models: either the state is chosen by nature, or by o ... Full text Cite

Learning the valuations of a k-demand agent

Conference 37th International Conference on Machine Learning, ICML 2020 · January 1, 2020 We study problems where a learner aims to learn the valuations of an agent by observing which goods he buys under varying price vectors. More specifically, we consider the case of a k-demand agent, whose valuation over the goods is additive when receiving ... Cite

Learning opinions in social networks

Conference 37th International Conference on Machine Learning, ICML 2020 · January 1, 2020 We study the problem of learning opinions in social networks. The learner observes the states of some sample nodes from a social network, and tries to infer the states of other nodes, based on the structure of the network. We show that sample-efficient lea ... Cite

Mitigating manipulation in peer review via randomized reviewer assignments

Conference Advances in Neural Information Processing Systems · January 1, 2020 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,” ... Cite

Pacing Equilibrium in First-Price Auction Markets

Conference Proceedings of the 2019 ACM Conference on Economics and Computation · June 17, 2019 Full text Cite

A Puzzle about Further Facts

Journal Article Erkenntnis · June 15, 2019 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. ... Full text Cite

AIES 2019 program chairs' welcome

Conference AIES 2019 - Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society · January 27, 2019 Cite

The exact computational complexity of evolutionarily stable strategies

Journal Article Mathematics of Operations Research · January 1, 2019 While the computational complexity of many game-theoretic solution concepts, notably Nash equilibrium, has now been settled, the question of determining the exact complexity of computing an evolutionarily stable strategy has resisted solution since attenti ... Full text Cite

Designing preferences, beliefs, and identities for artificial intelligence

Conference 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Innovative Applications of Artificial Intelligence Conference, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019 · January 1, 2019 Research in artificial intelligence, as well as in economics and other related fields, generally proceeds from the premise that each agent has a well-defined identity, well-defined preferences over outcomes, and well-defined beliefs about the world. Howeve ... Full text Cite

A PAC framework for aggregating agents' judgments

Conference 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Innovative Applications of Artificial Intelligence Conference, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019 · January 1, 2019 Specifying the objective function that an AI system should pursue can be challenging. Especially when the decisions to be made by the system have a moral component, input from multiple stakeholders is often required. We consider approaches that query them ... Full text Cite

A better algorithm for societal tradeoffs

Conference 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Innovative Applications of Artificial Intelligence Conference, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019 · January 1, 2019 In the societal tradeoffs problem, each agent perceives certain quantitative tradeoffs between pairs of activities, and the goal is to aggregate these tradeoffs across agents. This is a problem in social choice; specifically, it is a type of quantitative j ... Full text Cite

Group fairness for the allocation of indivisible goods

Conference 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Innovative Applications of Artificial Intelligence Conference, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019 · January 1, 2019 We consider the problem of fairly dividing a collection of indivisible goods among a set of players. Much of the existing literature on fair division focuses on notions of individual fairness. For instance, envy-freeness requires that no player prefer the ... Full text Cite

When samples are strategically selected

Conference 36th International Conference on Machine Learning, ICML 2019 · January 1, 2019 In standard classification problems, the assumption is that the entity making the decision (the principal) has access to all the samples. However, in many contexts, she either docs not have direct access to the samples, or can inspect only a limited set of ... Cite

Distinguishing distributions when samples are strategically transformed

Conference Advances in Neural Information Processing Systems · January 1, 2019 Often, a principal must make a decision based on data provided by an agent. Moreover, typically, that agent has an interest in the decision that is not perfectly aligned with that of the principal. Thus, the agent may have an incentive to select from or mo ... Cite

When Do People Want AI to Make Decisions?

Conference AIES 2018 - Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society · December 27, 2018 AI systems are now or will soon be sophisticated enough to make consequential decisions. Although this technology has flourished, we also need public appraisals of AI systems playing these more important roles. This article reports surveys of preferences f ... Full text Cite

Adapting a Kidney Exchange Algorithm to Align with Human Values

Conference Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society · December 27, 2018 Full text Cite

Coalition structure generation in cooperative games with compact representations

Journal Article Autonomous Agents and Multi-Agent Systems · July 1, 2018 This paper presents a new way of formalizing the coalition structure generation problem (CSG) so that we can apply constraint optimization techniques to it. Forming effective coalitions is a major research challenge in AI and multi-agent systems. CSG invol ... Full text Cite

Dynamic Proportional Sharing

Conference Performance Evaluation Review · June 12, 2018 Sharing computational resources amortizes cost and improves utilization and efficiency. When agents pool their resources, each becomes entitled to a portion of the shared pool. Static allocations in each round can guarantee entitlements and are strategy-pr ... Full text Cite

Technical perspective designing algorithms and the fairness criteria they should satisfy

Journal Article Communications of the ACM · February 1, 2018 Full text Cite

Moral decision making frameworks for artificial intelligence

Conference International Symposium on Artificial Intelligence and Mathematics, ISAIM 2018 · January 1, 2018 The generality of decision and game theory has enabled domain-independent progress in AI research. For example, a better algorithm for finding good policies in (PO)MDPs can be instantly used in a variety of applications. But such a general theory is lackin ... Cite

Adapting a kidney exchange algorithm to align with human values

Conference 32nd AAAI Conference on Artificial Intelligence, AAAI 2018 · January 1, 2018 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 ... Cite

Complexity of scheduling charging in the smart grid

Conference Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2018 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 comp ... Cite

Complexity of scheduling charging in the smart grid

Conference IJCAI International Joint Conference on Artificial Intelligence · January 1, 2018 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 comp ... Full text Cite

Disarmament games with resources

Conference 32nd AAAI Conference on Artificial Intelligence, AAAI 2018 · January 1, 2018 A paper by Deng and Conitzer in AAAI'17 introduces disarmament games, in which players alternatingly commit not to play certain pure strategies. However, in practice disarmament usually does not consist in removing a strategy, but rather in removing a reso ... Cite

Fair public decision making

Conference EC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation · June 20, 2017 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 se.ing, a decision can provide positiv ... Full text Cite

Farewell Editorial: Looking Back on Our Terms Editing ACM TEAC and into the Future

Journal Article ACM Transactions on Economics and Computation · May 1, 2017 Full text Cite

Game-theoretic question selection for tests

Conference Journal of Artificial Intelligence Research · May 1, 2017 Conventionally, the questions on a test are assumed to be kept secret from test takers until the test. However, for tests that are taken on a large scale, particularly asynchronously, this is very hard to achieve. For example, TOEFL iBT and driver's licens ... Full text Open Access Cite

Justified representation in approval-based committee voting

Journal Article Social Choice and Welfare · February 1, 2017 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 just ... Full text Cite

Disarmament games

Conference 31st AAAI Conference on Artificial Intelligence, AAAI 2017 · January 1, 2017 Much recent work in the AI community concerns algorithms for computing optimal mixed strategies to commit to, as well as the deployment of such algorithms in real security applications. Another possibility is to commit not to play certain actions. If only ... Cite

Automated design of robust mechanisms

Conference 31st AAAI Conference on Artificial Intelligence, AAAI 2017 · January 1, 2017 We introduce a new class of mechanisms, robust mechanisms, that is an intermediary between ex-post mechanisms and Bayesian mechanisms. This new class of mechanisms allows the mechanism designer to incorporate imprecise estimates of the distribution over bi ... Cite

Fair and efficient social choice in dynamic settings

Conference IJCAI International Joint Conference on Artificial Intelligence · January 1, 2017 We study a dynamic social choice problem in which an alternative is chosen at each round according to the reported valuations of a set of agents. In the interests of obtaining a solution that is both efficient and fair, we aim to maximize the long-term Nas ... Full text Cite

Moral decision making frameworks for artificial intelligence

Conference AAAI Workshop - Technical Report · January 1, 2017 The generality of decision and game theory has enabled domain-independent progress in AI research. For example, a better algorithm for finding good policies in (PO)MDPs can be instantly used in a variety of applications. But such a general theory is lackin ... Cite

Mechanism design with unknown correlated distributions: Can we learn optimal mechanisms?

Conference Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2017 Due to Cremer and McLean (1985), it is well known that in a setting where bidders' values are correlated, an auction designer can extract the full social surplus as revenue. However, this result strongly relies on the assumption of a common prior distribut ... Cite

Introduction to the special issue on EC'14

Journal Article ACM Transactions on Economics and Computation · August 1, 2016 Full text Cite

The revelation principle for mechanism design with reporting costs

Conference EC 2016 - Proceedings of the 2016 ACM Conference on Economics and Computation · July 21, 2016 The revelation principle is a key tool in mechanism design. It allows the designer to restrict attention to the class of truthful mechanisms, greatly facilitating analysis. This is also borne out in an algorithmic sense, allowing certain computational prob ... Full text Cite

EC 2016 foreword

Conference EC 2016 - Proceedings of the 2016 ACM Conference on Economics and Computation · July 21, 2016 Cite

Philosophy in the Face of Artificial Intelligence

Journal Article · May 19, 2016 In this article, I discuss how the AI community views concerns about the emergence of superintelligent AI and related philosophical issues. ... Link to item Cite

On Stackelberg mixed strategies

Journal Article Synthese · March 1, 2016 It is sometimes the case that one solution concept in game theory is equivalent to applying another solution concept to a modified version of the game. In such cases, does it make sense to study the former separately (as it applies to the original represen ... Full text Cite

Timeability of extensive-form games

Journal Article ITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science · January 14, 2016 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 pr ... Full text Cite

Catcher-evader games

Journal Article IJCAI International Joint Conference on Artificial Intelligence · January 1, 2016 Algorithms for computing game-theoretic solutions have recently been applied to a number of security domains. However, many of the techniques developed for compact representations of security games do not extend to Bayesian security games, which allow us t ... Cite

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

Conference AAAI · 2016 Cite

Role assignment for game-theoretic cooperation

Conference IJCAI International Joint Conference on Artificial Intelligence · January 1, 2016 In multiagent systems, often agents need to be assigned to different roles. Multiple aspects should be taken into account for this, such as agents' skills and constraints posed by existing assignments. In this paper, we focus on another aspect: when the ag ... Cite

ATUCAPTS: Automated tests that a user cannot pass twice simultaneously

Conference IJCAI International Joint Conference on Artificial Intelligence · January 1, 2016 In highly anonymous environments such as the Internet, many applications suffer from the fact that a single user can pose as multiple users. Indeed, presumably many potential applications do not even get off the ground as a result. Consider the example of ... Cite

Computing equilibria with partial commitment

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2016 In security games, the solution concept commonly used is that of a Stackelberg equilibrium where the defender gets to commit to a mixed strategy. The motivation for this is that the attacker can repeatedly observe the defender’s actions and learn her distr ... Full text Cite

Maximizing revenue with limited correlation: The cost of ex-post incentive compatibility

Conference 30th AAAI Conference on Artificial Intelligence, AAAI 2016 · January 1, 2016 In a landmark paper in the mechanism design literature, Cremer and McLean (1985) (CM for short) show that when a bidder's valuation is correlated with an external signal, a monopolistic seller is able to extract the full social surplus as revenue. In the o ... Cite

Computing possible and necessary equilibrium actions (and bipartisan setwinners)

Conference 30th AAAI Conference on Artificial Intelligence, AAAI 2016 · January 1, 2016 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 ... Cite

Rules for choosing societal tradeoffs

Conference 30th AAAI Conference on Artificial Intelligence, AAAI 2016 · January 1, 2016 We study the societal tradeoffs problem, where a set of voters each submit their ideal tradeoff value between each pair of activities (e.g., "using a gallon of gasoline is as bad as creating 2 bags of landfill trash"), and these are then aggregated into th ... Cite

Handbook of computational social choice

Book · January 1, 2016 The rapidly growing field of computational social choice, at the intersection of computer science and economics, deals with the computational aspects of collective decision making. This handbook, written by thirty-six prominent members of the computational ... Full text Cite

Timeability of Extensive-Form Games.

Conference ITCS · 2016 Cite

Computing possible and necessary equilibrium actions (and bipartisan set winners)

Conference International Symposium on Artificial Intelligence and Mathematics, ISAIM 2016 · January 1, 2016 Copyright © 2016, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. In many multiagent environments, a designer has some, but limited control over the game being played. In this paper, we formalize this by cons ... Cite

Role Assignment for Game-Theoretic Cooperation: (Extended Abstract).

Conference AAMAS · 2016 Cite

Signaling in Bayesian stackelberg games

Conference Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2016 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 sig ... Cite

False-name-proof recommendations in social networks

Conference Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2016 We study the problem of finding a recommendation for an uninformed user in a social network by weighting and aggregating the opinions offered by the informed users in the network. In social networks, an informed user may try to manipulate the recommendatio ... Cite

Role assignment for game-theoretic cooperation

Conference Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2016 In multiagent systems, often agents need to be assigned to different roles. Multiple aspects should be taken into account for this, such as agents' skills and constraints posed by existing assignments. In this paper, we focus on another aspect: when the ag ... Cite

Introduction to computational social choice

Chapter · January 1, 2016 Computational Social Choice at a Glance Social choice theory is the field of scientific inquiry that studies the aggregation of individual preferences toward a collective choice. For example, social choice theorists- who hail from a range of different disc ... Full text Cite

Barriers to manipulation in voting

Chapter · January 1, 2016 Introduction In many situations, voters may vote strategically. That is, they may declare preferences that are not their true ones, with the aim of obtaining a better outcome for themselves. The following example illustrates this. Example 6.1. Consider an ... Full text Cite

Rules for choosing societal tradeoffs

Conference International Symposium on Artificial Intelligence and Mathematics, ISAIM 2016 · January 1, 2016 Copyright © 2016, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. We study the societal tradeoffs problem, where a set of voters each submit their ideal tradeoff value between each pair of activities (e.g., “ ... Cite

False-name-proof recommendations in social networks

Conference International Symposium on Artificial Intelligence and Mathematics, ISAIM 2016 · January 1, 2016 © 2016 University of Virginia. All rights reserved. We study the problem of finding a recommendation for an uninformed user in a social network by weighting and aggregating the opinions offered by the informed users in the network. In social networks, an i ... Cite

Computing possible and necessary equilibrium actions (and bipartisan set winners)

Conference International Symposium on Artificial Intelligence and Mathematics, ISAIM 2016 · January 1, 2016 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 ... Cite

False-name-proof recommendations in social networks

Conference International Symposium on Artificial Intelligence and Mathematics, ISAIM 2016 · January 1, 2016 We study the problem of finding a recommendation for an uninformed user in a social network by weighting and aggregating the opinions offered by the informed users in the network. In social networks, an informed user may try to manipulate the recommendatio ... Cite

Rules for choosing societal tradeoffs

Conference International Symposium on Artificial Intelligence and Mathematics, ISAIM 2016 · January 1, 2016 We study the societal tradeoffs problem, where a set of voters each submit their ideal tradeoff value between each pair of activities (e.g., “using a gallon of gasoline is as bad as creating 2 bags of landfill trash”), and these are then aggregated into th ... Cite

Can rational choice guide us to correct de se beliefs?

Journal Article Synthese · December 1, 2015 Significant controversy remains about what constitute correct self-locating beliefs in scenarios such as the Sleeping Beauty problem, with proponents on both the “halfer” and “thirder” sides. To attempt to settle the issue, one natural approach consists in ... Full text Cite

A Dutch book against sleeping beauties who are evidential decision theorists

Journal Article Synthese · October 1, 2015 In the context of the Sleeping Beauty problem, it has been argued that so-called “halfers” can avoid Dutch book arguments by adopting evidential decision theory. I introduce a Dutch book for a variant of the Sleeping Beauty problem and argue that evidentia ... Full text Cite

A devastating example for the Halfer Rule

Journal Article Philosophical Studies · September 23, 2015 How should we update de dicto beliefs in the face of de se evidence? The Sleeping Beauty problem divides philosophers into two camps, halfers and thirders. But there is some disagreement among halfers about how their position should generalize to other exa ... Full text Cite

Justified representation in approval-based committee voting

Journal Article Proceedings of the National Conference on Artificial Intelligence · June 1, 2015 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 jus ... Cite

Assessing the robustness of Cremer-McLean with automated mechanism design

Conference Proceedings of the National Conference on Artificial Intelligence · June 1, 2015 In a classic result in the mechanism design literature, Cremer and McLean (1985) show that if buyers' valuations are sufficiently correlated, a mechanism exists that allows the seller to extract the full surplus from efficient allocation as revenue. This r ... Cite

Cooperative game solution concepts that maximize stability under noise

Conference Proceedings of the National Conference on Artificial Intelligence · June 1, 2015 In cooperative game theory, it is typically assumed that the value of each coalition is known. We depart from this, assuming that v(S) is only a noisy estimate of the true value V(S), which is not yet known. In this context, we investigate which solution c ... Cite

Strategic voting and strategic candidacy

Conference Proceedings of the National Conference on Artificial Intelligence · June 1, 2015 Models of strategic candidacy analyze the incentives of candidates to run in an election. Most work on this topic assumes that strategizing only takes place among candidates, whereas voters vote truthfully. In this paper, we extend the analysis to also inc ... Cite

General tiebreaking schemes for computational social choice

Conference Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2015 In (computational) social choice, how ties are broken can affect the axiomatic and computational properties of a voting rule. In this paper, we first consider settings where we may have multiple winners. We formalize the notion of parallel universes tiebre ... Cite

Complexity of mechanism design with signaling costs

Conference Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2015 In mechanism design, it is generally assumed that an agent can submit any report at zero cost (with the occasional further restriction that certain types can not submit certain reports). More generally, however, an agent of type θ may be able to report θ', ... Cite

Crowdsourcing societal tradeoffs

Conference Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2015 It would be desirable if, as a society, we could reduce the amount of landfill trash we create, the amount of carbon dioxide we emit, the amount of forest we clear, etc. Since we cannot (or are in any case not willing to) simultaneously pursue all these ob ... Cite

Maximal cooperation in repeated games on social networks

Conference IJCAI International Joint Conference on Artificial Intelligence · January 1, 2015 Standard results on and algorithms for repeated games assume that defections are instantly observable. In reality, it may take some time for the knowledge that a defection has occurred to propagate through the social network. How does this affect the struc ... Cite

Notes from the EC'14 program chairs

Journal Article ACM SIGecom Exchanges · November 25, 2014 This short document describes the process used to create the EC'14 program, as well some comments on our experience. This year the conference, which had been called the ACM Conference on Electronic Commerce, was renamed the ACM Conference on Econom ... Full text Cite

Complexity of Mechanism Design

Conference · August 7, 2014 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 mot ... Link to item Cite

False-name-proof voting with costs over two alternatives

Journal Article International Journal of Game Theory · 2014 Cite

Strategy-proof contract auctions and the role of ties

Journal Article Games and Economic Behavior · January 1, 2014 A contract auction establishes a contract between a center and one of the bidders. As contracts may describe many terms, preferences over contracts typically display indifferences. The Qualitative Vickrey Auction (QVA) selects the best contract for the win ... Full text Cite

EC'14 foreword

Journal Article EC 2014 - Proceedings of the 15th ACM Conference on Economics and Computation · January 1, 2014 Cite

False-name-proof voting with costs over two alternatives

Journal Article International Journal of Game Theory · January 1, 2014 In open, anonymous settings such as the Internet, agents can participate in a mechanism multiple times under different identities. A mechanism is false-name-proof if no agent ever benefits from participating more than once. Unfortunately, the design of fal ... Full text Cite

On the value of commitment

Journal Article Autonomous Agents and Multi-Agent Systems · January 1, 2014 In game theory, it is well known that being able to commit to a strategy before other players move can be beneficial. In this paper, we analyze how much benefit a player can derive from commitment in various types of games, in a quantitative sense that is ... Full text Cite

Better redistribution with inefficient allocation in multi-unit auctions

Journal Article Artificial Intelligence · January 1, 2014 For the problem of allocating one or more items among a group of competing agents, the Vickrey-Clarke-Groves (VCG) mechanism is strategy-proof and efficient. However, the VCG mechanism is not strongly budget balanced: in general, value flows out of the sys ... Full text Cite

Solving zero-sum security games in discretized spatio-temporal domains

Conference Proceedings of the National Conference on Artificial Intelligence · January 1, 2014 Among the many deployment areas of Stackelberg Security games, a major area involves games played out in space and time, which includes applications in muitipte mobile defender resources protecting multiple mobile targets. Previous algorithms for such spat ... Cite

Beat the cheater: Computing game-theoretic strategies for when to kick a gambler out of a casino

Conference Proceedings of the National Conference on Artificial Intelligence · January 1, 2014 Gambles in casinos are usually set up so that the casino makes a profit in expectation-as long as gamblers play honestly. However, some gamblers are able to cheat, reducing the casino's profit. How should the casino address this? A common strategy is to se ... Cite

Mechanism design for scheduling with uncertain execution time

Conference Proceedings of the National Conference on Artificial Intelligence · January 1, 2014 We study the problem where a task (or multiple unrelated tasks) must be executed, there are multiple machines/agents that can potentially perform the task, and our objective is to minimize the expected sum of the agents' processing times. Each agent does n ... Cite

On the axiomatic characterization of runoff voting rules

Conference Proceedings of the National Conference on Artificial Intelligence · January 1, 2014 Runoff voting rules such as single transferable vote (STV) and Baldwin's rule are of particular interest in computational social choice due to their recursive nature and hardness of manipulation, as well as in (human) practice because they are relatively e ... Cite

Complexity of stability-based solution concepts in multi-issue and MC-net cooperative games

Conference 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014 · January 1, 2014 MC-nets constitute a natural compact representation scheme for cooperative games in multiagent systems. In this paper, we study the complexity of several natural computational problems that concern solution concepts such as the core, the least core and the ... Cite

The maximum likelihood approach to voting on social networks

Conference International Symposium on Artificial Intelligence and Mathematics, ISAIM 2014 · January 1, 2014 © 2014 University of Illinois at Chicago. All rights reserved. One view of voting is that voters have inherently different preferences – de gustibus non est disputandum – and that voting is merely a method for reaching a reasonable compromise solution. An ... Cite

Determining Possible and Necessary Winners Given Partial Orders.

Journal Article CoRR · 2014 Cite

Complexity of Mechanism Design.

Journal Article CoRR · 2014 Cite

Eliciting Single-Peaked Preferences Using Comparison Queries.

Journal Article CoRR · 2014 Cite

ACM Conference on Economics and Computation, EC '14, Stanford , CA, USA, June 8-12, 2014

Conference EC · 2014 Cite

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

Journal Article CoRR · 2014 Cite

The maximum likelihood approach to voting on social networks

Conference International Symposium on Artificial Intelligence and Mathematics, ISAIM 2014 · January 1, 2014 One view of voting is that voters have inherently different preferences – de gustibus non est disputandum – and that voting is merely a method for reaching a reasonable compromise solution. An alternative view is that some of the alternatives really are be ... Cite

The exact computational complexity of evolutionarily stable strategies

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · December 1, 2013 While the computational complexity of many game-theoretic solution concepts, notably Nash equilibrium, has now been settled, the question of determining the exact complexity of computing an evolutionarily stable strategy has resisted solution since attenti ... Full text Cite

Game-theoretic question selection for tests

Journal Article IJCAI International Joint Conference on Artificial Intelligence · December 1, 2013 Conventionally, the questions on a test are assumed to be kept secret from test takers until the test. However, for tests that are taken on a large scale, particularly asynchronously, this is very hard to achieve. For example, example TOEFL iBT and driver' ... Cite

Solving security games on graphs via marginal probabilities

Conference Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013 · December 1, 2013 Security games involving the allocation of multiple security resources to defend multiple targets generally have an exponential number of pure strategies for the defender. One method that has been successful in addressing this computational issue is to ins ... Cite

Fast equilibrium computation for infinitely repeated games

Conference Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013 · December 1, 2013 It is known that an equilibrium of an infinitely repeated two-player game (with limit average payoffs) can be computed in polynomial time, as follows: according to the folk theorem, we compute minimax strategies for both players to calculate the punishment ... Cite

On the value of commitment

Journal Article Autonomous Agents and Multi-Agent Systems · 2013 Cite

The maximum likelihood approach to voting on social networks

Journal Article 2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013 · January 1, 2013 One view of voting is that voters have inherently different preferences - de gustibus non est disputandum - and that voting is merely a method for reaching a reasonable compromise solution. An alternative view is that some of the alternatives really are be ... Full text Cite

The ACM transactions on economics and computation: An introduction

Journal Article ACM Transactions on Economics and Computation · January 1, 2013 Full text Cite

Undominated groves mechanisms

Journal Article Journal of Artificial Intelligence Research · January 1, 2013 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, unde ... Full text Cite

Security scheduling for real-world networks

Conference 12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013 · January 1, 2013 Network based security games, where a defender strategically places security measures on the edges of a graph to protect against an adversary, who chooses a path through a graph is an important research problem with potential for real-world impact. For exa ... Cite

Optimal Internet auctions with costly communication

Conference 12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013 · January 1, 2013 Iterative auctions can reach an outcome before all bidders have revealed all their preference information. This can decrease costs associated with communication, deliberation, and loss of privacy. We propose an explicit cost model that is inspired by singl ... Cite

False-name-proof matching

Conference 12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013 · January 1, 2013 Matching a set of agents to a set of objects has many real applications. One well-studied framework is that of priority-based matching, in which each object is assumed to have a priority order over the agents. The Deferred Acceptance (DA) and Top-Trading-C ... Cite

Strategy-proof contract auctions and the role of ties

Journal Article Games and Economic Behavior · 2013 Cite

Computing a profit-maximizing sequence of offers to agents in a social network

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · December 26, 2012 Firms have ever-increasing amounts of information about possible customers available to them; furthermore, they are increasingly able to push offers to them rather than having to passively wait for a consumer to initiate contact. This opens up enormous new ... Full text Cite

Computing Stackelberg strategies in stochastic games

Journal Article ACM SIGecom Exchanges · December 2012 Significant recent progress has been made in both the computation of optimal strategies to commit to (Stackelberg strategies), and the computation of correlated equilibria of stochastic games. In this letter we discuss some recent results in the in ... Full text Cite

Approximating common voting rules by sequential voting in multi-issue domains

Conference International Symposium on Artificial Intelligence and Mathematics, ISAIM 2012 · December 1, 2012 When agents need to make decisions on multiple issues, one solution is to vote on the issues sequentially. In this paper, we investigate how well the winner under the sequential voting process approximates the winners under some common voting rules. Some c ... Cite

Computing optimal strategies to commit to in stochastic games

Journal Article Proceedings of the National Conference on Artificial Intelligence · November 7, 2012 Significant progress has been made recently in the following two lines of research in the intersection of AI and game theory: (1) the computation of optimal strategies to commit to (Stackelberg strategies), and (2) the computation of correlated equilibria ... Cite

Evaluating resistance to false-name manipulations in elections

Journal Article Proceedings of the National Conference on Artificial Intelligence · November 7, 2012 In many mechanisms (especially online mechanisms), a strategic agent can influence the outcome by creating multiple false identities. We consider voting settings where the mechanism designer cannot completely prevent false-name manipulation, but may use fa ... Cite

False-name-proofness with Bid Withdrawal

Journal Article · August 31, 2012 We study a more powerful variant of false-name manipulation in Internet auctions: an agent can submit multiple false-name bids, but then, once the allocation and payments have been decided, withdraw some of her false-name identities (have some of her false ... Link to item Cite

Should social network structure be taken into account in elections?

Journal Article Mathematical Social Sciences · July 1, 2012 If the social network structure among the voters in an election is known, how should this be taken into account by the voting rule? In this brief article, I argue, via the maximum likelihood approach to voting, that it is optimal to ignore the social netwo ... Full text Cite

Hide and seek: Costly consumer privacy in a market with repeat purchases

Journal Article Marketing Science · March 1, 2012 When a firm can recognize its previous customers, it may use information about their past purchases to price discriminate. We study a model with a monopolist and a continuum of heterogeneous consumers, where consumers have the ability to maintain their ano ... Full text Cite

Choosing fair lotteries to defeat the competition

Journal Article International Journal of Game Theory · February 1, 2012 We study the following game: each agent i chooses a lottery over nonnegative numbers whose expectation is equal to his budget b i. The agent with the highest realized outcome wins (and agents only care about winning). This game is motivated by various real ... Full text Cite

Computing Optimal Strategies to Commit to in Stochastic Games

Conference Proceedings of the 26th AAAI Conference on Artificial Intelligence, AAAI 2012 · January 1, 2012 Significant progress has been made recently in the following two lines of research in the intersection of AI and game theory: (1) the computation of optimal strategies to commit to (Stackelberg strategies), and (2) the computation of correlated equilibria ... Cite

Computing Game-Theoretic Solutions and Applications to Security

Conference Proceedings of the 26th AAAI Conference on Artificial Intelligence, AAAI 2012 · January 1, 2012 The multiagent systems community has adopted game theory as a framework for the design of systems of multiple self-interested agents. For this to be effective, efficient algorithms must be designed to compute the solutions that game theory prescribes. In t ... Full text Cite

Evaluating Resistance to False-Name Manipulations in Elections

Conference Proceedings of the 26th AAAI Conference on Artificial Intelligence, AAAI 2012 · January 1, 2012 In many mechanisms (especially online mechanisms), a strategic agent can influence the outcome by creating multiple false identities. We consider voting settings where the mechanism designer cannot completely prevent false-name manipulation, but may use fa ... Cite

An undergraduate course in the intersection of computer science and economics

Journal Article Proceedings of the National Conference on Artificial Intelligence · January 1, 2012 In recent years, major research advances have taken place in the intersection of computer science and economics, but this material has so far been taught primarily at the graduate level. This paper describes a novel semester-long undergraduate-level course ... Full text Cite

Computing game-theoretic solutions and applications to security

Journal Article Proceedings of the National Conference on Artificial Intelligence · January 1, 2012 The multiagent systems community has adopted game theory as a framework for the design of systems of multiple self-interested agents. For this to be effective, efficient algorithms must be designed to compute the solutions that game theory prescribes. In t ... Full text Cite

Computing optimal outcomes under an expressive representation of settings with externalities

Journal Article Journal of Computer and System Sciences · January 1, 2012 When a decision must be made based on the preferences of multiple agents, and the space of possible outcomes is combinatorial in nature, it becomes necessary to think about how preferences should be represented, and how this affects the complexity of findi ... Full text Cite

Paradoxes of multiple elections: An approximation approach

Conference Proceedings of the International Conference on Knowledge Representation and Reasoning · January 1, 2012 When agents need to make decisions on multiple issues, applying common voting rules becomes computationally hard due to the exponentially large number of alternatives. One computationally efficient solution is to vote on the issues sequentially. In this pa ... Cite

Discussion of "a conditional game for comparing approximations"

A maximum likelihood approach towards aggregating partial orders

Conference IJCAI International Joint Conference on Artificial Intelligence · December 1, 2011 In many of the possible applications as well as the theoretical models of computational social choice, the agents' preferences are represented as partial orders. In this paper, we extend the maximum likelihood approach for defining "optimal" voting rules t ... Full text Cite

Hypercubewise preference aggregation in multi-issue domains

Conference IJCAI International Joint Conference on Artificial Intelligence · December 1, 2011 We consider a framework for preference aggregation on multiple binary issues, where agents' preferences are represented by (possibly cyclic) CP-nets. We focus on the majority aggregation of the individual CP-nets, which is the CP-net where the direction of ... Full text Cite

Security games with multiple attacker resources

Conference IJCAI International Joint Conference on Artificial Intelligence · December 1, 2011 Algorithms for finding game-theoretic solutions are now used in several real-world security applications. This work has generally assumed a Stackelberg model where the defender commits to a mixed strategy first. In general two-player normal-form games, Sta ... Full text Cite

Hide and Seek: Costly Consumer Privacy in a Market with Repeat Purchases

Journal Article · October 15, 2011 Cite

Commitment to Correlated Strategies

Conference Proceedings of the 25th AAAI Conference on Artificial Intelligence, AAAI 2011 · August 11, 2011 The standard approach to computing an optimal mixed strategy to commit to is based on solving a set of linear programs, one for each of the follower's pure strategies. We show that these linear programs can be naturally merged into a single linear program; ... Full text Cite

Dominating Manipulations in Voting with Partial Information

Conference Proceedings of the 25th AAAI Conference on Artificial Intelligence, AAAI 2011 · August 11, 2011 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 information set, which is the set of profiles of the non-manipulators that are indistin ... Full text Cite

Coalition structure generation utilizing compact characteristic function representations

Journal Article Transactions of the Japanese Society for Artificial Intelligence · May 19, 2011 This paper presents a new way of formalizing the Coalition Structure Generation problem (CSG), so that we can apply constraint optimization techniques to it. Forming effective coalitions is a major research challenge in AI and multi-agent systems. CSG invo ... Full text Cite

Stackelberg vs. nash in security games: An extended investigation of interchangeability, equivalence, and uniqueness

Journal Article Journal of Artificial Intelligence Research · May 1, 2011 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 Airpor ... Full text Cite

Determining possible and necessary winners under common voting rules given partial orders

Journal Article Journal of Artificial Intelligence Research · May 1, 2011 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. The ... Full text Cite

Expressive markets for donating to charities

Journal Article Artificial Intelligence · May 1, 2011 When donating money to a (say, charitable) cause, it is possible to use the contemplated donation as a bargaining chip to induce other parties interested in the charity to donate more. Such negotiation is usually done in terms of matching offers, where one ... Full text Cite

A double oracle algorithm for zero-sum security games on graphs

Journal Article 10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011 · January 1, 2011 In response to the Mumbai attacks of 2008, the Mumbai police have started to schedule a limited number of inspection checkpoints on the road network throughout the city. Algorithms for similar security-related scheduling problems have been proposed in rece ... Cite

Solving stackelberg games with uncertain observability

Journal Article 10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011 · January 1, 2011 Recent applications of game theory in security domains use algorithms to solve a Stackelberg model, in which one player (the leader) first commits to a mixed strategy and then the other player (the follower) observes that strategy and best-responds to it. ... Cite

Stackelberg versus nash in security games: Interchangeability, equivalence, and uniqueness

Chapter · January 1, 2011 Introduction There has been significant recent research interest in game-theoretic approaches to security at airports, ports, transportation, shipping and other infrastructure (Basilico, Gatti, and Amigoni, 2009; Conitzer and Sandholm, 2006; Kiekintveld et ... Full text Cite

A double oracle algorithm for zero-sum security games on graphs.

Conference AAMAS · 2011 Cite

Approximation algorithm for security games with costly resources

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2011 In recent years, algorithms for computing game-theoretic solutions have been developed for real-world security domains. These games are between a defender, who must allocate her resources to defend potential targets, and an attacker, who chooses a target t ... Full text Cite

Budget-balanced and nearly efficient randomized mechanisms: Public goods and beyond

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2011 Many scenarios where participants hold private information require payments to encourage truthful revelation. Some of these scenarios have no natural residual claimant who would absorb the budget surplus or cover the deficit. Faltings [7] proposed the idea ... Full text Cite

Commitment to correlated strategies

Journal Article Proceedings of the National Conference on Artificial Intelligence · January 1, 2011 The standard approach to computing an optimal mixed strategy to commit to is based on solving a set of linear programs, one for each of the follower's pure strategies. We show that these linear programs can be naturally merged into a single linear program; ... Full text Cite

An NTU cooperative game theoretic view of manipulating elections

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2011 Social choice theory and cooperative (coalitional) game theory have become important foundations for the design and analysis of multiagent systems. In this paper, we use cooperative game theory tools in order to explore the coalition formation process in t ... Full text Cite

Dominating manipulations in voting with partial information

Journal Article Proceedings of the National Conference on Artificial Intelligence · January 1, 2011 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 information set, which is the set of profiles of the non-manipulators that are indistin ... Full text Cite

Strategic sequential voting in multi-issue domains and multiple-election paradoxes

Journal Article Proceedings of the ACM Conference on Electronic Commerce · January 1, 2011 In many settings, a group of voters must come to a joint decision on multiple issues. In practice, this is often done by voting on the issues in sequence. We model sequential voting in multi-issue domains as a complete-information extensive-form game, in w ... Full text Cite

Aggregating value ranges: Preference elicitation and truthfulness

Journal Article Autonomous Agents and Multi-Agent Systems · January 1, 2011 We study the case where agents have preferences over ranges (intervals) of values, and we wish to elicit and aggregate these preferences. For example, consider a set of climatologist agents who are asked for their predictions for the increase in temperatur ... Full text Cite

AI and Economic Theory

Journal Article IEEE INTELLIGENT SYSTEMS · January 1, 2011 Link to item Cite

Strategy-proof voting rules over multi-issue domains with restricted preferences

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · December 1, 2010 In this paper, we characterize strategy-proof voting rules when the set of alternatives has a multi-issue structure, and the voters' preferences are represented by acyclic CP-nets that follow a common order over issues. Our main result is a simple full cha ... Full text Cite

False-name-proofness in social networks

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · December 1, 2010 In mechanism design, the goal is to create rules for making a decision based on the preferences of multiple parties (agents), while taking into account that agents may behave strategically. An emerging phenomenon is to run such mechanisms on a social netwo ... Full text Cite

Computing optimal strategies to commit to in extensive-form games

Journal Article Proceedings of the ACM Conference on Electronic Commerce · July 23, 2010 Computing optimal strategies to commit to in general normal-form or Bayesian games is a topic that has recently been gaining attention, in part due to the application of such algorithms in various security and law enforcement scenarios. In this paper, we e ... Full text Cite

A scheduling approach to coalitional manipulation

Journal Article Proceedings of the ACM Conference on Electronic Commerce · July 23, 2010 The coalitional manipulation problem is one of the central problems in computational social choice. In this paper, we focus on solving the problem under the important family of positional scoring rules, in an approximate sense that was advocated by Zuckerm ... Full text Cite

Complexity of Computing Optimal Stackelberg Strategies in Security Resource Allocation Games

Conference Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010 · July 15, 2010 Recently, algorithms for computing game-theoretic solutions have been deployed in real-world security applications, such as the placement of checkpoints and canine units at Los Angeles International Airport. These algorithms assume that the defender (secur ... Cite

Stackelberg Voting Games: Computational Aspects and Paradoxes

Conference Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010 · July 15, 2010 We consider settings in which voters vote in sequence, each voter knows the votes of the earlier voters and the preferences of the later voters, and voters are strategic. This can be modeled as an extensive-form game of perfect information, which we call a ... Cite

Computationally Feasible Automated Mechanism Design: General Approach and Case Studies

Conference Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010 · July 15, 2010 In many multiagent settings, a decision must be made based on the preferences of multiple agents, and agents may lie about their preferences if this is to their benefit. In mechanism design, the goal is to design procedures (mechanisms) for making the deci ... Cite

Compilation Complexity of Common Voting Rules

Conference Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010 · July 15, 2010 In computational social choice, one important problem is to take the votes of a subelectorate (subset of the voters), and summarize them using a small number of bits. This needs to be done in such a way that, if all that we know is the summary, as well as ... Cite

Online Privacy and Price Discrimination

Scholarly Edition · July 2010 Cite

Editor's puzzle

Journal Article ACM SIGecom Exchanges · June 2010 Solutions should be sent to the editor at conitzer@cs.duke.edu with subject header SIGecom Exchanges Puzzle . The author(s) of the most elegant solution (as judged by the editor) will be a ... Full text Cite

Comparing multiagent systems research in combinatorial auctions and voting

Journal Article Annals of Mathematics and Artificial Intelligence · April 1, 2010 In a combinatorial auction, a set of items is for sale, and agents can bid on subsets of these items. In a voting setting, the agents decide among a set of alternatives by having each agent rank all the alternatives. Many of the key research issues in thes ... Full text Cite

Optimal-in-expectation redistribution mechanisms

Journal Article Artificial Intelligence · April 1, 2010 Many important problems in multiagent systems involve the allocation of multiple resources among the agents. If agents are self-interested, they will lie about their valuations for the resources if they perceive this to be in their interest. The well-known ... Full text Cite

Making decisions based on the preferences of multiple agents

10101 Abstracts Collection - Computational Foundations of Social Choice.

Conference Computational Foundations of Social Choice · 2010 Cite

10101 Executive Summary - Computational Foundations of Social Choice.

Conference Computational Foundations of Social Choice · 2010 Cite

Computational Foundations of Social Choice, 07.03. - 12.03.2010

Conference Computational Foundations of Social Choice · 2010 Cite

False-name-proofness with bid withdrawal.

Conference AAMAS · 2010 Cite

Computational Foundations of Social Choice - Dagstuhl Seminar -

Conference Dagstuhl Seminar Proceedings · January 1, 2010 This seminar addressed some of the key issues in computational social choice, a novel interdisciplinary eld of study at the interface of social choice theory and computer science. Computational social choice is concerned with the application of computation ... Cite

Using mechanism design to prevent false-name manipulations

Journal Article AI Magazine · January 1, 2010 Full text Cite

Complexity of computing optimal Stackelberg strategies in security resource allocation games

Journal Article Proceedings of the National Conference on Artificial Intelligence · January 1, 2010 Recently, algorithms for computing game-theoretic solutions have been deployed in real-world security applications, such as the placement of checkpoints and canine units at Los Angeles International Airport. These algorithms assume that the defender (secur ... Cite

Computationally feasible automated mechanism design: General approach and case studies

Journal Article Proceedings of the National Conference on Artificial Intelligence · January 1, 2010 In many multiagent settings, a decision must be made based on the preferences of multiple agents, and agents may lie about their preferences if this is to their benefit. In mechanism design, the goal is to design procedures (mechanisms) for making the deci ... Cite

Stackelberg voting games: Computational aspects and paradoxes

Journal Article Proceedings of the National Conference on Artificial Intelligence · January 1, 2010 We consider settings in which voters vote in sequence, each voter knows the votes of the earlier voters and the preferences of the later voters, and voters are strategic. This can be modeled as an extensive-form game of perfect information, which we call a ... Cite

Compilation complexity of common voting rules

Journal Article Proceedings of the National Conference on Artificial Intelligence · January 1, 2010 In computational social choice, one important problem is to take the votes of a subelectorate (subset of the voters), and summarize them using a small number of bits. This needs to be done in such a way that, if all that we know is the summary, as well as ... Cite

Using a memory test to limit a user to one account

Journal Article Lecture Notes in Business Information Processing · January 1, 2010 In many Web-based applications, there are incentives for a user to sign up for more than one account, under false names. By doing so, the user can send spam e-mail from an account (which will eventually cause the account to be shut down); distort online ra ... Full text Cite

Incentive compatible budget elicitation in multi-unit auctions

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2010 In this paper, we consider the problem of designing incentive compatible auctions for multiple (homogeneous) units of a good, when bidders have private valuations and private budget constraints. When only the valuations are private and the budgets are publ ... Full text Cite

Incentive Compatible Budget Elicitation in Multi-unit Auctions.

Conference SODA · 2010 Cite

Strategy-proof allocation of multiple items between two agents without payments or priors

Conference Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2010 We investigate the problem of allocating items (private goods) among competing agents in a setting that is both prior-free and payment-free. Specificall, we focus on allocating multiple heterogeneous items between two agents with additive valuation functio ... Cite

Stackelberg vs. Nash in security games: Interchangeability, equivalence, and uniqueness

Conference Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2010 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; for example, these games are at the heart of major applications such as t ... Cite

Aggregating preferences in multi-issue domains by using maximum likelihood estimators

Conference Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2010 In this paper, we study a maximum likelihood estimation (MLE) approach to voting when the set of alternatives has a multi-issue structure, and the voters' preferences are represented by CP-nets. We first consider general multi-issue domains, and study whet ... Cite

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

Conference Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2010 This paper analyzes the worst-case efficiency ratio of false-name-proof combinatorial auction mechanisms. False-name-proofness generalizes strategy-proofness by assuming that a bidder can submit multiple bids under fictitious identifiers. Even the well-kno ... Cite

Learning and approximating the optimal strategy to commit to

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · December 14, 2009 Computing optimal Stackelberg strategies in general two-player Bayesian games (not to be confused with Stackelberg strategies in routing games) is a topic that has recently been gaining attention, due to their application in various security and law enforc ... Full text Cite

Editor's puzzle

Journal Article ACM SIGecom Exchanges · December 2009 Solutions should be sent to the editor at conitzer@cs.duke.edu with subject header SIGecom Exchanges Puzzle . The author(s) of the most elegant solution (as judged by the editor) will be a ... Full text Cite

A qualitative Vickrey auction

Journal Article Proceedings of the ACM Conference on Electronic Commerce · December 1, 2009 Restricting the preferences of the agents by assuming that their utility functions linearly depend on a payment allows for the positive results of the Vickrey auction and the Vickrey-Clarke-Groves mechanism. These results, however, are limited to settings ... Full text Cite

Approximation guarantees for fictitious play

Journal Article 2009 47th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2009 · December 1, 2009 Fictitious play is a simple, well-known, and often-used algorithm for playing (and, especially, learning to play) games. However, in general it does not converge to equilibrium; even when it does, we may not be able to run it to convergence. Still, we may ... Full text Cite

Prediction mechanisms that do not incentivize undesirable actions

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · December 1, 2009 A potential downside of prediction markets is that they may incentivize agents to take undesirable actions in the real world. For example, a prediction market for whether a terrorist attack will happen may incentivize terrorism, and an in-house prediction ... Full text Cite

Anonymity-proof shapley value: Compact and computationally efficient solution concept for coalitional games in open anonymous environment

Journal Article Computer Software · December 1, 2009 Coalition formation is an important capability for automated negotiation among self-interested agents. In order for coalitions to be stable, a key question that must be answered is how the gains from cooperation are to be distributed. Coalitional game theo ... Cite

Competitive repeated allocation without payments

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · December 1, 2009 We study the problem of allocating a single item repeatedly among multiple competing agents, in an environment where monetary transfers are not possible. We design (Bayes-Nash) incentive compatible mechanisms that do not rely on payments, with the goal of ... Full text Cite

A hybrid of a Turing test and a prediction market

Conference Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering · December 1, 2009 We present Turing Trade, a web-based game that is a hybrid of a Turing test and a prediction market. In this game, there is a mystery conversation partner, the "target," who is trying to appear human, but may in reality be either a human or a bot. There ar ... Full text Cite

Auction protocols

Chapter · November 20, 2009 Cite

Coalition structure generation utilizing compact characteristic function representations

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · November 2, 2009 This paper presents a new way of formalizing the Coalition Structure Generation problem (CSG), so that we can apply constraint optimization techniques to it. Forming effective coalitions is a major research challenge in AI and multi-agent systems. CSG invo ... Full text Cite

Worst-case optimal redistribution of VCG payments in multi-unit auctions

Journal Article Games and Economic Behavior · September 1, 2009 For allocation problems with one or more items, the well-known Vickrey-Clarke-Groves (VCG) mechanism (aka Clarke mechanism, Generalized Vickrey Auction) is efficient, strategy-proof, individually rational, and does not incur a deficit. However, it is not ( ... Full text Cite

Who Benefits from Online Privacy?

Journal Article · August 15, 2009 Open Access Cite

Editor's puzzle

Journal Article ACM SIGecom Exchanges · July 2009 Full text Cite

A multiagent turing test based on a prediction market

Journal Article Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2009 Cite

Editorial Introductions

Other Current Opinion in Oncology · January 1, 2009 Cite

Prediction Markets, Mechanism Design, and Cooperative Game Theory.

Conference UAI · 2009 Cite

A multiagent Turing test based on a prediction market.

Conference AAMAS (2) · 2009 Cite

AAAI 2008 workshop reports

Journal Article AI Magazine · January 1, 2009 AAAI was pleased to present the AAAI-08 Workshop Program, held Sunday and Monday, July 13-14, in Chicago, Illinois, USA. The program included the following 15 workshops: Advancements in POMDP Solvers; AI Education Workshop Colloquium; Coordination, Organiz ... Full text Cite

Finite local consistency characterizes generalized scoring rules

Journal Article IJCAI International Joint Conference on Artificial Intelligence · January 1, 2009 An important problem in computational social choice concerns whether it is possible to prevent manipulation of voting rules by making it computationally intractable. To answer this, a key question is how frequently voting rules are manipulable. We [Xia and ... Cite

Prediction markets, mechanism design, and cooperative game theory

Journal Article Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, UAI 2009 · January 1, 2009 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 consi ... Cite

Complexity of unweighted coalitional manipulation under some common voting rules

Journal Article IJCAI International Joint Conference on Artificial Intelligence · January 1, 2009 Understanding the computational complexity of manipulation in elections is arguably the most central agenda in Computational Social Choice. One of the influential variations of the the problem involves a coalition of manipulators trying to make a favorite ... Cite

Multi-step multi-sensor hider-seeker games

Journal Article IJCAI International Joint Conference on Artificial Intelligence · January 1, 2009 We study a multi-step hider-seeker game where the hider is moving on a graph and, in each step, the seeker is able to search c subsets of the graph nodes. We model this game as a zero-sum Bayesian game, which can be solved in weakly polynomial time in the ... Cite

Preference functions that score rankings and maximum likelihood estimation

Journal Article IJCAI International Joint Conference on Artificial Intelligence · January 1, 2009 In social choice, a preference function (PF) takes a set of votes (linear orders over a set of alternatives) as input, and produces one or more rankings (also linear orders over the alternatives) as output. Such functions have many applications, for exampl ... Cite

How hard is it to control sequential elections via the agenda?

Journal Article IJCAI International Joint Conference on Artificial Intelligence · January 1, 2009 Voting on multiple related issues is an important and difficult problem. The key difficulty is that the number of alternatives is exponential in the number of issues, and hence it is infeasible for the agents to rank all the alternatives. A simple approach ... Cite

Eliciting single-peaked preferences using comparison queries

Journal Article Journal of Artificial Intelligence Research · January 1, 2009 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 thealternatives (or at least a winning alternative) is produced. However, when there a ... Full text Cite

Optimal false-name-proof voting rules with costly voting

Journal Article Proceedings of the National Conference on Artificial Intelligence · December 29, 2008 One way for agents to reach a joint decision is to vote over the alternatives. In open, anonymous settings such as the Internet, an agent can vote more than once without being detected. A voting rule is false-name-proof if no agent ever benefits from casti ... Cite

Voting on multiattribute domains with cyclic preferential dependencies

Journal Article Proceedings of the National Conference on Artificial Intelligence · December 24, 2008 In group decision making, often the agents need to decide on multiple attributes at the same time, so that there are exponentially many alternatives; In this case, it is unrealistic to ask agents to communicate a full ranking of all the alternatives. To ad ... Cite

Determining possible and necessary winners under common voting rules given partial orders

Journal Article Proceedings of the National Conference on Artificial Intelligence · December 24, 2008 Usually a voting rule or correspondence 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 o ... Cite

Metareasoning as a formal computational problem

Journal Article AAAI Workshop - Technical Report · December 1, 2008 Metareasoning research often lays out high-level principles, which are then applied in the context of larger systems. While this approach has proven quite successful, it sometimes obscures how metareasoning can be seen as a crisp computational problem in i ... Cite

An "ethical" game-theoretic solution concept for two-player perfect-information games

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · December 1, 2008 The standard solution concept for perfect-information extensive form games is subgame perfect Nash equilibrium. However, humans do not always play according to a subgame perfect Nash equilibrium, especially in games where it is possible for all the players ... Full text Cite

AAAI Workshop - Technical Report: Preface

Journal Article AAAI Workshop - Technical Report · December 1, 2008 Cite

Better redistribution with inefficient allocation in multi-unit auctions with unit demand

Journal Article Proceedings of the ACM Conference on Electronic Commerce · December 1, 2008 For the problem of allocating one or more items among a group of competing agents, the Vickrey-Clarke-Groves (VCG) mechanism is strategy-proof and efficient. However, the VCG mechanism is not strongly budget balanced: in general, value flows out of the sys ... Full text Cite

Anonymity-proof voting rules

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · December 1, 2008 A (randomized, anonymous) voting rule maps any multiset of total orders (aka. votes) over a fixed set of alternatives to a probability distribution over these alternatives. A voting rule f is false-name-proof if no voter ever benefits from casting more tha ... Full text Cite

Welfare undominated groves mechanisms

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · December 1, 2008 A common objective in mechanism design is to choose the outcome (for example, allocation of resources) that maximizes the sum of the agents' valuations, without introducing incentives for agents to misreport their preferences. The class of Groves mechanism ... Full text Cite

A sufficient condition for voting rules to be frequently manipulable

Journal Article Proceedings of the ACM Conference on Electronic Commerce · December 1, 2008 The Gibbard-Satterthwaite Theorem states that (in unrestricted settings) any reasonable voting rule is manipulable. Recently, a quantitative version of this theorem was proved by Ehud Friedgut, Gil Kalai, and Noam Nisan: when the number of alternatives is ... Full text Cite

Generalized scoring rules and the frequency of coalitional manipulability

Journal Article Proceedings of the ACM Conference on Electronic Commerce · December 1, 2008 We introduce a class of voting rules called generalized scoring rules. Under such a rule, each vote generates a vector of k scores, and the outcome of the voting rule is based only on the sum of these vectors - more specifically, only on the order (in term ... Full text Cite

Comparing multiagent systems research in combinatorial auctions and voting

Journal Article 10th International Symposium on Artificial Intelligence and Mathematics, ISAIM 2008 · December 1, 2008 In a combinatorial auction, a set of resources is for sale, and agents can bid on subsets of these resources. In a voting setting, the agents decide among a set of alternatives by having each agent rank all the alternatives. Many of the key research issues ... Cite

Editor's puzzle

Journal Article ACM SIGecom Exchanges · November 2008 Full text Cite

New complexity results about Nash equilibria

Journal Article Games and Economic Behavior · July 1, 2008 We provide a single reduction that demonstrates that in normal-form games: (1) it is NP-complete to determine whether Nash equilibria with certain natural properties exist (these results are similar to those obtained by Gilboa and Zemel [Gilboa, I., Zemel, ... Full text Cite

Editor's puzzle

Journal Article ACM SIGecom Exchanges · June 2008 Full text Cite

Structure-based protein NMR assignments using native structural ensembles.

Journal Article Journal of biomolecular NMR · April 2008 An important step in NMR protein structure determination is the assignment of resonances and NOEs to corresponding nuclei. Structure-based assignment (SBA) uses a model structure ("template") for the target protein to expedite this process. Nuclear vector ... Full text Cite

Undominated VCG redistribution mechanisms

Journal Article Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2008 Many important problems in multiagent systems can be seen as resource allocation problems. For such problems, the well-known Vickrey-Clarke-Groves (VCG) mechanism is efficient, incentive compatible, individually rational, and does not incur a deficit. Howe ... Cite

Optimal-in-expectation redistribution mechanisms

Journal Article Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2008 Many important problems in multiagent systems involve the allocation of multiple resources to multiple agents. If agents are self-interested, they will lie about their valuations for the resources if they perceive this to be in their interest. The well-kno ... Cite

Strategie betting for competitive agents

Journal Article Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2008 In many multiagent settings, each agent's goal is to come out ahead of the other agents on some metric, such as the currency obtained by the agent. In such settings, it is not appropriate for an agent to try to maximize its expected score on the metric; ra ... Cite

Anonymity-proof Shapley value: Extending Shapley value for coalitional games in open environments

Journal Article Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS · January 1, 2008 Coalition formation is an important capability for automated negotiation among self-interested agents. In order for coalitions to be stable, a key question that must be answered is how the gains from cooperation are to be distributed. Coalitional game theo ... Cite

Welfare Undominated Groves Mechanisms.

Conference WINE · 2008 Cite

Optimal-in-expectation redistribution mechanisms.

Conference AAMAS (2) · 2008 Cite

Strategic betting for competitive agents.

Conference AAMAS (2) · 2008 Cite

Undominated VCG redistribution mechanisms.

Conference AAMAS (2) · 2008 Cite

Anonymity-proof Shapley value: extending shapley value for coalitional games in open environments.

Conference AAMAS (2) · 2008 Cite

Worst-case optimal redistribution of VCG payments

Journal Article EC'07 - Proceedings of the Eighth Annual Conference on Electronic Commerce · December 3, 2007 For allocation problems with one or more items, the wellknown Vickrey-Clarke-Groves (VCG) mechanism is efficient, strategy-proof, individually rational, and does not incur a deficit. However, the VCG mechanism is not (strongly) budget balanced: generally, ... Full text Cite

Editor's puzzle

Journal Article ACM SIGecom Exchanges · December 2007 Full text Cite

Eliciting single-peaked preferences using comparison queries

Journal Article Proceedings of the International Conference on Autonomous Agents · December 1, 2007 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 ... Full text Cite

Limited verification of identities to induce false-name-proofness

Conference Proceedings of the 11th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2007 · December 1, 2007 In open, anonymous environments such as the Internet, mechanism design is complicated by the fact that a single agent can participate in the mechanism under multiple identifiers. One way to address this is to design false-name-proof mechanisms, which choos ... Full text Cite

Automated design of multistage mechanisms

Conference IJCAI International Joint Conference on Artificial Intelligence · December 1, 2007 Mechanism design is the study of preference aggregation protocols that work well in the face of self-interested agents. We present the first general-purpose techniques for automatically designing multistage mechanisms. These can reduce elicitation burden b ... Cite

Incremental mechanism design

Conference IJCAI International Joint Conference on Artificial Intelligence · December 1, 2007 Mechanism design has traditionally focused almost exclusively on the design of truthful mechanisms. There are several drawbacks to this: 1. in certain settings (e.g. voting settings), no desirable strategy-proof mechanisms exist; 2. truthful mechanisms are ... Cite

When are elections with few candidates hard to manipulate

Journal Article Journal of the ACM · June 1, 2007 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 coul ... Full text Cite

AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents

Journal Article Machine Learning · May 1, 2007 Two minimal requirements for a satisfactory multiagent learning algorithm are that it 1. learns to play optimally against stationary opponents and 2. converges to a Nash equilibrium in self-play. The previous algorithm that has come closest, WoLF-IGA, has ... Full text Cite

Limited Verification of Identities to Induce False-Name-Proofness

Conference Dagstuhl Seminar Proceedings · January 1, 2007 In open, anonymous environments such as the Internet, mechanism design is complicated by the fact that a single agent can participate in the mechanism under multiple identifiers. One way to address this is to design false-name-proof mechanisms, which choos ... Cite

Anonymity-Proof Voting Rules

Conference Dagstuhl Seminar Proceedings · January 1, 2007 A (randomized, anonymous) voting rule maps any multiset of total orders of (aka. votes over) a fixed set of alternatives to a probability distribution over these alternatives. A voting rule f is neutral if it treats all alternatives symmetrically. It satis ... Cite

Invited talk by winner of IFAAMAS Victor Lesser Distinguished Dissertation Award.

Conference AAMAS · 2007 Cite

A technique for reducing normal-form games to compute a nash equilibrium

Journal Article Proceedings of the International Conference on Autonomous Agents · December 1, 2006 We present a technique for reducing a normal-form (aka. (bi)matrix) game, O, to a smaller normal-form game, R, for the purpose of computing a Nash equilibrium. This is done by computing a Nash equilibrium for a subcomponent, G, of O for which a certain con ... Full text Cite

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

Journal Article ACM International Conference Proceeding Series · December 1, 2006 In a principal-agent problem, a principal seeks to motivate an agent to take a certain action beneficial to the principal, while spending as little as possible on the reward. This is complicated by the fact that the principal does not know the agent's util ... Full text Cite

Failures of the VCG mechanism in combinatorial auctions and exchanges

Journal Article Proceedings of the International Conference on Autonomous Agents · December 1, 2006 The VCG mechanism is the canonical method for motivating bidders in combinatorial auctions and exchanges to bid truthfully. We study two related problems concerning the VCG mechanism: the problem of revenue guarantees, and that of collusion. The existence ... Full text Cite

A compact representation scheme for coalitional games in open anonymous environments

Journal Article Proceedings of the National Conference on Artificial Intelligence · November 13, 2006 Coalition formation is an important capability of automated negotiation among self-interested agents. In order for coalitions to be stable, a key question that must be answered is how the gains from cooperation are to be distributed. Recent research has re ... Cite

Improved bounds for computing kemeny rankings

Journal Article Proceedings of the National Conference on Artificial Intelligence · November 13, 2006 Voting (or rank aggregation) is a general method for aggregating the preferences of multiple agents. One voting rule of particular interest is the Kemeny rule, which minimizes the number of cases where the final ranking disagrees with a vote on the order o ... Cite

Nonexistence of voting rules that are usually hard to manipulate

Journal Article Proceedings of the National Conference on Artificial Intelligence · November 13, 2006 Aggregating the preferences of self-interested agents is a key problem for multiagent systems, and one general method for doing so is to vote over the alternatives (candidates). Unfortunately, the Gibbard-Satterthwaite theorem shows that when there are thr ... Cite

Computing slater rankings using similarities among candidates

Journal Article Proceedings of the National Conference on Artificial Intelligence · November 13, 2006 Voting (or rank aggregation) is a general method for aggregating the preferences of multiple agents. One important voting rule is the Slater rule. It selects a ranking of the alternatives (or candidates) to minimize the number of pairs of candidates such t ... Cite

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

Journal Article ICML 2006 - Proceedings of the 23rd International Conference on Machine Learning · October 6, 2006 In a principal-agent problem, a principal seeks to motivate an agent to take a certain action beneficial to the principal, while spending as little as possible on the reward. This is complicated by the fact that the principal does not know the agent's util ... Cite

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

Journal Article Artificial Intelligence · May 1, 2006 Coalition formation is a key problem in automated negotiation among self-interested agents, and other multiagent applications. A coalition of agents can sometimes accomplish things that the individual agents cannot, or can accomplish them more efficiently. ... Full text Cite

Computing the optimal strategy to commit to

Journal Article Proceedings of the ACM Conference on Electronic Commerce · January 1, 2006 In multiagent systems, strategic settings are often analyzed under the assumption that the players choose their strategies simultaneously. However, this model is not always realistic. In many settings, one player is able to commit to a strategy before the ... Full text Cite

A new solution concept for coalitional games in open anonymous environments

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2006 Coalition formation is a key aspect of automated negotiation among self-interested agents. In order for coalitions to be stable, a key question that must be answered is how the gains from cooperation are to be distributed. Various solution concepts (such a ... Full text Cite

Revenue failures and collusion in combinatorial auctions and exchanges with VCG payments

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · December 1, 2005 In a combinatorial auction, there are multiple items for sale, and bidders are allowed to place a bid on a bundle of these items rather than just on the individual items. A key problem in this and similar settings is that of strategic bidding, where bidder ... Cite

Communication complexity of common voting rules

Journal Article Proceedings of the ACM Conference on Electronic Commerce · December 1, 2005 We determine the communication complexity of the common voting rules. The rules (sorted by their communication complexity from low to high) are plurality, plurality with runoff, single transferable vote (STV), Condorcet, approval, Bucklin, cup, maximin, Bo ... Full text Cite

Expressive negotiation in settings with externalities

Journal Article Proceedings of the National Conference on Artificial Intelligence · December 1, 2005 In recent years, certain formalizations of combinatorial negotiation settings, most notably combinatorial auctions, have become an important research topic in the AI community. A pervasive assumption has been that of no externalities: the agents deciding o ... Cite

Complexity of (iterated) dominance

Journal Article Proceedings of the ACM Conference on Electronic Commerce · December 1, 2005 We study various computational aspects of solving games using dominance and iterated dominance. We first study both strict and weak dominance (not iterated), and show that checking whether a given strategy is dominated by some mixed strategy can be done in ... Full text Cite

A generalized strategy eliminability criterion and computational methods for applying it

Journal Article Proceedings of the National Conference on Artificial Intelligence · December 1, 2005 We define a generalized strategy eliminability criterion for bimatrix games that considers whether a given strategy is eliminable relative to given dominator & eliminee subsets of the players' strategies. We show that this definition spans a spectrum of el ... Cite

Mixed-integer programming methods for finding Nash equilibria

Journal Article Proceedings of the National Conference on Artificial Intelligence · December 1, 2005 We present, to our knowledge, the first mixed integer program (MIP) formulations for finding Nash equilibria in games (specifically, two-player normal form games). We study different design dimensions of search algorithms that are based on those formulatio ... Cite

Computational aspects of mechanism design

Journal Article Proceedings of the National Conference on Artificial Intelligence · December 1, 2005 Cite

Combinatorial auctions with k-wise dependent valuations

Journal Article Proceedings of the National Conference on Artificial Intelligence · December 1, 2005 We analyze the computational and communication complexity of combinatorial auctions from a new perspective: the degree of interdependency between the items for sale in the bidders' preferences. Denoting by G k the class of valuations displaying up to k-wis ... Cite

Coalitional games in open anonymous environments

Journal Article Proceedings of the National Conference on Artificial Intelligence · December 1, 2005 Coalition formation is a key aspect of automated negotiation among self-interested agents. In order for coalitions to be stable, a key question that must be answered is how the gains from cooperation are to be distributed. Various solution concepts (such a ... Cite

Coalitional games in open anonymous environments

Conference IJCAI International Joint Conference on Artificial Intelligence · December 1, 2005 Cite

Common voting rules as maximum likelihood estimators

Journal Article Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence, UAI 2005 · January 1, 2005 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 potentia ... Cite

Computing shapley values, manipulating value division schemes, and checking core membership in multi-issue domains

Journal Article Proceedings of the National Conference on Artificial Intelligence · December 13, 2004 Coalition formation is a key problem in automated negotiation among self-interested agents. In order for coalition formation to be successful, a key question that must be answered is how the gains from cooperation are to be distributed. Various solution co ... Cite

Combinatorial auctions with structured item graphs

Journal Article Proceedings of the National Conference on Artificial Intelligence · December 9, 2004 Combinatorial auctions (CAs) are important mechanisms for allocating interrelated items. Unfortunately, winner determination is NP-complete unless there is special structure. We study the setting where there is a graph (with some desired property), with th ... Cite

Communication complexity as a lower bound for learning in games

Journal Article Proceedings, Twenty-First International Conference on Machine Learning, ICML 2004 · December 1, 2004 A fast-growing body of research in the AI and machine learning communities addresses learning in games, where there are multiple learners with different interests. This research adds to more established research on learning in games conducted in economics. ... Cite

An algorithm for automatically designing deterministic mechanisms without payments

Journal Article Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 2004 · September 27, 2004 Mechanism design is the art of designing the rules of the game so that a desirable outcome is reached even though the agents in the game behave selfishly. This is a difficult problem because the designer is uncertain about the agents' preferences and the a ... Cite

Towards a characterization of polynomial preference elicitation with value queries in combinatorial auctions

Journal Article Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science) · January 1, 2004 Communication complexity has recently been recognized as a major obstacle in the implementation of combinatorial auctions. In this paper, we consider a setting in which the auctioneer (elicitor), instead of passively waiting for the bids presented by the b ... Full text Cite

Revenue failures and collusion in combinatorial auctions and exchanges with VCG payments

Journal Article Proceedings of the ACM Conference on Electronic Commerce · January 1, 2004 Full text Cite

Self-interested automated mechanism design and implications for optimal combinatorial auctions

Journal Article Proceedings of the ACM Conference on Electronic Commerce · January 1, 2004 Often, an outcome must be chosen on the basis of the preferences reported by a group of agents. The key difficulty is that the agents may report their preferences insincerely to make the chosen outcome more favorable to themselves. Mechanism design is the ... Full text Cite

Expressive negotiation over donations to charities

Journal Article Proceedings of the ACM Conference on Electronic Commerce · January 1, 2004 When donating money to a (say, charitable) cause, it is possible to use the contemplated donation as negotiating material to induce other parties interested in the charity to donate more. Such negotiation is usually done in terms of matching offers, where ... Full text Cite

Computational criticisms of the revelation principle

Journal Article Proceedings of the ACM Conference on Electronic Commerce · January 1, 2004 Full text Cite

Automated Mechanism Design: Complexity Results Stemming from the Single-Agent Setting

Journal Article Proceedings of the ACM Conference on Electronic Commerce · December 1, 2003 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 mot ... Cite

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

Journal Article Proceedings, Twentieth International Conference on Machine Learning · December 1, 2003 A satisfactory multiagent learning algorithm should, 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 proper ... Cite

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

Journal Article Proceedings, Twentieth International Conference on Machine Learning · December 1, 2003 We present BL-WoLF, a framework for learnability in repeated zero-sum games where the cost of learning is measured by the losses the learning agent accrues (rather than the number of rounds). The game is adversarially chosen from some family that the learn ... Cite

Complexity of determining nonemptiness of the core

Journal Article IJCAI International Joint Conference on Artificial Intelligence · December 1, 2003 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. Howev ... Cite

Automated mechanism design: Complexity results stemming from the single-agent setting

Journal Article ACM International Conference Proceeding Series · December 1, 2003 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 mot ... Full text Cite

Complexity results about Nash equilibria

Journal Article IJCAI International Joint Conference on Artificial Intelligence · December 1, 2003 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 ... Cite

Definition and complexity of some basic metareasoning problems

Journal Article IJCAI International Joint Conference on Artificial Intelligence · December 1, 2003 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 method ... Cite

Universal voting protocol tweaks to make manipulation hard

Journal Article IJCAI International Joint Conference on Artificial Intelligence · December 1, 2003 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 benef ... Cite

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

Journal Article Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2003 · June 20, 2003 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 coul ... Full text Cite

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

Conference TARK · 2003 Cite

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

Conference ICML · 2003 Cite

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

Conference ICML · 2003 Cite

Definition and Complexity of Some Basic Metareasoning Problems.

Conference IJCAI · 2003 Cite

Universal Voting Protocol Tweaks to Make Manipulation Hard.

Conference IJCAI · 2003 Cite

Automated mechanism design for a self-interested designer

Journal Article Proceedings of the ACM Conference on Electronic Commerce · January 1, 2003 Often, an outcome must be chosen on the basis of the preferences reported by a group of agents. The key difficulty is that the agents may report their preferences insincerely to make the chosen outcome more favorable to themselves. Mechanism design is the ... Full text Cite

Complexity of determining nonemptiness of the core

Conference Proceedings of the ACM Conference on Electronic Commerce · January 1, 2003 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 efficient ... Full text Cite

Complexity of determining nonemptiness of the core

Conference IJCAI International Joint Conference on Artificial Intelligence · 2003 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. Howev ... Cite

Complexity of manipulating elections with few candidates

Journal Article Proceedings of the National Conference on Artificial Intelligence · December 1, 2002 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 coul ... Cite

Vote elicitation: Complexity and strategy-proofness

Journal Article Proceedings of the National Conference on Artificial Intelligence · December 1, 2002 Preference elicitation is a central problem in AI, and has received significant attention in single-agent settings. It is also a key problem in multiagent systems, but has received little attention here so far. In this setting, the agents may have differen ... Cite

Complexity of Mechanism Design

Journal Article Proceedings of the 18th Annual Conference on Uncertainty in Artificial Intelligence (UAI-02), Edmonton, Canada, 2002 · May 28, 2002 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 mot ... Link to item Cite

Vote Elicitation: Complexity and Strategy-Proofness.

Conference AAAI/IAAI · 2002 Cite

Complexity of Manipulating Elections with Few Candidates.

Conference AAAI/IAAI · 2002 Cite

Complexity Results about Nash Equilibria

Journal Article CoRR · 2002 Cite

Editor's Introduction

Journal Article Journal of Soviet Nationalities · March 1990 Cite

Editors' introduction

Journal Article Journal of Econometrics · January 1, 1990 Full text Cite

Moral Decision Making Frameworks for Artificial Intelligence

Conference The generality of decision and game theory has enabled domain-independent progress in AI research. For example, a better algorithm for finding good policies in (PO)MDPs can be instantly used in a variety of applications. But such a general theory is lackin ... Cite