Publications (56)
Algorithmic Stability in Fair Allocation of Indivisible Goods Among Two Agents
Vijay Menon, Kate Larson
Many allocation problems in multiagent systems rely on agents specifying cardinal preferences. However, allocation mechanisms can be sensitive to small perturbations in cardinal pr…
Information and Contract Design for Repeated Interactions between Agents with Misaligned Incentives
Nanda Kishore Sreenivas, Kate Larson
We study the consequences of information asymmetries and misaligned incentives in settings with multiple independent agents. We model an interaction between a Sender, who holds vit…
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, evidenc…
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…
Your Recourse, My Loss? Algorithmic Recourse under Shared Constraints
Zahra Khotanlou, Kate Larson, Amir-Hossein Karimi
Decision makers are increasingly relying on machine learning in sensitive situations. Algorithmic recourse aims to provide individuals with actionable and minimally costly steps to…
Evaluating Agents using Social Choice Theory
Marc Lanctot, Kate Larson, Yoram Bachrach +6
We argue that many general evaluation problems can be viewed through the lens of voting theory. Each task is interpreted as a separate voter, which requires only ordinal rankings o…
Investigating the Characteristics of One-Sided Matching Mechanisms Under Various Preferences and Risk Attitudes
Hadi Hosseini, Kate Larson, Robin Cohen
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-stud…
Complexity of Manipulation in Elections with Top-truncated Ballots
Vijay Menon, Kate Larson
In the computational social choice literature, there has been great interest in understanding how computational complexity can act as a barrier against manipulation of elections. M…
Random Serial Dictatorship versus Probabilistic Serial Rule: A Tale of Two Random Mechanisms
Hadi Hosseini, Kate Larson, Robin Cohen
For assignment problems where agents, specifying ordinal preferences, are allocated indivisible objects, two widely studied randomized mechanisms are the Random Serial Dictatorship…
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 team…
Curated Synthetic Data Doesn't Have to Collapse: A Theoretical Study of Generative Retraining with Pluralistic Preferences
Ali Falahati, Mohammad Mohammadi Amiri, Kate Larson +1
Recursive retraining of generative models poses a critical representation challenge: when synthetic outputs are curated based on a fixed reward signal, the model tends to collapse…
Embodied Explainability and Ontological Obstacles: Why We Struggle to Explain the Answers of Large Language Models (LLMs)
Marvin Pafla, Jesse Hoey, Kate Larson +1
Explainability is often framed as a property of an AI model, with explanations extracted from its internals and shown to users. In this argument paper, we instead provide an embodi…
On a Reliable Peer-Review Process
Arthur Carvalho, Kate Larson
We propose an enhanced peer-review process where the reviewers are encouraged to truthfully disclose their reviews. We start by modelling that process using a Bayesian model where…
Matching Games with Additive Externalities
Simina Brânzei, Tomasz P. Michalak, Talal Rahwan +2
Two-sided matchings are an important theoretical tool used to model markets and social interactions. In many real life problems the utility of an agent is influenced not only by th…
Strategy, Not Payoffs: A Behavioural Embedding of Normal-Form Games
Joshua Caiata, Sreepriya Pulyassary, Xiang Li +1
The paper introduces a lightweight behavioural embedding for normal-form games, using Nash equilibrium entropy and response sensitivity, to predict how fine‑tuning large language m…
Liquid Ensemble Selection for Continual Learning
Carter Blair, Ben Armstrong, Kate Larson
Continual learning aims to enable machine learning models to continually learn from a shifting data distribution without forgetting what has already been learned. Such shifting dis…
Strategyproof Quota Mechanisms for Multiple Assignment Problems
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 lexicogr…
Unraveling the Dilemma of AI Errors: Exploring the Effectiveness of Human and Machine Explanations for Large Language Models
Marvin Pafla, Kate Larson, Mark Hancock
The field of eXplainable artificial intelligence (XAI) has produced a plethora of methods (e.g., saliency-maps) to gain insight into artificial intelligence (AI) models, and has ex…
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…
Towards a Better Understanding of Learning with Multiagent Teams
David Radke, Kate Larson, Tim Brecht +1
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 mo…
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…
Combining Tree-Search, Generative Models, and Nash Bargaining Concepts in Game-Theoretic Reinforcement Learning
Zun Li, Marc Lanctot, Kevin R. McKee +7
Opponent modeling methods typically involve two crucial steps: building a belief distribution over opponents' strategies, and exploiting this opponent model by playing a best respo…
Liquid Democracy for Low-Cost Ensemble Pruning
Ben Armstrong, Kate Larson
We argue that there is a strong connection between ensemble learning and a delegative voting paradigm -- liquid democracy -- that can be leveraged to reduce ensemble training costs…
A taxonomy of strategic human interactions in traffic conflicts
Atrisha Sarkar, Kate Larson, Krzysztof Czarnecki
In order to enable autonomous vehicles (AV) to navigate busy traffic situations, in recent years there has been a focus on game-theoretic models for strategic behavior planning in…
Generating Fair Consensus Statements with Social Choice on Token-Level MDPs
Carter Blair, Kate Larson
Current frameworks for consensus statement generation with large language models lack the inherent structure needed to provide provable fairness guarantees when aggregating diverse…
Learning from Multiple Independent Advisors in Multi-agent Reinforcement Learning
Sriram Ganapathi Subramanian, Matthew E. Taylor, Kate Larson +1
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…
Improving Welfare in One-sided Matching using Simple Threshold Queries
Thomas Ma, Vijay Menon, Kate Larson
We study one-sided matching problems where agents have preferences over objects and each of them need to be assigned to at most one object. Most work on such problems assum…
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 looki…
Anytime Coalition Structure Generation with Worst Case Guarantees
Tuomas Sandholm, Kate Larson, Martin Andersson +2
Coalition formation is a key topic in multiagent systems. One would prefer a coalition structure that maximizes the sum of the values of the coalitions, but often the number of coa…
Multi-Agent Risks from Advanced AI
Lewis Hammond, Alan Chan, Jesse Clifton +41
The rapid development of advanced AI agents and the imminent deployment of many instances of these agents will give rise to multi-agent systems of unprecedented complexity. These s…
Sharing a Reward Based on Peer Evaluations
Arthur Carvalho, Kate Larson
We study a problem where a group of agents has to decide how some fixed value should be shared among them. We are interested in settings where the share that each agent receives is…
Nash without Numbers: A Social Choice Approach to Mixed Equilibria in Context-Ordinal Games
Ian Gemp, Crystal Qian, Marc Lanctot +1
Nash equilibrium serves as a fundamental mathematical tool in economics and game theory. However, it classically assumes knowledge of player utilities, whereas economics generally…
Multi-Agent Advisor Q-Learning
Sriram Ganapathi Subramanian, Matthew E. Taylor, Kate Larson +1
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 sl…
Braess's Paradox for Flows Over Time
Martin Macko, Kate Larson, Ľuboš Steskal
We study the properties of Braess's paradox in the context of the model of congestion games with flow over time introduced by Koch and Skutella. We compare them to the well known p…
Equilibria of Chinese Auctions
Simina Brânzei, Clara Forero, Kate Larson +1
Chinese auctions are a combination between a raffle and an auction and are held in practice at charity events or festivals. In a Chinese auction, multiple players compete for sever…
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. Intui…
Inducing Honest Reporting Without Observing Outcomes: An Application to the Peer-Review Process
Arthur Carvalho, Stanko Dimitrov, Kate Larson
When eliciting opinions from a group of experts, traditional devices used to promote honest reporting assume that there is an observable future outcome. In practice, however, this…
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 pre…
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…
Mechanism Design for Locating a Facility under Partial Information
Vijay Menon, Kate Larson
We study the classic mechanism design problem of locating a public facility on a real line. In contrast to previous work, we assume that the agents are unable to fully specify wher…
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…
Matching Demand with Supply in the Smart Grid using Agent-Based Multiunit Auction
Tri Kurniawan Wijaya, Kate Larson, Karl Aberer
Recent work has suggested reducing electricity generation cost by cutting the peak to average ratio (PAR) without reducing the total amount of the loads. However, most of these pro…
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 proper…
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 th…
Open Problems in Cooperative AI
Allan Dafoe, Edward Hughes, Yoram Bachrach +5
Problems of cooperation--in which agents seek ways to jointly improve their welfare--are ubiquitous and important. They can be found at scales ranging from our daily routines--such…
Robust and Approximately Stable Marriages under Partial Information
Vijay Menon, Kate Larson
We study the stable marriage problem in the partial information setting where the agents, although they have an underlying true strict linear order, are allowed to specify partial…
Soft Condorcet Optimization for Ranking of General Agents
Marc Lanctot, Kate Larson, Michael Kaisers +7
Driving progress of AI models and agents requires comparing their performance on standardized benchmarks; for general agents, individual performances must be aggregated across a po…
Developing, Evaluating and Scaling Learning Agents in Multi-Agent Environments
Ian Gemp, Thomas Anthony, Yoram Bachrach +24
The Game Theory & Multi-Agent team at DeepMind studies several aspects of multi-agent learning ranging from computing approximations to fundamental concepts in game theory to simul…
Network Bargaining: Using Approximate Blocking Sets to Stabilize Unstable Instances
Jochen Koenemann, Kate Larson, David Steiner
We study a network extension to the Nash bargaining game, as introduced by Kleinberg and Tardos (STOC'08), where the set of players corresponds to vertices in a graph and…
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 wit…
Approximating the Core via Iterative Coalition Sampling
Ian Gemp, Marc Lanctot, Luke Marris +11
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…
The Alignment Game: A Theory of Long-Horizon Alignment Through Recursive Curation
Ali Falahati, Mohammad Mohammadi Amiri, Kate Larson +1
In self-consuming generative models that train on their own outputs, alignment with user preferences becomes a recursive rather than one-time process. We provide the first formal f…
Imagining and building wise machines: The centrality of AI metacognition
Samuel G. B. Johnson, Amir-Hossein Karimi, Yoshua Bengio +8
Although AI has become increasingly smart, its wisdom has not kept pace. In this article, we examine what is known about human wisdom and sketch a vision of its AI counterpart. We…
Democratizing Reward Design for Personal and Representative Value-Alignment
Carter Blair, Kate Larson, Edith Law
Aligning AI agents with human values is challenging due to diverse and subjective notions of values. Standard alignment methods often aggregate crowd feedback, which can result in…
Active Evaluation of General Agents: Problem Definition and Comparison of Baseline Algorithms
Marc Lanctot, Kate Larson, Ian Gemp +1
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 tha…
Jackpot! Alignment as a Maximal Lottery
Roberto-Rafael Maura-Rivero, Marc Lanctot, Francesco Visin +1
Reinforcement Learning from Human Feedback (RLHF), the standard for aligning Large Language Models (LLMs) with human values, is known to fail to satisfy properties that are intuiti…