Fair and Efficient Graphical Resource Allocation with Matching-Induced Utilities

Zheng Chen; Bin Deng; Bo Li; Minming Li; Weidong Li; Guochuan Zhang

doi:10.1007/978-981-95-0215-8_22

Fair and Efficient Graphical Resource Allocation with Matching-Induced Utilities

Zheng Chen^*, Bin Deng, Bo Li, Minming Li, Weidong Li, Guochuan Zhang

^*Corresponding author for this work

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

Abstract

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. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.

Original language	English
Title of host publication	Computing and Combinatorics
Subtitle of host publication	31st International Computing and Combinatorics Conference, COCOON 2025, Chengdu, China, August 15–17, 2025, Proceedings, Part I
Editors	Fedor V. Fomin, Mingyu Xiao
Place of Publication	Singapore
Publisher	Springer
Pages	293-306
ISBN (Electronic)	978-981-95-0215-8
ISBN (Print)	9789819502141
DOIs	https://doi.org/10.1007/978-981-95-0215-8_22
Publication status	Published - 2026
Event	31st International Computing and Combinatorics Conference (COCOON 2025) - Crowne Plaza Chengdu West, Chengdu, China Duration: 15 Aug 2025 → 17 Aug 2025

Publication series

Name	Lecture Notes in Computer Science
Volume	15983
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	31st International Computing and Combinatorics Conference (COCOON 2025)
Place	China
City	Chengdu
Period	15/08/25 → 17/08/25

Funding

This work is supported in part by NSFC No. 12271477, HK RGC No. PolyU 25211321, and GDSTC No. 2024A1515011524.

Access Output

10.1007/978-981-95-0215-8_22

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Chen, Z., Deng, B., Li, B., Li, M., Li, W., & Zhang, G. (2026). Fair and Efficient Graphical Resource Allocation with Matching-Induced Utilities. In F. V. Fomin, & M. Xiao (Eds.), Computing and Combinatorics: 31st International Computing and Combinatorics Conference, COCOON 2025, Chengdu, China, August 15–17, 2025, Proceedings, Part I (pp. 293-306). (Lecture Notes in Computer Science; Vol. 15983). Springer . https://doi.org/10.1007/978-981-95-0215-8_22

Chen, Zheng ; Deng, Bin ; Li, Bo et al. / Fair and Efficient Graphical Resource Allocation with Matching-Induced Utilities. Computing and Combinatorics: 31st International Computing and Combinatorics Conference, COCOON 2025, Chengdu, China, August 15–17, 2025, Proceedings, Part I. editor / Fedor V. Fomin ; Mingyu Xiao. Singapore : Springer , 2026. pp. 293-306 (Lecture Notes in Computer Science).

@inproceedings{27b254b79a0945569c7a575e9edaa624,

title = "Fair and Efficient Graphical Resource Allocation with Matching-Induced Utilities",

abstract = "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{\textquoteright}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. {\textcopyright} The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.",

author = "Zheng Chen and Bin Deng and Bo Li and Minming Li and Weidong Li and Guochuan Zhang",

year = "2026",

doi = "10.1007/978-981-95-0215-8_22",

language = "English",

isbn = "9789819502141",

series = "Lecture Notes in Computer Science",

publisher = "Springer ",

pages = "293--306",

editor = "Fomin, {Fedor V. } and Xiao, {Mingyu }",

booktitle = "Computing and Combinatorics",

note = "31st International Computing and Combinatorics Conference (COCOON 2025) ; Conference date: 15-08-2025 Through 17-08-2025",

}

Chen, Z, Deng, B, Li, B, Li, M, Li, W & Zhang, G 2026, Fair and Efficient Graphical Resource Allocation with Matching-Induced Utilities. in FV Fomin & M Xiao (eds), Computing and Combinatorics: 31st International Computing and Combinatorics Conference, COCOON 2025, Chengdu, China, August 15–17, 2025, Proceedings, Part I. Lecture Notes in Computer Science, vol. 15983, Springer , Singapore, pp. 293-306, 31st International Computing and Combinatorics Conference (COCOON 2025), Chengdu, China, 15/08/25. https://doi.org/10.1007/978-981-95-0215-8_22

Fair and Efficient Graphical Resource Allocation with Matching-Induced Utilities. / Chen, Zheng; Deng, Bin; Li, Bo et al.
Computing and Combinatorics: 31st International Computing and Combinatorics Conference, COCOON 2025, Chengdu, China, August 15–17, 2025, Proceedings, Part I. ed. / Fedor V. Fomin; Mingyu Xiao. Singapore: Springer , 2026. p. 293-306 (Lecture Notes in Computer Science; Vol. 15983).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

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

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. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.

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. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.

UR - http://www.scopus.com/inward/record.url?scp=105013165043&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-105013165043&origin=recordpage

U2 - 10.1007/978-981-95-0215-8_22

DO - 10.1007/978-981-95-0215-8_22

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9789819502141

T3 - Lecture Notes in Computer Science

SP - 293

EP - 306

BT - Computing and Combinatorics

A2 - Fomin, Fedor V.

A2 - Xiao, Mingyu

PB - Springer

CY - Singapore

T2 - 31st International Computing and Combinatorics Conference (COCOON 2025)

Y2 - 15 August 2025 through 17 August 2025

ER -

Chen Z, Deng B, Li B, Li M, Li W, Zhang G. Fair and Efficient Graphical Resource Allocation with Matching-Induced Utilities. In Fomin FV, Xiao M, editors, Computing and Combinatorics: 31st International Computing and Combinatorics Conference, COCOON 2025, Chengdu, China, August 15–17, 2025, Proceedings, Part I. Singapore: Springer . 2026. p. 293-306. (Lecture Notes in Computer Science). Epub 2025 Aug 1. doi: 10.1007/978-981-95-0215-8_22

Fair and Efficient Graphical Resource Allocation with Matching-Induced Utilities

Abstract

Publication series

Conference

Funding

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this