Maximizing social welfare among EF1 allocations at the presence of two types of agents

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\sqrt{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 $\frac{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.

A shorter version appears in ISAAC 2025; 20 pages in this full version