Maxileximin Envy Allocations and Connected Goods
Authors: Gianluigi Greco, Francesco Scarcello
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this study, we analyze the computational properties of maxileximin allocations in the context of fair allocation problems with constraints. Specifically, we focus on the Connected Fair Division problem, where goods correspond to the nodes of a graph, and a bundle of goods is allowed if the subgraph formed by those goods is connected. We demonstrate that the problem is F P 2 -complete, even for instances with simple graphical structures such as path and star graphs. However, we identify islands of tractability for instances with more intricate graphs, such as those having bounded treewidth, provided that the number of agents is bounded by a fixed number and utility functions use small values. |
| Researcher Affiliation | Academia | Gianluigi Greco, Francesco Scarcello University of Calabria {gianluigi.greco, francesco.scarcello}@unical.it |
| Pseudocode | Yes | Input: σ, E, T, χ Task: decide whether there is an allocation B such that, i, j N, E[i][j] = ui(Bj) Method: let q be root of T CHECKPROFILE(q, , E, , N) Procedure CHECKPROFILE(q, λp, ωp, CT p, rest) Begin Procedure guess a (total) mapping λq : χ(q) 7 N assigning to agents the goods occurring at q let new = AGq AGp (the new active agents introduced at q) Stop and Fail if new rest or λq(g) = λp(g), for some good g occurring in both mappings let terminal = AGp AGq (the agents that are active at p and disappear at q) for each agent a terminal, Stop and Fail if ωp[i][a] = 0 , for some i N (some value of the bundle assigned to a does not match the profile E), or CT p[a] contains more than one component (the bundle of goods assigned to a is not connected) for each agent a AGq: i N, update the profile value for i w.r.t. the bundle assigned to a: ωq[i][a] = ωp[i][a] P g (goodsq[a] goodsp[a]) ui(g) if a new then guess the components-tree CT q[a] with the connected components of the induced subgraph G[goodsq[a]] else guess an update of the components-tree CT q[a] (to consider new goods and remove disappeared goods) if q is a leaf of T then if rest = new then Stop and Fail (there is some agent without any bundle of goods) for each agent a AGq and each agent i N, Stop and Fail if ωq[i][a] = 0 (the profile value for i w.r.t. the bundle assigned to a does not match E[i][a]), or CT q[a] contains more than one component (the bundle of goods assigned to a is not connected) else (q is not a leaf of T ) guess a partition rest , rest of the agents in rest new to be dealt with in the two subtrees guess two matrices ω q and ω q such that, i N, a AGq, ω q[i][a] + ω q [i][a] = ωq[i][a], and i N, j N AGq, ω q[i][j] = ω q [i][j] = ωq[i][j] guess a split (CT q[a], CT q [a]) of the components-tree of each a AGq Let ℓand r be the left child and the right child of q in T CHECKPROFILE(ℓ, λq, ω q, CT q, rest ) CHECKPROFILE(r, λq, ω q , CT q , rest ) End Procedure |
| Open Source Code | No | The paper does not provide any concrete access information (e.g., repository link, explicit statement of code release) for the source code of the described methodology. |
| Open Datasets | No | The paper is theoretical and does not use datasets for empirical training or evaluation. Its 'instances' are theoretical constructs for complexity analysis. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments with data splits. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments, thus no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments, thus no software dependencies are specified with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments, thus no experimental setup details like hyperparameters are provided. |