Nicholas Teh

AAAI Conference 2026 Conference Paper

Fairness in Repeated Matching: A Maximin Perspective

• Eugene Lim
• Tzeh Yuan Neoh
• Nicholas Teh

We study a sequential decision-making model where a set of items is repeatedly matched to the same set of agents over multiple rounds. The objective is to determine a sequence of matchings that either maximizes the utility of the least advantaged agent at the end of all rounds (optimal) or at the end of every individual round (anytime optimal). We investigate the computational challenges associated with finding (anytime) optimal outcomes and demonstrate that these problems are generally computationally intractable. However, we provide approximation algorithms, fixed-parameter tractable algorithms, and identify several special cases whereby the problem(s) can be solved efficiently. Along the way, we also establish characterizations of Pareto-optimal/maximum matchings, which may be of independent interest to works in matching theory and house allocation.

AIJ Journal 2026 Journal Article

Settling the score: Portioning with cardinal preferences

• Edith Elkind
• Matthias Greger
• Patrick Lederer
• Warut Suksompong
• Nicholas Teh

AAAI Conference 2026 Conference Paper

Voting in Divisible Settings: A Survey

• Warut Suksompong
• Nicholas Teh

Voting is one of the most prominent applications of preference aggregation and computational social choice. While much of the literature focuses on models involving discrete candidates, there has been a growing interest in voting over divisible resources, such as budget, space, and time. In this survey, we review existing work on voting in divisible settings, including fundamental models of budget aggregation, fair mixing, and cake sharing. We also establish connections among these models, highlight unifying themes across different frameworks, and suggest directions for future research.

ICML Conference 2025 Conference Paper

Fraud-Proof Revenue Division on Subscription Platforms

• Abheek Ghosh
• Tzeh Yuan Neoh
• Nicholas Teh
• Giannis Tyrovolas

We study a model of subscription-based platforms where users pay a fixed fee for unlimited access to content, and creators receive a share of the revenue. Existing approaches to detecting fraud predominantly rely on machine learning methods, engaging in an ongoing arms race with bad actors. We explore revenue division mechanisms that inherently disincentivize manipulation. We formalize three types of manipulation-resistance axioms and examine which existing rules satisfy these. We show that a mechanism widely used by streaming platforms, not only fails to prevent fraud, but also makes detecting manipulation computationally intractable. We also introduce a novel rule, ScaledUserProp, that satisfies all three manipulation-resistance axioms. Finally, experiments with both real-world and synthetic streaming data support ScaledUserProp as a fairer alternative compared to existing rules.

IJCAI Conference 2025 Conference Paper

Not in My Backyard! Temporal Voting Over Public Chores

• Edith Elkind
• Tzeh Yuan Neoh
• Nicholas Teh

We study a temporal voting model where voters have dynamic preferences over a set of public chores---projects that benefit society, but impose individual costs on those affected by their implementation. We investigate the computational complexity of optimizing utilitarian and egalitarian welfare. Our results show that while optimizing the former is computationally straightforward, minimizing the latter is computationally intractable, even in very restricted cases. Nevertheless, we identify several settings where this problem can be solved efficiently, either exactly or by an approximation algorithm. We also examine the effects of enforcing temporal fairness and its impact on social welfare, and analyze the competitive ratio of online algorithms. We then explore the strategic behavior of agents, providing insights into potential malfeasance in such decision-making environments. Finally, we discuss a range of fairness measures and their suitability for our setting.

AAAI Conference 2025 Short Paper

Strategic Manipulation in Temporal Voting with Undesirable Candidates (Student Abstract)

• Tzeh Yuan Neoh
• Nicholas Teh

We study a model of sequential decision-making where voters have dynamic preferences over a set of candidates that are undesirable. This models scenarios such as the implementation of projects that are overall beneficial to society, but impose individual costs on certain affected individuals. We show that while minimizing the sum of agents' disutilities can be done in polynomial time, minimizing the maximum disutility obtained by any agent is computationally intractable, even in restricted cases. We then examine the potential for agents to engage in strategic manipulation in response to these welfare objectives, offering insights into possible misconduct within such decision-making environments.

AAMAS Conference 2025 Conference Paper

Temporal Fair Division of Indivisible Items

• Edith Elkind
• Alexander Lam
• Mohamad Latifian
• Tzeh Yuan Neoh
• Nicholas Teh

We study a fair division model where indivisible items arrive sequentially, and must be allocated immediately and irrevocably. Previous work on online fair division has shown impossibility results for achieving approximate envy-freeness under the assumption that agents have no information about future items. In contrast, we assume that the algorithm has complete knowledge of the future, and aim to ensure that the cumulative allocation at each round satis�es approximate envy-freeness, which we de�ne as temporal envy-freeness up to one item (TEF1). We focus on settings where items are exclusively goods or exclusively chores. For goods, while TEF1 allocations may fail to exist, we identify several special cases where they do—two agents, two item types, generalized binary valuations, unimodal preferences—and provide polynomial-time algorithms for these cases. We also prove that determining the existence of a TEF1 allocation is NP-hard. For chores, we obtain analogous results for the special cases, but present a slightly weaker intractability result. We also show that TEF1 is incompatible with Pareto optimality, with the implication that it is intractable to�nd a TEF1 allocation that maximizes any? -mean welfare, even for two agents.

AAAI Conference 2025 Conference Paper

Understanding EFX Allocations: Counting and Variants

• Tzeh Yuan Neoh
• Nicholas Teh

Envy-freeness up to any good (EFX) is a popular and important fairness property in the fair allocation of indivisible goods, of which its existence in general is still an open question. In this work, we investigate the problem of determining the minimum number of EFX allocations for a given instance, arguing that this approach may yield valuable insights into the existence and computation of EFX allocations. We focus on restricted instances where the number of goods slightly exceeds the number of agents, and extend our analysis to weighted EFX (WEFX) and a novel variant of EFX for general monotone valuations, termed EFX+. In doing so, we identify the transition threshold for the existence of allocations satisfying these fairness notions. Notably, we resolve open problems regarding WEFX by proving polynomial-time computability under binary additive valuations, and establishing the first constant-factor approximation for two agents.

AAAI Conference 2025 Conference Paper

Verifying Proportionality in Temporal Voting

• Edith Elkind
• Svetlana Obraztsova
• Jannik Peters
• Nicholas Teh

We study a model of temporal voting where there is a fixed time horizon, and at each round the voters report their preferences over the available candidates and a single candidate is selected. Prior work has adapted popular notions of justified representation as well as voting rules that provide strong representation guarantees from the multiwinner election setting to this model. In our work, we focus on the complexity of verifying whether a given outcome offers proportional representation. We show that in the temporal setting verification is strictly harder than in multiwinner voting, but identify natural special cases that enable efficient algorithms.

AAMAS Conference 2024 Conference Paper

Distributive and Temporal Fairness in Algorithmic Collective Decision-Making

• Nicholas Teh

From dividing parliamentary seats after a national election, to scheduling conference activities for an international AI conference, or deciding how to split public budget for city-wide projects, numerous real-life scenarios necessitates a group of individuals collectively reaching a desirable outcome through a preference aggregation process. In recent years, algorithms have been deployed in many scenarios to aid humans in such collective decision-making processes, with the goal of achieving fair outcomes efficiently. My work looks at the design and analysis of algorithms for various collective decision-making settings, including (i) indivisible resource allocation in the presence of strategic agents with different entitlements, (ii) multiwinner elections with temporal considerations, and (iii) the division of time and money when agents have cardinal preferences.

ECAI Conference 2024 Conference Paper

Multiwinner Temporal Voting with Aversion to Change

• Valentin Zech
• Niclas Boehmer
• Edith Elkind
• Nicholas Teh

We study two-stage committee elections where voters have dynamic preferences over candidates; at each stage, a committee is chosen under a given voting rule. We are interested in identifying a winning committee for the second stage that overlaps as much as possible with the first-stage committee. We show a full complexity dichotomy for the class of Thiele rules: this problem is tractable for Approval Voting (AV) and hard for all other Thiele rules (including, in particular, Proportional Approval Voting and the Chamberlin–Courant rule). We extend this dichotomy to the greedy variants of Thiele rules. We also explore this problem from a parameterized complexity perspective for several natural parameters. We complement the theory with experimental analysis: e. g. , we investigate the average number of changes in the committee as a function of changes in voters’ preferences and the role of ties.

ECAI Conference 2024 Conference Paper

Temporal Elections: Welfare, Strategyproofness, and Proportionality

• Edith Elkind
• Tzeh Yuan Neoh
• Nicholas Teh

We investigate a model of sequential decision-making where a single alternative is chosen at each round. We focus on two objectives—utilitarian welfare (UTIL) and egalitarian welfare (EGAL)—and consider the computational complexity of the associated maximization problems, as well as their compatibility with strategyproofness and proportionality. We observe that maximizing UTIL is easy, but the corresponding decision problem for EGAL is NP-complete even in restricted cases. We complement this hardness result for EGAL with parameterized complexity analysis and an approximation algorithm. Additionally, we show that, while a mechanism that outputs a UTIL outcome is strategyproof, all deterministic mechanisms for computing EGAL outcomes fail a very weak variant of strategyproofness, called non-obvious manipulability (NOM). However, we show that when agents have non-empty approval sets at each timestep, choosing an EGAL-maximizing outcome while breaking ties lexicographically satisfies NOM. Regarding proportionality, we prove that a proportional (PROP) outcome can be computed efficiently, but finding an outcome that maximizes UTIL while guaranteeing PROP is NP-hard. We also derive upper and lower bounds on the price of proportionality with respect to UTIL and EGAL.

AAAI Conference 2024 Conference Paper

Temporal Fairness in Multiwinner Voting

• Edith Elkind
• Svetlana Obraztsova
• Nicholas Teh

Multiwinner voting captures a wide variety of settings, from parliamentary elections in democratic systems to product placement in online shopping platforms. There is a large body of work dealing with axiomatic characterizations, computational complexity, and algorithmic analysis of multiwinner voting rules. Although many challenges remain, significant progress has been made in showing existence of fair and representative outcomes as well as efficient algorithmic solutions for many commonly studied settings. However, much of this work focuses on single-shot elections, even though in numerous real-world settings elections are held periodically and repeatedly. Hence, it is imperative to extend the study of multiwinner voting to temporal settings. Recently, there have been several efforts to address this challenge. However, these works are difficult to compare, as they model multi-period voting in very different ways. We propose a unified framework for studying temporal fairness in this domain, drawing connections with various existing bodies of work, and consolidating them within a general framework. We also identify gaps in existing literature, outline multiple opportunities for future work, and put forward a vision for the future of multiwinner voting in temporal settings.

AAMAS Conference 2024 Conference Paper

Verifying Proportionality in Temporal Voting

• Edith Elkind
• Svetlana Obraztsova
• Nicholas Teh

We study a model of multiwinner voting where candidates are selected sequentially in rounds over a time horizon. Prior work has adapted popular notions of justified representation as well as voting rules that provide strong representation guarantees from the standard single-round multiwinner election case to the temporal setting. In our work, we focus on the complexity of verifying whether a given outcome is proportional. We show that the temporal setting is strictly harder than the standard single-round model of multiwinner voting, but identify natural special cases that enable efficient verification.

AAAI Conference 2024 Conference Paper

Weighted Envy-Freeness for Submodular Valuations

• Luisa Montanari
• Ulrike Schmidt-Kraepelin
• Warut Suksompong
• Nicholas Teh

We investigate the fair allocation of indivisible goods to agents with possibly different entitlements represented by weights. Previous work has shown that guarantees for additive valuations with existing envy-based notions cannot be extended to the case where agents have matroid-rank (i.e., binary submodular) valuations. We propose two families of envy-based notions for matroid-rank and general submodular valuations, one based on the idea of transferability and the other on marginal values. We show that our notions can be satisfied via generalizations of rules such as picking sequences and maximum weighted Nash welfare. In addition, we introduce welfare measures based on harmonic numbers, and show that variants of maximum weighted harmonic welfare offer stronger fairness guarantees than maximum weighted Nash welfare under matroid-rank valuations.

AAAI Conference 2024 Short Paper

Welfare Maximization in Perpetual Voting (Student Abstract)

• Tzeh Yuan Neoh
• Nicholas Teh

We study the computational problems associated with maximizing various welfare objectives—namely utilitarian welfare, egalitarian welfare, and Nash welfare—in perpetual voting, a sequential collective decision-making framework. Prior work look into notions of fairness over time and study extensions of single-round voting rules to the multi-round setting. We show that while a utilitarian-welfare maximizing outcome can be computed efficiently, an outcome that maximizes egalitarian or Nash welfare is computationally intractable, even in the case of two candidates. We complement this by showing that maximizing egalitarian welfare is fixed-parameter tractable in the number of agents, and maximizing egalitarian or Nash welfare is W[2]-hard and slicewise polynomial in the number of timesteps. We also provide an approximation algorithm for maximizing egalitarian welfare and study strategyproofness with respect to these welfare objectives. Finally, we show that a simple greedy algorithm can achieve approximate proportionality in this setting.

AAMAS Conference 2023 Conference Paper

For One and All: Individual and Group Fairness in the Allocation of Indivisible Goods

• Jonathan Scarlett
• Nicholas Teh
• Yair Zick

Fair allocation of indivisible goods is a well-explored problem. Traditionally, research focused on individual fairness — are individual agents satisfied with their allotted share? — and group fairness — are groups of agents treated fairly? In this paper, we explore the coexistence of individual envy-freeness (𝑖-EF) and its group counterpart, group weighted envy-freeness (𝑔-WEF), in the allocation of indivisible goods. We propose several polynomial-time algorithms that provably achieve𝑖-EF and𝑔-WEF simultaneously in various degrees of approximation under three different conditions: (i) when agents have identical additive valuation functions, 𝑖-EFX and 𝑔-WEF1 can be achieved simultaneously; (ii) when agents within a group share a common valuation function, an allocation satisfying both 𝑖-EF1 and 𝑔-WEF1 exists; and (iii) when agents’ valuations for goods within a group differ, we show that while maintaining 𝑖-EF1, we can achieve a 1 3 -approximation to a notion termed ex-ante 𝑔-WEF1. Our results thus provide a first step towards connecting individual and group fairness in the allocation of indivisible goods, in the hopes of its useful application to domains requiring the reconciliation of diversity with individual demands.

ECAI Conference 2023 Conference Paper

Settling the Score: Portioning with Cardinal Preferences

• Edith Elkind
• Warut Suksompong
• Nicholas Teh

We study a portioning setting in which a public resource such as time or money is to be divided among a given set of candidates, and each agent proposes a division of the resource. We consider two families of aggregation rules for this setting—those based on coordinate-wise aggregation and those that optimize some notion of welfare—as well as the recently proposed Independent Markets mechanism. We provide a detailed analysis of these rules from an axiomatic perspective, both for classic axioms, such as strategyproofness and Pareto optimality, and for novel axioms, which aim to capture proportionality in this setting. Our results indicate that a simple rule that computes the average of all proposals satisfies many of our axioms, including some that are violated by more sophisticated rules.

IJCAI Conference 2022 Conference Paper

Better Collective Decisions via Uncertainty Reduction

• Shiri Alouf-Heffetz
• Laurent Bulteau
• Edith Elkind
• Nimrod Talmon
• Nicholas Teh

We consider an agent community wishing to decide on several binary issues by means of issue-by-issue majority voting. For each issue and each agent, one of the two options is better than the other. However, some of the agents may be confused about some of the issues, in which case they may vote for the option that is objectively worse for them. A benevolent external party wants to help the agents to make better decisions, i. e. , select the majority-preferred option for as many issues as possible. This party may have one of the following tools at its disposal: (1) educating some of the agents, so as to enable them to vote correctly on all issues, (2) appointing a subset of highly competent agents to make decisions on behalf of the entire group, or (3) guiding the agents on how to delegate their votes to other agents, in a way that is consistent with the agents' opinions. For each of these tools, we study the complexity of the decision problem faced by this external party, obtaining both NP-hardness results and fixed-parameter tractability results.