Online Resource Sharing: Better Robust Guarantees via Randomized Strategies
Authors: David X. Lin, Daniel Hall, Giannis Fikioris, Siddhartha Banerjee, Éva Tardos
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section, we experimentally investigate the fraction of ideal utility an agent gets when all agents use robust strategies and show that our proposed strategy performs very well. Specifically, we compare the agents utilities under the following two strategies. First, all agents use the deterministic (1/2 o(1))-robust strategy given by [Gorokh et al., 2021], where each agent bids 2 each time their value is in the top αi-quantile of their value distribution. Second, all agents use our Randomized Robust Bidding strategy, where each agent bids according to a uniform distribution instead. To also illustrate our theoretical results where the other agents are behaving adversarially, we also run an experiment where one agent is using Randomized Robust Bidding but the other agents adversarially always bid 1 regardless of their values. We consider the symmetric agent case, where each agent has fair share αi = 1/n. We consider each agent s value distribution to be Bernoulli(1/n). For each strategy, we compare the agents resulting utility for each number of players n {2, 3, . . . , 30}. We ran the mechanism for T = 100000 time periods 10 times and recorded the average fraction of ideal utility that a particular agent obtained1. We plot our results in Fig. 2. |
| Researcher Affiliation | Academia | David X. Lin , Daniel Hall , Giannis Fikioris , Siddhartha Banerjee , Eva Tardos Cornell University EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Mechanism 1 Repeated first-price auction with artificial currency Input: Number of rounds T, number of agents n, and fair shares α1, . . . , αn 1: Endow each agent i with Bi[1] = αi T tokens of artificial currency. 2: for t = 1, 2, . . . , T do 3: Agents submit bids bi[t] where each bi[t] Bi[t]. 4: Select the winner i = arg maxi bi[t] (ties broken arbitrarily). 5: Set the payments as Pi[t] = bi[t]1{i = i }. 6: Update budgets Bi[t + 1] = Bi[t] Pi[t]. 7: Agents get utility Ui[t] = Vi[t]1{i = i }. 8: end for |
| Open Source Code | Yes | Our code can be found at https://github.com/davidxlin/ repeated-fisher-market-experiments |
| Open Datasets | No | The paper simulates agent behavior based on a Bernoulli(1/n) value distribution and does not use or provide access to any external, publicly available datasets. For example, in Section 5: "We consider each agent s value distribution to be Bernoulli(1/n)." |
| Dataset Splits | No | The paper describes a simulation study with parameters like 'T = 100000 time periods' and 'n {2, 3, . . . , 30}' for the number of players, but it does not specify any training, validation, or test dataset splits as it generates data through simulation rather than using a fixed dataset. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware used to run its simulations or experiments. |
| Software Dependencies | No | The paper mentions that code is available but does not specify any software dependencies or their version numbers (e.g., programming languages, libraries, frameworks). |
| Experiment Setup | Yes | In this section, we experimentally investigate the fraction of ideal utility an agent gets when all agents use robust strategies and show that our proposed strategy performs very well. ... We consider the symmetric agent case, where each agent has fair share αi = 1/n. We consider each agent s value distribution to be Bernoulli(1/n). For each strategy, we compare the agents resulting utility for each number of players n {2, 3, . . . , 30}. We ran the mechanism for T = 100000 time periods 10 times and recorded the average fraction of ideal utility that a particular agent obtained1. |