IJCAI 2026 论文列表

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.

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.

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.

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.

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.)

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.)

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.

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.

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.

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.

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.

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.

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.

Graph-level anomaly detection (GLAD) is crucial for ensuring the reliability of graph-driven applications by identifying abnormal graphs that deviate from the majority. Considering the privacy concerns in distributed scenarios, federated graph-level anomaly detection (FedGLAD) has emerged as a promising solution to enable collaborative detection without sharing raw data. However, existing methods suffer from poor generalization due to the reliance on unrealistic synthetic anomalies and insufficient personalization capabilities under data heterogeneity. To address these challenges, we propose a novel Federated graph-level anomaly detection approach with Cluster-adaptIve GAted Reconstruction (FedCIGAR). Specifically, we design a reconstruction-based paradigm trained on normal graphs to avoid synthetic data. Furthermore, we introduce a client-side node contribution gating mechanism and a server-side sliding window-based clustering strategy to tackle data heterogeneity. Extensive experiments demonstrate that FedCIGAR achieves superior performance and robustness compared to state-of-the-art methods.

Graph anomaly detection (GAD) aims to identify nodes that exhibit significant deviations from expected structural or attribute patterns, and has garnered increasing attention in recent years. Recent approaches for GAD have predominantly focused on local inconsistency mining, which refers to the difficulty of establishing high similarity relationships between anomalous nodes and their neighbors. While local inconsistency mining requires the incorporation of topological information, the use of Graph Neural Networks (GNNs) to introduce such information tends to homogenize connected nodes, thereby causing the loss of local anomalous signals. To address this challenge, we propose LTRGAD, a two-stage GAD framework that performs feature selection based on local feature-topological residuals (LTR). By processing features separately, LTRGAD effectively introduces topological information while preserving the original local anomalous patterns, enabling more accurate local anomaly detection. Subsequently, global anomaly detection is conducted on the entire graph by leveraging the results from the local detection phase. Extensive experiments on seven benchmark datasets demonstrate the effectiveness of the proposed LTRGAD framework.

Forecasting precise future motion of surrounding agents is essential for reliable autonomous vehicles. However, as the demand for longer prediction horizons increases, existing endpoint-completion or iterative-refine methods increasingly struggle with weak guidance and compounding errors. To tackle the long-horizon prediction challenge, we propose Pivot-Centric Trajectory Prediction (PCTP). By introducing "pivots" and focusing on predicting pivot points along extended trajectories, we divide the long-term prediction task into short-term sub-tasks at various scales. Specifically, PCTP decouples the long-term trajectory predicting process into two processes: pivot prediction and pivot-based trajectory refinement. The pivot prediction process aims to utilize global map context and agent-to-agent interactions to identify these "pivot points", while the pivot-based trajectory refinement process focuses on local map details and refines the short-term trajectory based on predicted "pivot points". Compared with existing methods, PCTP provides more intermediate guidance while reducing compounding errors. Moreover, PCTP is a flexible approach that can be integrated into most state-of-the-art trajectory prediction models. Experimental results show that PCTP improves the prediction accuracy of leading models on both Argoverse I and Argoverse II datasets with minimal impact on model size. Specifically, PCTP combined with QCNet outperforms all published ensemble-free methods on the Argoverse II leaderboard at submission.

Mainstream industrial information retrieval systems (e.g., search and recommendation) are usually built upon Multi-Stage Cascade Architectures (MCAs), which balance effectiveness and efficiency through a coarse-to-fine "retrieval-ranking" pipeline. However, the optimization objectives across different stages are substantially inconsistent, propagating or even amplifying the early-stage errors that ultimately degrade the quality of final results. While emerging end-to-end generative models offer a potential solution by unifying the pipeline, their online serving performance is severely hindered by the auto-regressive process inherited from the standard decoder-only structure. To bridge this gap, we introduce DaV-Gen, a novel unified solution designed to fundamentally refactor the paradigm for both search and recommendation via a "Draft-and-Verify" mechanism. Inspired by the process used by speculative decoding, our framework redesigns the generation task into two synergistic operations within a single model. During training, the model is concurrently optimized for both candidate drafting and fine-grained verification. This is achieved by a composite loss function that jointly trains the model on two distinct but related objectives: 1) a contrastive loss that structures the embedding space for efficient drafting, and 2) a fusion loss that combines generative likelihood with vector similarity to produce a superior verification score. This integrated training strategy equips the model with dual capabilities. At inference time, it first performs highly efficient vector-based drafting to generate a candidate set, and then verifies these candidates using the more powerful fused scoring function, thereby achieving both the speed of sparse drafting and the precision of advanced generative models within a unified, end-to-end architecture.

Dynamic origin-destination (OD) flow generation seeks to synthesize realistic mobility dynamics from temporal context alone, without relying on historical OD observations. A key challenge is to translate semantic temporal signals into temporally coherent OD patterns while preserving the inherent spatial heterogeneity of urban regions. We propose DynaOD, a semantic-driven framework that models temporal dynamics through two complementary perspectives: discrete directional trends that characterize qualitative shifts in urban activity patterns, and continuous temporal evolution that captures how such shifts unfold over time. By jointly encoding these temporal semantics, the framework constructs time-varying region representations that condition pretrained static OD generators in a lightweight and plug-and-play fashion. This modular design further supports scalable deployment and cross-city transferability. Extensive experiments on large-scale real-world datasets show that our method consistently outperforms representative baselines in both predictive accuracy and distributional fidelity. Code is publicly available at https://github.com/csjiezhao/DynaOD.

Knowledge distillation has become a prevalent technique for deploying efficient recommender systems, enabling lightweight student models to approximate the performance of larger teachers. However, we identify a critical issue: distillation systematically amplifies popularity bias, as student models inherit and intensify the popularity-driven shortcuts encoded in teachers trained on interaction data dominated by popular items. To address this limitation, we propose GUIDE (Geodesic aware Unbiased Instructive Distillation with Experts), a collaborative distillation framework that incorporates domain-specific debiasing experts alongside the global teacher. GUIDE tackles two key challenges in this paradigm. First, for expert routing, we introduce Spherical Expert Alignment, which conducts expert-student matching on the spherical manifold with geodesic distance optimization, eliminating magnitude-induced bias and ensuring stable gradient flow. Second, for context fusion, we design a Meta-Debiasing Gate that dynamically arbitrates teacher-expert influence based on real-time user-item context through end-to-end meta-learning. Extensive experiments on multiple real-world datasets demonstrate that GUIDE significantly mitigates popularity bias while preserving recommendation accuracy, with state-of-the-art trade-offs among efficiency, accuracy, and fairness. The code and data are available at:https://github.29com/zx19971219/GUIDE.