TY - GEN
T1 - Fair and Efficient Graphical Resource Allocation with Matching-Induced Utilities
AU - Chen, Zheng
AU - Deng, Bin
AU - Li, Bo
AU - Li, Minming
AU - Li, Weidong
AU - Zhang, Guochuan
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.
PY - 2026
Y1 - 2026
N2 - We study the fair allocation of graphical resources, where the resources are the vertices in a graph. Upon receiving a set of resources, an agent’s utility equals the weight of a maximum matching in the induced subgraph. We care about maximin share (MMS) fairness and envy-freeness up to one item (EF1). Regarding MMS fairness, the problem does not admit a finite approximation ratio for heterogeneous agents. For homogeneous agents, we design polynomial-time constant-approximation algorithms, and also note that significant amount of social welfare is sacrificed inevitably in order to ensure (approximate) MMS fairness. We then consider EF1 allocations whose existence is guaranteed. However, the social welfare guarantee of EF1 allocations cannot be better than 1/n for the general case, where n is the number of agents. Fortunately, for three special cases, two-agent, binary-weight and homogeneous-agent, we are able to design polynomial-time algorithms that also ensure a constant fraction of the maximum social welfare.
AB - We study the fair allocation of graphical resources, where the resources are the vertices in a graph. Upon receiving a set of resources, an agent’s utility equals the weight of a maximum matching in the induced subgraph. We care about maximin share (MMS) fairness and envy-freeness up to one item (EF1). Regarding MMS fairness, the problem does not admit a finite approximation ratio for heterogeneous agents. For homogeneous agents, we design polynomial-time constant-approximation algorithms, and also note that significant amount of social welfare is sacrificed inevitably in order to ensure (approximate) MMS fairness. We then consider EF1 allocations whose existence is guaranteed. However, the social welfare guarantee of EF1 allocations cannot be better than 1/n for the general case, where n is the number of agents. Fortunately, for three special cases, two-agent, binary-weight and homogeneous-agent, we are able to design polynomial-time algorithms that also ensure a constant fraction of the maximum social welfare.
UR - https://www.scopus.com/pages/publications/105013165043
U2 - 10.1007/978-981-95-0215-8_22
DO - 10.1007/978-981-95-0215-8_22
M3 - 会议稿件
AN - SCOPUS:105013165043
SN - 9789819502141
T3 - Lecture Notes in Computer Science
SP - 293
EP - 306
BT - Computing and Combinatorics - 31st International Computing and Combinatorics Conference, COCOON 2025, Proceedings
A2 - Fomin, Fedor V.
A2 - Xiao, Mingyu
PB - Springer Science and Business Media Deutschland GmbH
T2 - 31st International Computing and Combinatorics Conference, COCOON 2025
Y2 - 15 August 2025 through 17 August 2025
ER -