paperlist.ai

AI conference papers

AI conference paper library

Search papers from 30+ top conferences, including NeurIPS, ICLR, ICML, CVPR, ACL and AAAI. Filter by keyword, then open any paper for its abstract, authors and links.

IJCAI 2026

Online Contract Design

Elad Lavi, Hadas Shachnai, Inbal Talgam-Cohen

We initiate the study of online contracts, which integrate the game-theoretic considerations of economic contract theory, with the algorithmic and informational challenges of online algorithm design. Our starting point is the classic online setting with preemption, in which a hiring principal faces a sequence of adversarial agent arrivals. Upon arrival, the principal must decide whether to tentatively accept the agent to their team, and whether to dismiss previous tentative choices. Dismissal is irrevocable, giving the setting its online decision-making flavor. In our setting, the agents are rational players: once the team is finalized, a game is played where the principal offers contracts (performance-based payment schemes), and each agent decides whether or not to work. Working agents reward the principal, and the goal is to choose a team that maximizes the principal's utility. Our main positive result is a 1/2-competitive algorithm when agent rewards are additive, which matches the best-possible competitive ratio. Our algorithm is randomized and this is necessary, as we show that no deterministic algorithm can attain a bounded competitive ratio. Moreover, if agent rewards are allowed to exhibit combinatorial structure known as XOS, even randomized algorithms might fail. En route to our competitive algorithm, we develop the technique of balance points, which can be useful for further exploration of online contracts in the adversarial model.

IJCAI 2026

Group Vitality Indices: Axioms and Algorithms

Natalia Kucharczuk, Oskar Skibski

We consider the problem of assessing a group of nodes in a network. Our focus is on vitality indices—a natural class of centrality measures that evaluate the importance of a node by examining the impact of its removal on the network. We conduct a comprehensive analysis of group vitality indices. Specifically, we show that every vitality index admits a unique extension to groups, which can be defined using a group variant of the Shapley value recently proposed in the literature. We also provide an axiomatization of the entire class, along with two specific group vitality indices that satisfy additional normalization conditions. Furthermore, we study the computational properties of all vitality indices, as well as Group Attachment Centrality.

IJCAI 2026

Equilibrium Refinements Improve Subgame Solving in Imperfect-Information Games

Ondrej Kubicek, Viliam Lisý, Tuomas Sandholm

Subgame solving is a technique for scaling algorithms to large games by locally refining a precomputed blueprint strategy during gameplay. While straightforward in perfect-information games where search starts from the current state, subgame solving in imperfect-information games must account for hidden states and uncertainty about the opponent's past strategy. Gadget games were developed to ensure that the improved subgame strategy is robust against any possible opponent's strategy in a zero-sum game. Gadget games typically contain infinitely many Nash equilibria. We demonstrate that while these equilibria are equivalent in the gadget game, they yield vastly different performance in the full game, even when facing a rational opponent. We propose gadget game sequential equilibria as the preferred solution concept. We introduce modifications to the sequence-form linear program and counterfactual regret minimization that converge to these refined solutions with only mild additional computational cost. Additionally, we provide several new insights into the surprising superiority of the resolving gadget game over the max-margin gadget game. Our experiments compare different Nash equilibria of gadget games in several standard benchmark games, showing that our refined equilibria consistently outperform unrefined Nash equilibria, and can reduce the exploitability of the overall strategy by more than 50%.

IJCAI 2026

Fairly Dividing Non-identical Random Items: Just Sample or Match

Aprup Kale, Navya Garg, Rucha Kulkarni

We study the question of existence and fast computation of fair and efficient allocations of indivisible resources among agents with additive valuations. As such allocations may not exist for arbitrary instances, we ask if they exist for typical or random instances, meaning when the utility values of agents for the resources are drawn from certain distributions. In this paper, we extend the previously studied formal models of this problem to non-identical items. We assume that every item is associated with a distribution U_j, and every agent's utility value for the item is drawn independently from U_j. We show that envy-free fair and maximum social welfare efficient allocations exist with high probability in the asymptotic setting, meaning when the number of agents n and items m are large. Further, we show that when m = Ω(n log n), then by only sampling O(log m) or O((log m)^2) utility values per item instead of all the n, we can compute these allocations in Õ(m) time. Finally, we simulate our algorithms on randomly generated instances and show that even for small instances, we suffer small multiplicative losses in the fairness and efficiency guarantees and converge to fully optimal guarantees quickly.

IJCAI 2026

Optimally Curating an Event

Mohammad Hajiaghayi, Sebastien Lahaie, Mohammad Mahdavi, Suho Shin

We study the optimal design of a self-financing event, a problem that requires balancing the recruitment of costly, positive-value participants with revenue-generating agents who may impose negative values on the event. We introduce a novel two-sided mechanism design framework with plus agents equipped with private costs and positive impact, and minus agents with private values and negative impact upon inclusion in the event, to maximize the overall quality of the event under a budget-balanced (BB) constraint so that the designer does not run a deficit. We conduct a comprehensive study on the theory of optimal event curation on various utility functions. For additive utility, we fully characterize the optimal incentive-compatible Bayesian mechanism under both the ex-ante and ex-post BB constraints. For submodular utility, we propose an ex-ante BB mechanism that achieves a constant-factor approximation to the optimal Bayesian mechanism.

IJCAI 2026

Computing Epistemtic EF1 and Pareto-Optimal Allocations of Indivisible Chores

Jugal Garg, Aniket Murhekar

We study the allocation of m indivisible chores among n agents with additive disutilities under the fairness notion of envy-freeness up to one chore (EF1) and the efficiency notion of Pareto-optimality (PO). Although the existence of an allocation satisfying both EF1 and PO was recently established using a highly non-constructive fixed-point argument, an effective algorithm for computing such an allocation remains elusive, prompting the study of meaningful relaxations of these desiderata. Prior work introduced a natural relaxation through the concept of epistemic fairness: an allocation is said to be epistemic EF1 (EEF1), if for every agent i, it is possible to re-allocate the bundles of agents other than i such that i becomes EF1. In this work, we present a pseudo-polynomial time algorithm for computing an allocation of chores that is both EEF1 and PO. This gives an efficient polynomial-time algorithm for most practical settings where disutility values are integral and polynomially bounded in m and n. Our result employs the competitive equilibrium framework and relies on several technical insights that both utilize the distinct structure of epistemic EF1 and address the challenges it introduces.

IJCAI 2026

Stability Under Valuation Updates in Coalition Formation

Fabian Frank, Matija Novaković, René Romen

Coalition formation studies how to partition a set of agents into disjoint coalitions based on their preferences. In this paper, we consider the class of additively separable hedonic games and study the setting in which agents' valuations of each other evolve over time. Since rearranging coalitions can be costly, our goal is to find a stable partition close to the current one, where distance is measured by the number of agents that must change coalition. We study this problem for four stability notions based on single-agent deviations: Nash, individual, contractual Nash, and contractual individual stability. For all four, deciding whether a close stable partition exists is NP-complete, even under severe restrictions on the valuations and even when only a single valuation changes. On the positive side, we give polynomial-time algorithms for the two contractual notions under restricted symmetric valuations, and show that over long sequences of updates, these algorithms maintain stability with constant average reconfiguration cost.

IJCAI 2026

Beyond Stability: Improved Efficiency Guarantees for α-Stable Matchings

Isabel Fernandez Abad, Sophie Klumper, Guido Schäfer

Stable matching mechanisms are fundamental to market design but face an inherent tension between stability and social welfare optimality. We study a natural relaxation of stability, termed α-stability, which models agents as willing to deviate only when the potential improvement is sufficiently large. Under α-stability, no pair of agents can deviate and improve their valuations by more than a factor of 1/α, with α ∈ (0,1]. We provide a complete characterization of the stability--efficiency tradeoff under asymmetric valuations. This tradeoff depends on the degree of asymmetry μ ∈ (0,1], which bounds the ratio between agents’ valuations for any pair. Our results show that relaxing stability can substantially improve achievable efficiency guarantees. We further present a polynomial-time algorithm that computes an α-stable matching attaining the best possible efficiency guarantee. For α ≤ μ/(μ+1), our algorithm achieves 1-efficiency; for larger α, it computes an α-stable matching achieving at least (1/α) · μ/(μ+1) of the optimal social welfare. Remarkably, our algorithm inflates the values of an optimal matching and then applies the Gale–Shapley algorithm to the modified instance. Finally, we show that computing an optimal α-stable matching is NP-hard, even under slight relaxations of stability, i.e., for α close to 1.

IJCAI 2026

Computing Better Approximate Pure Nash Equilibria in Payoff-maximization Potential Games

Angelo Fanelli

Potential games are a fundamental class of games in which pure Nash equilibria are guaranteed to exist, yet computing such equilibria is computationally intractable for several subclasses. This has led to extensive research on computing approximate pure Nash equilibria. In this paper, we study payoff-maximization potential games. For these games, strong approximation guarantees are known only for restricted subclasses, most notably Pd--Flip games. We show that standard approaches based on unilateral improvement moves can fail to provide any finite approximation guarantee even for simple extensions of Pd--Flip games. To overcome this limitation, we propose an algorithmic framework based on coordinated moves by small groups of players, whose approximation guarantee and number of moves are controlled by two natural game parameters, the stretch and the spread, which are bounded for broad classes of games of interest. In the special case of Pd--Flip games, our framework can be configured to recover the existing algorithm, matching its approximation guarantee and the number of moves performed.

IJCAI 2026

Agreement, Diversity, and Polarization Indices for Approval Elections

Piotr Faliszewski, Jitka Mertlová, Krzysztof Sornat, Stanisław Szufa, Tomasz Wąs

An index is a function that measures the extent to which an election has a particular feature. We seek indices that capture agreement, diversity, and polarization among voters in approval elections, normalized with respect to saturation. The latter means that if two elections differ by the fraction of candidates approved by an average voter, but otherwise are of similar nature, then they should have similar index values. We propose several indices, analyze their properties, and use them to derive a new map of approval elections, and compare various real-life elections from Pabulib, Preflib and other sources.

IJCAI 2026

Multi-Agent Non-Discriminatory Contracts

Ke Ding, Bo Li, Ankang Sun

We study multi-agent contracts, in which a principal delegates a task to multiple agents and incentivizes them to exert effort. Prior research has mostly focused on maximizing the principal’s utility, often resulting in highly disparate payments among agents. Such disparities among agents may be undesirable in practice, for example, in standardized public contracting or worker cooperatives where fairness concerns are essential. Motivated by these considerations, our objective is to quantify the tradeoff between maximizing the principal's utility and equalizing payments among agents, which we call the price of non-discrimination. Our first result is an almost tight bound on the price of non-discrimination, which scales logarithmically with the number of agents. This bound can be improved to a constant by allowing some relaxation of the non-discrimination requirement. We then provide a comprehensive characterization of the tradeoff between the level of non-discrimination and the loss in the optimal utility.

IJCAI 2026

The Communication Complexity of Instant-Runoff Voting

Elie De Panafieu, François Durand, Jérôme Lang

The communication complexity of a voting rule is the worst-case number of bits that n voters must transmit to a central authority under the most efficient elicitation protocol in an election with m candidates. We study the communication complexity of Instant-Runoff Voting (IRV). Conitzer and Sandholm [2005] established an upper bound of O(n (log m)^2), but did not provide a matching lower bound beyond Omega(n log m). We resolve this open problem by raising the lower bound to Omega(n (log m)^2) using the fooling set technique, thereby showing that the communication complexity of IRV is Theta(n (log m)^2). We further show that this complexity drops to Theta(n log m) under the single-peakedness restriction, and that both the IRV-Average variant and Single Transferable Vote (STV), the multiwinner extension of IRV, have the same asymptotic communication complexity as IRV. (Extended version with appendices: https://shs.hal.science/hal-05566718. Short video: https://youtu.be/gTXV3R2DS6o.)

IJCAI 2026

Super Condorcet Winners and Limit Coalitional Manipulability of IRV

Elie De Panafieu, François Durand, Guillem Perarnau

We study the limit CM rate of single-winner voting rules under Impartial Culture, defined as the probability that a preference profile is coalitionally manipulable in the limit of large electorates. For three candidates, Lepelley and Valognes [1999] derived a closed-form expression for Plurality with Runoff, or equivalently Instant-Runoff Voting (IRV), and showed that its limit CM rate is strictly below one. This is remarkable because Kim and Roush [1996] established a limit of one for several major rules, including Maximin and all positional scoring rules except Veto. In this paper, we generalize the result of Lepelley and Valognes to any number of candidates greater than or equal to four. We show that Plurality with Runoff has a limit CM rate equal to one for all such numbers of candidates, whereas IRV retains a limit CM rate strictly below one. To this end, we rely on the notion of Super Condorcet Winner, recently introduced by Durand [2025], which yields an upper bound on the CM rate of IRV. We prove that this bound is asymptotically tight and compute the probability that a Super Condorcet Winner exists, thereby obtaining the exact limit CM rate of IRV. (Extended version with appendices: https://hal.science/hal-05566713. Short video: https://youtu.be/4i2A7qUP-eo.)

IJCAI 2026

Tight Asymptotic Bounds for Fair Division with Externalities

Frank Connor, Max Dupre la Tour, Vishnu V. Narayan, Šimon Schierreich

We study the problem of allocating a set of indivisible items among agents whose preferences include externalities. Unlike the standard fair division model, agents may derive positive or negative utility not only from items allocated directly to them, but also from items allocated to other agents. Since exact envy-freeness cannot be guaranteed, prior work has focused on its relaxations. However, two central questions remained open: does there always exist an allocation that is envy-free up to one item (EF1), and if not, what is the optimal relaxation EF-k that can always be attained? We settle both questions by deriving tight asymptotic bounds on the number of items sufficient to eliminate envy. We show that for any instance with n agents, an allocation that is envy-free up to O(√n) items always exists and can be found in polynomial time. Additionally, via a reduction from fair division with externalities to discrepancy theory combined with recent discrepancy lower bounds, we prove a matching Ω(√n) lower bound showing that this result is tight even when the valuations are binary and satisfy the no-chores condition, which refutes a conjecture from previous work and resolves the main open question in the area, ruling out the existence of EF1 allocations when agents have externalities.

IJCAI 2026

Cycles in Liquid Democracy: A Game-Theoretic Justification

Markus Brill, Rachael Colley, Anne-Marie George, Grzegorz Lisowski, Georgios Papasotiropoulos, Ulrike Schmidt-Kraepelin

A common criticism of liquid democracy within the relevant academic literature is that delegation cycles can occur, seemingly resulting in unused voting power. Yet, practitioners argue that delegation cycles are not only unproblematic but are even formed intentionally by participants. To bring theory closer to reality, we introduce a model that captures this strategic behavior under uncertainty. We study the existence, structure and quality of Nash equilibria, revealing that delegation cycles naturally emerge. To complement these findings, we perform computational experiments using best-response dynamics.

IJCAI 2026

Approximate Strategyproofness in Approval-Based Budget Division

Haris Aziz, Patrick Lederer, Jeremy Vollen

In approval-based budget division, the task is to allocate a divisible resource to the candidates based on the voters' approval preferences over the candidates. For this setting, Brandl et al. (2021) have shown that no distribution rule can be strategyproof, efficient, and fair at the same time. In this paper, we aim to circumvent this impossibility theorem by focusing on approximate strategyproofness. To this end, we analyze the incentive ratio of distribution rules, which quantifies the maximum multiplicative utility gain of a voter by manipulating. While it turns out that several classical rules have a large incentive ratio, we prove that the Nash product rule (NASH) has an incentive ratio of 2, thereby demonstrating that we can bypass the impossibility of Brandl et al. by relaxing strategyproofness. Moreover, we show that an incentive ratio of 2 is optimal within three natural classes of rules and that the positive result for the Nash product rule even holds when voters may report arbitrary concave utility functions. Finally, we complement our results with an experimental analysis.

IJCAI 2026

Disentangled Hypergraph Network with Implicit Structure Learning for Mobility Social Relationship Inference

Jingjing Zhu, Xiang Li, Dongliang Chen, Haobing Liu, Yuan Cao, Yanwei Yu

Inferring social relationships from users' mobile data holds significant value for personalized recommendations. Most methods model user interactions based on co-occurrence records, achieving impressive success in capturing social signals. However, despite these advancements, current techniques still face three primary challenges. First, compressing higher-order co-occurrences into a single representation space easily leads to semantic entanglement. Second, relying on deterministic topology overlooks unobserved homophily. Third, the intrinsic characteristics of the users themselves are frequently ignored. To address these challenges, we propose a Disentangled Hypergraph Network with Implicit Structure Learning for mobility social relationship inference, named DHISL. Specifically, it first captures individual spatiotemporal characteristics through feature-guided representation initialization, and then adopts a dual-branch framework: the explicit branch models social and spatiotemporal preference signals, while the implicit branch adaptively learns a sparse channel-wise relational structure via differentiable structure learning. Furthermore, we introduce dual constraints in a multi-channel disentangled space to achieve intra-channel consistency and inter-channel exclusivity. Experiments on four real-world datasets demonstrate that DHISL outperforms state-of-the-art models, achieving average improvements of 6.34% in ROCAUC and 6.39% in PRAUC. The source code is available at https://github.com/Tilamisu-zz/DHISL.

IJCAI 2026

GMM-TDQN:Two-Stage Multi-Objective Reinforcement Learning for Large-Scale Edge Server Deployment

Zhou Zhou, Tingyu Zheng, Yifu Zeng

The deployment of edge servers plays a crucial role in supporting large-scale edge computing systems, where multiple conflicting objectives—such as latency, energy consumption, load balancing, and service reliability—must be jointly optimized in complex, dynamic environments. Existing solutions often struggle to scale effectively or to balance these objectives in a unified learning framework. In this paper, we propose GMM-TDQN, a two-stage multi-objective reinforcement learning framework for large-scale edge server deployment. The first stage employs a Gaussian Mixture Model (GMM) to capture spatial and workload heterogeneity, enabling an efficient reduction of the deployment search space. Building upon this structured initialization, the second stage formulates the deployment problem as a sequential decision-making task and adopts a Transformer-enhanced Deep Q-Network (TDQN) to learn adaptive deployment policies that balance multiple objectives. Extensive experiments on real-world datasets demonstrate that GMM-TDQN consistently outperforms state-of-the-art methods, achieving reductions of 29.18% in average latency and 17.55% in energy consumption, while improving load balancing by 27.50% and system reliability by 32.55%. These results validate the effectiveness and scalability of the proposed framework for multi-objective edge server deployment.

IJCAI 2026

ASTPKEFormer: Adaptive Spatiotemporal Prior Knowledge Embedding-Induced Transformers for Traffic Data Forecasting

Wenfeng Zhou, Xiaoyun Xia, Xiangjie Kong, Guojiang Shen, Bin CHEN, Fei Wu, Binbin Guo

Traffic forecasting is fundamentally challenging due to the complex and dynamic spatiotemporal dependencies inherent in road networks. Although existing prediction models are able to achieve certain results on this task, existing Transformer-based models usually rely on simple embedding strategies and do not fully utilize the prior knowledge embedded in traffic patterns and network topology. To address these limitations, we propose ASTPKEformer, a prior knowledge-guided Transformer framework for traffic prediction. Based on the pure Transformer spatiotemporal self-attention mechanism, this model first uses a multi-scale temporal channel alignment module to generate discriminative feature embeddings. Then, it incorporates temporal prior embeddings and spatial graph structure prior embeddings to provide learning guidance for the model in both temporal and spatial dimensions. To further enhance the representation capability, an embedding cross-fusion mechanism is introduced to strengthen the interaction between the previous embeddings and the adaptive spatiotemporal embedding. Extensive experiments on six real-world traffic datasets demonstrate that ASTPKEformer consistently outperforms state-of-the-art (SOTA) baselines, validating its effectiveness and strong generalization ability.

IJCAI 2026

Detection-Explanation-Improvement: A Closed-Loop Framework of Enhancing Anomaly Detection with Counterfactual Explanations

Peng Zhou, Zhiyong Huang, Yuanting Yan

Many state‑of‑the‑art anomaly detection models operate as black boxes, limiting interpretability and hindering reliable deployment. While recent advances in explainable artificial intelligence have focused on explaining why individual instances are detected as anomalous, comparatively little attention has been paid to how such explanations can be systematically exploited to improve the detectors themselves. To address this gap, we propose EAD‑CE (Enhancing Anomaly Detection with Counterfactual Explanations), a model‑agnostic, closed‑loop framework that tightly integrates detection, explanation, and improvement. Specifically, given a trained anomaly detector and its detected anomalies, EAD‑CE generates minimal and semantically meaningful counterfactual explanations that reveal how targeted feature perturbations influence anomaly scores or decisions. Feature importance inferred from these counterfactual explanations is then used to guide a dynamic feature-weight optimization process, enabling detector refinement without modifying its underlying architecture. Extensive experiments on nine real‑world datasets and three anomaly detection models demonstrate that EAD‑CE accurately identifies anomaly‑driving features, substantially enhances interpretability, and consistently improves detection performance (average AUC increases by 6.9%, up to 23%). Implementation details are provided to support reproducibility.

Keep browsing

More papers from top AI conferences

30+ top conferences, by conference, year, and topic.