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].
Computing Bayes-Nash Equilibria in Combinatorial Auctions with Verification
Authors: Vitor Bosshard, Benedikt Bünz, Benjamin Lubin, Sven Seuken
JAIR 2020 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We validate our approach by running a series of experiments in the LLG domain with two items and three bidders. Our experiments show that the techniques we use significantly speed up our algorithm s runtime and that our algorithm converges consistently despite the use of randomness. Moving beyond single-dimensional domains like LLG, we also discuss the difficulties of scaling any BNE algorithm to high-dimensional auctions (Section 7). We introduce the new multi-minded LLLLGG domain with eight goods and six bidders, which is much larger than any domain that previous algorithms have been able to tackle. In this domain, we find accurate ε-BNEs for both the VCG-nearest and first-price payment rules, which demonstrates the scaling capabilities of our algorithm, and sets a benchmark for future work on BNE algorithms. |
| Researcher Affiliation | Academia | Vitor Bosshard EMAIL Department of Informatics, University of Zurich Benedikt B unz EMAIL Department of Computer Science, Stanford University Benjamin Lubin EMAIL Questrom School of Business, Boston University Sven Seuken EMAIL Department of Informatics, University of Zurich |
| Pseudocode | Yes | Our full algorithm is presented as Algorithm 1 and described below at a high level. Algorithm 1: Iterated Best Response with Verification Appendix A. Pseudocode for Adaptive Control Point Placement Algorithm 2: Computing a best response for one bidder with adaptive control point placement Algorithm 3: Computing the priority of a control point based on the curvature of a bidder s strategy |
| Open Source Code | Yes | We release our code under an open-source license to enable researchers to perform algorithmic analyses of auctions, to enable bidders to analyze different strategies, and to facilitate many other applications. We release the software publicly under an open-source license at https://github.com/marketdesignresearch/CA-BNE. |
| Open Datasets | No | The paper introduces the LLG domain and the LLLLGG domain, and states that valuations are drawn from uniform distributions (e.g., U[0, 2] or U[0, 1]), indicating synthetic data generation rather than the use of pre-existing public datasets. No specific links, DOIs, or citations for datasets are provided. |
| Dataset Splits | No | The paper uses synthetically generated data based on uniform distributions for its experiments (e.g., "the global bidder s valuation is drawn from U[0, 2], while the local bidders valuations are drawn from U[0, 1]"). There are no mentions of explicit train/test/validation splits, sample counts for splits, or citations to predefined splits, as the data is generated on the fly for each run. |
| Hardware Specification | Yes | Each run is performed single-threaded on a 2.8Ghz Intel Xeon E5-2680 v2. |
| Software Dependencies | No | In this section, we describe the software implementation of our BNE algorithm, which is written in Java 8. In particular, we briefly explain how to use the software and then discuss its main features. |
| Experiment Setup | Yes | We lay an evenly-spaced grid of 160 control points over the value space, and at each control point vi, we maximize ui(vi, .) by running Brent search... using 200, 000 Monte Carlo samples. To make the convergence process of the algorithm smoother, we now design an adaptive form of strategy updates (see the work of Fudenberg and Levine (1995) and Lubin and Parkes (2009) for earlier examples of adaptive dampening). Concretely, we set the update weight dynamically for each individual control point, based on how close to a solution we expect to be: ...In our experiments we use the constants wmin = 0.2, wmax = 0.7, and c = 1/2ε. In LLG, we use a pattern of 3 points and a budget of 12 steps. For each run, we show the parameters that vary between the runs, i.e., the grid sizes and the number of Monte Carlo samples used in the search and verification phases. For all runs, as the pattern in pattern search, we use a grid of 3x3 points, with an initial grid spacing of 0.1, and a budget of 8 steps in search and 12 steps in verification. |