On-demand delivery platforms rely on Travel Time Estimation (TTE) to balance courier earnings and overdue risks. In collaboration with one of China's largest platforms, we address a critical "Fairness Gap" in TTE: current systems fail to capture complex delivery patterns in GNSS-denied environments, subjecting couriers handling high concurrent order volumes to disproportionate pressure due to overdue deliveries. Analyzing 1.27 million real-world trajectories, we attribute this bias to unique challenges in GNSS-denied scenarios: distributional heterogeneity, structural heterogeneity, and contextual uncertainty. To bridge this gap, we propose DART (Distribution-Adaptive Robust Timing). DART incorporates a Learnable Adaptive Spline (LAS) encoder with a gradient-driven knot migration mechanism to enhance non-linear expressiveness for outliers, significantly improving long-tail accuracy. Furthermore, a Spatio-Temporal Transition Graph (STTG) reconstructs the latent topology by integrating sequence semantics, such as Wi-Fi-sensed arrival merchant timestamps. At the same time, a Distribution Gating Mechanism characterizes delivery time distributions under distinct contexts. Through extensive experiments and large-scale online A/B testing, DART not only reduces MAE by 14.0% in complex environments but also decreases the Order Overdue Rate by 1.7% (saving $24,000 daily), demonstrating how AI effectively reconciles operational efficiency with labor fairness.
论文检索
输入标题、作者或关键词，从 2,854 篇学术成果中精准定位
Fairness auditing aims to assess whether a model is fair, playing a critical role in identifying potential risks in deployed AI systems. In practice, due to limited access, third-party auditors often rely on self-collected datasets (e.g., via sock-puppets), which may differ from real-world deployment scenarios. Such discrepancy can lead to inconsistencies between audit conclusions on the collected data and those in actual deployment, raising concerns about the reliability of third-party audits. This motivates a critical question: When can we trust the fairness audit conclusion derived from third-party datasets? Answering this question is challenging, as the actual deployment distribution is typically inaccessible or unobservable. To tackle this, we introduce the Consistency Radius, a metric that quantifies the maximum distribution shift under which an audit conclusion based on third-party dataset remain consistent. We further propose a convex relaxation optimization-based method to estimate the radius relying solely on model responses over the audit dataset. Leveraging this framework, third-party auditors can provide their datasets to model providers and request the magnitude of distributional discrepancy relative to the deployment distribution, enabling reliable audit conclusions without requiring any direct data access.
Envy-free (EF) allocation is a fundamental problem at the intersection of theoretical computer science and economics. When resources are indivisible, achieving an EF allocation is often impossible. A common remedy is to compensate agents with subsidies. Brustle et al. proved that a total subsidy of n-1 is both necessary and sufficient to guarantee EF in the worst case, where n is the number of agents and each agent has additive valuations with marginal values of at most 1 per item. In this paper, we consider a constrained setting, namely graph orientation, that was recently introduced by Christodoulou et al. In this model, agents correspond to vertices in a multigraph, and resources correspond to edges, with each edge allocated to one of its two incident agents. Despite extensive study of the graph orientation model, it remains unclear how much subsidy is sufficient to guarantee EF. We show that a total subsidy of n/2 is always sufficient to guarantee EF in any multigraph, halving the subsidy required in the unconstrained setting, and provide a polynomial-time algorithm to compute such an allocation. We show that this bound is tight, even for simple graphs.
We study EFX and approximate EFX allocations of indivisible goods among agents with at most k distinct valuations (i.e., k types of agents). For exact EFX, it is known that an EFX allocation always exists when there are at most three types of agents. For approximate EFX, the best known guarantee is a 0.618-EFX allocation, and this has been improved recently to a φ-EFX allocation when the number of agents is at most seven. We settle another natural case in this landscape by showing that a φ-EFX allocation exists for any number of agents whenever there are at most four distinct valuations. We then consider a relaxation, EFX with charity, where some goods may remain unallocated and no agent envies the set of unallocated goods. It is known that, for n agents and any ε ∈ (0, 1/2], there exists an EFXε allocation with at most Õ((n/ε)^(1/2)) goods allocated to charity. We prove that when there are at most k distinct valuation types, there exists an EFXε allocation with only Õ((k/ε)^(1/2)) goods allocated to charity; in particular, the required amount of charity is sublinear in the number of distinct valuations rather than in the number of agents. We show that any EFX guarantee for k types of agents can be extended, with an additional (1 − 2ε) approximation factor, to a more general setting where the valuations can be partitioned into k clusters such that the maximum heterogeneity of valuations within each cluster is at most ε.
With the increasing demand of privacy protection, Machine Unlearning (MU) appears to remove private data from an already trained model without retraining from scratch. Most current works suffer from overly unlearning (low fidelity) or incomplete unlearning (low effectiveness). To identify the issues behind, we conduct causal analysis to obtain a resolvable route, i.e., disentangling shared knowledge into attribute-level semantics to remove it as the confounder. We further perform MU loss analysis to reformulate it as balanced form of constraints, thus guaranteeing high fidelity and effectiveness. Based on theoretical analysis, we propose disentangled knowledge forgetting constrained by the reformulated MU loss, which disentangles knowledge with variational auto-encoder and refines knowledge with counterfactual inference. Extensive experimental results demonstrate that our method achieves state-of-the-art performance.
Fairness-aware graph learning has become increasingly important amid growing concerns about algorithmic bias in networked data. Among existing approaches, counterfactual fairness is particularly appealing as it seeks to eliminate unfairness at its causal origin by ensuring that predictions remain invariant in counterfactual worlds where sensitive attributes are altered. However, most existing methods assume that all observed variables are directly influenced by sensitive attributes, an overly strong and often unrealistic assumption in real-world graphs. To address this limitation, we propose Graph Counterfactual Fairness (GCFair), a novel framework that achieves counterfactual fairness by explicitly identifying and disentangling the subsets of node features and graph structures genuinely affected by sensitive attributes. This principled joint disentanglement enables the generation of authentic counterfactual instances that selectively modify only sensitive-related information while preserving all sensitive-irrelevant factors. Extensive experiments show that GCFair effectively mitigates bias and outperforms state-of-the-art fairness methods in both counterfactual fairness and predictive accuracy.
Skeleton-based human activity recognition (HAR) has achieved strong empirical performance, yet most existing models remain black boxes and difficult to interpret. In this work, we introduce a neurosymbolic formulation of skeleton-based HAR that reframes action recognition as concept-driven first-order logical reasoning over motion primitives. Our framework bridges representation learning and symbolic inference by grounding first-order logic predicates in learnable spatial and temporal motion concepts. Specifically, we employ a standard spatio-temporal skeleton encoder to extract latent motion representations, which are then mapped to interpretable concept predicates via a spatio-temporal concept decoder that explicitly separates pose-centric and dynamics-centric abstractions. These concept predicates are composed through differentiable first-order logic layers, enabling the model to learn human-readable logical rules that govern action semantics. To impose semantic structure on the learned concepts, we align skeleton representations with LLM-derived descriptions of atomic motion primitives, establishing a shared conceptual space for perception and reasoning. Extensive experiments on NTU RGB+D 60/120 and NW-UCLA demonstrate that our approach achieves competitive recognition performance while providing explicit, interpretable explanations grounded in logical structure. Our results highlight neurosymbolic reasoning as an effective paradigm for interpretable spatio-temporal action understanding.
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.
Large Language Models (LLMs) achieve strong performance in many applications but remain limited in handling graph-structured data due to their reliance on textual context. Recent approaches integrate Graph Neural Networks (GNNs) to enhance structural modeling, yet they largely overlook fairness, leaving models vulnerable to bias amplification across graph and text modalities. To address this issue, we propose FairGEnt, a disentangled graph-enhanced large language model for fair graph learning. FairGEnt separates sensitive-related and sensitive-invariant factors in both graph and textual representations to mitigate bias while preserving task-relevant information, and further aligns the two modalities through a fairness-aware integration module. In addition, FairGEnt incorporates fair graph-enhanced instruction tuning to improve LLM understanding of complex graph structures. Experiments on multiple benchmark datasets demonstrate that FairGEnt consistently outperforms existing methods in both fairness and predictive performance.
We study the consequences of information asymmetries and misaligned incentives in settings with multiple independent agents. We model an interaction between a Sender, who holds vital private information but cannot act, and a Receiver, who must make decisions but is dependent on the Sender's information. We find that the Sender learns an optimal communication strategy that the Receiver reliably acts on. Importantly, this strategy is highly sensitive to the degree of conflict in the agents' rewards and the amount of environmental information the Receiver can already observe. We introduce a mechanism allowing the agents to form linear contracts, where a price is established for the information. We demonstrate that the Sender learns to use these payment structures to improve its rewards, though this comes at a cost of “fairness” between agents as the Sender is able to extract much of the Receiver’s surplus. This raises questions about fairness, contract design, and learning in the context of multi-agent systems.
In several socioeconomic-critical decision-making settings, such as fair resource allocation, climate policy, or AI alignment, multiple principals interact within a common arena. While it is well established that these principals may have differing preferences, decision-making under heterogeneous time preferences remains relatively unexplored. In particular, principals may weigh future outcomes differently and may derive distinct utilities from the same decisions. Motivated by such scenarios, we introduce the notion of heterogeneous time preferences in MDPs, where multiple principals possess distinct reward functions and apply different discount factors to future rewards. To compute meaningful decisions in such settings, an AI agent must rely on a notion of optimality that accounts for the preferences of all principals. We adopt a utilitarian notion of social welfare, defined as the sum of utilities accrued to all principals, and study the synthesis of agent strategies that maximise this welfare. Under heterogeneous time preferences, we show that optimal strategies are no longer positional, even when all principals receive identical rewards. Nevertheless, optimal strategies remain structurally simple: they can be realised as pure finite-memory counting strategies, require only polynomial memory in the system size, and can be synthesised in polynomial time. On the other hand, we show that deciding threshold questions for optimal positional strategies is NP-hard, exposing a poor trade-off: insisting on positional simplicity neither makes synthesis tractable nor preserves social welfare.
Algorithmic decision-making in high-stakes settings can have profound impacts on individuals and populations. While much prior work studies fairness in static settings, recent results show that enforcing static fairness constraints may exacerbate long-run disparities. Motivated by this tension, we study a stylized sequential selection problem in which a decision-maker repeatedly selects individuals, affecting both immediate utility and the population distribution over time. We introduce notions of group fairness for both the short and long term and theoretically analyze the trade-off between fairness and utility via the Price of Fairness (PoF). We characterize optimal and fair policies in the short term and show that the PoF can be large even when group distributions are nearly identical. In contrast, we show that long-term disparities can vanish under simple investment policies that achieve a low PoF. We also empirically validate these theoretical observations using both synthetic and real datasets.
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.
In this paper, we prove the existence of an envy-free up to one item (EF1) division for a discrete chore. Our approach builds upon the powerful Simmons-Su framework, which leverages Sperner’s lemma to guarantee the existence of a simplex corresponding to a sequence of similar fractional divisions, ensuring that each agent is satisfied with a different bundle. For allocations of goods, existing works have introduced rounding techniques that convert an envy-free fractional division into a connected integral EF1 division for any number of agents with monotone valuations. However, the analogous problem for chores has remained unresolved, and existing rounding techniques fail due to the asymmetric definitions of EF1 for goods and chores. To overcome this asymmetry, we refine the existing rounding techniques and show that connected EF1 divisions exist for a discrete chore.
Fair clustering has garnered considerable attention, with various fairness notions proposed to ensure equitable representation across demographic groups. In this paper, we focus on the k-center problem in bounded doubling metrics under two popular fairness requirements: group fairness and data summarization fairness, referred to Group Fair k-Center (Gf-k-Cen) and Data Summarization Fair k-Center (Dsf-k-Cen), respectively. Both fairness notions extend classical clustering formulation by associating each data point with a demographic label. Motivated by recent advances in parameterized approximation results for fair clustering, we investigate whether these problems admit Fixed-Parameter Tractable (FPT) approximation schemes in bounded doubling metrics. The previous algorithms typically neglect the local structural properties induced by fairness constraints itself, which limits their approximation quality. By further leveraging the geometric properties of doubling metrics together with local fairness information, we develop a candidate-based structural method that yields (1+eps)-approximation algorithms with FPT running times for both problems, parameterized by the number of selected centers. To the best of our knowledge, these results constitute the first parameterized approximation schemes for the Gf-k-Cen and Dsf-k-Cen problems in bounded doubling metrics.
Motivated by the growing importance of fairness in machine learning, fair k-center clustering has attracted considerable research attention as a fundamental problem. In this problem, a dataset is partitioned into m disjoint groups, and the objective is to select k data points as centers, subject to upper bounds on the number of centers chosen from each group, aiming to minimize the maximum distance between any data point and its assigned center. Focusing on Euclidean spaces, which are ubiquitous in machine learning applications, we first develop a parameterized approximation algorithm for Euclidean fair k-center with an approximation ratio of 2.732. By incorporating this algorithm as a post-processing stage into a one-pass streaming framework for large-scale data, we obtain an approximation ratio of 4.464. These ratios can be further respectively improved to 2.414 and 3.828 with a runtime exponential on k. To ensure polynomial-time complexity, we further design a one-pass streaming algorithm with an approximation ratio of 4.732, which can be further improved to 4.42, outperforming the state-of-the-art ratio. Finally, extensive experiments show that our methods significantly outperform state-of-the-art approaches in terms of clustering accuracy.
Graph Neural Networks (GNNs) have demonstrated strong predictive performance across a wide range of applications. However, their increasing deployment has raised critical fairness concerns, as these models can inherit and amplify existing biases. Most existing fairness approaches rely on explicit demographic information, either directly available or inferred, to measure and mitigate bias. In real-world settings, however, such information is often unavailable or legally prohibited to infer due to privacy concerns, legal restrictions, or regulatory constraints, which substantially limits the applicability of these methods. To address this challenge, we propose Demographic-Independent Fair Graph Learning (DIFGL), a novel framework for fair graph learning without demographic supervision. DIFGL mitigates group unfairness by minimizing disparities in individual treatment across implicitly identified subgroups, thereby enforcing fairness without requiring explicit demographic information. Extensive experiments on benchmark datasets demonstrate that DIFGL achieves significant improvements in fairness while maintaining competitive predictive performance.
Fair dynamic graph embedding is crucial for real-world systems, such as recommendation and social networks. Prior studies impose a single-axis fairness formulation, treating attribute and structural bias as separable artifacts. This overlooks their coupling relationship, under which debiasing along one axis can induce cross-axis amplification. This coupling further introduces opposing gradient constraints under joint optimization, leading to optimization conflicts. Furthermore, the evolution of dynamic graphs causes shifts in bias distribution, leading to unstable optimization and exacerbating these conflicts. To address these issues, we propose FairTCD, a Fair Dual-Teacher Temporal Contrastive Distillation framework. FairTCD employs two adversarial fairness teachers to decouple attribute and structural fairness representations. To reconcile dynamic conflicts between two fairness objectives, we introduce a temporal contrastive distillation to induce consistency between attribute and structural fairness representations across time while retaining temporal semantics. A unified student model distills complementary knowledge from both teachers to achieve twofold fairness. Experiments on three real-world benchmarks demonstrate that FairTCD preserves performance while improving twofold fairness metrics by at least 4.53%.
Fairness k-submodular maximization has attracted increasing interest due to its broad relevance in artificial intelligence and machine learning. However, most existing works are limited to monotone objectives or simple size constraints, while non-monotone settings with richer constraints remain largely unexplored. In this paper, we first introduce a constant-factor approximation algorithm for the problem with a general non-monotone objective function under a matroid constraint. Our approach is built upon a two-stage algorithmic framework. Specifically, we first develop an algorithm that guarantees feasibility with respect to upper fairness bounds only. We then show how this algorithm can be systematically extended to simultaneously enforce fairness bounds, while preserving provable approximation guarantees. Comprehensive experiments on standard benchmark datasets demonstrate that our algorithm achieves competitive objective values while maintaining a favorable balance between fairness guarantees and query complexity efficiency compared to existing state-of-the-art methods.
Real-world multi-agent systems, from traffic coordination to resource allocation, are often modeled as general-sum games where individual incentives conflict with collective welfare. In these settings, the central challenge is not merely finding an equilibrium, but selecting socially desirable outcomes among many suboptimal Nash equilibria. Standard deep multi-agent reinforcement learning (MARL) methods struggle with this problem, as value-decomposition approaches are constrained by monotonicity assumptions and policy-gradient methods often converge to stable but socially inefficient equilibria. To address this limitation, we propose Phi-Actor-Critic (Phi-AC), a framework that leverages swap regret minimization to steer learning toward high-welfare correlated equilibria (CE). To make counterfactual regret estimation tractable in deep MARL, Phi-AC employs a centralized attention critic that predicts vector-valued regrets in a single forward pass, avoiding computationally expensive counterfactual simulations. We further introduce a Lagrangian-based equilibrium selection mechanism that optimizes social welfare while enforcing stability through regret constraints. Experiments on matrix games, Multi-Agent Particle Environments (MPE), and the Melting Pot Harvest scenario demonstrate that Phi-AC learns efficient and stable coordination strategies across diverse mixed-motive settings while maintaining high collective return and competitive fairness.