Online Market Equilibrium with Application to Fair Division
Authors: Yuan Gao, Alex Peysakhovich, Christian Kroer
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, numerical experiments on real and synthetic datasets show that the dynamics converges quickly under various metrics. |
| Researcher Affiliation | Collaboration | Yuan Gao Columbia University gao.yuan@columbia.edu Alex Peysakhovich Facebook AI Research alex.peys@gmail.com Christian Kroer Columbia University christian.kroer@columbia.edu |
| Pseudocode | Yes | In the PACE dynamics, each buyer maintains a pacing multiplier βt i, starting from an initial value β1 i = 1 + δ0 for some small δ0 > 0 (e.g., δ0 = 0.05). At time step t, the following events take place. (a) An item θt appears and each buyer i sees a value vi(θt). (b) Each buyer i bids their paced value βt ivi(θt) for the item. (c) The item is allocated to the highest bidder (the winner at t): it = arg maxi βt ivi(θt), with ties broken arbitrarily. For concreteness, we always choose the lowest winning index, i.e., it = min arg max i βt ivi(θt). Then, the price of θt is set by the first-price rule pt(θt) = max i βt ivi(θt) = βt itvi(θt) and the winner it pays this price pt(θt) for the item θt. (d) Each buyer i gets a utility ut i = vi(θt)I{i = it}. In other words, the winner it gets vit(θt) and other buyers get zero. (e) Each buyer i updates its cumulative average utility ut i: ut i = t 1 t ut 1 i + 1 t vi(θt)I{i = it}. (f) Each buyer i updates their pacing multiplier βt+1 i as follows: βt+1 i = Π[li,hi](Bi/ ut i) := min{max{li, Bi/ ut i}, hi}. where li = Bi/(1 + δ0) and hi = 1 + δ0 for some fixed δ0 > 0 (e.g., δ0 = 0.05). |
| Open Source Code | Yes | Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? Yes. |
| Open Datasets | Yes | We evaluate the PACE dynamics in several real and synthetic datasets, namely, Movie Lens, Household Items and an infinite-dimensional market instance with item space Θ = [0, 1] and vi being linear functions on [0, 1]. For the first two datasets, see [31] for more information and exploratory data analysis. |
| Dataset Splits | No | Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? N.A. |
| Hardware Specification | No | Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? No. (N.A.) |
| Software Dependencies | No | The paper does not provide specific software dependencies with version numbers. |
| Experiment Setup | No | Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? N.A. |