GenAI4ELab/papercli-papers huggingface dataset:
Edge-Binary Public Goods Games
Authors: Thekla Hamm; Paloma T. de Lima
Venue: AAAI 2026 (main)

Abstract: Binary networked public goods games model situations in which players can choose whether to participate in an action at some cost which benefits players in their immediate vicinity within some typically social or infrastructural network.
An important underlying assumption for this model is that participation in an action impacts the entire vicinity of participating players.
However, there are numerous natural settings in which participation influences only a subset of the neighbors and is in fact more "interaction-specific''.
In this work, we introduce a type of game that is more appropriate in such settings. 
We initiate the investigation of these games, by studying the complexity of deciding existence of their Nash equilibria in general and with respect to well-motivated structural restrictions on the network.
The outcome is a comprehensive understanding of the complexity of computing Nash equilibria with respect to any combination of three natural properties of the network structure.
Scalable Solutions to Zero-Sum Partially Observable Stochastic Games Through Belief Aggregation with Approximation Guarantees
Authors: Kim Hammar; Tansu Alpcan
Venue: AAAI 2026 (main)

Abstract: We study the problem of solving one-sided, zero-sum, partially observable stochastic games (POSGs). These games model sequential interactions between two adversaries, where one player has partial observability of the game state. They are applicable to many important domains, such as robotics and cybersecurity. Solving such games is computationally challenging since the solution depends on the first player's belief about the game state, which belongs to a continuous (and often high-dimensional) belief space. In the literature, only a single method has demonstrated reliable performance for solving these types of games, namely Heuristic Search Value Iteration (HSVI). However, this method is restricted to small games. We address this limitation by presenting a new method with similar approximation and convergence guarantees but improved scalability and flexibility, which we call SAB: Shapley iteration with Aggregated Beliefs. Our method aggregates the belief space into a finite set of representative beliefs and computes their values through Shapley iteration. It then approximates the value function of the POSG through interpolation from these values. We prove that SAB converges and provide a bound on its approximation error. Experiments across several benchmark games show that SAB matches the performance of HSVI on small game instances while also scaling to larger games. Moreover, we find that SAB is up to 79% faster than HSVI at obtaining a near-optimal approximation.
Improved Differentially Private Algorithms for Rank Aggregation
Authors: Quentin Hillebrand; Pasin Manurangsi; Vorapong Suppakitpaisarn; Phanu Vajanopath
Venue: AAAI 2026 (main)

Abstract: Rank aggregation is a task of combining the rankings of items from multiple users into a single ranking that best represents the users' rankings. Alabi et al. (AAAI'22) presents differentially-private (DP) polynomial-time approximation schemes (PTASes) and 5-approximation algorithms with certain additive errors for the Kemeny rank aggregation problem in both central and local models. In this paper, we present improved DP PTASes with smaller additive error in the central model. Furthermore, we are first to study the footrule rank aggregation problem under DP. We give a near-optimal algorithm for this problem; as a corollary, this leads to 2-approximation algorithms with the same additive error as the 5-approximation algorithms of Alabi et al. for the Kemeny rank aggregation problem in both central and local models.
Stable Voting and the Splitting of Cycles
Authors: Wesley H. Holliday; Milan Mossé; Chase Norman; Eric Pacuit; Cynthia Wang
Venue: AAAI 2026 (main)

Abstract: Algorithms for resolving majority cycles in preference aggregation have been studied extensively in computational social choice. Several sophisticated cycle-resolving methods, including Tideman's Ranked Pairs, Schulze's Beat Path, and Heitzig's River, are refinements of the Split Cycle (SC) method that resolves majority cycles by discarding the weakest majority victories in each cycle. Recently, Holliday and Pacuit proposed a new refinement of Split Cycle, dubbed Stable Voting, and a simplification thereof, called Simple Stable Voting (SSV). They conjectured that SSV is a refinement of SC whenever no two majority victories are of the same size. In this paper, we prove the conjecture up to 6 alternatives and refute it for more than 6 alternatives. While our proof of the conjecture for up to 5 alternatives uses traditional mathematical reasoning, our 6-alternative proof and 7-alternative counterexample were obtained with the use of SAT solving. The SAT encoding underlying this proof and counterexample is applicable far beyond SC and SSV: it can be used to test properties of any voting method whose choice of winners depends only on the ordering of margins of victory by size.
Fair Societies: Algorithms for House Allocations
Authors: Hadi Hosseini; Sanjukta Roy; Aditi Sethia
Venue: AAAI 2026 (main)

Abstract: House allocations concern with matchings involving one-sided preferences, where houses serve as a proxy encoding valuable indivisible resources  (e.g. organs, course seats, subsidized public housing units) to be allocated among the agents. Every agent must receive exactly one resource.  
We study algorithmic approaches towards ensuring fairness in such settings. Minimizing the number of envious agents is known to be computationally hard. We present two tractable approaches to deal with the hardness. 
When the agents are presented with an initial allocation of houses, we aim to refine this allocation by reallocating a bounded number of houses to reduce the number of envious agents. We show an efficient algorithm when the agents express preference for a bounded number of houses and houses are accepted by a bounded number of agents. Next, we consider single peaked preference domain and present a polynomial time algorithm for finding an allocation that minimize the number of envious agents. We further extend it to satisfy Pareto efficiency. Our former algorithm works for other measures of envy such as total envy, or maximum envy, with
suitable modifications. Finally, we present
an empirical analysis recording the fairness-welfare trade-off
of our algorithms.
Non-Monotonicity in Fair Division of Graphs
Authors: Hadi Hosseini; Shraddha Pathak; Yu Zhou
Venue: AAAI 2026 (main)

Abstract: We consider the problem of fairly allocating the vertices of a graph among n agents, where the value of a bundle is determined by its cut value---the number of edges with exactly one endpoint in the bundle.
This model naturally captures applications such as team formation and network partitioning, where valuations are inherently non-monotonic: the marginal values may be positive, negative, or zero depending on the composition of the bundle.
We focus on the fairness notion of envy-freeness up to one item (EF1) and explore its compatibility with several efficiency concepts such as Transfer Stability (TS) that prohibits any transfer of item that benefit one agent at another's expense.
For general graphs, our results uncover a non-monotonic relationship between the number of agents n and the existence of allocations satisfying EF1 and transfer stability (TS): such allocations always exist for n=2, may fail to exist for n=3, but exist again for all n>= 4. 
We further show that existence can be guaranteed for any n by slightly weakening the efficiency requirement or by restricting the graph to forests. All of our positive results are achieved via efficient algorithms.
Fair and Efficient Balanced Allocation for Indivisible Goods
Authors: Yasushi Kawase; Ryoga Mahara
Venue: AAAI 2026 (main)

Abstract: We study the problem of allocating indivisible goods among agents with additive valuation functions to achieve both fairness and efficiency under the constraint that each agent receives exactly the same number of goods (the balanced constraint). While this constraint is common in real-world scenarios such as team drafts or asset division, it significantly complicates the search for allocations that are both fair and efficient. Envy-freeness up to one good (EF1) is a well-established fairness notion for indivisible goods. Pareto optimality (PO) and its stronger variant, fractional Pareto optimality (fPO), are widely accepted efficiency criteria. Our main contribution establishes both the existence and polynomial-time computability of allocations that are simultaneously EF1 and fPO under balanced constraints in two fundamental cases: (1) when agents have at most two distinct types of valuation functions, and (2) when each agent has a personalized bivalued valuation. Our algorithms leverage novel applications of maximum-weight matching in bipartite graphs and duality theory, providing the first polynomial-time solutions for these cases and offering new insights for constrained fair division problems.
Sequential Selling with Sunk Cost Bias
Authors: Yasushi Kawase; Tomohiro Nakayoshi
Venue: AAAI 2026 (main)

Abstract: We study a sequential selling problem in which an agent receives daily offers to sell a good, incurs a holding cost each day, and is subject to sunk cost bias---allowing past, irrecoverable costs to influence present decisions. We introduce a formal model parameterizing the degree of sunk cost bias and distinguish between three behavioral types: optimistic (who ignore future bias), naive (who assume their current bias persists), and sophisticated (who anticipate the evolution of their own bias). For each type, we characterize the optimal selling strategy and precisely quantify the worst-case gap in expected objective profit compared to an unbiased agent. Our results show that optimistic agents can suffer a quadratic loss in profit due to excessive waiting, naive agents perform identically to unbiased agents, and sophisticated agents limit their losses to a linear function of the time horizon. These findings clarify how different anticipations of sunk cost bias affect sequential decision-making and suggest targeted interventions to mitigate inefficiency.
Algorithms for Structured Elections Under Thiele Voting Rules
Authors: Alexandra Lassota; Krzysztof Sornat
Venue: AAAI 2026 (main)

Abstract: We study the computational complexity of winner determination problems in approval-based committee elections under Thiele voting rules. These form a class of rules parameterized by a fixed weight vector that specifies how a voter's satisfaction depends on the number of approved candidates elected. We first analyze the structure of optimal solutions based on the sets of voters who approve each candidate---that is, how voters' approval ballots induce dependencies between candidates---revealing constraints on a winning committee under any fixed Thiele voting rule. Using this, we design FPT algorithms for Proportional Approval Voting (PAV) and other Thiele rules on a natural restricted domain known as the Voter Interval domain---that is, after a suitable ordering of voters, each candidate is approved by a consecutive interval of voters. In particular, we show that every Thiele rule on Voter Interval is FPT with respect to a parameter for which the problem is NP-hard on general instances, even when the parameter takes constant values. Our results advance the understanding of the computational complexity of PAV on Voter Interval instances, which remains one of the central open questions in this area. We further resolve two open questions from the literature on PAV (and other Thiele voting rules) by providing a polynomial-time algorithm for instances where each candidate is approved by at most two voters, and an FPT algorithm parameterized by the total score of a winning committee.
Facility Location for Congesting Commuters and Generalizing the Cost-Distance Problem
Authors: Thanasis Lianeas; Marios Mertzanidis; Aikaterini Nikolidaki
Venue: AAAI 2026 (main)

Abstract: In Facility Location problems there are agents that should be connected to facilities and  locations where facilities may be opened so that agents can connect to them. We depart from Uncapacitated Facility Location and by assuming that the connection costs of agents to facilities are congestion dependent, we define a novel problem, namely, Facility Location for Congesting (Selfish) Commuters. The connection costs of agents to facilities come as a result of how the agents commute to reach the facilities in an underlying network with cost functions on the edges. Inapproximability results follow from the related literature and thus approximate solutions is all we can hope for. For when the cost functions are nondecreasing we employ in a novel way an approximate version of Caratheodory’s Theorem to show how approximate solutions for different versions of the problem can be derived. For when the cost functions are nonincreasing we show how this problem generalizes the Cost-Distance problem and provide an algorithm that for this more general case achieves the same approximation guarantees.
EFX Allocation in (Multi)Hypergraphs
Authors: Thanasis Lianeas; Alkmini Sgouritsa; Minas Marios Sotiriou
Venue: AAAI 2026 (main)

Abstract: We study fair allocations of indivisible goods among agents with heterogeneous monotone valuations. As fair we consider the allocations that are envy-free-up-to-any-good (EFX). Finding if EFX allocations always exist, even for agents with additive valuations, is a major open problem in Fair Division. 
Christodoulou et al. (2023) introduced the (multi-hyper)graph setting, where agents and goods are represented by vertices and edges of a graph, respectively, and only the endpoints of an edge may have non-zero marginal value for it. We show that for hypergraphs with girth at least 4 and agents with general monotone valuations there always exists an EFX allocation and can be constructed in polynomial time. We generalize our approach to also show that multi-hypergraphs with girth (on the simple hypergraph) at least 4 always admit an EFX allocation, as long as there exists a single vertex whose adjacent edges have multiplicity at most the size of that edge minus 2; our construction in this case needs pseudo-polynomial time.
Fairness in Repeated Matching: A Maximin Perspective
Authors: Eugene Lim; Tzeh Yuan Neoh; Nicholas Teh
Venue: AAAI 2026 (main)

Abstract: 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.
Security Games with Layered Defenses: Adaptive Adversaries and Gittins Indices
Authors: Chun Kai Ling; Jakub Černý; Chin Hui Han; Garud Iyengar; Christian Kroer
Venue: AAAI 2026 (main)

Abstract: Real-world security applications (e.g., cybersecurity) often involve multiple attack paths, each with layers of defenses that an attacker needs to sequentially overcome before a successful attack on the entire system. Each defensive resource changes dynamically in efficacy as the attack unfolds.
In this paper, we study the case where attackers are adaptive, potentially switching paths over time in response to these changes with the goal to minimize the expected time until a successful attack.
We formalize this as a min-max game and give examples where adaptive attackers are more powerful than non-adaptive ones. We show that defenses that do not account for adaptivity can perform arbitrarily worse. A connection between the attacker's optimal strategy with the classical theory of multi-armed bandits and the Gittins index is made, yielding a simple gradient based algorithm to solve our proposed min-max game. Experiments on synthetic settings validate our approach.
The Power of Initial Investigation in Audit Games
Authors: Ren Liu; Weiran Shen
Venue: AAAI 2026 (main)

Abstract: Audit games are an important variant of the Stackelberg security game, a widely studied game-theoretic model over the past years. It has been acknowledged that a pre-audit phase can notably enhance the audit's efficiency by informing and directing the following audit procedures.

In this paper, we model the above process with a two-stage audit game. The game encompasses two stages: an investigation stage where the auditor gathers information about potential policy breaches, and an audit stage where the auditor allocates the audit resources based on the investigation results.

We formulate the problem as a set of mathematical programs. Due to the non-convexity of the programs, we consider a restricted strategy space and show that the optimal strategy in the restricted space can be determined by solving a polynomial number of convex optimization problems. Finally, we conduct extensive experiments to evaluate the effect of introducing the initial investigation stage and our algorithm. Our experiments show that even a small budget for the initial investigations can significantly enhance the defender's utility.
Position Fair Mechanisms Allocating Indivisible Goods
Authors: Ryoga Mahara; Ryuhei Mizutani; Taihei Oki; Tomohiko Yokoyama
Venue: AAAI 2026 (main)

Abstract: Fair division mechanisms for indivisible goods require agent orderings to deterministically select one allocation when running the algorithm in practice. We introduce position envy-freeness up to one good (PEF1) as a fairness criterion for mechanisms: a mechanism is said to satisfy PEF1 if for any pair of agent orderings, no agent prefers their bundle determined under one ordering to that under another ordering by more than the utility of a single good. First, we propose a scale-invariant, polynomial-time mechanism that satisfies PEF1 and yields an envy-freeness up to one good (EF1) allocation. For the case of two agents, we establish that any mechanism producing a maximum Nash welfare allocation eliminates envy based on positions by removing one good, provided that utilities are positive. Additionally, we present a polynomial-time mechanism based on the adjusted winner procedure, which satisfies PEF1 and produces an EF1 and Pareto optimal allocation for two agents. In contrast, we demonstrate that well-known mechanisms such as round-robin and envy-cycle elimination do not generally satisfy PEF1.
Area-Optimal Control Strategies for Heterogeneous Multi-Agent Pursuit
Authors: Kamal Mammadov; Damith C. Ranasinghe
Venue: AAAI 2026 (main)

Abstract: This paper presents a novel strategy for a multi-agent pursuit-evasion game involving multiple faster pursuers with heterogenous speeds and a single slower evader. We define a geometric region, the evader's safe-reachable set, as the intersection of Apollonius circles derived from each pursuer-evader pair. The capture strategy is formulated as a zero-sum game where the pursuers cooperatively minimize the area of this set, while the evader seeks to maximize it, effectively playing a game of spatial containment. By deriving the analytical gradients of the safe-reachable set's area with respect to agent positions, we obtain closed-form, instantaneous optimal control laws for the heading of each agent. These strategies are computationally efficient, allowing for real-time implementation. Simulations demonstrate that the gradient-based controls effectively steer the pursuers to systematically shrink the evader’s safe region, leading to guaranteed capture. This area-minimization approach provides a clear geometric objective for cooperative capture.
On Condorcet’s Jury Theorem with Abstention
Authors: Reshef Meir; Ganesh Ghalme
Venue: AAAI 2026 (main)

Abstract: The well-known Condorcet Jury Theorem states that, under majority rule, the better of two alternatives is chosen with probability approaching one as the population grows. We study an asymmetric setting where voters face varying participation costs and share a possibly heuristic belief about their pivotality (ability to influence the outcome).

In a costly voting setup where voters abstain if their participation cost is greater than their pivotality estimate, we identify a single property of the heuristic belief---weakly vanishing pivotality---that  gives rise to multiple stable equilibria in which elections are nearly tied. In contrast, strongly vanishing pivotality (as in the standard Calculus of Voting model) yields a unique, trivial equilibrium where only zero-cost voters participate as the population grows.  We then characterize when nontrivial equilibria satisfy  a version of the Jury Theorem: below a sharp threshold, the majority-preferred candidate wins with probability approaching one; above it, both candidates either win with equal probability.
Faster Game Solving via Asymmetry of Step Sizes
Authors: Linjian Meng; Tianpei Yang; Youzhi Zhang; Zhenxing Ge; Yang Gao
Venue: AAAI 2026 (main)

Abstract: Counterfactual Regret Minimization (CFR) algorithms are widely used to compute a Nash equilibrium (NE) in two-player zero-sum imperfect-information extensive-form games (IIGs). Among them, Predictive CFR+ (PCFR+) is particularly powerful, achieving an exceptionally fast empirical convergence rate via the prediction in many games. However, the empirical convergence rate of PCFR+ would significantly degrade if the prediction is inaccurate, leading to unstable performance on certain IIGs. To enhance the robustness of PCFR+, we propose Asymmetric PCFR+ (APCFR+), which employs an adaptive asymmetry of step sizes between the updates of implicit and explicit accumulated counterfactual regrets to mitigate the impact of the prediction inaccuracy on convergence. We present a theoretical analysis demonstrating why APCFR+ can enhance the robustness. To the best of our knowledge, we are the first to propose the asymmetry of step sizes, a simple yet novel technique that effectively improves the robustness of PCFR+. Then, to reduce the difficulty of implementing APCFR+ caused by the adaptive asymmetry, we propose a simplified version of APCFR+ called Simple APCFR+ (SAPCFR+), which uses a fixed asymmetry of step sizes to enable only a single-line modification compared to original PCFR+. Experimental results on five standard IIG benchmarks and two heads-up no-limit Texas Hold’em (HUNL) Subagems show that (i) both APCFR+ and SAPCFR+ outperform PCFR+ in most of the tested games, (ii) SAPCFR+ achieves a comparable empirical convergence rate with APCFR+, and (iii) our approach can be generalized to improve other CFR algorithms, e.g., Discount CFR (DCFR).