Approximating Fair Division on D-Claw-Free Graphs
Authors: Zbigniew Lonc
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | For this class of graphs we prove that there is an allocation assigning each agent a connected bundle of value at least 1/d of her maximin share. Moreover, for the same class of graphs of goods, we show a theorem which speciļ¬es what fraction of the proportional share can be guaranteed to each agent if the values of single goods for the agents are bounded by a given fraction of this share. Finding a polynomial time algorithm for constructing a 1/d-mms allocation for (d+1)-claw-free graphs of goods will be a subject of our future research. |
| Researcher Affiliation | Academia | Zbigniew Lonc Warsaw University of Technology, Poland zbigniew.lonc@pw.edu.pl |
| Pseudocode | Yes | Algorithm 1 allocate(N , G X, c) 1 T := N ; 2 for j = 1, 2, . . . , s do 3 sort the agents i T non increasingly according to the key f(i, j): ij 1, ij 2, . . . , ij |T |; 4 kj := the largest p such that f(ij p, j) p; 5 Ij := {ij 1, ij 2, . . . , ij kj}; 6 agents in Ij distribute the vertices of V (Gj) among themselves according to the allocation A(Ij, Gj); 7 T := T Ij; 8 if T = then 9 return |
| Open Source Code | No | The paper does not provide any statement or link indicating that source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and does not use datasets, thus no information about public availability of a dataset is provided. |
| Dataset Splits | No | The paper is theoretical and does not use datasets, therefore no training/test/validation splits are discussed. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers required for replication. |
| Experiment Setup | No | The paper is theoretical and does not provide details about an experimental setup, hyperparameters, or system-level training settings. |