2025-11-12T03:19:33.205062

EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture

Afshinmehr, Danaei, Kazemi et al.

We consider the fundamental problem of fairly allocating a set of indivisible items among agents having valuations that are represented by a multi-graph -- here, agents appear as vertices and items as edges between them and each vertex (agent) only values the set of its incident edges (items). The goal is to find a fair, i.e., envy-free up to any item (EFX) allocation. This model has recently been introduced by Christodoulou et al. (EC-23) where they show that EFX allocations always exist on simple graphs for monotone valuations, i.e., where any two agents can share at most one edge (item). A natural question arises as to what happens when we go beyond simple graphs and study various classes of multi-graphs? We answer the above question affirmatively for the valuation class of bipartite multi-graphs and multi-cycles. The main contribution of this work is to establish the existence of EFX allocations on bipartite multi-graphs for monotone valuations and on multi-cycles for MMS-feasible valuations. We also present pseudo-polynomial time algorithms to compute EFX allocations for the above settings. Furthermore, we show that for bipartite multi-graphs with cancelable valuations, EFX allocations can be computed in polynomial time. We thus widen the spectrum where EFX allocations are guaranteed to exist. Next, we study EFX orientations (allocations where every item is assigned to one of its two endpoint agents) and provide a complete characterization of their existence on bipartite multi-graphs in terms of two key parameters: (i) the number of edges shared between any two agents and (ii) the diameter of the graph. Finally, we prove that it is NP-complete to determine whether a given fair division instance on a bipartite multi-graph admits an EFX orientation, even with a constant number of agents.

academic

EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture

基本信息

论文ID: 2410.17002
标题: EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture
作者: Mahyar Afshinmehr, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, Nidhi Rathi
分类: cs.GT (博弈论), cs.DS (数据结构与算法)
发表时间: 2024年10月 (arXiv预印本)
论文链接: https://arxiv.org/abs/2410.17002

摘要

本文研究了在多重图表示的估值函数下，不可分割物品的公平分配问题。在这个模型中，智能体对应图的顶点，物品对应边，每个智能体只对其关联的边有正估值。目标是找到一个公平的分配，即满足EFX (envy-free up to any item)条件的分配。论文建立在Christodoulou等人(2023)的工作基础上，后者证明了在简单图上单调估值函数的EFX分配总是存在的。本文将研究扩展到多重图的各种类别，主要贡献包括：(1)证明了二部多重图上单调估值和多重环上MMS-feasible估值的EFX分配存在性；(2)提供了相应的伪多项式时间算法；(3)对EFX定向问题给出了完整的刻画；(4)证明了判断EFX定向存在性的NP完全性。

理论挑战: 对于四个或更多智能体，EFX分配的存在性仍然是一个重大开放问题
模型扩展: Christodoulou等人证明了简单图上EFX分配的存在性，自然的问题是多重图情况如何
实际应用: 该模型适用于地理环境中智能体只关心附近资源的情况，如贸易走廊、天然气管道等

现有方法局限性

现有结果主要局限于简单图(任意两个智能体最多共享一个物品)
对于多重图(两个智能体可以共享多个物品)的情况缺乏系统性研究
EFX定向的存在性和计算复杂性尚未得到完整刻画

核心贡献

存在性定理: 证明了二部多重图上单调估值函数的EFX分配总是存在，多重环上MMS-feasible估值的EFX分配总是存在
算法设计: 提供了计算EFX分配的伪多项式时间算法，对于可约估值函数可在多项式时间内计算
完整刻画: 基于两个关键参数(q和d(G))给出了二部多重图上EFX定向存在性的完整刻画
复杂性分析: 证明了判断EFX定向存在性问题的NP完全性，即使对于常数个智能体也成立
近似结果: 对于不存在EFX定向的情况，证明了存在至少⌈n/2⌉个智能体满足EFX，其余智能体满足1/2-EFX的定向

方法详解

任务定义

输入:

多重图G = (V,E)，其中V = n表示n个智能体，E表示m个物品
估值函数{vi}i∈n，满足vi(S) = vi(S ∩ E(i))，其中E(i)是智能体i的关联边集

输出:

完整分配X = (X1,...,Xn)，满足EFX条件
或EFX定向(每个物品分配给其端点智能体之一)

约束条件:

EFX: 对于任意智能体i,j和物品g ∈ Xj，有vi(Xi) ≥ vi(Xj \ {g})
估值函数类型：单调、可约、MMS-feasible等

模型架构

核心概念

T-cut配置: 对于相邻智能体i ∈ S和j ∈ T，让智能体j将E(i,j)划分为两个包C1和C2，使得两者对j都是EFX-feasible的
可用集合: 定义Ai,j(X)为智能体i在当前分配X下从E(i,j)中的可用边集
安全集合: 对于被嫉妒的智能体i，定义Si(X)为其安全集合

关键性质

算法维护六个关键性质：

X是EFX定向
E(i,j)中的物品按照j-cut配置分配
每个智能体获得其最偏好的可用包
非被嫉妒智能体的可用集合为空
非被嫉妒智能体对其未分配关联边的估值不超过当前包
被嫉妒智能体的嫉妒者在其安全集合中

Algorithm 1: 贪心定向满足性质(1)-(3)
Algorithm 2: 处理非被嫉妒智能体满足性质(4)
Algorithm 3: 增加非被嫉妒智能体估值满足性质(5)
Algorithm 4: 构建安全集合满足性质(6)
Algorithm 5: 最终分配剩余物品

存在性证明: 构造性证明显示如何找到满足条件的分配
算法复杂性分析: 分析各个算法步骤的时间复杂度
反例构造: 通过具体实例证明某些情况下EFX定向不存在

评价指标

EFX满足性: 是否所有智能体都满足EFX条件
时间复杂度: 算法运行时间(多项式vs伪多项式)
近似比: 对于不存在精确解的情况，近似解的质量

参数条件	EFX定向存在性
无环, q=2, d(G)≤4	存在
无环, q=2, d(G)>4	可能不存在
无环, q>2, d(G)≤2	存在
无环, q>2, d(G)>2	可能不存在
有环, q≥2, d(G)≥2	可能不存在