Online Price Competition under Generalized Linear Demands

Technische Samenvatting: Online Prijsconcurrentie onder Gegeneraliseerde Lineaire Vraag

Probleemformulering
Het artikel behandelt het probleem van sequentiële prijsconcurrentie tussen $N$ verkopers die opereren over een eindige tijdshorizon $T$. In tegenstelling tot traditionele monopolistische settings of eerdere competitieve modellen die uitgaan van lineaire vraag, beschouwt dit werk een gegeneraliseerd lineair (single-index) vraagkader. Voor elke verkoper $i$ wordt de verwachte vraag gemodelleerd als:
$$\lambda_i(p) = \mu_i(\langle \theta_{i,0}, p \rangle) = \mu_i(-\beta_{i,0}p_i + \langle \gamma_{i,0}, p_{-i} \rangle)$$
waarbij:

• $p$ de vector van prijzen is die alle verkopers simultaan vaststellen.
• $\mu_i$ een bekende, strikt toenemende link-functie is (bijv. de logistieke functie voor binaire uitkomsten, of de identiteitsfunctie voor lineaire uitkomsten).
• $\theta_{i,0}$ een onbekende parametervector is die de eigen prijsgevoeligheid van de verkoper ($-\beta_{i,0}$) en de prijsgevoeligheden van concurrenten ($\gamma_{i,0}$) bevat.
• De waarnemingen van de vraag $y_i(t)$ volgen een canonieke exponentiële familie-distributie, geconditioneerd op de prijzen.

Informatiestructuur en Beperkingen
De setting wordt gekenmerkt door een specifieke informatie-asymmetrie die verschilt van standaard Multi-Agent Reinforcement Learning (MARL):

1. Partiële Observabiliteit: Elke verkoper observeert alleen de eigen gerealiseerde vraag (of omzet) en de prijzen die door rivalen zijn ingesteld. Zij observeren niet de gerealiseerde vraag of omzet van concurrenten.
2. Simultane Bewegingen: Verkopers kiezen hun prijzen simultaan. Hierdoor observeert een verkoper de context (de prijzen van rivalen $p_{-i}$) pas nadat de eigen actie $p_i$ is gekozen, wat een tijdsasymmetrie creëert die de standaard contextuele bandit-analyses (waarbij de context vóór de actie-selectie wordt waargenomen) uitsluit.
3. Geen Coördinatie: Het beleid moet volledig gedecentraliseerd zijn; verkopers kunnen de exploratiefases niet coördineren.

Methodologie: PML-GLUCB
De auteurs stellen PML-GLUCB voor (Penalized Maximum Likelihood Generalized Linear Upper Confidence Bound), een gedecentraliseerd algoritme dat de noodzaak voor een voorafgaande, gecoördineerde exploratiefase elimineert. De methode werkt als volgt:

1. Penalized Maximum Likelihood Estimation (PMLE): In elke ronde $t$ werkt verkoper $i$ de schatting van $\theta_{i,0}$ bij door een gepenaliseerde log-likelihood functie te maximaliseren op basis van historische data $(p(s), y_i(s))_{s < t}$. Om te garanderen dat de estimator binnen de begrensde parameterruimte $\Theta_i$ blijft, wordt een projectiestap toegepast indien de ruwe PMLE de normgrens overschrijdt.
2. Optimistische Prijsstelling (UCB): In plaats van een pure "explore-then-commit" strategie, gebruikt het algoritme een Upper Confidence Bound (UCB) benadering. De verkoper construeert een optimistische schatting van de omzettingsfunctie door een confidence bonus toe te voegen aan de geschatte omzet. De bonus wordt afgeleid van een concentratie-ongelijkheid die is afgestemd op het generalized linear model, gebruikmakend van een elliptische potentiaal-bound die is aangepast voor simultane bewegingen.
3. Best-Response Update: De verkoper selecteert de prijs $p_i(t)$ die deze optimistische omzettingsfunctie maximaliseert, gegeven de geobserveerde prijzen van concurrenten uit de vorige ronde (of de huidige ronde, afhankelijk van de specifieke update-timing in het algoritme, hoewel de tekst benadrukt dat $p_{-i}$ na het kiezen van $p_i$ wordt waargenomen in de algemene setting, gebruikt het algoritme $p(t-1)_{-i}$ voor de beslissing bij $t$).

Belangrijkste Bijdragen

1. Front-Loaded Exploration-Free Learning: Het artikel introduceert een beleid dat gelijktijdig leert en optimaliseert zonder dat een expliciete initiële fase van i.i.d. willekeurige prijsstelling vereist is. Dit adresseert praktische beperkingen waarbij "experimenteren met prijzen" vaak onhaalbaar is en vermijdt de afhankelijkheid van onbekende, probleem-specifieke constanten die nodig zijn om de lengte van de exploratie te bepalen in eerdere werken.
2. Generalisatie van Vraagdocumenten: Het framework generaliseert bestaande lineaire vraagmodellen strikt door een brede klasse van niet-lineaire, monotone single-index modellen op te nemen. Het verenigt de analyse van zowel binaire vraag (aankoop/geen aankoop) als continue vraag-observaties onder één enkele theoretische paraplu.
3. Nieuwe Concentratie-instrumenten: Vanwege de simultane aard van het spel kunnen standaard elliptische potentiaal-lemma's (die uitgaan van een exogene context) niet direct worden toegepast. De auteurs hebben een nieuwe elliptisch-type bound (Lemma C.2) afgeleid die geschikt is voor settings waar de context (de prijzen van concurrenten) endogeen is en met een vertraging wordt waargenomen ten opzichte van de actie.

Resultaten

• Regret Bound: Ten opzichte van een dynamische benchmark (de best-response op de sequentie van rivalen's prijzen in hindsight), bereikt elke verkoper een regret bound van:
  $$\text{Reg}_i(T) = \tilde{O}(N^2 \sqrt{T})$$
  Dit komt overeen met de optimale $\tilde{O}(\sqrt{T})$ rate die bekend is voor lineaire prijsconcurrentie, met uitzondering van de logaritmische factoren en de afhankelijkheid van het aantal verkopers $N$.
• Convergentie naar Evenwicht: Het algoritme zorgt ervoor dat de gemiddelde kwadratische afwijking van de prijsvector van de Nash-evenwicht (NE) prijsvector $p^*$ afneemt als:
  $$\frac{1}{T} \sum_{t=1}^T \mathbb{E}[\|p(t) - p^*\|_2^2] = \tilde{O}\left(\frac{N^2}{\sqrt{T}}\right)$$
  Dit geeft aan dat regret-optimale actie het marktevenwicht gemiddeld dicht bij het Nash-evenwicht houdt.
• Computationele Complexiteit: Het algoritme is computationeel tractabel, met een per-ronde complexiteit van $O(N^2)$ per verkoper (gedomineerd door matrix-updates en vectorproducten), wat schaalbaar is voor een matig aantal $N$.

Betekenis en Claims
Het artikel claimt dat PML-GLUCB order-optimaal (minimax optimaal tot aan de logaritmische factoren) is in de generalized linear setting. Door de vereiste voor gecoördineerde exploratie te verwijderen, sluit de methode beter aan bij realistische marktomstandigheden waar bedrijven onafhankelijk handelen en niet kunnen vooraf afspreken over exploratieschema's. Het werk overbrugt de kloof tussen theoretisch vraag-leren en praktische implementatie in competitieve omgevingen met niet-lineaire vraagstructuren.

De auteurs merken op dat hoewel de $\sqrt{T}$ afhankelijkheid optimaal is, de $N^2$ afhankelijkheid van het aantal verkopers een open vraag blijft met betrekking tot de nauwkeurigheid (tightness). Bovendien erkent het artikel dat hoewel de gemiddelde afwijking van het evenwicht wordt gecontroleerd, puntwijze convergentie van de prijssequentie naar het NE niet gegarandeerd is zonder een initiële i.i.d. exploratiefase, wat consistent is met de bredere literatuur over adaptieve bandit-algoritmen.