Bisection-Based Pricing for Repeated Contextual Auctions against Strategic Buyer
Authors: Anton Zhiyanov, Alexey Drutsa
ICML 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We introduce a novel deterministic learning algorithm that is based on ideas of the Bisection method and has strategic regret upper bound of O(log2 T). Unlike previous works, our algorithm does not require any assumption on the distribution of context information, and the regret guarantee holds for any realization of feature vectors (adversarial upper bound). To construct our algorithm we non-trivially adopted techniques of integral geometry to act against buyer strategicness and improved the penalization trick to work in contextual auctions. Theorem 1. Let A be Algorithm1 for a fixed time horizon T. Then the seller total regret SReg(T, A, θ , γ, x1:T , D) has an upper bound of O(d3 log2 2(d T) log2(γ) + d3 log2(d T) logγ(1 γ)) for all θ [0, 1]d, x1:T XT and all distributions D over the feature domain XT . |
| Researcher Affiliation | Collaboration | Anton Zhiyanov 1 2 Alexey Drutsa 1 2 1Yandex Research, Moscow, Russian Federation 2Faculty of Mechanics and Mathematics, Moscow State University im. Lomonosova, Moscow, Russian Federation. |
| Pseudocode | Yes | In Algorithm 1 we present the pseudo-code of our algorithm. |
| Open Source Code | No | The paper does not contain any statements about releasing source code or links to repositories for the described methodology. |
| Open Datasets | No | The paper focuses on theoretical analysis and algorithm design, not on empirical evaluation using datasets. No specific dataset is mentioned or made accessible. |
| Dataset Splits | No | As the paper is theoretical and does not report empirical experiments, there is no mention of dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for experiments. |
| Software Dependencies | No | The paper focuses on theoretical algorithm design and analysis, and therefore does not list any specific software dependencies with version numbers for implementation or experimentation. |
| Experiment Setup | No | As the paper presents a theoretical algorithm and its analysis rather than empirical experiments, it does not provide specific details about an experimental setup or hyperparameters. |