Groupwise Maximin Fair Allocation of Indivisible Goods
Authors: Siddharth Barman, Arpita Biswas, Sanath Krishnamurthy, Yadati Narahari
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, we empirically demonstrate the existence of GMMS allocations in a large set of randomly generated instances. For the same set of instances, we additionally show that our algorithm achieves an approximation factor better than the established, worst-case bound. For an experimental investigation, we generated 1000 random instances, for several combinations of n agents and m goods (n ranging from 3 to 5, and m from 3 to 11), by randomly drawing the valuations from two different distributions (a) gaussian distribution with mean 0.5, standard deviation 0.1 (truncated at 0 to ensure nonnegative valuations) and (b) uniform distribution [0, 1]. |
| Researcher Affiliation | Academia | Siddharth Barman Indian Institute of Science barman@iisc.ac.in Arpita Biswas Indian Institute of Science arpitab@iisc.ac.in Sanath Kumar Krishnamurthy Chennai Mathematical Institute sanathkumar9@cmi.ac.in Yadati Narahari Indian Institute of Science narahari@iisc.ac.in |
| Pseudocode | Yes | Algorithm 1 Finding an EFL Allocation Input : n agents, m items, and valuations vi{g} for each agent i [n] and for each good g [m]. Output: An EFL allocation. 1: Initialize allocation A = (A1, A2, . . . , An) with Ai = for each agent i [n], and M = [m]. 2: Initialize directed envy graph G(A) = ([n], E) where E = . 3: while M = do 4: Pick a source vertex i of G(A). {such a vertex always exists, since G(A) is acyclic.} 5: Pick g arg maxj M vi{g}. 6: Update Ai Ai {g} and M M \ {g}. 7: while the current envy graph G(A) contains a cycle do 8: Update A (using Lemma 2) to remove the cycle. 9: end while 10: end while 11: Return A. |
| Open Source Code | No | The paper does not provide an explicit statement or link for the open-source code of the methodology described in the paper. |
| Open Datasets | No | The paper states, 'For an experimental investigation, we generated 1000 random instances, for several combinations of n agents and m goods (n ranging from 3 to 5, and m from 3 to 11), by randomly drawing the valuations from two different distributions (a) gaussian distribution with mean 0.5, standard deviation 0.1 (truncated at 0 to ensure nonnegative valuations) and (b) uniform distribution [0, 1].' However, it does not provide concrete access information (link, DOI, repository, or citation) for these generated instances to be publicly available. |
| Dataset Splits | No | The paper mentions generating 'random instances' for empirical investigation but does not specify any training, validation, or test dataset splits. |
| Hardware Specification | Yes | Our algorithm was about 107 times faster than the exact GMMS computation on a machine with a quad Intel Core i7 processor and 32 GB RAM. |
| Software Dependencies | No | The paper does not provide specific software dependencies with version numbers. |
| Experiment Setup | Yes | For an experimental investigation, we generated 1000 random instances, for several combinations of n agents and m goods (n ranging from 3 to 5, and m from 3 to 11), by randomly drawing the valuations from two different distributions (a) gaussian distribution with mean 0.5, standard deviation 0.1 (truncated at 0 to ensure nonnegative valuations) and (b) uniform distribution [0, 1]. |