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.
论文检索
输入标题、作者或关键词，从 2,854 篇学术成果中精准定位
Understanding when fair allocation mechanisms lead to stable coalition structures is fundamental for designing robust multi-agent systems. We investigate the compatibility between stable allocations in transferable utility (TU) games and the stability of coalition structures in induced hedonic games, where agents' preferences over coalitions are derived from payoffs assigned by a fixed allocation rule applied to all subgames of the TU game. We analyze FX-FE strong Nash stability (SNS) in induced hedonic games, which captures a strong form of robustness under free-exit and free-entry conditions. We show that any efficient allocation rule ensuring core membership for the grand coalition induces a hedonic game that guarantees the existence of an FX-FE strong Nash stable partition. Examining the Shapley value, we further show that when it lies outside the core, the resulting hedonic game may or may not possess FX-FE strongly Nash stable partitions, highlighting a sensitive interaction between Shapley-based fairness and coalition-level stability. Our framework bridges SHAP methodology from explainable AI with hedonic coalition theory, providing theoretical foundations for understanding when fair allocation mechanisms shape coalition-level incentives in a way that ensures strategic stability in team formation and multi-agent systems.
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.
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.
Responsibility allocation---determining the extent to which agents are accountable for outcomes---is a fundamental challenge in the design and analysis of multi-agent systems. In this work, we model such systems as concurrent stochastic multi-player games and introduce a notion of retrospective (backward) counterfactual responsibility, which quantifies an agent's accountability for outcomes resulting from a given strategy profile. To allocate responsibility among agents, we utilise the Shapley value and formally show that this method satisfies key desirable properties, including fairness and consistency. Building on this foundation, we propose a formal framework that supports both verification and strategic reasoning in responsibility-aware multi-agent systems. Furthermore, by adopting Nash equilibrium as the solution concept, we demonstrate how to compute stable strategy profiles in which agents trade off responsibility against expected reward.
Breaking the Trade-off: Orthogonal Semantic Decoupling for Generalizable and Fair Deepfake Detection
Deepfake detection faces dual challenges in real-world deployment: cross-domain generalization and demographic fairness. Existing approaches often struggle with a trade-off between these goals. Generalization-oriented detectors can over-rely on demographic shortcuts, while fairness constraints tend to steer optimization away from the most discriminative decision boundary. To address this, we propose Orthogonal Semantic Decoupling (OSD), a framework that decouples demographic semantics from forgery cues. Specifically, we perform Singular Value Decomposition on the pretrained weights of a vision-language model, freezing the principal semantic subspace while learning parameter-efficient low-rank experts in the residual subspace. The experts comprise (1) Demographic Semantic Experts, a set of experts specialized via hard sampling and routed based on the similarities between image embeddings and text embeddings of predefined descriptions; and (2) a Universal Forgery Expert, which captures forgery features transferable across domains and demographics. Extensive experiments across multiple benchmarks demonstrate that our approach outperforms state-of-the-art methods in both generalization and fairness, breaking the trade-off. The code is available at https://github.com/sonder-lin/osd-deepfake-detection.
Generative models have emerged as a powerful paradigm in sequential recommendation due to their superior distribution modeling. However, long-tail data distributions inevitably induce popularity bias, as iterative generation trajectories gravitate toward dense clusters of popular items. Current debiasing methods struggle to enforce consistent step-wise constraints, rendering them ineffective for the multi-step process of generative recommendation. To address this challenge, we propose a method called Popularity-Debiased Flow Matching for sequential recommendation (PDFlow). Specifically, grounded in the flow matching framework, PDFlow integrates a residual popularity vector field beyond the main flow to model the popularity debiasing flow at each step. This enables real-time trajectory intervention to adjust the generative path, preventing the model from overemphasizing popular items. Subsequently, we incorporate cross-popularity alignment loss, using co-occurrence patterns within the same sequence to align features of both popular and tail items, thereby mitigating popularity-driven distribution separation. Jointly, trajectory correction prevents popularity overfitting while cross-popularity alignment ensures latent fairness, effectively mitigating popularity bias. Extensive experiments on four real-world datasets demonstrate the effectiveness of PDFlow in improving long-tail coverage and overall recommendation performance. All codes and datasets are available at https://github.com/eqmll/PDFlow.
Fair multi-view clustering aims to exploit complementary information across views to improve clustering quality, while ensuring unbiased outcomes with respect to sensitive groups. Existing methods typically separate multi-view clustering from fairness optimization into distinct stages. However, such a decoupled design provides limited synergy between the two objectives, which often makes progress on one objective detrimental to the other. To address this challenge, we propose Mutually Reinforced Fair Multi-View Clustering (MR-FMVC), which optimizes fairness alignment and clustering iteratively to enable coordinated optimization. Specifically, we first disentangle view representations into common and private components to mitigate fairness-related discrepancies across views. Subsequently, the optimization proceeds by interleaving cross-group matching in the common space with updating cluster centroids in the joint representation space, ultimately assigning matched samples to consistent clusters. Extensive experiments on four fairness datasets demonstrate that MR-FMVC achieves a superior trade-off between clustering performance and fairness.
We study repeated allocation of shared resources among agents with time-varying demands and capped linear utilities. In this setting, independently maximizing the minimum utility in each round satisfies sharing incentives (agents weakly prefer participating in the mechanism to not participating), strategyproofness (agents have no incentive to misreport their demands), and Pareto efficiency. However, this max-min mechanism can lead to large disparities in the total resources received by agents, even when they have the same average demand. We introduce credit fairness, a property that, together with Pareto efficiency, strengthens sharing incentives by ensuring that agents who lend resources in early rounds are able to recoup them in later rounds. Credit fairness can be achieved in conjunction with either Pareto efficiency or strategyproofness individually, but we show that, under anonymity, it cannot be achieved together with both. We propose a mechanism that is credit fair and Pareto efficient, and evaluate it in a computational resource-sharing setting.
The rapid progress of identity-feature-based face-swapping technology has raised concerns about impersonation and privacy violations. Although proactive defenses aim to block identity extraction at the source, existing methods suffer from perceptible visual artifacts, poor generalization across diverse deepfake models, and vulnerability to post-processing techniques (e.g., diffusion purification, image compression, and transformations). This work proposes a robust, generalizable proactive face-swapping defense via semantic gradient divergence (SGD-Guard) to address these challenges. It introduces an integrated feature gallery that uses CLIP features and a generalized identity feature, obtained by iteratively refining heterogeneous identity features into a homogeneous representation. This framework facilitates our semantic distortion attack by leveraging consensus weighting to target specific facial attributes within a CLIP-identity joint embedding space, disrupting deepfake generation while preserving visual fidelity. Furthermore, to ensure robustness against purification and post-processing, this method incorporates a module that prioritizes critical transformations by exploiting directional discrepancies. Comprehensive experiments demonstrate that the method effectively defends against diverse face-swapping models with high cross-model transferability.
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.
Achieving fairness in machine learning models while maintaining high accuracy is an important but complex task, especially when handling multiple sensitive attributes. Traditional fairness methods often struggle to eliminate bias within subgroups divided by sensitive attributes. Several key challenges have been identified in this context: (1) Multiple sensitive attribute scalability challenge, where methods fail to ensure fairness as the number of sensitive attributes increases, despite scenarios with multiple sensitive attributes being prevalent in real-world applications; (2) Multiple objective optimization conflict challenge, where simultaneously optimizing for accuracy, fairness, and other relevant objectives leads to conflicting gradient updates, causing suboptimal performance. To address these challenges, we propose BAMFair, a Barycenter Aligned Mediation framework for fairness across multiple sensitive attributes. It comprises two core modules: a Global Barycentric Alignment (GBA) module and a Nash Fairness Mediator (NFM) module. Specifically, GBA innovatively introduces a global fair barycenter and minimizes the distances from subgroups divided by sensitive attributes to it, providing a scalable and efficient solution for fairness optimization across multiple sensitive attributes. Subsequently, NFM negotiates an agreement among inconsistent gradient updates between different objectives. Extensive experiments on four real-world datasets validate that BAMFair outperforms state-of-the-art methods in scenarios with multiple sensitive attributes.
Auditing recommendation systems has attracted growing attention due to increasing concerns over filter bubbles, unfairness, and data misuse. A common approach is sock-puppet auditing, where autonomous agents interact with platforms to reveal risks. However, existing approaches rely on hard-coded agents, lacking adaptability to dynamic GUI layouts and generating behaviors far from those of real users, limiting the comprehensiveness and representativeness of assessment. To address these issues, we introduce AuditAgent, an LLM-powered GUI-agent framework for risk auditing. AuditAgent simulates realistic user preferences and performs adaptive, human-like interactions on recommendation platforms. This design enables more thorough and faithful auditing, providing comprehensive assessments across multiple risk dimensions, including filter bubbles, unfairness, and data misuse.
Reproducible benchmarking of tools that automatically detect vulnerabilities in source code remains challenging due to inconsistent implementations, varying data preprocessing, and methodological flaws that compromise fair model comparison. In a recent study, 9 in 10 vulnerability detection studies were found to use inappropriate evaluation approaches, with models achieving high scores through spurious correlations rather than actual vulnerability detection. We present VulnBench, an extensible, open-source benchmarking tool that enables fair comparison across models and datasets. Our systematic evaluation of CodeBERT, GraphCodeBERT, CodeT5 (encoder-only and full), and NatGen across eight mostly C/C++ source code datasets reveals that proper threshold optimization can improve F1-scores by up to 54%, as well as wide variation in F1-scores showing the large gap in the difficulty of the vulnerability dataset field. By standardising evaluation protocols, VulnBench enables researchers to distinguish between genuine model improvements and methodological artifacts as well as reducing wasteful duplication of effort spent on reproducing results.
Retrieval-Augmented Generation (RAG) has become the standard approach for integrating domain knowledge into Large Language Models (LLMs). However, fair comparison of RAG pipelines remains difficult: data preparation is often ad hoc, subsampling methods are opaque, parameters vary across implementations, and evaluation is fragmented. We present In-Situ Eval, a unified and reproducible framework that operationalizes the full RAG pipeline with configurable subsampling strategies and both RAG-specific and generic evaluation metrics. The platform supports two execution modes: an offline Dataset mode for evaluating precomputed outputs, and a live Retrieval mode for benchmarking RAG variants with state-of-the-art LLMs. Users can flexibly select datasets, retrieval techniques, models, and metrics, enabling side-by-side comparisons, ablations, and targeted analyses. This holistic approach reduces computational costs, clarifies the impact of subsampling techniques, and provides actionable insights for real-world deployments. By facilitating transparent, customizable, and interactive benchmarking, In-Situ Eval empowers both researchers and practitioners to make informed decisions in adapting RAG pipelines to domain-specific needs.
De-Speakerizing Accented ASR: Measuring and Mitigating Speaker Entanglement for Fair, Reliable Recognition
PDF ↗This research statement proposes to measure and mitigate speaker entanglement, where accent features inadvertently encode who is speaking in accented automatic speech recognition (ASR). We argue that entanglement inflates scores under lenient split for the same speaker and worsens fairness gaps across accents, and we outline a parameter-efficient mitigation that combines adversarial de-speakerization with safe conditioning. The plan is grounded in established results in accented ASR, domain-adversarial learning, and parameter-efficient fine-tuning; it is feasible with public datasets and a frozen Whisper backbone, and can potentially guide low-resource data collection.
Decomposing Direct and Indirect Biases in Linear Models Under Demographic Parity Constraint (Student Abstract)
PDF ↗Linear models are widely used in high-stakes decision-making due to their interpretability, but fairness constraints like Demographic Parity (DP) create opaque effects on model coefficients and predictive bias distribution. We propose a post-processing framework that can be applied on top of any linear model to decompose bias into direct (sensitive-attribute) and indirect (correlated-features) components. Our method analytically characterizes how DP reshapes each coefficient, enabling transparent feature-level interpretation.
When Equal Isn’t Fair: Mitigating Over-Normalization in Large Language Models (Student Abstract)
PDF ↗Bias in Large Language Models (LLMs) is increasingly addressed through fairness-oriented techniques. However, in some cases, these approaches may inadvertently remove genuine cultural differences between groups, leading to “over-normalization” or models losing important socio-cultural distinctions. In this work, we introduce OverNormEval, a benchmark designed to detect when an LLM exhibits such over-normalization. We further explore the use of Direct Preference Optimization (DPO) to mitigate over-normalization.
Towards Fairness in Transportation Gig Markets: Identifying, Imitating, and Mitigating Algorithm Discrimination via Deep Reinforcement Learning
PDF ↗Recently, deep Reinforcement Learning (RL) methods have been widely used in labor management within transportation gig markets, such as ride-hailing, food delivery, and express delivery. Compared to traditional rule-based and optimization-based methods, RL can capture more information about long-term uncertainty and environmental dynamics, leading to better and non-myopic strategies. However, deep learning methods have long been criticized for their low interpretability, raising concerns about algorithmic discrimination in gig markets. Currently, most works focus on this issue from the perspective of statistical analysis and surveys. However, the underlying reasons related to the algorithms remain unclear, as most companies do not disclose their algorithms. This lack of transparency can hinder governments from designing efficient management policies to address these problems. To fill this research gap, this thesis proposal aims to develop appropriate RL methods to mimic the labor management behavior of transportation gig platforms and to propose effective policies that protect the rights of gig workers.
Machine learning is widely used in various areas. However, the current machine learning framework remains vulnerable to issues such as adversarial attacks, fairness violations, and data leakage. These problems are not adequately captured by fitting models to collected data and focusing on test performance metrics alone, like accuracy or F1-score. In practice, machine learning tasks often involve additional quantities of interest, which turns an originally unconstrained optimisation problem (only optimising toward accuracy) into a constrained one. This thesis formally studies machine learning under different types of commonly concerning constraints, such as robustness, fairness, and privacy. I first focus on how the formal machine learning framework can be extended to incorporate robustness, which is a critical factor for safety. After that, I turn to more ethics-related aspects like fairness and privacy, to explore the possibility of formally fitting them into machine learning. My approach differs from empirically pushing up multiple metrics and instead emphasises fundamental ways to understand and address the underlying challenges.