Conflict and Fairness in Resource Allocation

在公平分配资源给代理人的标准模型中，每个代理人对每种资源都有一定的效用，目标是将资源分配给代理人，使得代理人的福利最大化。受到工作调度的启发，对这个问题的兴趣可以追溯到Deuermeyer等人的研究[SIAM J. on Algebraic Discrete Methods'82]。最近的研究考虑资源之间的兼容性，并且只分配相互兼容的资源给代理人。我们研究了一个公平分配问题，给定一组代理人、一组资源、每个代理人对一组资源的效用函数以及资源的“冲突图”（其中一条边表示资源之间的不兼容性）。目标是将资源分配给代理人，使得$(i)$分配给代理人的资源是相互兼容的，$(ii)$最小满意度最大化，其中代理人的满意度是分配资源效用的总和。Chiarelli等人[Algorithmica'22]从经典复杂度的角度探讨了这个问题，划分了多项式可解和NP难的情况。在本文中，我们通过考虑几个自然和结构参数，研究了该问题（及其变体）的参数化复杂度。

研究公平分配问题中的参数化复杂度，考虑了多种自然和结构参数。

在考虑冲突图和资源兼容性的基础上，通过参数化复杂度的研究，探讨了如何将资源公平地分配给代理商，以最大化代理商的福利。

论文提出了多种参数化复杂度算法，并进行了实验验证。研究结果表明，该问题在某些参数下是多项式时间可解的，而在其他参数下是NP难的。值得关注的是，该问题的研究有助于更好地理解公平分配问题的本质。

在此前的研究中，已经探讨过公平分配问题。例如，Deuermeyer等人在1982年提出了一个公平分配模型。Chiarelli等人在本文中提到的最近的工作中，考虑了资源兼容性，并探究了该问题的复杂度问题。