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.
论文检索
输入标题、作者或关键词，从 6,795 篇学术成果中精准定位
Modern AI-driven systems rely on large populations of autonomous agents that make decentralized routing decisions under uncertainty, where rare but severe tail latency can critically degrade quality of experience, safety, and reliability. To model agents’ aversion to such tail latency, we study nonatomic selfish routing games in which agents minimize the Conditional Value-at-Risk (CVaR) of path latency. CVaR explicitly captures both the likelihood and severity of tail latency, but its inherent nonadditivity across network edges poses a fundamental challenge. We address it by identifying a worst-case dependence structure—tail risk concentration—under which tail latency across network edges is synchronized. We show that CVaR penalizes this dependence structure and becomes additive under worst-case tail dependence, which enables tight inefficiency analysis. To quantify the resulting inefficiency induced by risk-aversion, we adopt the price of risk aversion (PRA), defined as the worst-case ratio between the total system cost at a risk-averse equilibrium and that at a risk-neutral equilibrium. We show that, for arbitrary latency functions and general network topologies, the PRA under CVaR admits a tight upper bound that grows linearly with both the network size and the maximum edge-level upper-tail cost. We further prove that this bound is tight by constructing a family of Braess-type networks that achieve a matching lower bound. These results provide the first tight worst-case inefficiency bound for CVaR-based selfish routing and offer insights into how tail-risk-averse decision making by autonomous agents amplifies congestion externalities in large-scale multi-agent systems.
Parameter sharing is a central design choice in cooperative multi-agent reinforcement learning, yet it fundamentally conflicts with the need for role specialization in heterogeneous cooperative environments. Existing role-based methods typically learn monolithic role representations, which often suffer from gradient interference and fail to capture the compositional structure of complex behaviors. Inspired by Trait Theory, we propose DEcompose and COnstruct Roles (DECOR), a framework that models agent roles as dynamic compositions of orthogonal behavioral traits. DECOR introduces an orthogonal Mixture-of-Experts architecture to decompose behaviors into independent traits, mitigating destructive gradient interference under parameter sharing, and a group-consensus guided mechanism to extract team-level tactical intents that guide role composition.Experiments on multiple benchmarks demonstrate that DECOR consistently improves sample efficiency and overall performance over existing related methods.
We introduce Hedonic Project Games, a model in which agents choose projects with divisible rewards while holding subjective preferences over coalition composition. This framework captures a fundamental trade-off absent from existing models: agents care simultaneously about who they collaborate with and what they work on. We study three stability notions: classical Nash Stability and two refinements, Joining Stability and Leaving Stability, which account for the welfare of both the deviating agent and the affected coalition members. We evaluate the efficiency of stable outcomes using the Price of Anarchy and Price of Stability, comparing the social welfare of stable outcomes to that of an optimal allocation. While stable outcomes may not exist in general, we identify broad and natural preference classes in which stability and efficiency improve significantly. In particular, under monotonic-decreasing preferences in coalition size, Nash and joining stability coincide and are guaranteed to exist, whereas leaving stability may fail. Under per-capita non-decreasing preferences, socially optimal outcomes are always Nash stable and coincide with leaving stability, although equilibrium inefficiency remains unbounded. Experiments on synthetic and real-world data support the theoretical efficiency results.
We introduce QUINTIC, a general algorithm for actively learning quantitative automata from preferences. Quantitative automata evaluate input sequences by applying a valuation function---such as sum, product, or average---to the output labels of the states visited. Such models naturally arise in use cases ranging from probabilistic verification, sequence classification, and sequential decision making. However, existing learning approaches, such as variants of L*, weighted‐automata learning algorithms, and active learning preference‐driven methods, either assume finite output alphabets or restrict the valuation function to particular forms. QUINTIC utilizes a symbolic observation table and applies deductive reasoning with the assistance of an SMT solver to identify the correct minimal state, transition, and state label combination of the quantitative automaton. The deductive reasoning relies on the minimal combination of theories determined by the valuation function and output alphabet. Consequently, QUINTIC has completeness, minimalism, and query complexity guarantees, and learns quantitative automata across finite, integer, and rational outputs. Our extensive experiments show how QUINTIC scales under weak or strong feedback, and alternative MaxSMT objectives.
Hedonic games are a central model of coalition formation, yet most of their general subclasses are marked by negative results: stable outcomes often fail to exist, and deciding their existence is typically computationally hard. The most notable exception is the class of hedonic games with the common ranking property (HGCRP), a nontrivial subclass that guarantees both the existence and tractability of stable partitions. The common ranking property implies the top-coalition property, which in turn implies the weak top-coalition property, forming a natural hierarchy of increasingly general domains. In this paper, we extend the frontier of strong existence and tractability results beyond the HGCRP to hedonic games with the top-coalition property (HGTCP) and hedonic games with the weak top-coalition property (HGWTCP). We show that every HGWTCP instance admits a strong individually stable (SIS) partition that can be computed in polynomial time, and prove that our polynomial-time algorithm generates a partition that is both SIS and Pareto optimal (PO) if preferences are strict. These results show that strong stability and tractability results persist well beyond the common ranking framework. We further show that a contractually Nash stable (CNS) partition may fail to exist even in HGTCP, revealing a sharp contrast with HGCRP, where the existence of partitions that are both CNS and PO is guaranteed. Taken together, these results provide a comprehensive characterization of stability and efficiency in top-coalition-based hedonic games, mapping how stability guarantees evolve from HGCRP to HGWTCP.
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.
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.
The Kidney Exchange Problem is a prominent challenge in healthcare and economics, arising in the context of organ transplantation. It has been extensively studied in artificial intelligence and optimization. In a kidney exchange, a set of donor-recipient pairs and altruistic donors are considered, with the goal of identifying a sequence of exchanges—comprising cycles or chains starting from altruistic donors—such that each donor provides a kidney to the compatible recipient in the next donor-recipient pair. These exchanges create a network of transplants aimed at maximizing the total number, t, of successful transplants. Due to constraints in medical resources, limits are often imposed on the lengths of these cycles and chains. Recently, this problem was deterministically solved in O* (14.34ᵗ) time (IJCAI 2024). In this paper, we introduce the representative set technique for the Kidney Exchange Problem, showing that the problem can be deterministically solved in O* (6.855ᵗ) time.
Partial Dependence Plots (PDPs) visualize how changes in a single feature affect the average model prediction. They are widely used in practice to interpret decision tree ensembles and other machine learning models. Joint-PDPs extend this idea to pairs of features, revealing their combined effect. Partial Dependence Interaction Values (PDIVs) measure feature interactions. The Any-Order-PDIVs task computes these interactions for every feature subset across all rows of the dataset. We introduce WOODELF++, a unified and efficient approach for computing all these useful explainability tools on decision tree ensembles, building on WOODELF, an algorithm for efficient SHAP computation. By deriving suitable metrics over pseudo-Boolean functions, WOODELF++ can compute PDPs (exact and approximate), Joint-PDPs, and Any-Order-PDIVs in a unified framework. Our method delivers substantial complexity improvements over the state of the art, including an exponential gain for Any-Order-PDIVs. Additionally, we introduce and efficiently compute Full PDPs, which leverage the model’s split thresholds to faithfully capture its behavior across all possible feature values. WOODELF++ is implemented in pure Python and supports GPU acceleration. On a dataset with 400,000 rows, WOODELF++ computes PDP and Joint-PDP up to 6x faster than the state of the art and up to five orders of magnitude faster than scikit-learn. For Any-Order-PDIVs, the gap is even larger: WOODELF++ computes all interaction values in 5 minutes, while the state of the art is estimated to require over 1,000,000 years.
Low-Light Image Enhancement (LLIE) has long been a challenging problem in low-level vision, as insufficient illumination often leads to low contrast, detail loss, and noise. Recent studies show that deep learning-based Retinex theory can effectively decouple illumination and reflectance. However, existing methods frequently suffer from over-enhancement or color distortion, and often assume uniform noise or ideal lighting. To address these limitations, we propose InterLight, a novel framework that systematically excavates and operationalizes intrinsic illumination priors for LLIE. Our core insight is that robust enhancement requires not just estimating illumination, but constructing an illumination-aware pipeline. We first inject sensor-level illumination-response priors via physics-guided augmentation, then represent the degradation through adaptive prompts conditioned on the scene's latent illumination state. This explicit representation directly guides a luminance-gated intrinsic memory mechanism to selectively compensate for information loss, prioritizing reconstruction in dark regions while preserving fidelity in bright ones. Finally, the entire process is regularized by a self-supervised consistency objective that distills illumination-invariant features. By deeply exploiting intrinsic illumination priors, our method achieves clearer textures and more visually coherent enhancement results. Extensive experiments across multiple benchmarks demonstrate the effectiveness of our approach. Code is available at: https://github.com/House-yuyu/InterLight.
Multi-objective bandits with hierarchical preferences and safety constraints is central to many real-world decision-making tasks such as healthcare treatment planning and safe autonomous control, where multiple objectives must be optimized according to their priorities while ensuring safety requirements are satisfied. In this paper, we study a multi-objective stochastic linear bandit framework that incorporates hierarchical preferences together with safety constraints, requiring the learner to remain competitive with respect to a known baseline policy. We consider two practically motivated safety models: (i) cumulative constraints, which require the cumulative performance to exceed the baseline, and (ii) stage-wise constraints, which impose this requirement at each time step. We propose two algorithms, LexUCB-C and LexTS-S, designed for the cumulative and stage-wise settings, respectively. We establish regret bounds showing that both algorithms achieve performance comparable to existing single-objective safe linear bandit methods, while simultaneously optimizing multiple objectives. In addition to theoretical guarantees, we develop a carefully designed experimental framework that captures the interaction between hierarchical preferences and safety constraints. Experiments on synthetic and real-world datasets validate our theory and demonstrate the effectiveness of the proposed methods.
Bounded fitting is an attractive paradigm for learning logical formulas from labeled data examples that offers PAC-style generalization guarantees and can often be implemented leveraging SAT solvers. It has been successfully applied to learning concepts of the description logic ALC. We study bounded fitting for learning concepts in expressive description logics that extend ALC with inverse roles, qualified number restrictions, and feature comparisons. We investigate under which conditions bounded fitting keeps its favorable theoretical properties in this setting, and implement is using a SAT solver. We compare our implementation against state-of-the-art concept learners with encouraging results, demonstrating that it is a practical approach to expressive concept learning.
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.
We initiate the study of online contracts, which integrate the game-theoretic considerations of economic contract theory, with the algorithmic and informational challenges of online algorithm design. Our starting point is the classic online setting with preemption, in which a hiring principal faces a sequence of adversarial agent arrivals. Upon arrival, the principal must decide whether to tentatively accept the agent to their team, and whether to dismiss previous tentative choices. Dismissal is irrevocable, giving the setting its online decision-making flavor. In our setting, the agents are rational players: once the team is finalized, a game is played where the principal offers contracts (performance-based payment schemes), and each agent decides whether or not to work. Working agents reward the principal, and the goal is to choose a team that maximizes the principal's utility. Our main positive result is a 1/2-competitive algorithm when agent rewards are additive, which matches the best-possible competitive ratio. Our algorithm is randomized and this is necessary, as we show that no deterministic algorithm can attain a bounded competitive ratio. Moreover, if agent rewards are allowed to exhibit combinatorial structure known as XOS, even randomized algorithms might fail. En route to our competitive algorithm, we develop the technique of balance points, which can be useful for further exploration of online contracts in the adversarial model.
Subgame solving is a technique for scaling algorithms to large games by locally refining a precomputed blueprint strategy during gameplay. While straightforward in perfect-information games where search starts from the current state, subgame solving in imperfect-information games must account for hidden states and uncertainty about the opponent's past strategy. Gadget games were developed to ensure that the improved subgame strategy is robust against any possible opponent's strategy in a zero-sum game. Gadget games typically contain infinitely many Nash equilibria. We demonstrate that while these equilibria are equivalent in the gadget game, they yield vastly different performance in the full game, even when facing a rational opponent. We propose gadget game sequential equilibria as the preferred solution concept. We introduce modifications to the sequence-form linear program and counterfactual regret minimization that converge to these refined solutions with only mild additional computational cost. Additionally, we provide several new insights into the surprising superiority of the resolving gadget game over the max-margin gadget game. Our experiments compare different Nash equilibria of gadget games in several standard benchmark games, showing that our refined equilibria consistently outperform unrefined Nash equilibria, and can reduce the exploitability of the overall strategy by more than 50%.
Current self-evolution methods mostly chase recall, they learn from any trajectory that ends with the right answer, even when the path relies on a "lucky guess". Such reasoning appears valid in-distribution but often fails the moment the task shifts slightly. We argue that robust evolution implies Structural Invariance: a reasoning path is valid only if its core dependency graph remains isomorphic under counterfactual perturbations. I-EDI enforces this with Verifiable Counterfactual Simulation (VCS). Instead of treating data generation as mere "sample and filter," we treat it as an intervention. Unlike standard rejection sampling, VCS acts as a structural stress test: it accepts a reasoning trace only if it remains valid across generated counterfactuals (e.g., numerical perturbations, context shifts). While this strict filtering reduces the volume of training data (trading recall for precision), our experiments on MATH and GSM8K show it effectively prevents hallucination accumulation, achieving superior out-of-distribution generalization compared to baselines.
We address the problem of selecting k representative nodes from a network, aiming to simultaneously achieve two objectives: identifying the most influential nodes and ensuring that the selection proportionally reflects the diversity within the network. We propose a general approach to accomplish this by combining ideas from network science and computational social choice. Notably, our algorithms depend only on the connections between nodes and do not utilize any additional information that would explicitly identify groups of nodes. We analyze them theoretically, and demonstrate their effectiveness through a series of experiments.
Adaptive Learning Systems (ALS) play a key role in promoting the equity of education, which can provide personalized teaching on a large scale. However, the existing question recommendation methods face the problem of data sparsity at the scenario of cold-start, and lack the ability of long-term teaching reasoning. To address these challenges, we propose QuesRecAgent, a multi-agent framework which involves Large Language Models (LLMs) and the Relexion mechanism for adaptive question recommendation. Different from the traditional black-box methods, the QuesRecAgent applies a framework Dual-Loop State Decoupling architecture, which achieves a rapid updating of beliefs through simulated interaction in the inner loop and do the authoritative diagnosis and meta-strategy reflection to optimize the teaching strategy in the outer loop. Furthermore, with the support of a Topological Knowledge Graph (TKG) and the theory of Zone of Proximal Development (ZPD), the QuesRecAgent ensures a high-quality learning guidance even facing students with limited interaction records. Our experiments on three real-world datasets show that the QuesRecAgent outperforms state-of-the-art baselines in total knowledge gain and other metrics, providing a robust and interpretable solution for promoting high-quality personalized education.