We study the comparison-query complexity of computing allocations that are envy-free up to one item (EF1) for $n$ agents with heterogeneous additive preferences over $m$ indivisible items. In this model, the algorithm may only query which of two bundles an agent prefers, without ever observing numerical valuations or costs. Prior work established $O(\log m)$ query bounds for at most three agents, leaving open whether query complexity logarithmic in $m$ is achievable for every fixed $n \ge 4$. We resolve this open question in the affirmative: for every fixed $n\ge2$, we design algorithms that compute EF1 allocations using $O(\log m)$ comparison queries, matching the known $Ω(\log m)$ lower bound. Our results hold for both chores with nonnegative costs and goods with nonnegative valuations.
Rongqing Jiang, Xuebo Liu Harbin Institute of Technology, Shenzhen, Shengxin Liu Harbin Institute of Technology, Shenzhen, Yutong Wang, Min Zhang Huawei Technologies Ltd., Shimin Tao, Daimeng Wei Huawei Technologies Ltd., Min Zhang Harbin Institute of Technology, Shenzhen and Harbin Institute of Technology
Idiom translation remains a formidable challenge for Large Language Models (LLMs), as the constraints of static parametric memory and the noise in sentence-level retrieval often lead to literal misinterpretations. To address this, we propose DeReA, a detect-retrieve-arbitrate framework. The system employs a preference-aligned detector to identify idiomatic spans by reasoning over semantic conflicts between literal and contextual meanings. Subsequently, an idiom-centric translator invokes a fine-tuned embedding model to efficiently retrieve canonical definitions from an external knowledge base. The translator then utilizes a dual-path arbitration mechanism to select the optimal rendering by weighing the retrieval-augmented translations against direct translation. To evaluate our framework, we introduce LoMI, a high-difficulty benchmark with low data contamination. Experimental results demonstrate that DeReA significantly enhances performance across various model scales, improving GPT-5-mini by over 5.2 points in both idiomatic quality and consistency according to LLM-based metrics. Furthermore, evaluations on an emerging slang dataset from Urban Dictionary validate the potential of our approach in handling novel and evolving linguistic data. Our code is available at https://github.com/jrongqing/DeReA.
尚无 AI 解读，展示原文摘要
cs.CL
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表