GenAI4ELab/papercli-papers huggingface dataset:
Perturbing Best Responses in Zero-Sum Games
Authors: Adam Dziwoki; Rostislav Horcik
Venue: AAAI 2026 (main)

Abstract: This paper investigates the impact of perturbations on the best-response-based algorithms approximating Nash equilibria in zero-sum games, namely Double Oracle and Fictitious Play. More precisely, we assume that the oracle computing the best responses perturbs the utilities before selecting the best response. We show that using such an oracle reduces the number of iterations for both algorithms. For some cases, suitable perturbations ensure the expected number of iterations is logarithmic. Although the utility perturbation is computationally demanding as it requires iterating through all pure strategies, we demonstrate that one can efficiently perturb the utilities in games where pure strategies have further inner structure.
Computing Equilibrium Nominations in Presidential Elections
Authors: Piotr Faliszewski; Stanisław Kaźmierowski; Grzegorz Lisowski; Ildikó Schlotter; Paolo Turrini
Venue: AAAI 2026 (main)

Abstract: We study strategic candidate nomination by parties in elections decided by Plurality voting. Each party selects a nominee before the election, and the winner is chosen from the nominated candidates based on the voters' preferences. We introduce a new restriction on these preferences, which we call party-aligned single-peakedness: all voters agree on a common ordering of the parties along an ideological axis, but may differ in their perceptions of the positions of individual candidates within each party. The preferences of each voter are single-peaked with respect to their own axis over the candidates, which is consistent with the global ordering of the parties. We present a polynomial-time algorithm for recognizing whether a preference profile satisfies party-aligned single-peakedness. In this domain, we give polynomial-time algorithms for deciding whether a given party can become the winner under some (or all) nominations, and whether this can occur in some pure Nash equilibrium. 
We also prove a tight result about the guaranteed existence of pure strategy Nash equilibria for elections with up to three parties for single-peaked and party-aligned single-peaked preference profiles.
Diversity of Structured Domains via k-Kemeny Scores
Authors: Piotr Faliszewski; Krzysztof Sornat; Stanisław Szufa; Tomasz Wąs
Venue: AAAI 2026 (main)

Abstract: In the k-Kemeny problem, we are given an ordinal election, i.e., a collection of votes ranking the candidates from best to worst, and we seek the smallest number of swaps of adjacent candidates that ensure that the election has at most k different rankings. We study this problem for a number of structured domains, including the single-peaked, single-crossing, group-separable, and Euclidean ones. We obtain two kinds of results: (1) We show that k-Kemeny remains intractable under most of these domains, even for k=2, and (2) we use k-Kemeny to rank these domains in terms of their diversity.
Identifying Imperfect Clones in Elections
Authors: Piotr Faliszewski; Łukasz Janeczko; Grzegorz Lisowski; Kristýna Pekárková; Ildikó Schlotter
Venue: AAAI 2026 (main)

Abstract: A perfect clone in an ordinal election (i.e., an election where the voters rank the candidates in a strict linear order) is a set of candidates that each voter ranks consecutively. We consider different relaxations of this notion:  *independent* or *subelection clones* are sets of candidates that only some of the voters recognize as a perfect clone, whereas *approximate clones* are sets of candidates such that every voter ranks their members close to each other, but not necessarily consecutively. We establish the complexity of identifying such imperfect clones, and of partitioning the candidates into families of imperfect clones. We also study the parameterized complexity of these problems with respect to a set of natural parameters such as the number of voters, the size or the number of imperfect clones we are searching for, or their level of  imperfection.
Fairness and Stability for Shared Resource Allocation Problems
Authors: Jiazhu Fang; Qizhi Fang; Minming Li; Wenjing Liu
Venue: AAAI 2026 (main)

Abstract: This paper investigates the problem of shared resource allocation, where a set of agents must be assigned to heterogeneous resources, with each agent allocated exactly one resource and each resource potentially shared by multiple agents. An agent’s utility for a given resource is jointly determined by the resource's type and the number of agents sharing it. We focus on two fundamental classes of monotone valuations: monotone nondecreasing and monotone nonincreasing, where an agent’s utility respectively increases or decreases with the number of agents sharing the resource. Within this shared resource framework, we examine classical notions of fairness and stability, including maximin-share fairness, envy-freeness, Nash stability, and two epistemic relaxations—epistemic envy-freeness and epistemic Nash stability—as well as swap stability. We propose formal definitions adapted to this setting and systematically analyze the relationships among these concepts. The primary contributions of this work consist of establishing existence and computational complexity results for each notion under both monotonicity assumptions and developing polynomial-time algorithms in cases where fair or stable allocations are guaranteed to exist.
No-Regret Strategy Solving in Imperfect-Information Games via Pre-Trained Embedding
Authors: Yanchang Fu; Shengda Liu; Pei Xu; Kaiqi Huang
Venue: AAAI 2026 (main)

Abstract: High-quality information set abstraction remains a core challenge in solving large-scale imperfect-information extensive-form games (IIEFGs)--such as no-limit Texas Hold’em--where the finite nature of spatial resources hinders solving strategies for the full game. State-of-the-art AI methods rely on pre-trained discrete clustering for abstraction, yet their hard classification irreversibly discards critical information: specifically, the quantifiable subtle differences between information sets--vital for strategy solving--thus compromising the quality of such solving. Inspired by the word embedding paradigm in natural language processing, this paper proposes the Embedding CFR algorithm, a novel approach for solving strategies in IIEFGs within an embedding space. The algorithm pre-trains and embeds the features of individual information sets into an interconnected low-dimensional continuous space, where the resulting vectors more precisely capture both the distinctions and connections between information sets. Embedding CFR introduces a strategy-solving process driven by regret accumulation and strategy updates in this embedding space, with supporting theoretical analysis verifying its ability to reduce cumulative regret. Experiments on poker show that with the same spatial overhead, Embedding CFR achieves significantly faster exploitability convergence compared to cluster-based abstraction algorithms, confirming its effectiveness. Furthermore, to our knowledge, it is the first algorithm in poker AI that pre-trains information set abstractions via low-dimensional embedding for strategy solving.
Designing Truthful Mechanisms for Asymptotic Fair Division
Authors: Jugal Garg; Vishnu V. Narayan; Yuang Eric Shen
Venue: AAAI 2026 (main)

Abstract: We study the problem of fairly allocating a set of m goods among n agents in the asymptotic setting, where each item's value for each agent is drawn from an underlying joint distribution. Prior works have shown that if this distribution is well-behaved, then an envy-free allocation exists with high probability when m=Ω(n log n). Under the stronger assumption that item values are independently and identically distributed (i.i.d.) across agents, it is known that this requirement improves to m=Ω(n log n / log log n), which is tight. However, these results rely on non-strategyproof mechanisms, such as maximum-welfare allocation or the round-robin algorithm, limiting their applicability in settings with strategic agents. 

In this work, we extend the theory to a broader, more realistic class of joint value distributions, allowing for correlations among agents, atomicity, and unequal probabilities of having the highest value for an item. We show that envy-free allocations continue to exist with a high probability when m=Ω(n log n). More importantly, we give a new randomized mechanism that is truthful in expectation, efficiently implementable in polynomial time, and outputs envy-free allocations with high probability, answering an open question from the literature. We further extend our mechanism to settings with asymptotic weighted fair division and multiple agent types and good types, proving new results in each case.
Existence of 2-EFX Allocations of Chores
Authors: Jugal Garg; Aniket Murhekar
Venue: AAAI 2026 (main)

Abstract: We study the fair division of indivisible chores among agents with additive disutility functions. We investigate the existence of allocations satisfying the popular fairness notion of envy-freeness up to any chore (EFX), and its multiplicative approximations. The existence of 4-EFX allocations was recently established by Garg, Murhekar, and Qin (2025). We improve this guarantee by proving the existence of 2-EFX allocations for all instances with additive disutilities. This approximation was previously known only for restricted instances such as bivalued disutilities (Lin, Wu, and Zhou (2025)) or three agents (Afshinmehr, Ansaripour, Danaei, and Mehlhorn (2024)). 

We obtain our result by providing a general framework for achieving approximate-EFX allocations. The approach begins with a suitable initial allocation and performs a sequence of local swaps between the bundles of envious and envied agents. For our main result, we begin with an initial allocation that satisfies envy-freeness up to one chore (EF1) and Pareto-optimality (PO); the existence of such an allocation was recently established in a major breakthrough by Mahara (2025). We further demonstrate the strength and generality of our framework by giving simple and unified proofs of existing results, namely (i) 2-EFX for bivalued instances, (ii) 2-EFX for three agents, (iii) EFX when the number of chores is at most twice the number of agents, and (iv) 4-EFX for all instances. We expect this framework to have broader applications in approximate-EFX due to its simplicity and generality.
Optimized Distortion in Linear Social Choice
Authors: Luise Ge; Gregory Kehne; Yevgeniy Vorobeychik
Venue: AAAI 2026 (main)

Abstract: Social choice theory offers a wealth of approaches for selecting a candidate on behalf of voters based on their reported preference rankings over options. When voters have explicit utilities for these options, however, using preference rankings may lead to suboptimal outcomes vis-a-vis utilitarian social welfare. Distortion is a measure of this suboptimality, and an extensive literature 
uses it to develop and analyze voting rules when utilities have minimal structure. However, in many settings, such as common paradigms for value alignment, available options admit a vector representation, and it is natural to suppose that utilities are parametric functions thereof.

We undertake the first study of distortion for linear utility functions. Our theoretical contributions are organized into two parts: randomized and deterministic voting rules. We obtain bounds that depend only on dimension of the candidate embedding, and are independent of the numbers of candidates or voters. Additionally, we introduce poly-time instance-optimal algorithms for minimizing distortion given a collection of candidates and votes. We empirically evaluate these in two real-world domains: recommendation systems using collaborative filtering embeddings, and opinion surveys utilizing language model embeddings. Our results benchmark the distortion bounds of several standard rules against our instance-optimal algorithms.
Fair Incentives for Early Arrival in 0-1 Cooperative Games
Authors: Yaoxin Ge; Yao Zhang; Dengji Zhao
Venue: AAAI 2026 (main)

Abstract: Incentives for early arrival (I4EA) was recently proposed for studying online cooperative games. In an online cooperative game, players arrive in an unknown order, and the value increase after each player arrived should be distributed immediately among all the arrived players. Although there is only one arriving order in the game, we also hope that the value distribution is equal to their Shapley value in expectation. To achieve these goals, the early solutions ignored the fairness in each single arriving order. More specifically, an important player may receive nothing in a game, which seems unfair in reality. To combat this, we propose refined fairness in this paper and design new solutions in 0-1 value games. Specifically, we compute the distance of the distribution in each order to the Shapley value and aim to minimize it. We propose a new mechanism called Egalitarian Value-Sharing (EVS) to do so. We also show that the mechanism can maximize the egalitarian welfare among all the players who made contributions.
On the Approximation Ratio of Optimal Fixed-Price Mechanisms for Single and Multi-Unit Bilateral Trade
Authors: Giordano Giambartolomei; Bart de Keijzer
Venue: AAAI 2026 (main)

Abstract: Multi-unit bilateral trade refers to the setting, where there is a buyer and a seller, who holds a finite number of units of an indivisible item. An automated mechanism has to decide how many units are transferred from the seller to the buyer and the corresponding payment from the buyer to the seller. The buyer and the seller have both either increasing or increasing submodular valuation functions in the number of units in possession. The (single-unit) bilateral trade problem arises as a particular case.

We study the problem of social welfare maximisation by establishing the fraction (approximation ratio) of the optimal social welfare that a fixed-price mechanism can recover. Fixed-price mechanisms, understood as per-unit price in the multi-unit setting, have been characterised as the only truthful, individually rational and strongly budget balanced mechanisms. We narrow the gap on the approximation ratio of optimal fixed-price mechanisms for bilateral trade, which has been shown to lie between 0.72 and 0.7381. We show that it must lie between 0.7292 and 0.73805, which leads to improved bounds on the approximation ratio of optimal fixed-price mechanisms for multi-unit bilateral trade. In particular, we show that multi-unit bilateral trade is at least as hard as single-unit bilateral trade, and obtain several hardness results for different numbers of units.
Fair Allocation of Indivisible Goods with Variable Groups
Authors: Paul Gölz; Ayumi Igarashi; Pasin Manurangsi; Warut Suksompong
Venue: AAAI 2026 (main)

Abstract: We study the fair allocation of indivisible goods with variable groups. In this model, the goal is to partition the agents into groups of given sizes and allocate the goods to the groups in a fair manner. We show that for any number of groups and corresponding sizes, there always exists an envy-free up to one good (EF1) outcome, thereby generalizing an important result from the individual setting. Our result holds for arbitrary monotonic utilities and comes with an efficient algorithm. We also prove that an EF1 outcome is guaranteed to exist even when the goods lie on a path and each group must receive a connected bundle. In addition, we consider a probabilistic model where the utilities are additive and drawn randomly from a distribution. We show that if there are n agents and the number of goods m is divisible by the number of groups k, then an envy-free outcome exists with high probability if m = ω(log n), and this bound is tight. On the other hand, if m is not divisible by k, then an envy-free outcome is unlikely to exist as long as m = o(√n).
Fair Division Among Couples and Small Groups
Authors: Paul Gölz; Hannane Yaghoubizade
Venue: AAAI 2026 (main)

Abstract: We study the fair allocation of indivisible goods across groups of agents, where each agent fully enjoys all goods allocated to their group.
We focus on groups of two (couples) and other groups of small size.
For two couples, an EF1 allocation — one in which all agents find their group's bundle no worse than the other group's, up to one good — always exists and can be found efficiently.
For three or more couples, EF1 allocations need not exist.

Turning to proportionality, we show that, whenever groups have size at most k, a PROPk allocation exists and can be found efficiently.
In fact, our algorithm additionally guarantees (fractional) Pareto optimality and PROP1 to the first agent in each group, PROP2 to the second, and so on, for an arbitrary agent ordering.
In special cases, we show that there are PROP1 allocations for any number of couples.
City Sampling for Citizens’ Assemblies
Authors: Paul Gölz; Jan Maly; Ulrike Schmidt-Kraepelin; Markus Utke; Philipp C. Verpoort
Venue: AAAI 2026 (main)

Abstract: In citizens' assemblies, a group of constituents is randomly selected to weigh in on policy issues. We study a two-stage sampling problem faced by practitioners in countries such as Germany, in which constituents' contact information is stored at a municipal level. As a result, practitioners can only select constituents from a bounded number of cities ex post, while ensuring equal selection probability for constituents ex ante. 

We develop several algorithms for this problem. Although minimizing the number of contacted cities is NP-hard, we provide a pseudo-polynomial time algorithm and an additive 1-approximation, both based on separation oracles for a linear programming formulation. Recognizing that practical objectives go beyond minimizing city count, we further introduce a simple and more interpretable greedy algorithm, which additionally satisfies an ex-post monotonicity property and achieves an additive 2-approximation. Finally, we explore a notion of ex-post proportionality, for which we propose two practical algorithms: an optimal algorithm based on column generation and integer linear programming and a simple heuristic creating particularly transparent distributions. We evaluate these algorithms on data from Germany, and plan to deploy them in cooperation with a leading nonprofit organization in this space.
Multi-District School Choice: Playing on Several Fields
Authors: Yannai A. Gonczarowski; Michael Yin; Shirley Zhang
Venue: AAAI 2026 (main)

Abstract: We extend the seminal model of Pathak and Sönmez (2008) to a setting with multiple school districts, each running its own separate centralized match, and focus on the case of two districts. In our setting, in addition to each student being either sincere or sophisticated, she is also either constrained—able to apply only to schools within her own district of residence—or unconstrained—able to choose any single district within which to apply. We show that several key results from Pathak and Sönmez (2008) qualitatively flip: A sophisticated student may prefer for a sincere student to become sophisticated, and a sophisticated student may prefer for her own district to use Deferred Acceptance over the Boston Mechanism, irrespective of the mechanism used by the other district. We furthermore show that an unconstrained student may prefer for a constrained student to become unconstrained, regardless of the mechanisms used. Many of these phenomena appear abundantly in large random markets.
Fair Diffusion Auctions
Authors: Zixin Gu; Yaoxin Ge; Yao Zhang; Dengji Zhao
Venue: AAAI 2026 (main)

Abstract: Diffusion auction design is a new trend in mechanism design which extends the original incentive compatibility property to include buyers' private connection report. Reporting connections is equivalent to inviting their neighbors to join the auction in practice. Then, the social welfare is collectively accumulated by all participants: reporting high valuations or inviting high-valuation neighbors. Hence, we can measure each participant's contribution by the marginal social welfare increase due to her participation.

Therefore, in this paper, we introduce a new property called Shapley fairness to capture participants' social welfare contribution and use it as a benchmark to guide our auction design for a fairer utility allocation. Not surprisingly, none of the existing diffusion auctions has ever approximated the fairness, because Shapley fairness depends on each buyer's own valuation and this dependence can easily violate incentive compatibility.  Thus, we combat this challenge by proposing a new diffusion auction called Permutation Diffusion Auction (PDA) for selling k homogeneous items, which is the first diffusion auction satisfying 1/(k+1)-Shapley fairness, incentive compatibility and individual rationality. Moreover, PDA can be extended to the general combinatorial auction setting where the literature did not discover meaningful diffusion auctions yet.
Minimizing Inequity in Facility Location Games
Authors: Yuhang Guo; Houyu Zhou
Venue: AAAI 2026 (main)

Abstract: This paper studies the problem of minimizing group-level inequity in facility location games on the real line, where agents belong to different groups and may act strategically. We explore a fairness-oriented objective that minimizes the maximum group effect. For each group, the group effect is defined as its total or maximum distance to the nearest facility, weighted by group-specific factors. We show that this formulation generalizes several prominent optimization objectives, including the classical utilitarian (social cost) and egalitarian (maximum cost) objectives, as well as two group-fair objectives, maximum total and average group cost. In order to minimize the maximum group effect, we first propose two novel mechanisms for the single-facility case, the Balanced mechanism and the Major-Phantom mechanism. Both are strategyproof and achieve tight approximation guarantees under distinct formulations of the maximum group effect objective. Our mechanisms not only close the existing gap in approximation bounds for the group-fairness objectives, maximum total group cost and maximum average group cost, but also unify many classical truthful mechanisms within a broader fairness-aware framework. For the two-facility case, we revisit and extend the classical endpoint mechanism to our generalized setting and demonstrate that it provides tight bounds for two distinct maximum group effect objectives.
Pricing Online LLM Services with Data-Calibrated Stackelberg Routing Game
Authors: Zhendong Guo; Wenchao Bai; Jiahui Jin
Venue: AAAI 2026 (main)

Abstract: The proliferation of Large Language Models (LLMs) has established LLM routing as a standard service delivery mechanism, where users select models based on cost, Quality of Service (QoS), among other things.
However, optimal pricing in LLM routing platforms requires precise modeling for dynamic service markets, and solving this problem in real time at scale is computationally intractable.
In this paper, we propose PriLLM, a novel practical and scalable solution for real-time dynamic pricing in competitive LLM routing.
PriLLM models the service market as a Stackelberg game, where providers set prices and users select services based on multiple criteria.
To capture real-world market dynamics, we incorporate both objective factors (eg cost, QoS) and subjective user preferences into the model.
For scalability, we employ a deep aggregation network to learn provider abstraction that preserve user-side equilibrium behavior across pricing strategies.
Moreover, PriLLM offers interpretability by explaining its pricing decisions.
Empirical evaluation on real-world data shows that PriLLM achieves over 95% of the optimal profit while only requiring less than 5% of the optimal solution's computation time.