United States

We study the fair allocation of indivisible goods among a group of agents, aiming to limit the envy
between any two agents. The central open problem in this literature, which has proven to be extremely
challenging, is regarding the existence of an EFX allocation, i.e., an allocation such that any envy from
some agent i toward another agent j would vanish if we were to remove any single good from the bundle
allocated to j. When the agents’ valuations are additive, which has been the main focus of prior works,
Chaudhury et al. [2024] were able to show that an EFX allocation is guaranteed to exist for all instances
involving up to three agents. However, the existence of EFX allocations for four agents remains open.
In this paper we contribute to this literature by studying a relaxations of EFX and extending the
existence guarantees to instances with more than three agents. Specifically, we focus on the existence
of EF2X allocations, which ensure that any envy toward some agent vanishes if any two of the goods
allocated to that agent were to be removed. Our main result shows that EF2X allocations are guaranteed
to exist for any instance with four agents, even for the class of cancelable valuations, which is more general
than additive. Furthermore, for instances involving three agents, we provide an algorithm that computes
an EF2X allocation in polynomial time, in contrast to EFX for which the fastest known algorithm for
three agents is only pseudo-polynomial.

AAAI 2025

EF2X Exists for Four Agents

gtep

fair division

technical paper

We are pleased to announce the Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI-25), which will be held in Philadelphia, Pennsylvania at the Pennsylvania Convention Center from February 25 to March 4, 2025.

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.

### [Invited Speakers](https://aaai.org/conference/aaai/aaai-25/aaai-25-invited-speakers/)

Register [here](https://aaai.org/conference/aaai/aaai-25/registration/)

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.



Large Language Models (LLMs) possess vast amounts of knowledge within their parameters, prompting research into methods for locating and editing this knowledge. Previous work has largely focused on locating entity-related (often _single-token_) facts in smaller models. However, several key questions remain unanswered: (1) _How can we effectively locate query-relevant neurons in contemporary autoregressive LLMs, such as Llama and Mistral?_ (2) _How can we address the challenge of long-form text generation?_ (3) _Are there localized knowledge regions in LLMs?_ In this study, we introduce Query-Relevant Neuron Cluster Attribution (QRNCA), a novel architecture-agnostic framework capable of identifying query-relevant neurons in LLMs. QRNCA allows for the examination of long-form answers beyond triplet facts by employing the proxy task of multi-choice question answering. To evaluate the effectiveness of our detected neurons, we build two multi-choice QA datasets spanning diverse domains and languages. Empirical evaluations demonstrate that our method outperforms baseline methods significantly. Further, analysis of neuron distributions reveals the presence of visible localized regions, particularly within different domains. Finally, we show potential applications of our detected neurons in knowledge editing and neuron-based prediction.

Identifying Query-Relevant Neurons in Large Language Models for Long-Form Texts

Multi-Agent Path Finding (MAPF) is the problem of planning collision-free paths for multiple agents. Unfortunately, during the execution of a MAPF plan, agents may suffer from unexpected delays. Given such delays, Switchable Temporal Plan Graph (STPG) provides a framework to search for an acyclic Temporal Plan Graph (TPG) with the minimum execution cost, which guarantees deadlock- and collision-free execution. However, existing optimal algorithms like Mixed-Integer Linear Programming (MILP) or Graph-Based Switchable Edge Search (GSES) are too slow. This paper speeds up GSES with four techniques: stronger admissible heuristics, edge grouping, prioritized branching, and incremental implementation. Experimenting on 4 different types of maps with varying numbers of agents, our method, Improved GSES (IGSES), consistently achieves more than double the success rates of GSES and demonstrates up to a 30-fold speedup on instances where both methods find solutions.

Speedup Techniques for Switchable Temporal Plan Graph Optimization

Cross-domain recommendation (CDR) mitigates data sparsity and cold-start issues in recommendation systems. While recent CDR approaches using graph neural networks (GNNs) capture complex user-item interactions, they rely on manually designed architectures that are often suboptimal and labor-intensive. Additionally, extracting valuable behavioral information from source domains to improve target domain recommendations remains challenging. To address these challenges, we propose Behavior importance-aware Graph Neural Architecture Search (BiGNAS), a framework that jointly optimizes GNN architecture and data importance for CDR. BiGNAS introduces two key components: a Cross-Domain Customized Supernetwork and a Graph-Based Behavior Importance Perceptron. The supernetwork, as a one-shot, retrain-free module, automatically searches the optimal GNN architecture for each domain without the need for retraining. The perceptron uses auxiliary learning to dynamically assess the importance of source domain behaviors, thereby improving target domain recommendations. Extensive experiments on benchmark CDR datasets and a large-scale industry advertising dataset demonstrate that BiGNAS consistently outperforms state-of-the-art baselines. To the best of our knowledge, this is the first work to jointly optimize GNN architecture and behavior data importance for cross-domain recommendation.

Behavior Importance-Aware Graph Neural Architecture Search for Cross-Domain Recommendation

The clique partitioning problem (CPP) aims to find a partition of vertices of a complete graph in order to maximize the sum of edge weights within each partition (clique), which has been proven to be NP-hard and has wide real-world applications. In this paper, we propose an elite-guided weighted simulated annealing algorithm called EWSA to solve the CPP. First, EWSA employs two specific configurations and alternates between them via an oscillation strategy, which balances the exploitation and exploration of the search. Second, a weighting strategy is introduced to improve the scoring function in traditional simulated annealing, which is able to guide the search to explore diverse solutions. Finally, a partition restriction strategy is adopted to reduce search space and increase the search efficiency. Experiments on 255 instances demonstrate the competitiveness of EWSA. For 130 open instances, EWSA discovers new upper bounds in 32 cases and matches the best known results for the others. For the remaining 125 closed instances, EWSA achieves the best known objective values within a short computational time.

An Elite-guided Weighted Simulated Annealing Algorithm for the Clique Partitioning Problem

In this paper, we introduce a new family of argument-ranking semantics which can be seen as a refinement of the classification of arguments into skeptically accepted, credulously accepted and rejected. To this end we use so-called social ranking functions which have been developed recently to rank individuals based on their performance in groups. We provide necessary and sufficient conditions for a social ranking function to give rise to an argument-ranking semantics satisfying the desired refinement property.

An Extension-Based Argument-Ranking Semantics: Social Rankings in Abstract Argumentation

Explainable AI increasingly relies on argumentation methods to facilitate interactive explanations between AI agents and human users. While most works assume a known human user model as a prior, there is a critical gap in effectively learning and updating these models dynamically. In this paper, we address this gap with a framework that enables AI agents to learn and update probabilistic human models through argumentation-based dialogues. Specifically, our approach, called Persona, is inspired by prospect theory and integrates a probability weighting function with a Bayesian belief update mechanism that refines a probability distribution over possible human models based on exchanged arguments. Through empirical evaluations with human users in an applied argumentation setting, we demonstrate the effectiveness of Persona in capturing evolving human beliefs and facilitating personalized interactions, while also outperforming state-of-the-art methods.

Does Your AI Agent Get You? A Personalizable Framework for Approximating Human Models from Argumentation-based Dialogue Traces

Sequential Recommender Systems (SRS), which model a user's interaction history to predict the next item of interest, are widely used in various applications. However, existing SRS often struggle with low-popularity items, a challenge known as the long-tail problem. This issue leads to reduced serendipity for users and diminished profits for sellers, ultimately harming the overall system. Large Language Model (LLM) has the ability to capture semantic relationships between items, independent of their popularity, making them a promising solution to this problem. In this paper, we introduce __LLMEmb__, a novel method leveraging LLM to generate item embeddings that enhance SRS performance. To bridge the gap between general-purpose LLM and the recommendation domain, we propose a Supervised Contrastive Fine-Tuning (SCFT) approach. This approach includes attribute-level data augmentation and a tailored contrastive loss to make LLM more recommendation-friendly. Additionally, we emphasize the importance of integrating collaborative signals into LLM-generated embeddings, for which we propose Recommendation Adaptation Training (RAT). This further refines the embeddings for optimal use in SRS. The LLMEmb-derived embeddings can be seamlessly integrated with any SRS model, underscoring the practical value. Comprehensive experiments conducted on three real-world datasets demonstrate that LLMEmb significantly outperforms existing methods across multiple SRS models. The code for our method is provided in the __Supplementary Materials__.

LLMEmb: Large Language Model Can Be a Good Embedding Generator for Sequential Recommendation

Text-to-SQL enables users to interact with databases through natural language, simplifying the retrieval and synthesis of information. Despite the success of large language models (LLMs) in converting natural language questions into SQL queries, their broader adoption is limited by two main challenges: achieving robust generalization across diverse queries and ensuring interpretative confidence in their predictions. To tackle these issues, our research investigates the integration of selective classifiers into text-to-SQL systems. 
We analyse the trade-off between coverage and risk using entropy based confidence estimation with selective classifiers and assess its impact on the overall performance of text-to-SQL models.  Additionally, we explore the models' initial calibration and improve it with calibration techniques for better model alignment between confidence and accuracy.  Our experimental results show that encoder-decoder T5 is better calibrated than in-context-learning GPT 4 and decoder-only Llama 3, thus the designated external entropy-based selective classifier has better performance.  The study also reveal that, in terms of error detection, selective classifier with a higher probability detects errors associated with irrelevant questions rather than incorrect query generations.

Confidence Estimation for Error Detection in Text-to-SQL Systems

Opponent Modeling (OM) aims to enhance decision-making by modeling other agents in multi-agent environments. Existing works typically learn opponent models against a pre-designated fixed set of opponents during training. However, this will cause poor generalization when facing unknown opponents during testing, as previously unseen opponents can exhibit out-of-distribution (OOD) behaviors that the learned opponent models cannot handle. To tackle this problem, we introduce a novel Open-Ended Opponent Modeling (OEOM) framework, which continuously generates opponents with diverse strengths and styles to reduce the possibility of OOD situations occurring during testing. Founded on population-based training and information-theoretic trajectory space diversity regularization, OEOM generates a dynamic set of opponents. This set is then fed to any OM approaches to train a potentially generalizable opponent model. Upon this, we further propose a simple yet effective OM approach that naturally fits within the OEOM framework. This approach is based on in-context reinforcement learning and learns a Transformer that dynamically recognizes and responds to opponents based on their trajectories. Extensive experiments in cooperative, competitive, and mixed environments demonstrate that OEOM is an approach-agnostic framework that improves generalizability compared to training against a fixed set of opponents, regardless of OM approaches or testing opponent settings. The results also indicate that our proposed approach generally outperforms existing OM baselines.

An Open-Ended Learning Framework for Opponent Modeling

Drafting radiology reports is a complex task requiring flexibility, where radiologists need to adjust the content based on the information available and particular clinical demands. However, most current automated radiology report generation (RRG) models are constrained to a fixed task paradigm, such as predicting the complete ``finding'' section from a single image. Such a fixed task paradigm inherently involves a mismatch between inputs and outputs. The trained models lack the flexibility for diverse inputs and could generate harmful, input-agnostic hallucinations. To bridge the gap between current RRG models and the clinical demands in practice, we first develop a data generation pipeline to create a new MIMIC-RG4 dataset, which considers four common radiology report drafting scenarios and has perfectly corresponded input and output. Secondly, we propose a novel large language model (LLM) based RRG framework, namely LLM-RG4, which utilizes LLM as the text decoder to leverage its flexible instruction-following capabilities and extensive general knowledge. We further develop an adaptive token fusion module that offers flexibility to handle diverse scenarios with different input combinations, while minimizing the additional computational burden associated with increased input volumes. Besides, we propose a token-level loss weighting strategy to direct the model's attention towards positive and uncertain descriptions, which are essential for accurate clinical diagnosis. Experimental results demonstrate that LLM-RG4 achieves state-of-the-art performance in both clinical efficiency and natural language generation on the MIMIC-RG4 and MIMIC-CXR datasets. We quantitatively demonstrate that our model has minimal input-agnostic hallucinations, whereas current open-source models commonly suffer from this problem.

Premium content

Downloads

Next from AAAI 2025

Identifying Query-Relevant Neurons in Large Language Models for Long-Form Texts

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES