Online Price Competition under Generalized Linear Demands

Sintesi Tecnica: Competizione sui Prezzi Online sotto Domande Lineari Generalizzate

Formulazione del Problema
Il documento affronta il problema della competizione sequenziale sui prezzi tra $N$ venditori che operano su un orizzonte temporale finito $T$. A differenza dei modelli monopolistici tradizionali o dei modelli competitivi precedenti che assumono una domanda lineare, questo lavoro considera un framework di domanda lineare generalizzata (single-index). Per ogni venditore $i$, la domanda attesa è modellata come:
$$\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)$$
dove:

• $p$ è il vettore dei prezzi stabiliti da tutti i venditori simultaneamente.
• $\mu_i$ è una funzione di link nota, strettamente crescente (ad esempio, logistica per esiti binari, identità per modelli lineari).
• $\theta_{i,0}$ è un vettore di parametri sconosciuti che contiene la sensibilità del venditore rispetto al proprio prezzo ($-\beta_{i,0}$) e la sensibilità rispetto ai prezzi dei concorrenti ($\gamma_{i,0}$).
• Le osservazioni della domanda $y_i(t)$ seguono una distribuzione di famiglia esponenziale canonica condizionata dai prezzi.

Struttura dell'Informazione e Vincoli
L'ambiente è caratterizzato da una specifica asimmetria informativa distinta dal classico Multi-Agent Reinforcement Learning (MARL):

1. Osservabilità Parziale: Ogni venditore osserva solo la propria domanda realizzata (o il proprio ricavo) e i prezzi stabiliti dai rivali. Non osserva invece le domande o i ricavi realizzati dai concorrenti.
2. Mosse Simultanee: I venditori scelgono i prezzi simultaneamente. Di conseguenza, un venditore osserva il contesto (i prezzi dei rivali $p_{-i}$) solo dopo aver scelto la propria azione $p_i$, creando un'asimmetria temporale che preclude le analisi standard dei contextual bandit in cui il contesto viene osservato prima della selezione dell'azione.
3. Assenza di Coordinamento: La policy deve essere completamente decentralizzata; i venditori non possono coordinare le fasi di esplorazione.

Metodologia: PML-GLUCB
Gli autori propongono PML-GLUCB (Penalized Maximum Likelihood Generalized Linear Upper Confidence Bound), un algoritmo decentralizzato che elimina la necessità di una fase di esplorazione coordinata e front-loaded. Il metodo opera come segue:

1. Stima della Massima Verosimiglianza Penalizzata (PMLE): In ogni round $t$, il venditore $i$ aggiorna la propria stima di $\theta_{i,0}$ massimizzando una funzione di log-verosimiglianza penalizzata basata sui dati storici $(p(s), y_i(s))_{s < t}$. Per garantire che lo stimatore rimanga all'interno dello spazio dei parametri limitato $\Theta_i$, viene applicato un passaggio di proiezione qualora il PMLE grezzo ecceda il limite della norma.
2. Pricing Ottimistico (UCB): Invece di una strategia pura di tipo "explore-then-commit", l'algoritmo impiega un approccio Upper Confidence Bound (UCB). Il venditore costruisce una stima ottimistica della funzione di ricavo aggiungendo un bonus di confidenza alla stima del ricavo. Il bonus è derivato da una disuguaglianza di concentrazione su misura per il modello lineare generalizzato, utilizzando un limite di potenziale ellittico adattato per mosse simultanee.
3. Aggiornamento della Best-Response: Il venditore seleziona il prezzo $p_i(t)$ che massimizza questa funzione di ricavo ottimistica, dato il prezzo dei competitor del round precedente (o del round corrente, a seconda del timing specifico di aggiornamento nell'algoritmo, sebbene il testo enfatizzi l'osservazione di $p_{-i}$ dopo la scelta di $p_i$ nel setting generale; l'algoritmo utilizza $p(t-1)_{-i}$ per la decisione al tempo $t$).

Contributi Chiave

1. Apprendimento Senza Esplorazione Front-Loaded: Il documento introduce una policy che apprende e ottimizza simultaneamente senza richiedere una fase iniziale esplicita di pricing casuale i.i.d. Questo affronta le limitazioni pratiche dove l'"esperimento con i prezzi" è spesso impraticabile e evita la dipendenza da costanti ignote specifiche del problema necessarie per determinare la lunghezza dell'esplorazione in lavori precedenti.
2. Generalizzazione dei Modelli di Domanda: Il framework generalizza rigorosamente i modelli di domanda lineare esistenti per includere una vasta classe di modelli single-index non lineari e monotoni. Unifica l'analisi sia della domanda binaria (acquisto/non acquisto) che delle osservazioni di domanda continua sotto un unico ombrello teorico.
3. Nuovi Strumenti di Concentrazione: A causa della natura a mosse simultanee del gioco, i classici lemmi del potenziale ellittico (che assumono un contesto esogeno) non possono essere applicati direttamente. Gli autori derivano un nuovo limite di tipo ellittico (Lemma C.2) adatto a contesti in cui il contesto (i prezzi dei rivali) è endogeno e osservato con un ritardo rispetto all'azione.

Risultati

• Regret Bound: Rispetto a un benchmark dinamico (la migliore risposta alla sequenza dei prezzi dei rivali nel passato), ogni venditore ottiene un limite di regret di:
  $$\text{Reg}_i(T) = \tilde{O}(N^2 \sqrt{T})$$
  Questo eguaglia il tasso ottimale $\tilde{O}(\sqrt{T})$ noto per la competizione sui prezzi lineare, salvo fattori logaritmici e una dipendenza dal numero di venditori $N$.
• Convergenza all'Equilibrio: L'algoritmo assicura che la deviazione quadratica media del vettore dei prezzi dal vettore di prezzo dell'Equilibrio di Nash (NE) $p^*$ decada come:
  $$\frac{1}{T} \sum_{t=1}^T \mathbb{E}[\|p(t) - p^*\|_2^2] = \tilde{O}\left(\frac{N^2}{\sqrt{T}}\right)$$
  Ciò indica che il gioco con regret-ottimale mantiene il mercato vicino all'equilibrio di Nash in media.
• Complessità Computazionale: L'algoritmo è computazionalmente trattabile, con una complessità per round di $O(N^2)$ per venditore (dominata da aggiornamenti di matrici e prodotti vettoriali), rendendolo scalabile per un $N$ moderato.

Significato e Rivendicazioni
Il documento sostiene che PML-GLUCB è order-optimal (ottimale in termini di minimax, salvo fattori logaritmici) nel setting lineare generalizzato. Rimuovendo il requisito di un'esplorazione coordinata, il metodo si allinea più da vicino alle condizioni reali di mercato dove le imprese agiscono indipendentemente e non possono pre-impegnarsi in programmi di esplorazione. Il lavoro colma il divario tra l'apprendimento della domanda teorica e l'implementazione pratica in ambienti competitivi con strutture di domanda non lineari.

Gli autori osservano che, sebbene la dipendenza $\sqrt{T}$ sia ottimale, la dipendenza $N^2$ dal numero di venditori rimane una questione aperta riguardo alla sua precisione (tightness). Inoltre, il documento riconosce che, mentre la deviazione media dall'equilibrio è controllata, la convergenza puntuale della sequenza dei prezzi verso l'NE non è garantita senza una fase iniziale di esplorazione i.i.d., in linea con la letteratura più ampia sugli algoritmi bandit adattivi.