On the Proximity of Markets with Integral Equilibria
Authors: Siddharth Barman, Sanath Kumar Krishnamurthy1748-1755
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 5 Some Empirical Results For an experimental analysis of ALG, we generate random instances of Fisher markets with equal incomes (e = 1) and uniformly random valuations for the agents. Details of our experimental setup and corresponding empirical results are deferred to a full version of the paper. In summary, our implementation (complying with Corollaries 10 and 11) always finds an allocation which is PROP1 and EF1 1. In fact, for about 96% of the (randomly generated) instances, the implemented method finds an envy-free allocation. This suggests that, in practice, our algorithms outperform the stated theoretical guarantees. In addition, we find that it takes notably less time to execute our rounding method than to compute a market equilibrium (i.e., solve the Eisenberg-Gale program). |
| Researcher Affiliation | Academia | Siddharth Barman Indian Institute of Science barman@iisc.ac.in Sanath Kumar Krishnamurthy Stanford University sanathsk@stanford.edu |
| Pseudocode | Yes | Algorithm: ALG Input : A Fisher market M = [n], [m], V, e with additive valuations and an equilibrium (x, p) of M. Output : An integral allocation x and a budget vector e such that (x , p) is an integral equilibrium of the market M = [n], [m], V, e and e e p 1 Set x ( , , . . . , ), i.e., for any agent i we initialize x i /* We construct x by assigning goods to agents until all goods are allocated */ 2 Initialize G to be the spending forest of (x, p), i.e., G G(x, p) /* Whenever we allocate a good, we delete the corresponding vertex from G. */ 3 Root each tree in the forest G at some agent 4 Allocate all leaf goods to parent agents /* That is, for all j [m] if xi,j = 1 then x i x i {j} and delete j from G. */ 5 while there is an agent i with no parent (i.e., i is a root node) in G do 6 while there is a good g in the neighborhood of i (i.e., edge (i, g) is in G) such that p(x i {g}) ei do 7 Allocate g to agent i: update x i x i {g} and delete g from G. 8 end 9 Allocate every remaining child j of i to any (agent) child k of j and delete j from G. Here, i and k are agents and j is a good /* That is, before agent i s deletion, its grandchildren inherit the remaining child goods of i */ 10 Delete agent i from G. 12 e (p(x 1), p(x 2), . . . , p(x n)) |
| Open Source Code | No | The paper mentions 'our implementation' but does not provide any concrete access information (e.g., a link to a repository or an explicit statement of code release). |
| Open Datasets | No | For an experimental analysis of ALG, we generate random instances of Fisher markets with equal incomes (e = 1) and uniformly random valuations for the agents. Details of our experimental setup and corresponding empirical results are deferred to a full version of the paper. |
| Dataset Splits | No | The paper mentions generating 'random instances' for experimental analysis but does not provide details on specific training, validation, or test splits. It states, 'Details of our experimental setup and corresponding empirical results are deferred to a full version of the paper.' |
| Hardware Specification | No | The paper discusses 'Some Empirical Results' but does not specify any hardware details like GPU/CPU models or other computing infrastructure used for the experiments. |
| Software Dependencies | No | The paper mentions 'our implementation' but does not provide specific software dependencies with version numbers. |
| Experiment Setup | No | For an experimental analysis of ALG, we generate random instances of Fisher markets with equal incomes (e = 1) and uniformly random valuations for the agents. Details of our experimental setup and corresponding empirical results are deferred to a full version of the paper. |