Truthful Fair Mechanisms for Allocating Mixed Divisible and Indivisible Goods
Authors: Zihao Li, Shengxin Liu, Xinhang Lu, Biaoshuai Tao
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the problem of designing truthful and fair mechanisms when allocating a mixture of divisible and indivisible goods. We first show that there does not exist an EFM (envy-free for mixed goods) and truthful mechanism in general. This impossibility result holds even if there is only one indivisible good and one divisible good and there are only two agents. Thus, we focus on some more restricted settings. Under the setting where agents have binary valuations on indivisible goods and identical valuations on a single divisible good (e.g., money), we design an EFM and truthful mechanism. When agents have binary valuations over both divisible and indivisible goods, we first show there exist EFM and truthful mechanisms when there are only two agents or when there is a single divisible good. On the other hand, we show that the mechanism maximizing Nash welfare cannot ensure EFM and truthfulness simultaneously. |
| Researcher Affiliation | Academia | Zihao Li1 , Shengxin Liu2 , Xinhang Lu3 and Biaoshuai Tao4 1Nanyang Technological University 2Harbin Institute of Technology, Shenzhen 3UNSW Sydney 4Shanghai Jiao Tong University |
| Pseudocode | Yes | Mechanism 1 A truthful EFM 0 mechanism for binary valuations on indivisible good and identical valuation on a single divisible good; Mechanism 2 A truthful EFM>0 mechanism for binary valuations on both divisible and indivisible goods with two agents; Mechanism 3 A truthful EFM>0 mechanism for binary valuations on indivisible goods and a single divisible good |
| Open Source Code | No | The paper does not provide any explicit statements about open-sourcing code, nor does it include links to code repositories. |
| Open Datasets | No | The paper is theoretical and does not involve empirical experiments or datasets, therefore no dataset access information is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments or datasets, therefore no dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe computational experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and describes algorithms conceptually. It does not mention any specific software implementations or dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments or their setup details like hyperparameters or training configurations. |