Low-Regret Algorithms for Strategic Buyers with Unknown Valuations in Repeated Posted-Price Auctions

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Samenvatting

We study repeated posted-price auctions where a single seller repeatedly interacts with a single buyer for a number of rounds. In previous works, it is common to consider that the buyer knows his own valuation with certainty. However, in many practical situations, the buyer may have a stochastic valuation. In this paper, we study repeated posted-price auctions from the perspective of a utility maximizing buyer who does not know the probability distribution of his valuation and only observes a sample from the valuation distribution after he purchases the item. We first consider non-strategic buyers and derive algorithms with sub-linear regret bounds that hold irrespective of the observed prices offered by the seller. These algorithms are then adapted into algorithms with similar guarantees for strategic buyers. We provide a theoretical analysis of our proposed algorithms and support our findings with numerical experiments. Our experiments show that, if the seller uses a low-regret algorithm for selecting the price, then strategic buyers can obtain much higher utilities compared to non-strategic buyers. Only when the prices of the seller are not related to the choices of the buyer, it is not beneficial to be strategic, but strategic buyers can still attain utilities of about 75% of the utility of non-strategic buyers.

Originele taal-2Engels
TitelMachine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2020, Proceedings
RedacteurenFrank Hutter, Kristian Kersting, Jefrey Lijffijt, Isabel Valera
UitgeverijSpringer Science and Business Media Deutschland GmbH
Pagina's416-436
Aantal pagina's21
ISBN van geprinte versie9783030676605
DOI's
StatusGepubliceerd - 2021
EvenementEuropean Conference on Machine Learning and Knowledge Discovery in Databases, ECML PKDD 2020 - Virtual, Online
Duur: 14 sep 202018 sep 2020

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12458 LNAI
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

CongresEuropean Conference on Machine Learning and Knowledge Discovery in Databases, ECML PKDD 2020
StadVirtual, Online
Periode14/09/2018/09/20

Vingerafdruk Duik in de onderzoeksthema's van 'Low-Regret Algorithms for Strategic Buyers with Unknown Valuations in Repeated Posted-Price Auctions'. Samen vormen ze een unieke vingerafdruk.

Citeer dit