Fair division of mixed divisible and indivisible goods

We study the problem of fair division when the set of resources contains both divisible and indivisible goods. Classic fairness notions such as envy-freeness (EF) and envy-freeness up to one good (EF1) cannot be directly applied to this mixed goods setting. In this work, we propose a new fairness...

Full description

Saved in:
Bibliographic Details
Main Authors: Bei, Xiaohui, Li, Zhihao, Liu, Jinyan, Liu, Shengxin, Lu, Xinhang
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2022
Subjects:
Online Access:https://hdl.handle.net/10356/159354
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-159354
record_format dspace
spelling sg-ntu-dr.10356-1593542022-06-16T02:33:43Z Fair division of mixed divisible and indivisible goods Bei, Xiaohui Li, Zhihao Liu, Jinyan Liu, Shengxin Lu, Xinhang School of Physical and Mathematical Sciences Science::Mathematics Fair Division Resource Allocation We study the problem of fair division when the set of resources contains both divisible and indivisible goods. Classic fairness notions such as envy-freeness (EF) and envy-freeness up to one good (EF1) cannot be directly applied to this mixed goods setting. In this work, we propose a new fairness notion, envy-freeness for mixed goods (EFM), which is a direct generalization of both EF and EF1 to the mixed goods setting. We prove that an EFM allocation always exists for any number of agents with additive valuations. We also propose efficient algorithms to compute an EFM allocation for two agents with general additive valuations and for n agents with piecewise linear valuations over the divisible goods. Finally, we relax the envy-freeness requirement, instead asking for ε-envy-freeness for mixed goods (ε-EFM), and present an efficient algorithm that finds an ε-EFM allocation. Ministry of Education (MOE) This work is supported in part by the Ministry of Education, Singapore, under its Academic Research Fund Tier 1 (RG23/20), and by an RGC grant (HKU 17203717E). 2022-06-16T02:33:43Z 2022-06-16T02:33:43Z 2021 Journal Article Bei, X., Li, Z., Liu, J., Liu, S. & Lu, X. (2021). Fair division of mixed divisible and indivisible goods. Artificial Intelligence, 293, 103436-. https://dx.doi.org/10.1016/j.artint.2020.103436 0004-3702 https://hdl.handle.net/10356/159354 10.1016/j.artint.2020.103436 2-s2.0-85098871382 293 103436 en RG23/20 Artificial Intelligence © 2020 Elsevier B.V. All rights reserved.
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic Science::Mathematics
Fair Division
Resource Allocation
spellingShingle Science::Mathematics
Fair Division
Resource Allocation
Bei, Xiaohui
Li, Zhihao
Liu, Jinyan
Liu, Shengxin
Lu, Xinhang
Fair division of mixed divisible and indivisible goods
description We study the problem of fair division when the set of resources contains both divisible and indivisible goods. Classic fairness notions such as envy-freeness (EF) and envy-freeness up to one good (EF1) cannot be directly applied to this mixed goods setting. In this work, we propose a new fairness notion, envy-freeness for mixed goods (EFM), which is a direct generalization of both EF and EF1 to the mixed goods setting. We prove that an EFM allocation always exists for any number of agents with additive valuations. We also propose efficient algorithms to compute an EFM allocation for two agents with general additive valuations and for n agents with piecewise linear valuations over the divisible goods. Finally, we relax the envy-freeness requirement, instead asking for ε-envy-freeness for mixed goods (ε-EFM), and present an efficient algorithm that finds an ε-EFM allocation.
author2 School of Physical and Mathematical Sciences
author_facet School of Physical and Mathematical Sciences
Bei, Xiaohui
Li, Zhihao
Liu, Jinyan
Liu, Shengxin
Lu, Xinhang
format Article
author Bei, Xiaohui
Li, Zhihao
Liu, Jinyan
Liu, Shengxin
Lu, Xinhang
author_sort Bei, Xiaohui
title Fair division of mixed divisible and indivisible goods
title_short Fair division of mixed divisible and indivisible goods
title_full Fair division of mixed divisible and indivisible goods
title_fullStr Fair division of mixed divisible and indivisible goods
title_full_unstemmed Fair division of mixed divisible and indivisible goods
title_sort fair division of mixed divisible and indivisible goods
publishDate 2022
url https://hdl.handle.net/10356/159354
_version_ 1736856388715413504