Attributing importance to the individual components of a larger unit has become a popular method for understanding models and data in AI and machine learning. Starting with feature explanation, this method is now also used in data valuation or federated learning, just to name a few. Despite their differences, all of these applications use the same mathematical attribution mechanism: the Shapley value, which is rooted in cooperative game theory. While the Shapley value is appealing and has strong axiomatic foundations, it is computationally intractable due to the combinatorial explosion of player subsets. Therefore, there is a need for approximation algorithms, which have been studied intensively in recent years. This survey provides an overview of general-purpose approximation methods applicable to any domain. We categorize these methods into algorithmic classes, compare their properties, and highlight connections between approaches in a comprehensive taxonomy.
论文检索
输入标题、作者或关键词，从 6,795 篇学术成果中精准定位
Liquid democracy encompasses a family of decision-making processes where votes can be cast directly or passed along proxy chains. We provide a community-maintainable and systematic survey of (computational) social choice papers on liquid democracy, organized through a searchable taxonomy of core modeling features that have appeared in the literature. Drawing on the insights from our survey, we also outline a number of research directions, which we consider of special importance for both the theory and practice of liquid democracy.
Most of the widely used estimators of the average treatment effect (ATE) in causal inference rely on the assumptions of unconfoundedness and overlap. Unconfoundedness requires that the observed covariates account for all correlations between the outcome and treatment. Overlap requires the existence of randomness in treatment decisions for all individuals. Nevertheless, many types of studies frequently violate unconfoundedness or overlap; for instance, observational studies with deterministic treatment decisions, popularly known as Regression Discontinuity designs, violate overlap. In this paper, we initiate the study of general conditions that enable the identification of the average treatment effect, extending beyond unconfoundedness and overlap. In particular, following the paradigm of statistical learning theory, we provide an interpretable condition that is sufficient and necessary for the identification of ATE. Moreover, this condition can be used to characterize other treatment effects, such as the average treatment effect on the treated (ATT), as well. To illustrate the utility of our condition, we present several well-studied scenarios where our condition is satisfied and, hence, we prove that ATE can be identified in regimes that prior works could not capture. For example, under mild assumptions on the data distributions, this holds for the models proposed by Tan (2006) and Rosenbaum (2002), and the Regression Discontinuity design model introduced by Thistlethwaite and Campbell (1960). For each of these scenarios, we also show that, under natural additional assumptions, ATE can be estimated from finite samples. We believe these findings open new avenues for bridging learning-theoretic insights and causal inference methodologies, particularly in observational studies with complex treatment mechanisms.
Large Language Models (LLMs) are often used in autonomous decision-making, where they have to sample options from vast action spaces. Here we present a summary of the work studying the heuristics that guide this sampling process and show it resembles that of human decision-making: comprising a descriptive component (reflecting statistical norm) and a prescriptive component (implicit ideal encoded in the LLM). We show that the deviation of a sample from the statistical norm towards a prescriptive component consistently appears in concepts across diverse real-world domains. To further illustrate the theory, we demonstrate that concept prototypes in LLMs are affected by prescriptive norms, similar to the concept of normality in humans. This finding has implications in LLM based agentic systems, explaining their exploration behavior and biases in decision making.
Letting AI agents interact in multi-agent settings in- troduces significant complexity in predicting and interpreting their collective behavior, with pro- found implications for trustworthy AI adoption in research and society. We present FAIRGAME (Framework for AI Agents Bias Recognition us- ing Game Theory), an open-source framework that simulates game-theoretic scenarios with LLM- based agents to systematically uncover biases aris- ing from model choice, language, agent personal- ity, and more. Applied to the Prisoner’s Dilemma and Battle of the Sexes across four LLMs and five human languages, FAIRGAME reveals inconsis- tencies across LLM models and consistent devia- tions from game-theoretic predictions; it also quan- tifies LLM-specific behavioral tendencies through a novel scoring system. Our results show that LLMs draw on prior world knowledge beyond payoff ma- trices, and that language and personality signifi- cantly shape strategic outcomes, supporting the use of reproducible and controlled simulation pipelines to predict the interacting behavior of LLM agents.
Artificial intelligence (AI) applications are prone to reproducing existing patterns of marginalization, bias, and discrimination. The adoption of automated decision-making tools, particularly those based on large language models (LLMs), necessitates the detection and analysis of their discriminatory behavior to ensure compliance with anti-discrimination regulations. This work advances metamorphic testing for bias detection, aiming to (1) uncover discriminatory behavior in AI tools and (2) standardize the metamorphic test creation approach, rooting it in the legal and academic research on discrimination. To fill in these gaps, we introduce a metamorphic test creation workflow and evaluate it on the LLM-based CV screening use case. Our method yields a metamorphic relation (MR) catalogue of 8 atomic and 6 composite MRs, legally justified by Article 21 (1) of the Charter of Fundamental Rights of the European Union and sociologically motivated by the intersectionality theory. The resulting metamorphic test suite uncovers discriminatory failures for all 6 evaluated LLMs, totaling 1,272 defects across 7,800 test cases. Both the new atomic MRs and the composite MRs detect additional discriminatory defects for all LLMs. Composite MRs consistently uncovered more defects than their atomic counterparts, with failure rates increasing by on average 9% for Llama-3.1 8B and 25% for Llama-3.2 3B.
Achieving an optimal balance between exploration and exploitation remains a fundamental challenge in reinforcement learning. This work revisits the exploration-exploitation dilemma through the lens of entropy, offering a novel perspective on this enduring problem. It establishes a theoretical connection between policy's entropy and exploratory behavior, using entropy as a rational measure to quantify the exploration-exploitation trade-off. Theoretical analyses demonstrate that a modified Bellman equation, augmented with a novelty-seeking term, ensures appropriate entropy adjustment and guarantees its globally monotonic decay. The derived policy optimization process inherently accommodates all three regimes of the exploration-exploitation spectrum, enabling a principled transition from exploration to exploitation. Building on these theoretical insights, this work introduces AdaZero, an adaptive deep architecture that dynamically balances exploration and exploitation. Extensive empirical evaluations highlight AdaZero's robust performance and validate the theory's feasibility.
The Tournament Fixing Problem (TFP) asks whether a knockout tournament can be scheduled to guarantee that a given player v* wins. Although TFP is NP-hard in general, it is known to be fixed-parameter tractable (FPT) when parameterized by the feedback arc/vertex set number, or the in/out-degree of v*. However, it remained open whether TFP is FPT with respect to the subset FAS number of v* --- the minimum number of arcs intersecting all cycles containing v* --- a parameter that is never larger than the aforementioned ones. In this paper, we resolve this question negatively by proving that TFP stays NP-hard even when the subset FAS number of v* is constant ≥ 1 and either the subgraph induced by the in-neighbors D[N_{in}(v*)] or the out-neighbors D[N_{out}(v*)] is acyclic. Conversely, when both D[N_{in}(v*)] and D[N_{out}(v*)] are acyclic, we show that TFP becomes FPT parameterized by the subset FAS number of v*. Furthermore, we provide sufficient conditions under which v* can win even when this parameter is unbounded.
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.
Dynamic systems in AI are often complex and heterogeneous, so that an internal specification is not accessible and hence verification techniques like model checking are not applicable. Monitoring is in such cases an attractive alternative, as it deals with the observation of desirable properties along traces generated by an unknown dynamic system. In this work, we consider anticipatory monitoring of linear-time properties enriched with an arbitrary SMT theory over finite traces (data-LTLf). Anticipatory monitoring in this setting is a highly challenging problem and undecidable in general, as the monitoring state depends on both the trace prefix seen so far and all its possible finite continuations. Under reasonable assumptions on the background theory, we present and formally prove the correctness of a novel foundational framework for monitoring data-LTLf properties. The framework combines automata-theoretic methods to handle the temporal aspects of reasoning with automated reasoning techniques to address the first-order dimension. Moreover, we identify for the first time decidable fragments of this monitoring problem that are practically relevant as they combine linear arithmetic with uninterpreted functions, which covers e.g. data-aware business processes and dynamic systems operating over a database. Feasibility is witnessed by a prototype implementation and preliminary evaluation.
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.
To make optimal joint pricing and inventory control decisions is a critical challenge for modern retailers. In practice, retailers face changing market conditions where demands are influenced by various contextual factors, while simultaneously dealing with the difficulty of lost sales that obscure true demand information. However, existing approaches often fail to account for both contextual information and censored demand observations. We address this gap by presenting a framework where we model demand as a linear combination of basis functions with unknown coefficients, allowing for adaptive pricing and inventory decisions that respond to changing contexts. We propose an efficient algorithm to achieve regret bound O(K sqrt(T) log T) under concave revenue conditions and O(K^(2/3) T^(2/3) (log T)^(1/2)) for the general case, with matching lower bounds confirming optimality. Extensive numerical experiments across diverse scenarios demonstrate our algorithm’s effectiveness.
Machine unlearning has become a critical capability for AI services to comply with evolving privacy regulations. A key yet underexplored challenge is how to verify whether a profit-driven AI server has faithfully performed unlearning. Existing verification approaches either incur prohibitive costs or provide insufficient deterrence, failing to balance audit cost and enforcement effectiveness. To bridge this gap, we propose UAG, a game-theoretic unlearning auditing framework that incentivizes truthful unlearning via strategic deterrence rather than exhaustive verification. We design a hierarchical auditing mechanism that combines low-cost screening with selectively triggered high-precision verification, and models the server-auditor interaction as a three-stage dynamic Bayesian game. By characterizing the equilibrium strategy, we derive optimal audit and penalty policies that incentivize honest unlearning. Theoretical analysis and experiments show that UAG maintains reliable detection while achieving a favorable cost-deterrence trade-off. Notably, UAG attains a server honesty rate of approximately 95% while screening only about 50% of unlearning requests, showing its practicality for trustworthy black-box unlearning services.
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 ε.
Understanding underlying agent attributes such as goals, preferences, beliefs, and ability level is key to explaining decision-making and predicting behaviour in complex environments. While goal recognition (GR) has produced effective methods for inferring goals, recent work has begun to explore reinforcement learning (RL)-based approaches to attribute recognition (AR), which generalises GR by inferring a wider range of agent attributes beyond goals. Existing frameworks treat attributes as discrete variables and typically require separate models for each attribute. In reality, many agent attributes vary continuously rather than as discrete values, making continuous representations crucial for capturing subtle variations in behaviour. We introduce a multivariate RL-based AR framework that jointly infers multiple continuous-valued attributes from observed behaviour using a single attribute-conditioned policy and continuous probabilistic inference. Our experiments demonstrate that the proposed framework achieves stable and fine-grained inference, offering improved flexibility and generality compared to existing approaches.
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.
Qualitative preferences specified in CP-theory define a partial order over outcomes based on induced dominance relations. We investigate the problem of measuring divergence between such induced orders. We introduce two formally equivalent distance metrics, each leveraging a distinct computational strategy based on different types of normalization. Preliminary empirical results support the soundness of the proposed methodologies and offer comparative insights into their computational properties. To the best of our knowledge, this is the first study to compute distance measures between qualitative preferences that jointly accounts for conditional dependencies and relative importance statements.
Our work evolves around Fictitious Play, one of the first iterative methods that is known to converge to a Nash equilibrium in zero-sum games. In recent years, there has been a revived interest, due to applications in various machine learning problems, which has motivated a line of work on its convergence properties and on proposing new variants of the initial algorithm. Our paper is along this direction and introduces one new variant, which we refer to as Almost Greedy Fictitious Play. The proposed algorithm greedily attempts to find the optimal stepsize at each iteration but its search space is constrained and includes almost all the line between the cumulative mixed strategy and the current best response. Our main result is that the method achieves an instance dependent convergence rate of O(1/T) with respect to the duality gap. This matches the rate of Continuous Fictitious Play, and offers an alternative to discretization. We complement our theoretical findings with experiments that demonstrate the effectiveness of the method.
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.
Understanding the training dynamics of deep neural networks remains a major open problem, with physics-inspired approaches offering promising insights. Building on this perspective, we develop a thermodynamic framework to describe the stationary distributions of stochastic gradient descent (SGD) with weight decay for scale-invariant neural networks, a setting that both reflects practical architectures with normalization layers and permits theoretical analysis. We establish analogies between training hyperparameters (e.g., learning rate, weight decay) and thermodynamic variables such as temperature, pressure, and volume. Starting with a simplified isotropic noise model, we uncover a close correspondence between SGD dynamics and ideal gas behavior, validated through theory and simulation. Extending to training of neural networks, we show that key predictions of the framework, including the behavior of stationary entropy, align closely with experimental observations. This framework provides a principled foundation for interpreting training dynamics and may guide future work on hyperparameter tuning and the design of learning rate schedulers.