An $\alpha$-regret analysis of Adversarial Bilateral Trade
Authors: Yossi Azar, Amos Fiat, Federico Fusco
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study sequential bilateral trade where sellers and buyers valuations are completely arbitrary (i.e., determined by an adversary). Sellers and buyers are strategic agents with private valuations for the good and the goal is to design a mechanism that maximizes efficiency (or gain from trade) while being incentive compatible, individually rational and budget balanced. In this paper we consider gain from trade which is harder to approximate than social welfare. We show several surprising results about the separation between the different scenarios. In particular, we show that (a) it is impossible to achieve sublinear α-regret for any α < 2, (b) but with full feedback sublinear 2-regret is achievable (c) with a single price and partial feedback one cannot get sublinear α regret for any constant α (d) nevertheless, posting two prices even with one-bit feedback achieves sublinear 2-regret, and (e) there is a provable separation in the 2-regret bounds between full and partial feedback. |
| Researcher Affiliation | Academia | Yossi Azar Department of Computer Science Tel Aviv University, Israel azar@tauex.tau.ac.il Amos Fiat Department of Computer Science Tel Aviv University, Israel fiat@tau.ac.il Federico Fusco Department of Computer, Control and Management Engineering Sapienza Università di Roma, Italy fuscof@diag.uniroma1.it |
| Pseudocode | Yes | Estimation procedure of GFT using two prices and one-bit feedback Input: price p Toss a biased coin with head probability p if head then Draw U u.a.r. in [0, p] and set ˆp U, ˆq p else Draw V u.a.r. in [p, 1] and set ˆp p, ˆq V Post price ˆp to the seller and ˆq to the buyer and observe the one-bit feedback I{s ˆp ˆq b} Return: [ GFT(p) I{s ˆp ˆq b} Unbiased estimator of GFT(p) AND BLOCK-DECOMPOSITION (BD) 1: Input: time horizon T, number of blocks S, grid Q and expert algorithm E 2: T/S, K |Q| 3: Bτ {(τ 1) + 1, . . . , τ }, for all τ = 1, 2, . . . , S 4: Initialize E with time horizon S and K actions, one for each pi Q 5: for each round τ = 1, 2, . . . , S do 6: Receive from E the price pτ 7: Select uniformly at random an injection hτ : Q Bτ We need >> |Q| 8: for each round t Bτ do 9: if hτ(pi) = t for some price pi then 10: Use the estimator [ GFT(pi) at time t and call its output [ GFTτ(pi) 11: else: Post price pτ and ignore feedback 12: Feed to E the estimated gains {[ GFTτ(pi)}i=1,...,K |
| Open Source Code | No | The ethics review section states: 'Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A]' |
| Open Datasets | No | The paper is theoretical and does not conduct empirical experiments with datasets. Thus, it does not specify public dataset availability. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical experiments with datasets. Thus, it does not specify training/test/validation dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not conduct empirical experiments. Thus, it does not specify hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not conduct empirical experiments. Thus, it does not specify software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not conduct empirical experiments. Thus, it does not specify details about experimental setup or hyperparameters. |