Search Results

Documents authored by Ma, Jiaxuan

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.49
Maximizing Social Welfare Among EF1 Allocations at the Presence of Two Types of Agents

Authors: Jiaxuan Ma, Yong Chen, Guangting Chen, Mingyang Gong, Guohui Lin, and An Zhang

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
We study the fair allocation of indivisible items to n agents to maximize the utilitarian social welfare, where the fairness criterion is envy-free up to one item and there are only two different utility functions shared by the agents. We present a 2-approximation algorithm when the two utility functions are normalized, improving the previous best ratio of 16 √n shown for general normalized utility functions; thus this constant ratio approximation algorithm confirms the APX-completeness in this special case previously shown APX-hard. When there are only three agents, i.e., n = 3, the previous best ratio is 3 shown for general utility functions, and we present an improved and tight 5/3-approximation algorithm when the two utility functions are normalized, and a best possible and tight 2-approximation algorithm when the two utility functions are unnormalized.
Cite as

Jiaxuan Ma, Yong Chen, Guangting Chen, Mingyang Gong, Guohui Lin, and An Zhang. Maximizing Social Welfare Among EF1 Allocations at the Presence of Two Types of Agents. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 49:1-49:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ma_et_al:LIPIcs.ISAAC.2025.49,
  author =	{Ma, Jiaxuan and Chen, Yong and Chen, Guangting and Gong, Mingyang and Lin, Guohui and Zhang, An},
  title =	{{Maximizing Social Welfare Among EF1 Allocations at the Presence of Two Types of Agents}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{49:1--49:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.49},
  URN =		{urn:nbn:de:0030-drops-249570},
  doi =		{10.4230/LIPIcs.ISAAC.2025.49},
  annote =	{Keywords: Fair allocation, utilitarian social welfare, envy-free up to one item, envy-cycle elimination, round robin, approximation algorithm}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact