Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Maximin Share Allocations on Cycles
Authors: Miroslaw Truszczynski, Zbigniew Lonc
JAIR 2020 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present cases when maximin share allocations of goods on cycles exist and provide in this case results on allocations guaranteeing each agent a certain fraction of her maximin share. We also study algorithms for computing maximin share allocations of goods on cycles. Our main contributions are as follows. 1. We show that for goods on a cycle, the maximin share value for an agent can be computed in polynomial time. ... 2. We show that the problem to decide the existence of maximin share allocations of goods on an arbitrary graph is in the complexity class P 2 . ... 3. We obtain approximation results on the existence of allocations of goods on a cycle that guarantee every agent a specified fraction of her maximin share value. ... The proof consists of many cases. In each case we provide a different construction of a 3/4-approximate allocation. |
| Researcher Affiliation | Academia | Zbigniew Lonc EMAIL Warsaw University of Technology Koszykowa 75 00-662 Warszawa Poland Miroslaw Truszczynski EMAIL Department of Computer Science University of Kentucky Lexington, KY 40506-0633 USA |
| Pseudocode | Yes | allocate(N, P, Q, c) % P is a path; we fix its direction so that prefixes (initial subpaths) of P are well defined % N = {1, . . . , n}, n 2, is a set of agents, each with a utility function on P % c is a positive real % Q is a prefix of P valued at least c by at least one agent in N 1 S := {i N: there is an (n 1)-split of P Q that is c-strong for i}; 2 R := N S; 3 j := 1; 4 while j n and P has value at least c for some agent in S R do 5 Qj := the shortest prefix of P worth at least c for some agent in S R 6 if Qj is worth at least c to an agent i R then 7 assign Qj to i; 8 R := R {i} 9 else 10 assign Qj to an agent i S such that Qj is worth at least c for i; 11 S := S {i}; 12 P := P Qj; 13 j := j + 1 Figure 5: Algorithm allocate |
| Open Source Code | No | The paper does not provide any statement or link indicating that source code for the described methodology is publicly available. It only mentions an earlier conference paper without offering code for the current work. |
| Open Datasets | No | The paper deals with theoretical concepts such as 'goods form a graph', 'trees', 'cycles', and 'unicyclic graphs'. It does not use any empirical datasets for experimentation, thus no information on open datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets. Therefore, there is no mention of dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design, complexity analysis, and mathematical proofs. It does not describe any experimental setup that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and proofs, rather than practical implementation or empirical evaluation. As such, it does not specify any software dependencies or their version numbers. |
| Experiment Setup | No | The paper presents theoretical results, including algorithm design and proofs, and does not conduct empirical experiments. Therefore, no experimental setup details, hyperparameters, or training configurations are provided. |