{"ID":2890839,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.18251","arxiv_id":"2507.18251","title":"On Pareto-Optimal and Fair Allocations with Personalized Bi-Valued Utilities","abstract":"We study the fair division problem of allocating $m$ indivisible goods to $n$ agents with additive personalized bi-valued utilities. Specifically, each agent $i$ assigns one of two positive values $a_i \u003e b_i \u003e 0$ to each good, indicating that agent $i$'s valuation of any good is either $a_i$ or $b_i$. For convenience, we denote the value ratio of agent $i$ as $r_i = a_i / b_i$. We give a characterization to all the Pareto-optimal allocations. Our characterization implies a polynomial-time algorithm to decide if a given allocation is Pareto-optimal in the case each $r_i$ is an integer. For the general case (where $r_i$ may be fractional), we show that this decision problem is coNP-complete. Our result complements the existing results: this decision problem is coNP-complete for tri-valued utilities (where each agent's value for each good belongs to $\\{a,b,c\\}$ for some prescribed $a\u003eb\u003ec\\geq0$), and this decision problem belongs to P for bi-valued utilities (where $r_i$ in our model is the same for each agent). We further show that an EFX allocation always exists and can be computed in polynomial time under the personalized bi-valued utilities setting, which extends the previous result on bi-valued utilities. We propose the open problem of whether an EFX and Pareto-optimal allocation always exists (and can be computed in polynomial time).","short_abstract":"We study the fair division problem of allocating $m$ indivisible goods to $n$ agents with additive personalized bi-valued utilities. Specifically, each agent $i$ assigns one of two positive values $a_i \u003e b_i \u003e 0$ to each good, indicating that agent $i$'s valuation of any good is either $a_i$ or $b_i$. For convenience,...","url_abs":"https://arxiv.org/abs/2507.18251","url_pdf":"https://arxiv.org/pdf/2507.18251v2","authors":"[\"Jiarong Jin\",\"Biaoshuai Tao\"]","published":"2025-07-24T09:49:50Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}