Kate Larson

AAMAS Conference 2026 Conference Paper

Active Evaluation of General Agents: Problem Definition and Comparison of Baseline Algorithms

• Marc Lanctot
• Kate Larson
• Ian Gemp
• Michael Kaisers

As intelligent agents become more generally-capable, i. e. , able to master a wide variety of tasks, the complexity and cost of properly evaluating them rises significantly. Tasks that assess specific capabilities of the agents can be correlated and stochastic, requiring many samples for accurate comparisons, leading to added costs. In this paper, we propose a formal definition and a conceptual framework for active evaluation of agents across multiple tasks, which assesses the performance of ranking algorithms as a function of number of evaluation data samples. Rather than curating, filtering, or compressing existing data sets as a preprocessing step, we propose an online framing: on every iteration, the ranking algorithm chooses the task and agents to sample scores from. Then, evaluation algorithms report a ranking of agents on each iteration and their performance is assessed with respect to the ground truth ranking over time. Several baselines are compared under different experimental contexts, with synthetic generated data and simulated online access to real evaluation data from Atari game-playing agents. We find that the classical Elo rating system– while it suffers from well-known failure modes, in theory– is a consistently reliable choice for efficient reduction of ranking error in practice. A recently-proposed method, Soft Condorcet Optimization, shows comparable performance to Elo on synthetic data and significantly outperformsEloonrealAtariagentevaluation. Whentaskvariation from the ground truth is high, selecting tasks based on proportional representation leads to higher rate of ranking error reduction.

AAMAS Conference 2026 Conference Paper

Generating Fair Consensus Statements with Social Choice on Token-Level MDPs

• Carter Blair
• Kate Larson

Current frameworks for aggregating free-form text-based opinions with large language models lack the inherent structure needed to provide meaningful fairness guarantees. To address this, we model the task as a multi-objective, token-level Markov Decision Process (MDP), where each objective corresponds to an agent’s preference. Each agent’s token-level reward is induced by its policy (e. g. , a personalized language model). Such policies implicitly define optimal Q-functions, thus enabling stepwise reward computation without an explicit value function [18]. This MDP formulation yields a formal structure that can be analyzed with tools from social choice theory. We first give a stochastic generation policy that is guaranteed to lie in the ex-ante core. It is derived from a distribution over complete statements that maximizes Nash welfare, extending core stability from cooperative game theory and voting to text generation. Second, for a single consensus statement, we target egalitarian welfare and use search within the MDP. Empirically, this search produces statements with improved worst-case agent alignment compared with baselines, including the Habermas Machine [24]. Our code is available here and supplementary material (the appendix) is available here.

AAMAS Conference 2026 Conference Paper

Procedural Fairness in Multi-Agent Bandits

• Joshua Caiata
• Carter Blair
• Kate Larson

In the context of multi-agent multi-armed bandits (MA-MAB), fairness is often reduced to outcomes: maximizing welfare, reducing inequality, or balancing utilities. However, evidence in psychology, economics, and Rawlsian theory suggests that fairness is also about process and who gets a say in the decisions being made. We introduce a new fairness objective, procedural fairness, which provides equaldecision-makingpowerforallagents, liesinthecore, andprovidesforproportionalityinoutcomes. Empiricalresultsconfirmthat fairness notions based on optimizing for outcomes sacrifice equal voice and representation, while the sacrifice in outcome-based fairness objectives (like equality and utilitarianism) is minimal under procedurally fair policies. This paper argues that procedural legitimacy deserves greater focus as a fairness objective, and provides a framework for putting procedural fairness into practice.

AAAI Conference 2026 Conference Paper

The Alignment Game: A Theory of Long-Horizon Alignment Through Recursive Curation

• Ali Falahati
• Mohammad Mohammadi Amiri
• Kate Larson
• Lukasz Golab

In self-consuming generative models that train on their own outputs, alignment with user preferences becomes a recursive rather than one-time process. In this paper, we provide the first formal foundation for analyzing the long-term effects of such recursive retraining on alignment. Under a two-stage curation mechanism based on the Bradley–Terry (BT) model, we model alignment as an interaction between two factions: the Model Owner, who filters which outputs should be learned by the model, and the Public User, who determines which outputs are ultimately shared and retained through interactions with the model. Our analysis reveals three structural convergence regimes: consensus collapse, compromise on shared optima, and asymmetric refinement, depending on the degree of preference alignment. We prove a fundamental impossibility theorem: no recursive BT-based curation mechanism can simultaneously preserve diversity, ensure symmetric influence, and eliminate dependence on initialization. Framing the process as dynamic social choice, we show that alignment is not a static goal but an evolving equilibrium shaped by power asymmetries and path dependence.

AAAI Conference 2026 Conference Paper

What Voting Rules Actually Do: A Data-Driven Analysis of Multi-Winner Voting

• Joshua Caiata
• Ben Armstrong
• Kate Larson

Committee-selection problems arise in many contexts and applications, and there has been increasing interest within the social choice research community on identifying which properties are satisfied by different multi-winner voting rules. In this work, we propose a data-driven framework to evaluate how frequently voting rules violate axioms across diverse preference distributions in practice, shifting away from the binary perspective of axiom satisfaction given by worst-case analysis. Using this framework, we analyze the relationship between multi-winner voting rules and their axiomatic performance under several preference distributions, and propose a methodology for systematically minimizing axioms violations. Our results suggest that data-driven approaches to social choice can inform the design of new voting systems and support the continuation of data-driven research in social choice.

IJCAI Conference 2025 Conference Paper

Combining Deep Reinforcement Learning and Search with Generative Models for Game-Theoretic Opponent Modeling

• Zun Li
• Marc Lanctot
• Kevin R. McKee
• Luke Marris
• Ian Gemp
• Daniel Hennes
• Paul Muller
• Kate Larson

Opponent modeling methods typically involve two crucial steps: building a belief distribution over opponents' strategies, and exploiting this opponent model by playing a best response. However, existing approaches typically require domain-specific heurstics to come up with such a model, and algorithms for approximating best responses are hard to scale in large, imperfect information domains. In this work, we introduce a scalable and generic multiagent training regime for opponent modeling using deep game-theoretic reinforcement learning. We first propose Generative Best Respoonse (GenBR), a best response algorithm based on Monte-Carlo Tree Search (MCTS) with a learned deep generative model that samples world states during planning. This new method scales to large imperfect information domains and can be plug and play in a variety of multiagent algorithms. We use this new method under the framework of Policy Space Response Oracles (PSRO), to automate the generation of an offline opponent model via iterative game-theoretic reasoning and population-based training. We propose using solution concepts based on bargaining theory to build up an opponent mixture, which we find identifying profiles that are near the Pareto frontier. Then GenBR keeps updating an online opponent model and reacts against it during gameplay. We conduct behavioral studies where human participants negotiate with our agents in Deal-or-No-Deal, a class of bilateral bargaining games. Search with generative modeling finds stronger policies during both training time and test time, enables online Bayesian co-player prediction, and can produce agents that achieve comparable social welfare and Nash bargaining score negotiating with humans as humans trading among themselves.

AAMAS Conference 2025 Conference Paper

Game of Thoughts: Iterative Reasoning in Game-Theoretic Domains with Large Language Models

• Benjamin Kempinski
• Ian Gemp
• Kate Larson
• Marc Lanctot
• Yoram Bachrach
• Tal Kachman

We explore the strategic reasoning capabilities of large language models (LLMs). We first show that naively allowing LLMs to select actions in games can lead to sub-optimal and easily exploitable strategies. To address this limitation we propose several algorithms that guide LLMs to iteratively refine their action choices by simulating game outcomes in self-play, akin to cognitive hierarchy models used to characterize human thought processes in strategic settings. Our empirical results in several prominent resource allocation and auction settings indicate that our approach produces stronger and less exploitable strategies. Hence, emulating human decision-making models can enable us to improve the reasoning capabilities of LLMs in multiagent interactions.

IJCAI Conference 2025 Conference Paper

Reflective Verbal Reward Design for Pluralistic Alignment

• Carter Blair
• Kate Larson
• Edith Law

AI agents are commonly aligned with "human values" through reinforcement learning from human feedback (RLHF), where a single reward model is learned from aggregated human feedback and used to align an agent's behavior. However, human values are not homogeneous--different people hold distinct and sometimes conflicting values. Aggregating feedback into a single reward model risks disproportionately suppressing minority preferences. To address this, we present a novel reward modeling approach for learning individualized reward models. Our approach uses a language model to guide users through reflective dialogues where they critique agent behavior and construct their preferences. This personalized dialogue history, containing the user's reflections and critiqued examples, is then used as context for another language model that serves as an individualized reward function (what we call a "verbal reward model") for evaluating new trajectories. In studies with 30 participants, our method achieved a 9-12% improvement in accuracy over non-reflective verbal reward models while being more sample efficient than traditional supervised learning methods.

AAMAS Conference 2025 Conference Paper

Soft Condorcet Optimization for Ranking of General Agents

• Marc Lanctot
• Kate Larson
• Michael Kaisers
• Quentin Berthet
• Ian Gemp
• Manfred Diaz
• Roberto-Rafael Maura-Rivero
• Yoram Bachrach

Driving progress of AI models and agents requires comparing their performance on standardized benchmarks; for general agents, individual performances must be aggregated across a potentially wide variety of different tasks. In this paper, we describe a novel ranking scheme inspired by social choice frameworks, called Soft Condorcet Optimization (SCO), to compute the optimal ranking of agents: the one that makes the fewest mistakes in predicting the agent comparisons in the evaluation data. This optimal ranking is the maximum likelihood estimate when evaluation data (which we view as votes) are interpreted as noisy samples from a ground truth ranking, a solution to Condorcet’s original voting system criteria. SCO ratings are maximal for Condorcet winners when they exist, which we show is not necessarily true for the classical rating system Elo. We propose three optimization algorithms to compute SCO ratings and evaluate their empirical performance. When serving as an approximation to the Kemeny-Young voting method, SCO rankings are on average 0 to 0. 043 away from the optimal ranking in normalized Kendall-tau distance across 865 preference profiles from the PrefLib open ranking archive. In a simulated noisy tournament setting, SCO achieves accurate approximations to the ground truth ranking and the best among several baselines when 59% or more of the preference data is missing. Finally, SCO ranking provides the best approximation to the optimal ranking, measured on held-out test sets, in a problem containing 52, 958 human players across 31, 049 games of the classic seven-player game of Diplomacy.

AAMAS Conference 2024 Conference Paper

Approximating the Core via Iterative Coalition Sampling

• Ian Gemp
• Marc Lanctot
• Luke Marris
• Yiran Mao
• Edgar Duéñez-Guzmán
• Sarah Perrin
• Andras Gyorgy
• Romuald Elie

The core is a central solution concept in cooperative game theory, defined as the set of feasible allocations or payments such that no subset of agents has incentive to break away and form their own subgroup or coalition. However, it has long been known that the core (and approximations, such as the least-core) are hard to compute. This limits our ability to analyze cooperative games in general, and to fully embrace cooperative game theory contributions in domains such as explainable AI (XAI), where the core can complement the Shapley values to identify influential features or instances supporting predictions by black-box models. We propose novel iterative algorithms for computing variants of the core, which avoid the computational bottleneck of many other approaches; namely solving large linear programs. As such, they scale better to very large problems as we demonstrate across different classes of cooperative games, including weighted voting games, induced subgraph games, and marginal contribution networks. We also explore our algorithms in the context of XAI, providing further evidence of the power of the core for such applications. This work is licensed under a Creative Commons Attribution International 4. 0 License. Proc. of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2024), N. Alechina, V. Dignum, M. Dastani, J. S. Sichman (eds.), May 6 – 10, 2024, Auckland, New Zealand. © 2024 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org).

AAMAS Conference 2024 Conference Paper

Liquid Democracy for Low-Cost Ensemble Pruning

• Ben Armstrong
• Kate Larson

We show that there is a strong connection between ensemble learning and a delegative voting paradigm, liquid democracy, which can be leveraged to reduce ensemble training costs. We present an incremental training procedure that removes redundant classifiers from an ensemble via delegation. By carefully selecting the underlying delegation mechanism weight-centralization among classifiers is avoided, leading to higher accuracy than some boosting methods with a significantly lower cost than training a full ensemble. This work serves as an exemplar of how ideas from computational social choice can be applied to problems in nontraditional domains.

IJCAI Conference 2023 Conference Paper

Deliberation and Voting in Approval-Based Multi-Winner Elections

• Kanav Mehra
• Nanda Kishore Sreenivas
• Kate Larson

Citizen-focused democratic processes where participants deliberate on alternatives and then vote to make the final decision are increasingly popular today. While the computational social choice literature has extensively investigated voting rules, there is limited work that explicitly looks at the interplay of the deliberative process and voting. In this paper, we build a deliberation model using established models from the opinion-dynamics literature and study the effect of different deliberation mechanisms on voting outcomes achieved when using well-studied voting rules. Our results show that deliberation generally improves welfare and representation guarantees, but the results are sensitive to how the deliberation process is organized. We also show, experimentally, that simple voting rules, such as approval voting, perform as well as more sophisticated rules such as proportional approval voting or method of equal shares if deliberation is properly supported. This has ramifications on the practical use of such voting rules in citizen-focused democratic processes.

AAMAS Conference 2023 Conference Paper

Learning from Multiple Independent Advisors in Multi-agent Reinforcement Learning

• Sriram Ganapathi Subramanian
• Matthew E. Taylor
• Kate Larson
• Mark Crowley

Multi-agent reinforcement learning typically suffers from the problem of sample inefficiency, where learning suitable policies involves the use of many data samples. Learning from external demonstrators is a possible solution that mitigates this problem. However, most prior approaches in this area assume the presence of a single demonstrator. Leveraging multiple knowledge sources (i. e. , advisors) with expertise in distinct aspects of the environment could substantially speed up learning in complex environments. This paper considers the problem of simultaneously learning from multiple independent advisors in multi-agent reinforcement learning. The approach leverages a two-level Q-learning architecture, and extends this framework from single-agent to multi-agent settings. We provide principled algorithms that incorporate a set of advisors by both evaluating the advisors at each state and subsequently using the advisors to guide action selection. We also provide theoretical convergence and sample complexity guarantees. Experimentally, we validate our approach in three different test-beds and show that our algorithms give better performances than baselines, can effectively integrate the combined expertise of different advisors, and learn to ignore bad advice.

IJCAI Conference 2023 Conference Paper

Multi-Agent Advisor Q-Learning (Extended Abstract)

• Sriram Ganapathi Subramanian
• Matthew E. Taylor
• Kate Larson
• Mark Crowley

In the last decade, there have been significant advances in multi-agent reinforcement learning (MARL) but there are still numerous challenges, such as high sample complexity and slow convergence to stable policies, that need to be overcome before wide-spread deployment is possible. However, many real-world environments already, in practice, deploy sub-optimal or heuristic approaches for generating policies. An interesting question that arises is how to best use such approaches as advisors to help improve reinforcement learning in multi-agent domains. We provide a principled framework for incorporating action recommendations from online sub-optimal advisors in multi-agent settings. We describe the problem of ADvising Multiple Intelligent Reinforcement Agents (ADMIRAL) in nonrestrictive general-sum stochastic game environments and present two novel Q-learning-based algorithms: ADMIRAL - Decision Making (ADMIRAL-DM) and ADMIRAL - Advisor Evaluation (ADMIRAL-AE), which allow us to improve learning by appropriately incorporating advice from an advisor (ADMIRAL-DM), and evaluate the effectiveness of an advisor (ADMIRAL-AE). We analyze the algorithms theoretically and provide fixed point guarantees regarding their learning in general-sum stochastic games. Furthermore, extensive experiments illustrate that these algorithms: can be used in a variety of environments, have performances that compare favourably to other related baselines, can scale to large state-action spaces, and are robust to poor advice from advisors.

AAMAS Conference 2023 Conference Paper

Revealed Multi-Objective Utility Aggregation in Human Driving

• Atrisha Sarkar
• Kate Larson
• Krzysztof Czarnecki

A central design problem in game theoretic analysis is the estimation of the players’ utilities. In many real-world interactive situations of human decision making, including human driving, the utilities are multi-objective in nature; therefore, estimating the parameters of aggregation, i. e. , mapping of multi-objective utilities to a scalar value, becomes an essential part of game construction. However, estimating this parameter from observational data introduces several challenges due to a host of unobservable factors, including the underlying modality of aggregation and the possibly boundedly rational behaviour model that generated the observation. Based on the concept of rationalisability, we develop algorithms for estimating multi-objective aggregation parameters for two common aggregation methods, weighted and satisficing aggregation, and for both strategic and non-strategic reasoning models. Based on three different datasets, we provide insights into how human drivers aggregate the utilities of safety and progress, as well as the situational dependence of the aggregation process. Additionally, we show that irrespective of the specific solution concept used for solving the games, a data-driven estimation of utility aggregation significantly improves the predictive accuracy of behaviour models with respect to observed human behaviour.

AAMAS Conference 2023 Conference Paper

Search-Improved Game-Theoretic Multiagent Reinforcement Learning in General and Negotiation Games

• Zun Li
• Marc Lanctot
• Kevin R. McKee
• Luke Marris
• Ian Gemp
• Daniel Hennes
• Kate Larson
• Yoram Bachrach

Multiagent reinforcement learning (MARL) has benefited significantly from population-based and game-theoretic training regimes. One approach, Policy-Space Response Oracles (PSRO), employs standard reinforcement learning to compute response policies via approximate best responses and combines them via meta-strategy selection. We augment PSRO by adding a novel search procedure with generative sampling of world states, and introduce two new meta-strategy solvers based on the Nash bargaining solution. We evaluate PSRO’s ability to compute approximate Nash equilibrium, and its performance in negotiation games: Colored Trails and Dealor-no-Deal. We conduct behavioral studies where human participants negotiate with our agents (𝑁 = 346). Search with generative modeling finds stronger policies during both training time and test time, enables online Bayesian co-player prediction, and can produce agents that achieve comparable social welfare negotiating with humans as humans trading among themselves.

AAMAS Conference 2023 Conference Paper

The Importance of Credo in Multiagent Learning

• David Radke
• Kate Larson
• Tim Brecht

We propose a model for multi-objective optimization, a credo, for agents in a system that are configured into multiple groups (i. e. , teams). Our model of credo regulates how agents optimize their behavior for the groups they belong to. We evaluate credo in the context of challenging social dilemmas with reinforcement learning agents. Our results indicate that the interests of teammates, or the entire system, are not required to be fully aligned for achieving globally beneficial outcomes. We identify two scenarios without full common interest that achieve high equality and significantly higher mean population rewards compared to when the interests of all agents are aligned.

IJCAI Conference 2023 Conference Paper

Towards a Better Understanding of Learning with Multiagent Teams

• David Radke
• Kate Larson
• Tim Brecht
• Kyle Tilbury

While it has long been recognized that a team of individual learning agents can be greater than the sum of its parts, recent work has shown that larger teams are not necessarily more effective than smaller ones. In this paper, we study why and under which conditions certain team structures promote effective learning for a population of individual learning agents. We show that, depending on the environment, some team structures help agents learn to specialize into specific roles, resulting in more favorable global results. However, large teams create credit assignment challenges that reduce coordination, leading to large teams performing poorly compared to smaller ones. We support our conclusions with both theoretical analysis and empirical results.

IJCAI Conference 2022 Conference Paper

Exploring the Benefits of Teams in Multiagent Learning

• David Radke
• Kate Larson
• Tim Brecht

For problems requiring cooperation, many multiagent systems implement solutions among either individual agents or across an entire population towards a common goal. Multiagent teams are primarily studied when in conflict; however, organizational psychology (OP) highlights the benefits of teams among human populations for learning how to coordinate and cooperate. In this paper, we propose a new model of multiagent teams for reinforcement learning (RL) agents inspired by OP and early work on teams in artificial intelligence. We validate our model using complex social dilemmas that are popular in recent multiagent RL and find that agents divided into teams develop cooperative pro-social policies despite incentives to not cooperate. Furthermore, agents are better able to coordinate and learn emergent roles within their teams and achieve higher rewards compared to when the interests of all agents are aligned.

AAAI Conference 2022 Conference Paper

Generalized Dynamic Cognitive Hierarchy Models for Strategic Driving Behavior

• Atrisha Sarkar
• Kate Larson
• Krzysztof Czarnecki

While there has been an increasing focus on the use of game theoretic models for autonomous driving, empirical evidence shows that there are still open questions around dealing with the challenges of common knowledge assumptions as well as modeling bounded rationality. To address some of these practical challenges, we develop a framework of generalized dynamic cognitive hierarchy for both modelling naturalistic human driving behavior as well as behavior planning for autonomous vehicles (AV). This framework is built upon a rich model of level-0 behavior through the use of automata strategies, an interpretable notion of bounded rationality through safety and maneuver satisficing, and a robust response for planning. Based on evaluation on two large naturalistic datasets as well as simulation of critical traffic scenarios, we show that i) automata strategies are well suited for level-0 behavior in a dynamic level-k framework, and ii) the proposed robust response to a heterogeneous population of strategic and non-strategic reasoners can be an effective approach for game theoretic planning in AV.

IJCAI Conference 2022 Conference Paper

How Should We Vote? A Comparison of Voting Systems within Social Networks

• Shiri Alouf-Heffetz
• Ben Armstrong
• Kate Larson
• Nimrod Talmon

Voting is a crucial methodology for eliciting and combining agents' preferences and information across many applications. Just as there are numerous voting rules exhibiting different properties, we also see many different voting systems. In this paper we investigate how different voting systems perform as a function of the characteristics of the underlying voting population and social network. In particular, we compare direct democracy, liquid democracy, and sortition in a ground truth voting context. Through simulations -- using both real and artificially generated social networks -- we illustrate how voter competency distributions and levels of direct participation affect group accuracy differently in each voting mechanism. Our results can be used to guide the selection of a suitable voting system based on the characteristics of a particular voting setting.

JAIR Journal 2022 Journal Article

Multi-Agent Advisor Q-Learning

• Sriram Ganapathi Subramanian
• Matthew E. Taylor
• Kate Larson
• Mark Crowley

In the last decade, there have been significant advances in multi-agent reinforcement learning (MARL) but there are still numerous challenges, such as high sample complexity and slow convergence to stable policies, that need to be overcome before wide-spread deployment is possible. However, many real-world environments already, in practice, deploy sub-optimal or heuristic approaches for generating policies. An interesting question that arises is how to best use such approaches as advisors to help improve reinforcement learning in multi-agent domains. In this paper, we provide a principled framework for incorporating action recommendations from online suboptimal advisors in multi-agent settings. We describe the problem of ADvising Multiple Intelligent Reinforcement Agents (ADMIRAL) in nonrestrictive general-sum stochastic game environments and present two novel Q-learning based algorithms: ADMIRAL - Decision Making (ADMIRAL-DM) and ADMIRAL - Advisor Evaluation (ADMIRAL-AE), which allow us to improve learning by appropriately incorporating advice from an advisor (ADMIRAL-DM), and evaluate the effectiveness of an advisor (ADMIRAL-AE). We analyze the algorithms theoretically and provide fixed point guarantees regarding their learning in general-sum stochastic games. Furthermore, extensive experiments illustrate that these algorithms: can be used in a variety of environments, have performances that compare favourably to other related baselines, can scale to large state-action spaces, and are robust to poor advice from advisors.

IJCAI Conference 2021 Conference Paper

Improving Welfare in One-Sided Matchings using Simple Threshold Queries

• Thomas Ma
• Vijay Menon
• Kate Larson

We study one-sided matching problems where each agent must be assigned at most one object. In this classic problem it is often assumed that agents specify only ordinal preferences over objects and the goal is to return a matching that satisfies some desirable property such as Pareto optimality or rank-maximality. However, agents may have cardinal utilities describing their preference intensities and ignoring this can result in welfare loss. We investigate how to elicit additional cardinal information from agents using simple threshold queries and use it in turn to design algorithms that return a matching satisfying a desirable matching property, while also achieving a good approximation to the optimal welfare among all matchings satisfying that property. Overall, our results show how one can improve welfare by even non-adaptively asking agents for just one bit of extra information per object.

AIJ Journal 2019 Journal Article

Empathetic decision making in social networks

• Amirali Salehi-Abari
• Craig Boutilier
• Kate Larson

Social networks play a central role in the transactions and decision making of individuals by correlating the behaviors and preferences of connected agents. We introduce a notion of empathy in social networks, in which individuals derive utility based on both their own intrinsic preferences, and empathetic preferences determined by the satisfaction of their neighbors in the network. After theoretically analyzing the properties of our empathetic framework, we study the problem of group recommendation, or consensus decision making, within this framework. We show how this problem translates into a weighted form of classical preference aggregation (e. g. , social welfare maximization or certain forms of voting), and develop scalable optimization algorithms for this task. Furthermore, we show that our framework can be generalized to encompass other multiagent systems problems, such as constrained resource allocation, and provide scalable iterative algorithms for these generalizations. Our empirical experiments demonstrate the value of accounting for empathetic preferences in group decisions, and the tractability of our algorithms.

AAMAS Conference 2019 Conference Paper

Multiple Assignment Problems under Lexicographic Preferences

• Hadi Hosseini
• Kate Larson

We study the problem of allocating multiple objects to agents without transferable utilities, where each agent may receive more than one object according to a quota. Under lexicographic preferences, we characterize the set of strategyproof, non-bossy, and neutral quota mechanisms and show that under a mild Pareto efficiency condition, serial dictatorship quota mechanisms are the only mechanisms satisfying these properties. We then extend quota mechanisms to randomized settings, and show that the random serial dictatorship quota mechanisms (RSDQ) are envyfree, strategyproof, and ex post efficient for any number of agents and objects and any quota system, proving that the well-studied Random Serial Dictatorship (RSD) satisfies envyfreeness when preferences are lexicographic.

AAMAS Conference 2018 Conference Paper

Boundedly Rational Voters in Large(r) Networks

• Alan Tsang
• Amirali Salehi-Abari
• Kate Larson

In Iterative Voting, voters first cast their ballots but may change their minds upon observing the ballots of others. Previous models have extended Iterative Voting to the incomplete information domain of social networks, where voters only observe the ballots of their friends. However, these models are based on computationallyintensive calculations of expected utilities. We propose a framework of bounded rationality for voters situated in social networks. Using this framework, we propose and test a number of heuristics that reduce the computation required for optimal strategic reasoning by several orders of magnitude compared to previous work, while retaining similar qualitative behaviors. These heuristics enable us to conduct simulations on how the size of the voting population affects strategic behavior. To illustrate the effectiveness of our approach, we apply our heuristics to explore the Micromega rule — an observation in political science that large political parties favor small assemblies. We find that the size of electoral districts is a contributing factor to the Micromega rule in some networks. Fringe candidates retain more support in smaller districts, while larger parties dominate in larger districts.

JAAMAS Journal 2018 Journal Article

Investigating the characteristics of one-sided matching mechanisms under various preferences and risk attitudes

• Hadi Hosseini
• Kate Larson
• Robin Cohen

Abstract One-sided matching mechanisms are fundamental for assigning a set of indivisible objects to a set of self-interested agents when monetary transfers are not allowed. Two widely-studied randomized mechanisms in multiagent settings are the Random Serial Dictatorship (RSD) and the Probabilistic Serial Rule (PS). Both mechanisms require only that agents specify ordinal preferences and have a number of desirable economic and computational properties. However, the induced outcomes of the mechanisms are often incomparable and thus there are challenges when it comes to deciding which mechanism to adopt in practice. In this paper, we first consider the space of general ordinal preferences and provide empirical results on the (in)comparability of RSD and PS. We analyze their respective economic properties under general and lexicographic preferences. We then instantiate utility functions with the goal of gaining insights on the manipulability, efficiency, and envyfreeness of the mechanisms under different risk-attitude models. Our results hold under various preference distribution models, which further confirm the broad use of RSD in most practical applications.

JAAMAS Journal 2017 Journal Article

Computational aspects of strategic behaviour in elections with top-truncated ballots

• Vijay Menon
• Kate Larson

Abstract Understanding when and how computational complexity can be used to protect elections against different manipulative actions has been a highly active research area over the past two decades. Much of this literature, however, makes the assumption that the voters or agents specify a complete preference ordering over the set of candidates. There are many multiagent systems applications, and even real-world elections, where this assumption is not warranted, and this in turn raises a series of questions on the impact of partial voting on the complexity of manipulative actions. In this paper, we focus on two of these questions. First, we address the question of how hard it is to manipulate elections when the agents specify only top-truncated ballots. Here, in particular, we look at the weighted manipulation problem—both constructive and destructive manipulation—when the voters are allowed to specify top-truncated ballots, and we provide general results for all scoring rules, for elimination versions of all scoring rules, for the plurality with runoff rule, for a family of election systems known as Copeland \(^{\alpha }\), and for the maximin protocol. The second question we address is the impact of top-truncated voting on the complexity of manipulative actions in electorates with structured preference profiles. In particular, we consider electorates that are single-peaked and we show how, for many voting protocols, allowing top-truncated voting reimposes the \(\mathcal {NP}\) -hardness shields that normally vanish in such electorates.

IJCAI Conference 2017 Conference Paper

Deterministic, Strategyproof, and Fair Cake Cutting

• Vijay Menon
• Kate Larson

We study the classic cake cutting problem from a mechanism design perspective, in particular focusing on deterministic mechanisms that are strategyproof and fair. We begin by looking at mechanisms that are non-wasteful and primarily show that for even the restricted class of piecewise constant valuations there exists no direct-revelation mechanism that is strategyproof and even approximately proportional. Subsequently, we remove the non-wasteful constraint and show another impossibility result stating that there is no strategyproof and approximately proportional direct-revelation mechanism that outputs contiguous allocations, again, for even the restricted class of piecewise constant valuations. In addition to the above results, we also present some negative results when considering an approximate notion of strategyproofness, show a connection between direct-revelation mechanisms and mechanisms in the Robertson-Webb model when agents have piecewise constant valuations, and finally also present a (minor) modification to the well-known Even-Paz algorithm that has better incentive-compatible properties for the cases when there are two or three agents.

AAAI Conference 2016 Conference Paper

Big-Data Mechanisms and Energy-Policy Design

• Ankit Pat
• Kate Larson
• Srinivasen Keshav

A confluence of technical, economic and political forces are revolutionizing the energy sector. Policy-makers, who decide on incentives and penalties for possible courses of actions, play a critical role in determining which outcomes arise. However, designing appropriate energy policies is a complex and challenging task. Our vision is to provide tools and methodologies for policy makers so that they can leverage the power of big data to make evidence-based decisions. In this paper we present an approach we call big-data mechanism design which combines a mechanism design framework with stakeholder surveys and data to allow policy-makers to gauge the costs and benefits of potential policy decisions. We illustrate the effectiveness of this approach in a concrete application domain: the peaksaver PLUS program in Ontario, Canada.

IJCAI Conference 2016 Conference Paper

Dynamic Task Allocation Algorithm for Hiring Workers that Learn

• Shengying Pan
• Kate Larson
• Josh Bradshaw
• Edith Law

The automation of hiring decisions is a well-studied topic in crowdsourcing. Existing hiring algorithms make a common assumption - that each worker has a level of task competence that is static and does not vary over time. In this work, we explore the question of how to hire workers who can learn over time. Using a medical time series classification task as a case study, we conducted experiments to show that workers' performance does improve with experience and that it is possible to model and predict their learning rate. Furthermore, we propose a dynamic hiring mechanism that accounts for workers' learning potential. Through both simulation and real-world crowdsourcing data, we show that our hiring procedure can lead to high-accuracy outcomes at lower cost compared to other mechanisms.

AAMAS Conference 2016 Conference Paper

Investigating the Characteristics of One-Sided Matching Mechanisms (Extended Abstract)

• Hadi Hosseini
• Kate Larson
• Robin Cohen

For one-sided matching problems, two widely studied mechanisms are the Random Serial Dictatorship (RSD) and the Probabilistic Serial Rule (PS). The induced outcomes of these two mechanisms are often incomparable and thus there are challenges when it comes to deciding which mechanism to adopt in practice. Working in the space of general preferences, we provide empirical results on the (in)comparability of RSD and PS and analyze their economic properties.

AAAI Conference 2016 Conference Paper

Reinstating Combinatorial Protections for Manipulation and Bribery in Single-Peaked and Nearly Single-Peaked Electorates

• Vijay Menon
• Kate Larson

Understanding when and how computational complexity can be used to protect elections against different manipulative actions has been a highly active research area over the past two decades. A recent body of work, however, has shown that many of the NP-hardness shields, previously obtained, vanish when the electorate has single-peaked or nearly single-peaked preferences. In light of these results, we investigate whether it is possible to reimpose NP-hardness shields for such electorates by allowing the voters to specify partial preferences instead of insisting they cast complete ballots. In particular, we show that in single-peaked and nearly single-peaked electorates, if voters are allowed to submit top-truncated ballots, then the complexity of manipulation and bribery for many voting rules increases from being in P to being NP-complete.

AAMAS Conference 2016 Conference Paper

The Echo Chamber: Strategic Voting and Homophily in Social Networks

• Alan Tsang
• Kate Larson

We propose a model where voters are embedded in a social network. Each voter observes the ballots of her neighbors in the network, from which she infers the likely outcome of the election. Each voter may then revise her vote strategically, to maximize her expected utility. Our work focuses on plurality voting, where strategic voting is a major concern. We show that in practice, strategization increases with voter knowledge, yet can improve the social welfare for the population. Real world social networks exhibit a property called homophily; sometimes called “The Echo Chamber Effect”, which is the tendency for friends to have similar ideologies. We find that homophily dampens the benefits of strategization, and correspondingly, lowers the frequency of its occurrence. This effect may contribute to the low number of strategic voters observed in real world elections. Additionally, strategization may lead to the elimination of less popular candidates, as voters revise their votes to less preferred but more hopeful candidates. This phenomenon is known as Duverger’s Law in political science, and we show that it does not hold in certain network structures.

AAAI Conference 2015 Conference Paper

Conventional Machine Learning for Social Choice

• John Doucette
• Kate Larson
• Robin Cohen

Deciding the outcome of an election when voters have provided only partial orderings over their preferences requires voting rules that accommodate missing data. While existing techniques, including considerable recent work, address missingness through circumvention, we propose the novel application of conventional machine learning techniques to predict the missing components of ballots via latent patterns in the information that voters are able to provide. We show that suitable predictive features can be extracted from the data, and demonstrate the high performance of our new framework on the ballots from many real world elections, including comparisons with existing techniques for voting with partial orderings. Our technique offers a new and interesting conceptualization of the problem, with stronger connections to machine learning than conventional social choice techniques.

AAAI Conference 2015 Conference Paper

Matching with Dynamic Ordinal Preferences

• Hadi Hosseini
• Kate Larson
• Robin Cohen

We consider the problem of repeatedly matching a set of alternatives to a set of agents with dynamic ordinal preferences. Despite a recent focus on designing one-shot matching mechanisms in the absence of monetary transfers, little study has been done on strategic behavior of agents in sequential assignment problems. We formulate a generic dynamic matching problem via a sequential stochastic matching process. We design a mechanism based on random serial dictatorship (RSD) that, given any history of preferences and matching decisions, guarantees global stochastic strategyproofness while satisfying desirable local properties. We further investigate the notion of envyfreeness in such sequential settings.

AAAI Conference 2015 Conference Paper

On Manipulablity of Random Serial Dictatorship in Sequential Matching with Dynamic Preferences

• Hadi Hosseini
• Kate Larson
• Robin Cohen

We consider the problem of repeatedly matching a set of alternatives to a set of agents in the absence of monetary transfer. We propose a generic framework for evaluating sequential matching mechanisms with dynamic preferences, and show that unlike single-shot settings, the random serial dictatorship mechanism is manipulable.

EUMAS Conference 2014 Conference Paper

A Study on the Influence of the Number of MTurkers on the Quality of the Aggregate Output

• Arthur Carvalho
• Stanko Dimitrov
• Kate Larson

Abstract Recent years have seen an increased interest in crowdsourcing as a way of obtaining information from a large group of workers at a reduced cost. In general, there are arguments for and against using multiple workers to perform a task. On the positive side, multiple workers bring different perspectives to the process, which may result in a more accurate aggregate output since biases of individual judgments might offset each other. On the other hand, a larger population of workers is more likely to have a higher concentration of poor workers, which might bring down the quality of the aggregate output. In this paper, we empirically investigate how the number of workers on the crowdsourcing platform Amazon Mechanical Turk influences the quality of the aggregate output in a content-analysis task. We find that both the expected error in the aggregate output as well as the risk of a poor combination of workers decrease as the number of workers increases. Moreover, our results show that restricting the population of workers to up to the overall top 40 % workers is likely to produce more accurate aggregate outputs, whereas removing up to the overall worst 40 % workers can actually make the aggregate output less accurate. We find that this result holds due to top-performing workers being consistent across multiple tasks, whereas worst-performing workers tend to be inconsistent. Our results thus contribute to a better understanding of, and provide valuable insights into, how to design more effective crowdsourcing processes.

IJCAI Conference 2013 Conference Paper

A Consensual Linear Opinion Pool

• Arthur Carvalho
• Kate Larson

An important question when eliciting opinions from experts is how to aggregate the reported opinions. In this paper, we propose a pooling method to aggregate expert opinions. Intuitively, it works as if the experts were continuously updating their opinions in order to accommodate the expertise of others. Each updated opinion takes the form of a linear opinion pool, where the weight that an expert assigns to a peer’s opinion is inversely related to the distance between their opinions. In other words, experts are assumed to prefer opinions that are close to their own opinions. We prove that such an updating process leads to consensus, i. e. , the experts all converge towards the same opinion. Further, we show that if rational experts are rewarded using the quadratic scoring rule, then the assumption that they prefer opinions that are close to their own opinions follows naturally. We empirically demonstrate the efficacy of the proposed method using real-world data.

AAAI Conference 2013 Conference Paper

Resource Sharing for Control of Wildland Fires

• Alan Tsang
• Kate Larson
• Rob McAlpine

Wildland fires (or wildfires) occur on all continents except for Antarctica. These fires threaten communities, change ecosystems, destroy vast quantities of natural resources and the cost estimates of the damage done annually is in the billions of dollars. Controlling wildland fires is resource-intensive and there are numerous examples where the resource demand has outstripped resource availability. Trends in changing climates, fire occurrence and the expansion of the wildland-urban interface all point to increased resource shortages in the future. One approach for coping with these shortages has been the sharing of resources across different wildlandfire agencies. This introduces new issues as agencies have to balance their own needs and risk-management with their desire to help fellow agencies in need. Using ideas from the field of multiagent systems, we conduct the first analysis of strategic issues arising in resourcesharing for wildland-fire control. We also argue that the wildland-fire domain has numerous features that make it attractive to researchers in artificial intelligence and computational sustainability.

AAMAS Conference 2011 Conference Paper

A Truth Serum for Sharing Rewards

• Arthur Carvalho
• Kate Larson

We study a problem where a group of agents has to decide how a joint reward should be shared among them. We focus on settings where the share that each agent receives depends on the subjective opinions of its peers concerning that agent's contribution to the group. To this end, we introduce a mechanism to elicit and aggregate subjective opinions as well as for determining agents' shares. The intuition behind the proposed mechanism is that each agent who believes that the others are telling the truth has its expected share maximized to the extent that it is well-evaluated by its peers and that it is truthfully reporting its opinions. Under the assumptions that agents are Bayesian decision-makers and that the underlying population is sufficiently large, we show that our mechanism is incentive-compatible, budget-balanced, and tractable. We also present strategies to make this mechanism individually rational and fair.

KER Journal 2011 Journal Article

Logical mechanism design

• Iyad Rahwan
• Kate Larson

Abstract Game theory is becoming central to the design and analysis of computational mechanisms in which multiple entities interact strategically. The tools of mechanism design are used extensively to engineer incentives for truth revelation into resource allocation (e.g. combinatorial auctions) and preference aggregation protocols (e.g. voting). We argue that mechanism design can also be useful in the design of logical inference procedures. In particular, it can help us understand and engineer inference procedures when knowledge is distributed among self-interested agents. We set a research agenda for this emerging area, and point to some early research efforts.

IJCAI Conference 2011 Conference Paper

Social Distance Games

• Simina Br
• acirc; nzei
• Kate Larson

In this paper we introduce and analyze social distance games, a family of non-transferable utility coalitional games where an agent's utility is a measure of closeness to the other members of the coalition. We study both social welfare maximisation and stability in these games using a graph theoretic perspective. We use the stability gap to investigate the welfare of stable coalition structures, and propose two new solution concepts with improved welfare guarantees. We argue that social distance games are both interesting in themselves, as well as in the context of social networks.

AAMAS Conference 2011 Conference Paper

Social Distance Games

• Simina Br
• acirc; nzei
• Kate Larson

In this paper we introduce and analyze social distance games, a family of non-transferable utility coalitional games where an agent's utility is a measure of closeness to the other members of the coalition. We study both social welfare maximisation and stability in these games from a graph theoretic perspective. We investigate the welfare of stable coalition structures, and propose two new solution concepts with improved welfare guarantees. We argue that social distance games are both interesting in themselves, as well as in the context of social networks.

AAMAS Conference 2010 Conference Paper

An Investigation of Representations of Combinatorial Auctions

• David Loker
• Kate Larson

Combinatorial auctions (CAs) are an important mechanismfor allocating multiple goods while allowing self-interestedagents to specify preferences over bundles of items. Winner determination for a CA is known to be NP-complete. However, restricting the problem can allow us to solve winner determination in polynomial time. These restrictionssometimes apply to the CA's representation. There are twocommonly studied, and structurally different graph representations of a CA: bid graphs and item graphs. We studythe relationship between these two representations. We show that for a given combinatorial auction, if a graphwith maximum cycle length three is a valid item graph forthe auction, then its bid graph representation is a chordalgraph. Next, we present a new technique for constructingitem graphs using a novel definition of equivalence amongcombinatorial auctions. The solution to the WDP for a givenCA can easily be translated to a solution on an equivalentCA. We use our technique to simplify item graphs, and showthat if a CA's bid graph is chordal, then there exists anequivalent CA with a valid item graph of treewidth one, forwhich a solution to the WDP is known to be efficient. Thisresult demonstrates how CA equivalence can simplify thestructure of item graphs and lead to more efficient solutionsto the WDP, which are also a solutions to the WDP for theoriginal auctions.

AAMAS Conference 2010 Conference Paper

Cultivating Desired Behavior: Policy Teaching Via Environment-Dynamics Tweaks

• Zinovi Rabinovich
• Lachlan Dufton
• Kate Larson
• Nicholas R. Jennings

In this paper we study, for the first time explicitly, the implications of endowing an interested party (i. e. a teacher)with the ability to modify the underlying dynamics of theenvironment, in order to encourage an agent to learn to follow a specific policy. We introduce a cost function whichcan be used by the teacher to balance the modifications itmakes to the underlying environment dynamics, with thelearner's performance compared to some ideal, desired, policy. We formulate teacher's problem of determining optimalenvironment changes as a planning and control problem, andempirically validate the effectiveness of our model.

AAMAS Conference 2010 Conference Paper

Parameterizing the Winner Determination Problem for Combinatorial Auctions

• David Loker
• Kate Larson

Combinatorial auctions (CAs) have been studied by the multiagent systems community for some time, since these auctions are an effective mechanism for resource allocation whenagents are self-interested. One challenge, however, is thatthe winner-determination problem (WDP) for combinatorialauctions is NP-hard in the general case. However, there areways to leverage meaningful structure in the auction so as toachieve a polynomial-time algorithm for the WDP. In thispaper, using the formal scope of parameterized complexitytheory, we systematically investigate alternative parameterizations of the bids made by the agents (i. e. the input tothe WDP for combinatorial auctions) and are able to determine when a parameterization reduces the complexity ofthe WDP (fixed-parameter tractable), and when a particularparameterization results in the WDP remaining hard (fixed-parameter intractable). Our results are relevant to auctiondesigners since they provide information as to what types ofbidding-restrictions are effective for simplifying the winnerdetermination problem, and which would simply limit theexpressiveness of the agents while not providing any additional computational gains.

AAMAS Conference 2010 Conference Paper

Preference Elicitation for Risky Prospects

• Greg Hines
• Kate Larson

Minimax-regret preference elicitation allows intelligent decisions to be made on behalf of people facing risky choices. Standard gamble queries, a vital tool in this type of preference elicitation, assume that people, from whom preference information is being elicited, can be modeled using expected utility theory. However, there is strong evidence frompsychology that people may systematically deviate from expected utility theory. Cumulative prospect theory is an alternative model to expected utility theory which has beenshown empirically, to better explain humans' decision making in risky settings. We show that the current minimaxregret preference elicitation techniques can fail to properlyelicit appropriate information if the preferences of the userfollow cumulative prospect theory. As a result, we developa new querying method for preference elicitation that is applicable to cumulative prospect theory models. Simulationsshow that our method can effectively elicit information fordecision making in both cumulative prospect theory and expected utility theory settings, resulting in a flexible and effective preference elicitation method.

AAMAS Conference 2010 Conference Paper

Scalable Mechanism Design for the Procurement of Services with Uncertain Durations

• Enrico Gerding
• Sebastian Stein
• Kate Larson
• Alex Rogers
• Nicholas R. Jennings

In this paper, we study a service procurement problem with uncertainty as to whether service providers are capable of completing agiven task within a specified deadline. This type of setting is often encountered in large and dynamic multi-agent systems, such ascomputational Grids or clouds. To effectively deal with this uncertainty, the consumer may dynamically and redundantly procuremultiple services over time, in order to increase the probability ofsuccess, while at the same time balancing this with the additionalprocurement costs. However, in order to do this optimally, the consumer requires information about the providers' costs and their success probabilities over time. This information is typically held privately by the providers and they may have incentives to misreportthis, so as to increase their own profits. To address this problem, weintroduce a novel mechanism that incentivises self-interested providers to reveal their true costs and capabilities, and we show thatthis mechanism is ex-post incentive compatible, efficient and individually rational. However, for these properties to hold, it generallyneeds to compute the optimal solution, which can be intractable inlarge settings. Therefore, we show how we can generate approximate solutions while maintaining the economic properties of themechanism. This approximation admits a polynomial-time solution that can be computed in seconds even for hundreds of providers, and we demonstrate empirically that it performs as well as theoptimal in typical scenarios. In particularly challenging settings, we show that it still achieves 97\% or more of the optimal.

AAMAS Conference 2010 Conference Paper

Sharing a Reward Based on Peer Evaluations

• Arthur Carvalho
• Kate Larson

We study a problem where a group of agents has to decidehow some fixed value should be shared among them. Weare interested in settings where the share that each agentreceives is based on how that agent is evaluated by othermembers of the group, where highly regarded agents receive a greater share compared to agents that are not wellregarded. We introduce two mechanisms for determiningagents' shares: the peer-evaluation mechanism, where eachagent gives a direct evaluation for every other member ofthe group, and the peer-prediction mechanism, where eachagent is asked to report how they believe group members willevaluate a particular agent. The sharing is based on the provided information. While both mechanisms are individuallyrational, the first mechanism is strategy-proof and budget-balanced, but it can be collusion-prone. Further, the secondmechanism is collusion-resistant and incentive-compatible.

IJCAI Conference 2009 Conference Paper

• Simina Brânzei
• Kate Larson

We present and analyze coalitional affinity games, a family of hedonic games that explicitly model the value that an agent receives from being associated with other agents. We provide a characterization of the social-welfare maximizing coalition structures, and study the stability properties of affinity games, using the core solution concept. Interestingly, we observe that members of the core do not necessarily maximize social welfare. We introduce a new measure, the stability-gap to capture this difference. Using the stability gap, we show that for an interesting class of coalitional affinity games, the difference between the social welfare of a stable coalition structure and a social welfare maximizing coalition structure is bounded by a factor of two, and that this bound is tight.

IJCAI Conference 2009 Conference Paper

• Iyad Rahwan
• Kate Larson
• Fernando Tohmé

Recently, Argumentation Mechanism Design (ArgMD) was introduced as a new paradigm for studying argumentation among self-interested agents using game-theoretic techniques. Preliminary results showed a condition under which a direct mechanism based on Dung’s grounded semantics is strategy-proof (i. e. truth enforcing). But these early results dealt with a highly restricted form of agent preferences, and assumed agents can only hide, but not lie about, arguments. In this paper, we characterise strategy-proofness under grounded semantics for a more realistic preference class (namely, focal arguments). We also provide the first analysis of the case where agents can lie.

IJCAI Conference 2009 Conference Paper

• Sebastian Stein
• Enrico Gerding
• Alex Rogers
• Kate Larson
• Nicholas R. Jennings

Emerging service-oriented technologies allow software agents to automatically procure distributed services to complete complex tasks. However, in many application scenarios, service providers demand financial remuneration, execution times are uncertain and consumers have deadlines for their tasks. In this paper, we address these issues by developing a novel approach that dynamically procures multiple, redundant services over time, in order to ensure success by the deadline. Specifically, we first present an algorithm for finding optimal procurement solutions, as well as a heuristic algorithm that achieves over 99% of the optimal and is capable of handling thousands of providers. Using experiments, we show that these algorithms achieve an improvement of up to 130% over current strategies that procure only single services. Finally, we consider settings where service costs are not known to the consumer, and introduce several mechanisms that incentivise providers to reveal their costs truthfully and that still achieve up to 95% efficiency.

IJCAI Conference 2009 Conference Paper

• Georgia Kastidou
• Kate Larson
• Robin Cohen

We introduce a framework so that communities can exchange reputation information about agents in environments where agents are migrating between communities. We view the acquisition of the reputation information as a purchase and focus on the design of a payment function to facilitate the payment for information in a way that motivates communities to truthfully report reputation information for agents. We prove that in our proposed framework, honesty is the optimal policy and demonstrate the value of using a payment-function approach for the exchange of reputation information about agents between communities in multiagent environments. Using our payment function, each community is strengthened: it is able to reason more effectively about which agents to accept and can enjoy agents that are motivated to contribute strongly to the benefit of the community.

UAI Conference 2008 Conference Paper

Learning When to Take Advice: A Statistical Test for Achieving A Correlated Equilibrium

• Greg Hines
• Kate Larson

We study a multiagent learning problem where agents can either learn via repeated interactions, or can follow the advice of a mediator who suggests possible actions to take. We present an algorithm that each agent can use so that, with high probability, they can verify whether or not the mediator’s advice is useful. In particular, if the mediator’s advice is useful then agents will reach a correlated equilibrium, but if the mediator’s advice is not useful, then agents are not harmed by using our test, and can fall back to their original learning algorithm. We then generalize our algorithm and show that in the limit it always correctly verifies the mediator’s advice.

AAMAS Conference 2008 Conference Paper

Mechanism Design for Abstract Argumentation

• Iyad Rahwan
• Kate Larson

Since their introduction by Dung over a decade ago, abstract argumentation frameworks have received increasing interest in artificial intelligence as a convenient model for reasoning about general characteristics of argument. Such a framework consists of a set of arguments and a binary defeat relation among them. Various semantic and computational approaches have been developed to characterise the acceptability of individual arguments in a given argumentation framework. However, little work exists on understanding the strategic aspects of abstract argumentation among self-interested agents. In this paper, we introduce (game-theoretic) argumentation mechanism design (ArgMD), which enables the design and analysis of argumentation mechanisms for self-interested agents. We define the notion of a direct-revelation argumentation mechanism, in which agents must decide which arguments to reveal simultaneously. We then design a particular direct argumentation mechanism and prove that it is strategy proof under specific conditions; that is, the strategy profile in which each agent reveals its arguments truthfully is a dominant strategy equilibrium.

AAMAS Conference 2008 Conference Paper

Using Adaptive Consultation of Experts to Improve Convergence Rates in Multiagent Learning

• Greg Hines
• Kate Larson

We present a regret-based multiagent learning algorithm which is provably guaranteed to converge (during self-play) to the set of Nash equilibrium in a wide class of games. Our algorithm, FRAME, consults experts in order to obtain strategy suggestions for agents. If the experts provide effective advice for the agent, then the learning process will quickly reach a desired outcome. If, however, the experts do not provide good advice, then the agents using our algorithm are still protected. We further expand our algorithm so that agents learn, not only how to play against the other agents in the environment, but also which experts are providing the most effective advice for the situation at hand.

AAMAS Conference 2006 Conference Paper

Reducing Costly Information Acquisition in Auctions

• Kate Larson

AAMAS Conference 2005 Conference Paper

Mechanism Design and Deliberative Agents

• Kate Larson
• Tuomas Sandholm

AAMAS Conference 2004 Conference Paper

Experiments on deliberation equilibria in auctions

• Kate Larson
• Tuomas Sandholm

AAAI Conference 2004 Conference Paper

Using Performance Profile Trees to Improve Deliberation Control

• Kate Larson
• Tuomas Sandholm

Performance profile trees have recently been proposed as a theoretical basis for fully normative deliberation control. In this paper we conduct the first experimental study of their feasibility and accuracy in making stopping decisions for anytime algorithms on optimization problems. Using data and algorithms from two different real-world domains, we compare performance profile trees to other well-established deliberation-control techniques. We show that performance profile trees are feasible in practice and lead to significantly better deliberation control decisions. We then conduct experiments using performance profile trees where deliberationcontrol decisions are made using conditioning on multiple features of the solution to illustrate that such an approach is feasible in practice.

AAMAS Conference 2003 Conference Paper

Miscomputing Ratio: Social Cost of Selfish Computing

• Kate Larson
• Tuomas Sandholm

AAMAS Conference 2002 Conference Paper

An Alternating Offers Bargaining Model for Computationally Limited Agents

• Kate Larson
• Tuomas Sandholm

AIJ Journal 2001 Journal Article

Bargaining with limited computation: Deliberation equilibrium

• Kate Larson
• Tuomas Sandholm

We develop a normative theory of interaction—negotiation in particular—among self-interested computationally limited agents where computational actions are game theoretically treated as part of an agent's strategy. We focus on a 2-agent setting where each agent has an intractable individual problem, and there is a potential gain from pooling the problems, giving rise to an intractable joint problem. At any time, an agent can compute to improve its solution to its own problem, its opponent's problem, or the joint problem. At a deadline the agents then decide whether to implement the joint solution, and if so, how to divide its value (or cost). We present a fully normative model for controlling anytime algorithms where each agent has statistical performance profiles which are optimally conditioned on the problem instance as well as on the path of results of the algorithm run so far. Using this model, we introduce a solution concept, which we call deliberation equilibrium. It is the perfect Bayesian equilibrium of the game where deliberation actions are part of each agent's strategy. The equilibria differ based on whether the performance profiles are deterministic or stochastic, whether the deadline is known or not, and whether the proposer is known in advance or not. We present algorithms for finding the equilibria. Finally, we show that there exist instances of the deliberation–bargaining problem where no pure strategy equilibria exist and also instances where the unique equilibrium outcome is not Pareto efficient.

AIJ Journal 1999 Journal Article

Coalition structure generation with worst case guarantees

• Tuomas Sandholm
• Kate Larson
• Martin Andersson
• Onn Shehory
• Fernando Tohmé

Coalition formation is a key topic in multiagent systems. One may prefer a coalition structure that maximizes the sum of the values of the coalitions, but often the number of coalition structures is too large to allow exhaustive search for the optimal one. Furthermore, finding the optimal coalition structure is NP -complete. But then, can the coalition structure found via a partial search be guaranteed to be within a bound from optimum? We show that none of the previous coalition structure generation algorithms can establish any bound because they search fewer nodes than a threshold that we show necessary for establishing a bound. We present an algorithm that establishes a tight bound within this minimal amount of search, and show that any other algorithm would have to search strictly more. The fraction of nodes needed to be searched approaches zero as the number of agents grows. If additional time remains, our anytime algorithm searches further, and establishes a progressively lower tight bound. Surprisingly, just searching one more node drops the bound in half. As desired, our algorithm lowers the bound rapidly early on, and exhibits diminishing returns to computation. It also significantly outperforms its obvious contenders. Finally, we show how to distribute the desired search across self-interested manipulative agents.