Two-Price Equilibrium
Authors: Michal Feldman, Galia Shabtai, Aner Wolfenfeld5008-5015
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We introduce a new market equilibrium notion, called two-price equilibrium (2PE). A 2PE is a relaxation of Walrasian equilibrium, where instead of a single price per item, every item has two prices: one for the item s owner and a (possibly) higher one for all other buyers. Thus, a 2PE is given by a tuple (S, ˆp, ˇp) of an allocation S and two price vectors ˆp, ˇp, where every buyer i is maximally happy with her bundle Si, given prices ˇp for items in Si and prices ˆp for all other items. 2PE generalizes previous market equilibrium notions, such as conditional equilibrium, and is related to relaxed equilibrium notions like endowment equilibrium. We define the discrepancy of a 2PE a measure of distance from Walrasian equilibrium as the sum of differences ˆpj ˇpj over all items (normalized by social welfare). We show that the social welfare degrades gracefully with the discrepancy; namely, the social welfare of a 2PE with discrepancy d is at least a fraction 1 d+1 of the optimal welfare. We use this to establish welfare guarantees for markets with subadditive valuations over identical items. In particular, we show that every such market admits a 2PE with at least 1/7 of the optimal welfare. This is in contrast to Walrasian equilibrium or conditional equilibrium which may not even exist. Our techniques provide new insights regarding valuation functions over identical items, which we also use to characterize instances that admit a WE. |
| Researcher Affiliation | Academia | Michal Feldman, Galia Shabtai, Aner Wolfenfeld Tel Aviv University michal.feldman@cs.tau.ac.il, galiashabtai@gmail.com, anerwolf@gmail.com |
| Pseudocode | Yes | Algorithm 1: An algorithm for finding an allocation with discrepancy of at most 6 for heterogeneous buyers. Input: m, n, (v1, v2, . . . , vn) Output: (k1, k2, . . . , kn), s.t. P i [n] ki = m and ki 0 for every i [n] |
| Open Source Code | No | The paper does not provide any explicit statements about open-source code availability or links to code repositories for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve experimental evaluation on datasets. Therefore, there is no mention of training data availability or access information. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental evaluation on datasets. Therefore, there is no mention of validation dataset splits or procedures. |
| Hardware Specification | No | The paper is theoretical and does not describe experimental procedures or computations that would require specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe specific software implementations or experiments. Therefore, it does not list any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not involve empirical experiments with specific setups or hyperparameters. Therefore, no experimental setup details are provided. |