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].
Regret Analysis of Bilateral Trade with a Smoothed Adversary
Authors: Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, Stefano Leonardi
JMLR 2024 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study repeated bilateral trade where an adaptive σ-smooth adversary generates the valuations of sellers and buyers. We completely characterize the regret regimes for fixed-price mechanisms under different feedback models in the two cases where the learner can post the same or different prices to buyers and sellers. We begin by showing that, in the full-feedback scenario, the minimax regret after T rounds is of order T. Under partial feedback, any algorithm that has to post the same price to buyers and sellers suffers worst-case linear regret. However, when the learner can post two different prices at each round, we design an algorithm enjoying regret of order T 3/4, ignoring log factors. We prove that this rate is optimal by presenting a surprising T 3/4 lower bound, which is the paper s main technical contribution. |
| Researcher Affiliation | Academia | Nicolò Cesa-Bianchi EMAIL Università degli Studi di Milano and Politecnico di Milano, Milan, Italy Tommaso Cesari EMAIL University of Ottawa, Ottawa, Canada Roberto Colomboni EMAIL Università degli Studi di Milano and Politecnico di Milano, Milan, Italy Federico Fusco EMAIL Sapienza Università di Roma, Rome, Italy Stefano Leonardi EMAIL Sapienza Università di Roma, Rome, Italy |
| Pseudocode | Yes | Learning algorithm with full feedback: Continuous-Price Hedge Input: Learning rate η (0, 1) Initialization: Initialize W1(x) = 1, for all x [0, 1] for time t = 1, 2, . . . do Let µt be a distribution with pdf defined by ft(x) = Wt(x) Wt 1 , for all x [0, 1] Post price pt drawn according to distribution µt Update Wt+1(x) = Wt(x) exp η GFTt(x) , for each x [0, 1] |
| Open Source Code | No | The paper does not provide any links to source code or statements about code availability. |
| Open Datasets | No | We study repeated bilateral trade where an adaptive σ-smooth adversary generates the valuations of sellers and buyers. |
| Dataset Splits | No | The paper describes theoretical models and algorithms without conducting empirical experiments on real-world datasets, hence dataset splits are not applicable. |
| Hardware Specification | No | This paper is theoretical in nature, presenting algorithms and proofs without empirical evaluation, thus no hardware specifications are provided. |
| Software Dependencies | No | The paper describes theoretical algorithms and proofs, and does not mention any specific software dependencies or version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and regret analysis, thus it does not include details on experimental setup or hyperparameter values. |