GenAI4ELab/papercli-papers huggingface dataset:
Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptions
Authors: Reda Ouhamma; Maryam Kamgarpour
Venue: AAAI 2026 (main)

Abstract: We address payoff-based decentralized learning in infinite-horizon zero-sum Markov games. In this setting, each player makes decisions based solely on received rewards, without observing the opponent's strategy or actions, nor sharing information. Prior works established polynomial-time convergence to an approximate Nash equilibrium under strong reachability and mixing time assumptions. We propose a convergent algorithm that significantly relaxes these assumptions, requiring only the existence of a single policy with bounded reachability and mixing time. Our key algorithmic novelty is introducing Tsallis entropy regularization to smooth the best-response policy updates. By suitably tuning this regularization, we ensure sufficient exploration, thus bypassing previous stringent assumptions on the MDP. We prove a polynomial-time convergence to an approximate Nash equilibrium by establishing novel properties of the value and policy updates induced by the Tsallis entropy regularizer.
Group Fair Matchings Using Convex Cost Functions
Authors: Atasi Panda; Harsh Sharma; Anand Louis; Prajakta Nimbhorkar
Venue: AAAI 2026 (main)

Abstract: We consider the problem of assigning items to platforms where each item has a utility associated with each of the platforms to which it can be assigned. Each platform has a soft constraint over the total number of items it serves, modeled via a convex cost function. Additionally, items are partitioned into groups, and each platform also incurs group-specific convex cost over the number of items from each group that can be assigned to the platform. These costs promote group fairness by penalizing imbalances, yielding a soft variation of fairness notions introduced in prior work, such as Restricted Dominance and Minority protection. Restricted Dominance enforces upper bounds on group representation, while Minority protection enforces lower bounds. Our approach replaces such hard constraints with cost-based penalties, allowing more flexible trade-offs. Our model also captures Nash Social Welfare kind of objective. 
 
The cost of an assignment is the sum of the values of all the cost functions across all the groups and platforms. The objective is to find an assignment that minimizes the cost while achieving a total utility that is at least a user-specified threshold. The main challenge lies in balancing the overall platform cost with group-specific costs, both governed by convex functions, while meeting the utility constraint. We present an efficient polynomial-time approximation algorithm, supported by theoretical guarantees and experimental evaluation. 

Our algorithm is based on techniques involving linear programming and network flows. We also provide an exact algorithm for a special case with uniform utilities and establish the hardness of the general problem when the groups can intersect arbitrarily. This work has applications in cloud computing, logistics, resource-constrained machine learning deployment, federated learning, and network design, where resources must be allocated across platforms with diverse cost structures and diminishing returns.
Fairness in the Multi-Secretary Problem
Authors: Georgios Papasotiropoulos; Zein Pishbin
Venue: AAAI 2026 (main)

Abstract: This paper bridges two perspectives: it studies the multi-secretary problem through the fairness lens of social choice, and examines multi-winner elections from the viewpoint of online decision making. After identifying the limitations of the prominent proportionality notion of Extended Justified Representation (EJR) in the online domain, the work proposes a set of mechanisms that merge techniques from online algorithms with rules from social choice---such as the Method of Equal Shares and the Nash Rule---and supports them through both theoretical analysis and extensive experimental evaluation.
Shapley Value Approximation Based on k-Additive Games
Authors: Guilherme Dean Pelegrina; Patrick Kolpaczki; Eyke Hüllermeier
Venue: AAAI 2026 (main)

Abstract: The Shapley value is the prevalent solution for fair division problems in which a payout is to be divided among multiple agents. By adopting a game-theoretic view, the idea of fair division and the Shapley value can also be used in machine learning to quantify the individual contribution of features or data points to the performance of a predictive model.Despite its popularity and axiomatic justification, the Shapley value suffers from a computational complexity that scales exponentially with the number of entities involved, and hence requires approximation methods for its reliable estimation. We propose SVAkADD, a novel approximation method that fits a k-additive surrogate game. By taking advantage of k-additivity, we are able to elicit the exact Shapley values of the surrogate game and then use these values as estimates for the original fair division problem. The efficacy of our method is evaluated empirically and compared to competing methods.
Weakest Bidder Types and New Core-Selecting Combinatorial Auctions
Authors: Siddharth Prasad; Maria Florina Balcan; Tuomas Sandholm
Venue: AAAI 2026 (main)

Abstract: Core-selecting combinatorial auctions are popular auction designs that constrain prices to eliminate the incentive for any group of bidders---with the seller---to renegotiate for a better deal. They help overcome the low-revenue issues of classical combinatorial auctions. We introduce a new class of core-selecting combinatorial auctions that leverage bidder information available to the auction designer. We model such information through constraints on the joint type space of the bidders---these are constraints on bidders' private valuations that are known to hold by the auction designer before bids are elicited. First, we show that type space information can overcome the well-known impossibility of incentive-compatible core-selecting combinatorial auctions. We present a revised and generalized version of that impossibility result that depends on how much information is conveyed by the type spaces. We then devise a new family of core-selecting combinatorial auctions and show that they minimize the sum of bidders' incentives to deviate from truthful bidding. We develop new constraint generation techniques---and build upon existing quadratic programming techniques---to compute core prices, and conduct experiments to evaluate the incentive, revenue, fairness, and computational merits of our new auctions. Our new core-selecting auctions directly improve upon existing designs that have been used in many high-stakes auctions around the world. We envision that they will be a useful addition to any auction designer's toolkit.
Testing Under Strategic Manipulation: Mechanism Design for Human and AI Institutions
Authors: Xiaoyun Qiu; Liren Shan
Venue: AAAI 2026 (main)

Abstract: We study how the design of testing institutions, encompassing both the tests themselves and the procedures used to administer them, shapes selection outcomes in environments with multiple criteria and strategic agents.
We model the testing agency as either a set of independent bureaucracies (each test administered separately) or a joint bureaucracy (where test order and personalization can be coordinated). Our mechanism design analysis shows that under a joint bureaucracy, fixed-order sequential mechanisms with stringent tests are optimal for maximizing the probability mass of qualified candidates selected. Furthermore, we demonstrate that personalizing tests through upfront communication, now increasingly feasible via AI and automation, can select all qualified candidates.
Finally, we compare institutional settings and quantify the value of controlling test order, showing that the benefit depends critically on the distribution of testees and the stringency of optimal tests. Our results contribute to the design of robust, efficient, and fair testing systems in both human and AI-mediated environments.
Truth, Justice, and Secrecy: Cake Cutting Under Privacy Constraints
Authors: Yaron Salman; Tamir Tassa; Omer Lev; Roie Zivan
Venue: AAAI 2026 (main)

Abstract: Cake-cutting algorithms, which aim to fairly allocate a continuous resource based on individual agent preferences, have seen significant progress over the past two decades. Much of the research has concentrated on fairness, with comparatively less attention given to other important aspects.
In 2010, Chen et al. introduced an algorithm that, in addition to ensuring fairness, was strategyproof---meaning agents had no incentive to misreport their valuations.
However, even in the absence of strategic incentives to misreport, agents may still hesitate to reveal their true preferences due to privacy concerns (e.g., when allocating advertising time between firms, revealing preferences could inadvertently expose planned marketing strategies or product launch timelines).
In this work, we extend the strategyproof algorithm of Chen et al. by introducing a privacy-preserving dimension. To the best of our knowledge, we present the first private cake-cutting protocol, and, in addition, this protocol is also envy-free and strategyproof. Our approach replaces the algorithm’s centralized computation with a novel adaptation of cryptographic techniques, enabling privacy without compromising fairness or strategyproofness. Thus, our protocol encourages agents to report their true preferences not only because they are not incentivized to lie, but also because they are protected from having their preferences exposed.
Promises Made, Promises Kept: Safe Pareto Improvements via Ex Post Verifiable Commitments
Authors: Nathaniel Sauerberg; Caspar Oesterheld
Venue: AAAI 2026 (main)

Abstract: A safe Pareto improvement (SPI) is a modification of a game that leaves all players better off with certainty. 
SPIs are typically proven under qualitative assumptions about the way different games are played. 
For example, we assume that strictly dominated strategies can be iteratively removed and that isomorphic games are played isomorphically.
In this work, we study SPIs achieved through three types of \textit{ex post} verifiable commitments -- promises about player behavior from which deviations can be detected by observing the game. 
First, we consider disarmament -- commitments not to play certain actions. 
Next, we consider SPIs based on \textit{token games}. A token game is a game played by simply announcing an action (via cheap talk). As such, its outcome is intrinsically meaningless. However, we assume the players commit in advance to play specific (pure or correlated) strategy profiles in the original game as a function of the token game outcome. Under such commitments, the token game becomes a new, meaningful normal-form game.
Finally, we consider default-conditional commitment: SPIs in settings where the players' default ways of playing the original game can be credibly revealed and hence the players can commit to act as a function of this default. 
We characterize the complexity of deciding whether SPIs exist in all three settings, giving a mixture of characterizations and efficient algorithms and \NP- and \textsc{Graph Isomorphism}-hardness
Exclusion Zones of Instant Runoff Voting
Authors: Kiran Tomlinson; Johan Ugander; Jon Kleinberg
Venue: AAAI 2026 (main)

Abstract: Recent research on instant runoff voting (IRV) shows that it exhibits a striking property over unimodal one-dimensional preferences: there is an exclusion zone around the median voter such that the winner must come from the exclusion zone, unless no such candidate exists. Thus, IRV cannot elect an extreme candidate in this setting as long as a sufficiently moderate candidate runs. In this work, we examine the mathematical structure of exclusion zones as a broad phenomenon in more general preference spaces. We prove that with voters uniformly distributed over any d-dimensional hyperrectangle (for d > 1), IRV has no such exclusion zone. However, we also show that IRV exclusion zones are not solely a one-dimensional phenomenon. For irregular higher-dimensional preference spaces with fewer symmetries than hyperrectangles, IRV can have nontrivial exclusion zones. As a further exploration, we study IRV exclusion zones with graph-based preferences, where nodes represent voters who prefer candidates closer to them in the graph. Here, we show that IRV exclusion zones present a surprising computational challenge: even checking whether a given set of positions is an IRV exclusion zone is NP-hard. We develop an efficient randomized approximation algorithm for checking and finding exclusion zones in graphs. Finally, we report on computational experiments with exclusion zones: (i) performing an exhaustive computer search of small graphs and trees, we find nontrivial IRV exclusion zones in most small graphs; and (ii) applying our approximation algorithm to a collection of larger real-world school friendship networks, we find that about 60% of these networks have probable nontrivial IRV exclusion zones. While our focus is on IRV, the properties of exclusion zones we establish provide new methods for analyzing voting systems in metric spaces more generally.
The Publication Choice Problem
Authors: Haichuan Wang; Yifan Wu; Haifeng Xu
Venue: AAAI 2026 (main)

Abstract: Researchers strategically choose where to submit their work in order to maximize its impact, and these publication decisions in turn determine venues' impact factors. To analyze how individual publication choices both respond to and shape venue impact, we introduce a game-theoretic framework - coined the Publication Choice Problem - that captures this two‐way interplay. We show the existence of a pure-strategy equilibrium in the Publication Choice Problem and its uniqueness under binary researcher types. Our characterizations of the equilibrium properties offer insights about what publication behaviors better indicate a researcher's impact level.

Through equilibrium analysis,  we further investigate how labeling papers with ``spotlight'' affects the impact factor of venues in the research community. Our analysis shows that competitive venue labeling top papers with ``spotlight'' may decrease the overall impact of other venues in the community, while less competitive venues with ``spotlight'' labeling have an opposite impact.
Centralized Group Equitability and Individual Envy-Freeness in the Allocation of Indivisible Items
Authors: Ying Wang; Jiaqian Li; Tianze Wei; Hau Chan; Minming Li
Venue: AAAI 2026 (main)

Abstract: We study the fair allocation of indivisible items to groups of agents from the perspectives of both the agents and a centralized allocator.
In our setting, the centralized allocator aims to ensure that the allocation is fair both among the groups and between individual agents. This setting applies to many real-world scenarios, such as when a school administrator allocates resources (e.g., office spaces and supplies) to staff members within departments or when a city council allocates limited housing units to families in need across different communities.
To ensure fairness between agents, we consider the classical notion of envy-freeness (EF).
To ensure fairness among groups, we introduce the notion of centralized group equitability (CGEQ), which captures fairness for groups from the centralized allocator’s perspective.
Because an EF or CGEQ allocation does not always exist in general, we consider their natural relaxations: envy-freeness to one item (EF1) and centralized group equitability up to one item (CGEQ1). 
For different classes of valuation functions of the agents and the centralized allocator, we show that allocations satisfying both EF1 and CGEQ1 always exist, and we design efficient algorithms to compute such allocations.
We also consider the centralized group maximin share (CGMMS) from the centralized allocator's perspective as a group-level fairness objective with EF1 for agents, and present several results.
Online Fair Allocations with Binary Valuations and Beyond
Authors: Yuanyuan Wang; Tianze Wei
Venue: AAAI 2026 (main)

Abstract: In an online fair allocation problem, a sequence of indivisible items arrives online and needs to be allocated to offline agents immediately and irrevocably.
In our paper, we study the online allocation of either goods or chores. 
We employ popular fairness notions, including envy-freeness up to one item (EF1) and maximin share fairness (MMS) to capture fairness, and utilitarian social welfare (USW) to measure efficiency. 
For both settings of items, we present a series of positive results regarding the existence of fair and efficient allocations with widely studied classes of additive binary and personalized bi-valued valuation/cost functions. 
Furthermore, we complement our results by constructing counterexamples to establish our results as among the best guarantees possible.
How Hard Is It to Rig a Tournament When Few Players Can Beat or Be Beaten by the Favorite?
Authors: Zhonghao Wang; Junqiang Peng; Yuxi Liu; Mingyu Xiao
Venue: AAAI 2026 (main)

Abstract: In knockout tournaments, players compete in successive rounds, with losers eliminated and winners advancing until a single champion remains. Given a tournament digraph D, which encodes the outcomes of all possible matches, and a designated player v* in V(D), the Tournament Fixing problem (TFP) asks whether the tournament can be scheduled in a way that guarantees v* emerges as the winner. TFP is known to be NP-hard, but is fixed-parameter tractable (FPT) when parameterized by structural measures such as the feedback arc set (fas) or feedback vertex set (fvs) number of the tournament digraph. In this paper, we introduce and study two new structural parameters: the number of players who can defeat v* (i.e., the in-degree of v*, denoted by k) and the number of players that v* can defeat (i.e., the out-degree of v*, denoted by l). A natural question is that: can TFP be efficiently solved when k or l is small? We answer this question affirmatively by showing that TFP is FPT when parameterized by either the in-degree or out-degree of v*. Our algorithm for the in-degree parameterization is particularly involved and technically intricate. Notably, the in-degree k can remain small even when other structural parameters, such as fas or fvs, are large. Hence, our results offer a new perspective and significantly broaden the parameterized algorithmic understanding of the Tournament Fixing problem.
Deep (Predictive) Discounted Counterfactual Regret Minimization
Authors: Hang Xu; Kai Li; Haobo Fu; Qiang Fu; Junliang Xing; Jian Cheng
Venue: AAAI 2026 (main)

Abstract: Counterfactual regret minimization (CFR) is a family of algorithms for effectively solving imperfect-information games. To enhance CFR's applicability in large games, researchers use neural networks to approximate its behavior. However, existing methods are mainly based on vanilla CFR and struggle to effectively integrate more advanced CFR variants. In this work, we propose an efficient model-free neural CFR algorithm, overcoming the limitations of existing methods in approximating advanced CFR variants. At each iteration, it collects variance-reduced sampled advantages based on a value network, fits cumulative advantages by bootstrapping, and applies discounting and clipping operations to simulate the update mechanisms of advanced CFR variants. Experimental results show that, compared with model-free neural algorithms, it exhibits faster convergence in typical imperfect-information games and demonstrates stronger adversarial performance in a large poker game.
Inequality in the Age of Pseudonymity
Authors: Aviv Yaish; Nir Chemaya; Dahlia Malkhi; Lin William Cong
Venue: AAAI 2026 (main)

Abstract: Inequality measures such as the Gini coefficient are used to inform and motivate policymaking, and are increasingly applied to digital platforms.
We analyze how measures fare in pseudonymous settings that are common in the digital age.
One key challenge of such environments is the ability of actors to create fake identities under fictitious false names, also known as ``Sybils.''
While some actors may do so to preserve their privacy, we show that this can hamper inequality measurements: it is impossible for measures satisfying the literature's canonical set of desired properties to assess the inequality of an economy that may harbor Sybils.
We characterize the class of all Sybil-proof measures, and prove that they must satisfy relaxed version of the aforementioned properties.
Furthermore, we show that the structure imposed restricts the ability to assess inequality at a fine-grained level.
We then apply our results to prove that popular measures are not Sybil-proof, with the famous Gini coefficient being but one example out of many.
Finally, we examine dynamics leading to the creation of Sybils in digital and traditional settings.
Pacing Equilibria in Second-Price Auctions with Few Buyers
Authors: Yonglei Yan; Zihe Wang; Zhengyang Liu
Venue: AAAI 2026 (main)

Abstract: We present a polynomial-time algorithm for exactly computing second-price pacing equilibria (SPPE) in auction markets with a constant number of buyers. SPPE plays a central role in modern advertising auctions; however, computing or even approximating it is PPAD-hard in general. To overcome this computational barrier in the restricted setting, we adopt the cell-decomposition method. Specifically, we partition the solution space into polynomially many cells, each defined by hyperplanes corresponding to a fixed ordering of buyers’ scaled valuations across goods. Within each cell, the equilibrium computation reduces to solving a constant number of linear programs. Notably, our algorithm can also efficiently identify equilibria that optimize key objectives such as revenue or social welfare. To the best of our knowledge, this is the first algorithm that efficiently computes an exact SPPE for a simple and natural class of second-price pacing games.
Deviation Dynamics in Cardinal Hedonic Games
Authors: Valentin Zech; Martin Bullinger
Venue: AAAI 2026 (main)

Abstract: Computing stable partitions in hedonic games is a challenging task because there exist games in which stable outcomes do not exist. Even more, these No-instances can often be leveraged to prove computational hardness results. We make this impression rigorous in a dynamic model of cardinal hedonic games by providing meta theorems. These imply hardness of deciding about the possible or necessary convergence of deviation dynamics based on the mere existence of No-instances. Our results hold for additively separable, fractional, and modified fractional hedonic games (ASHGs, FHGs, and MFHGs). Moreover, they encompass essentially all reasonable stability notions based on single-agent deviations. In addition, we propose dynamics as a method to find individually rational and contractually individual stable (CIS) partitions in ASHGs. In particular, we find that CIS dynamics from the singleton partition possibly converge after a linear number of deviations but may require an exponential number of deviations in the worst case.