Fairness Concepts for Indivisible Items with Externalities
Authors: Haris Aziz, Warut Suksompong, Zhaohong Sun, Toby Walsh
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We undertake a detailed study and present algorithms for finding fair allocations. First, we define the concepts of EF1 and EFX under externalities that still coincide with previous definitions for goods and chores when externalities do not exist. Second, we show how to compute an EFX allocation between two agents in time O(m log m), where m denotes the number of items, and how to compute an EF1 allocation between two agents in time linear in m. Third, we show that the set of EFX allocations among three agents could be empty. Under binary values and a nochore assumption, we show that an EF1 allocation always exists among three agents by proposing a new algorithm that computes such an allocation in polynomial time. Fourth, we propose a new fairness concept called general fair share (GFS) based on proportionality. We present a polynomial-time algorithm that computes an allocation satisfying general fair share up to one item (GFS1) for the more general public decision making model where both positive and negative valuations are allowed. |
| Researcher Affiliation | Collaboration | Haris Aziz1, Warut Suksompong2, Zhaohong Sun3, Toby Walsh1 1School of Computer Science and Engineering, University of New South Wales, Australia 2School of Computing, National University of Singapore, Singapore 3AI Lab, Cyber Agent, Japan |
| Pseudocode | Yes | The details are described in Algorithm 1. |
| Open Source Code | No | The paper does not mention releasing source code or provide any links to a code repository for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve empirical experiments with datasets, so no dataset availability information is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets, so no training, validation, or test split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments, thus no hardware specifications are provided. |
| Software Dependencies | No | The paper mentions writing 'a program to verify that for each case there always exists an EF1 allocation by exhaustive search' in Section 6, but it does not specify any particular software names with version numbers or dependencies for this program. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments, thus no experimental setup details like hyperparameters or training configurations are provided. |