{"ID":2872295,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.09641","arxiv_id":"2509.09641","title":"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 53$-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.","short_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 normal...","url_abs":"https://arxiv.org/abs/2509.09641","url_pdf":"https://arxiv.org/pdf/2509.09641v1","authors":"[\"Jiaxuan Ma\",\"Yong Chen\",\"Guangting Chen\",\"Mingyang Gong\",\"Guohui Lin\",\"An Zhang\"]","published":"2025-09-11T17:28:01Z","proceeding":"cs.GT","tasks":"[\"cs.GT\",\"cs.DS\"]","methods":"[]","has_code":false}