📊 statistics

Do Not Trust The Auctioneer: Learning to Bid in Feedback-Manipulated Auctions

Dit artikel analyseert herhaalde eerste-prijsveilingen waarbij shilling feedback manipuleert in plaats van toewijzing, en stelt een hybride algoritme voor dat optimale $\tilde{\mathcal{O}}(\sqrt{T})$ regret bereikt door robuuste intervaleliminatie te combineren met optimistische debiasing, terwijl wordt aangetoond dat dergelijke uitsluitend op feedback gerichte manipulatie de statistische moeilijkheid van het leren van biedgedrag aanzienlijk verhoogt.

Oorspronkelijke auteurs: Luigi Foscari, Matilde Tullii, Vianney Perchet

Gepubliceerd 2026-05-22

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Luigi Foscari, Matilde Tullii, Vianney Perchet

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je probeert een zeldzame verzamelobject te kopen bij een online veiling. Je weet niet hoeveel andere mensen bereid zijn te betalen, dus je moet leren door te kijken wat er gebeurt wanneer je je biedingen plaatst.

Meestal, als je een veiling verliest, vertelt het platform je het hoogste bod dat je heeft verslagen. Dit helpt je te leren: "Oh, ik moet de volgende keer iets hoger bieden."

Maar in dit artikel stellen de auteurs een scenario voor waarin de veilingmeester een beetje listig is. Ze noemen dit "shilling".

De truc: De "nepconcurrent"

Stel je voor dat de veilingmeester een geheime vriend heeft die nepbiedingen plaatst om de concurrentie er feller uit te laten zien dan hij echt is.

Als je wint: Geweldig! Je krijgt het item en de nepvriend doet er niet toe.
Als je verliest: De veilingmeester vertelt je het hoogste bod inclusief de nepbieding.

Dus, als het echte hoogste bod 50 dollar was, maar de nepvriend bood 80 dollar, zegt de veilingmeester tegen je: "Je hebt verloren van 80 dollar!"

Het probleem: Je denkt misschien: "Wauw, iedereen biedt 80 dollar! Ik moet de volgende keer beter 85 dollar bieden!" Maar de echte concurrentie was slechts 50 dollar. Je wordt bedrogen om te veel te betalen.
De draai: Soms biedt de nepvriend heel laag (zeg maar 10 dollar). Als het echte bod 50 dollar was, vertelt de veilingmeester je nog steeds het maximum, namelijk 50 dollar. In dit geval krijg je de echte informatie.

Het artikel vraagt: Hoe kan een slimme bieder de echte prijzen leren wanneer de veilingmeester liegt over de verliesbiedingen, maar slechts soms?

De tweeledige strategie

De auteurs ontwierpen een "leeralgoritme" (een reeks regels voor een computer) dat werkt als een voorzichtige detective. Het gebruikt tegelijkertijd twee verschillende benaderingen, alsof het een veiligheidsnet en een supersnelle auto heeft.

1. Het veiligheidsnet (de "robuste" tak)

Dit deel van het algoritme zegt: "Ik vertrouw de rapporten van verliesbiedingen helemaal niet. Ik ga de nepnummers negeren."

Het kijkt alleen of het heeft gewonnen of verloren.
Het behandelt de veiling als een simpel "prijskaartje"-spel (zoals het kopen van een koffie waarbij je gewoon ziet of je het kunt betalen).
Resultaat: Dit is traag en veilig. Het garandeert dat je niet te veel geld verliest, maar je leert niet supersnel. Het is alsof je voorzichtig loopt in het donker.

2. De optimist (de "optimistische" tak)

Dit deel zegt: "Laten we proberen de nepnummers te gebruiken, maar laten we er slim mee omgaan."

Het kent het patroon van de nepbiedingen (bijvoorbeeld: "De nepvriend biedt meestal tussen de 10 en 20 dollar").
Wanneer het een verliesbieding ziet, doet het wat wiskunde om het nepgedeelte af te trekken en te raden wat het echte bod misschien was.
De valkuil: Dit werkt alleen goed als de nepbiedingen laag genoeg zijn om het echte bod door te laten gluren.
Resultaat: Wanneer de nepbiedingen laag en nuttig zijn, leert deze methode veel sneller dan het veiligheidsnet. Het is alsof je snel rijdt op een heldere weg.

3. Het "races"-mechanisme

Het algoritme weet van tevoren niet welke methode beter werkt. Dus, het voert beide tegelijkertijd uit in een "race".

Het controleert voortdurend: "Maakt de optimist zin? Is de data betrouwbaar?"
Als de nepbiedingen te hoog zijn en de optimist in de war raakt, schakelt het algoritme terug naar het veiligheidsnet.
Als de data er schoon uitziet, leunt het op de optimist om sneller te leren.

De grote ontdekking

Het artikel bewijst dat hoewel de veilingmeester de informatie manipuleert, de leerling nog steeds verrassend goed kan presteren.

Als de nepbiedingen altijd hoog zijn: De leerling zit vast aan de trage snelheid van het "veiligheidsnet".
Als de nepbiedingen soms laag zijn: De leerling kan de "optimist" gebruiken om te versnellen, waardoor hij veel sneller leert dan wanneer hij alleen maar zou gissen.

De auteurs bewezen ook een wiskundige limiet: je kunt niet oneindig snel leren. Er is een "snelheidslimiet" gebaseerd op hoe vaak de nepbiedingen per ongeluk de waarheid onthullen. Als de nepbiedingen zeer zeldzaam zijn (lage waarschijnlijkheid), word je gedwongen om traag te gaan. Als ze vaak voorkomen, kun je snel gaan.

In het kort

Dit artikel gaat over het leren bieden in een rigide spel waarbij de scheidsrechter liegt over de scores. De auteurs bouwden een strategie die de leugens negeert wanneer nodig, maar slim de waarheid gebruikt die verborgen zit in de leugens wanneer dat mogelijk is. Ze toonden aan dat zelfs met een leugenachtige scheidsrechter je toch efficiënt de marktprijzen kunt leren, mits je een manier hebt om te vertellen wanneer de scheidsrechter behulpzaam is versus wanneer ze je gewoon aan het gek maken zijn.

Technische Samenvatting: Leren Bieden in Feedback-gemanipuleerde Veilingen

Probleemstelling
Het artikel onderzoekt herhaalde eerste-prijsveilingen waarbij de veilinghouder (of verkoper) zich bezighoudt met "shilling"—het gebruik van kunstmatige biedingen om de feedback die een lerende bieder ontvangt, te manipuleren. In tegenstelling tot traditionele modellen waarin manipulatie de toewijzingsregel of betaling kan veranderen, richt dit werk zich op feedback-gemanipuleerde veilingen. Specifiek concurreert de leraar tegen een reële hoogste concurrerende bieding, $b_t$ , en wint als zijn bieding $p_t \geq b_t$ . Echter, bij het verliezen observeert de leraar niet de ware $b_t$ . In plaats daarvan observeert hij een shill-rapport $o_t = \max\{b_t, s_t\}$ , waarbij $s_t$ een onafhankelijke shill-bieding is getrokken uit een bekende verdeling $S$ .

Deze opzet creëert een unieke leers uitdaging: de toewijzing blijft waarheidsgetrouw (de leraar wint of verliest op basis van de realiteit), maar het informatiekanaal is vervormd. Hoge shill-biedingen maskeren de ware concurrentie, terwijl lage shill-biedingen "suffix-informatie" onthullen (informatie over biedingen die groter zijn dan de gespeelde bieding). Het doel is om de regret te minimaliseren ten opzichte van de beste vaste bieding voor de gerealiseerde waarde, $v_t$ , in aanwezigheid van deze gemaskeerde feedback.

Methodologie
De auteurs stellen een algoritme voor dat werkt in epochen over een gediscretiseerd rooster van prijzen en waarden. De kerninnovatie is een dubbel-takbenadering gecombineerd met een validatie- en raceprocedure:

Robuuste Tak (Intervaleliminatie): Deze tak negeert de shill-rapporten volledig en vertrouwt uitsluitend op de binaire winst/verlies-uitkomst. Ze behandelt het probleem als een dynamische prijsbepalingstaak met gecensureerde feedback. Deze tak garandeert een regret-snelheid van $\tilde{O}(T^{2/3})$ en fungeert als veiligheidsnet wanneer shilling ernstig is of de shill-verdeling niet informatief is.
Optimistische Tak (Gedebiasseerde Suffix-Learning): Deze tak probeert de shill-rapporten te benutten. Aangezien de shill-verdeling $F_S$ $F_{S}$ bekend is, construeert het algoritme een onbevooroordeelde schatter voor de ware verdeling van de concurrerende biedingen $F_B$ $F_{B}$ met behulp van de observatie $o_t$ $o_{t}$ .
- Het maakt gebruik van suffix-observaties: Wanneer $o_t \leq q$ , impliceert dit $b_t \leq q$ (als de shill laag genoeg was).
- Het hanteert een gewogen kleinste-kwadraten-kader om directe winst/verlies-metingen te combineren met deze suffix-verschilmetingen.
- Cruciaal introduceert het een geometrische onzekerheidsanalyse. Het algoritme schat niet alleen puntsgewijze waarden, maar construeert betrouwbaarheidsintervallen over intervallen van actieve biedingen, gebruikmakend van het feit dat een enkele laag-shill-gebeurtenis informatie onthult over een heel bereik van hogere biedingen.
Dyadische Validatie: Het algoritme gaat er niet van uit dat de schaal van de shill-verdeling (specifiek de waarschijnlijkheid $\gamma$ van een "laag-shill"-gebeurtenis die informatie onthult) bekend is. Het valideert optimistische updates tegen een set van dyadische kandidaten voor de shill-schaal. Als een optimistische kandidaat de validatie niet doorstaat (bijvoorbeeld omdat de shill-verdeling te onregelmatig is of de schaal te klein), keert het algoritme terug naar de robuuste tak.

Belangrijkste Bijdragen

Robuustheid met Veiligheidsnetten: Het artikel biedt een robuuste interval-eliminatieprocedure die de $\tilde{O}(T^{2/3})$ -snelheid voor dynamische prijsbepaling bereikt, zelfs wanneer shilling de feedback nutteloos maakt.
Optimistische Debiasing: Het ontwikkelt een optimistische procedure die gestructureerde informatie extrahert uit de "ruisachtige pad-achtige" signalen van shill-rapporten. Door suffix-observaties om te zetten in metingen van aangrenzende nutverschillen, bereikt het algoritme snellere snelheden wanneer de actieve biedingsregio's regelmatig en goed gedekt zijn.
Adaptiviteit: Het algoritme past zich aan het onbekende effectieve shill-niveau aan via een dyadisch validatieschema, waardoor de behoefte aan voorkennis van de shill-schaal of feedback-geometrie wordt weggenomen.
Strakke Ondergrenzen: De auteurs bewijzen een overeenkomstige ondergrens voor het geval van één actieve regio. Ze construeren een "verborgen cel"-instance waar een kleine nutstijging bestaat in een onbekend interval. Het bewijs toont aan dat de regret fundamenteel wordt beperkt door de afweging tussen lokaal zoeken (regime van dynamische prijsbepaling) en cross-learning via rapporten van de verliezende kant.

Resultaten
Het artikel stelt de volgende regret-grenzen vast (tot op logaritmische factoren):

Bovengrens: Het algoritme bereikt een regret van $\tilde{O}\left(\min\left\{T^{2/3}, \rho^{1/4}\sqrt{T}\gamma^{-1/4}\right\}\right)$ $\tilde{O} (min {T^{2/3}, ρ^{1/4} T γ^{- 1/4}})$ , waarbij $\rho$ $ρ$ het aantal actieve biedingsregio's is en $\gamma$ $γ$ de waarschijnlijkheid van informatieve laag-shill-gebeurtenissen.
- In het geval van één actieve regio ( $\rho=1$ ) is de grens $\tilde{O}\left(\min\left\{T^{2/3}, \sqrt{T}\gamma^{-1/4}\right\}\right)$ .
- Deze snelheid interpoleert tussen de $T^{2/3}$ -snelheid van dynamische prijsbepaling (wanneer shilling zwaar is, $\gamma \to 0$ ) en de $\sqrt{T}$ -snelheid van standaard eerste-prijsveilingen (wanneer shilling licht is, $\gamma$ is groot).
Ondergrens: Voor het geval van één actieve regio bewijst het artikel een ondergrens van $\Omega\left(\min\left\{T^{2/3}, \sqrt{T}\gamma^{-1/4}\right\}\right)$ . Dit bevestigt dat het algoritme minimax-optimaal is tot op logaritmische factoren. De constructie van de ondergrens benadrukt dat zelfs met kennis van de shill-verdeling de leraar de $\sqrt{T}$ -snelheid niet volledig kan herstellen als informatieve shill-gebeurtenissen zeldzaam zijn, aangezien de "verborgen cel" moeilijk snel te identificeren blijft.

Betekenis en Claims
Het artikel beweert dat zelfs enkel feedback-shilling (waarbij de toewijzingsregel onaangetast blijft) de statistische moeilijkheid van herhaald bieden scherp kan veranderen. De manipulatie werkt via het informatiekanaal, wat de leraar bevooroordeelt richting hogere biedingen en de cross-learning-structuur gedeeltelijk vernietigt die typisch zorgt voor $\sqrt{T}$ -regret in eerste-prijsveilingen.

De auteurs positioneren dit werk als een eerste stap naar een theorie van feedback-manipulatie in veilingen. Ze stellen expliciet dat het uitbreiden van deze resultaten naar onbekende shill-verdelingen, rijkere shilling-modellen (bijvoorbeeld afhankelijk van de bieding van de leraar) en meer algemene geometrieën van actieve regio's een open vraag blijft. De betekenis ligt in het aantonen dat zorgvuldig benutten van de structuur van gemanipuleerde feedback veel meer kan opleveren dan een puur robuuste aanpak, mits de manipulatie specifieke structurele beperkingen volgt (zoals max-shilling met bekende verdeling).