Profit Maximization in Bilateral Trade against a Smooth Adversary

Sintesi Tecnica: Massimizzazione del Profitto nel Commercio Bilaterale contro un Avversario Liscio

Enunciato del Problema
Il lavoro affronta il problema della massimizzazione del profitto nel commercio bilaterale all'interno di un framework di apprendimento online. In questo contesto, un intermediario media tra un venditore e un acquirente, ciascuno dei quali possiede una valutazione privata per un bene. L'intermediario deve progettare un meccanismo (composto da una regola di allocazione e funzioni di pagamento) per massimizzare il profitto atteso soddisfacendo la Compatibilità Incentivale a Strategia Dominante (DSIC) e la Razionalità Individuale Ex-Post (IR).

L'ambiente di apprendimento è definito da un avversario $\sigma$-liscio. A differenza del setting stocastico standard in cui le valutazioni sono estratte in modo i.i.d. da una distribuzione fissa, o del setting avversario standard in cui le valutazioni possono essere arbitrarie, l'avversario $\sigma$-liscio seleziona distribuzioni ad ogni passo temporale che sono vincolate a non essere "troppo piccate" (ovvero, la loro massa di probabilità su qualsiasi insieme di Borel è limitata dalla misura di Lebesgue dell'insieme divisa per $\sigma$).

La sfida principale risiede nella natura non parametrica dello spazio delle azioni. L'insieme dei meccanismi validi è infinito e complesso; un meccanismo è definito da una regione di allocazione monotona nel quadrato unitario $[0,1]^2$ e dai relativi pagamenti di Myerson. Ciò distingue il problema dalla letteratura standard sulla progettazione di meccanismi online, che spesso si concentra su setting parametrici (ad esempio, l'apprendimento di un unico prezzo di riserva). Lavori precedenti hanno stabilito che un rimpianto sublineare è impossibile nel setting avversario generale ma raggiungibile nel setting i.i.d. La questione aperta era se il "divario" tra questi due estremi potesse essere colmato dal modello dell'avversario liscio.

Metodologia
Gli autori propongono un algoritmo di apprendimento denominato HIER-MECH, che raggiunge un limite di rimpianto di $\tilde{O}(\frac{1}{\sigma}\sqrt{T})$. La metodologia si basa su tre componenti tecniche chiave:

1. Meccanismi a Griglia e Garanzie $L_1$-Net:
   Gli autori discretizzano lo spazio continuo dei meccanismi utilizzando meccanismi a griglia $\epsilon$, dove la regione di allocazione è un'unione di tasselli provenienti da una griglia uniforme con passo $\epsilon$. Crucialmente, dimostrano una nuova garanzia $L_1$-net (Lemma 2) specifica per questo problema. Mostrano che per qualsiasi meccanismo $M$, esiste un'approssimazione a griglia $\phi_\epsilon(M)$ tale che la differenza attesa nel profitto è limitata da $O(\epsilon/\sigma)$. Questo limite si basa sulla regolarità dell'avversario e sulla specifica struttura geometrica dei pagamenti nel commercio bilaterale (proiezioni sul confine dell'allocazione). A differenza di lavori precedenti che si affidavano a reti deterministiche $L_\infty$ (che non esistono per questa classe di ipotesi), questo limite probabilistico è sufficiente per l'analisi.

2. Catena Algoritmica (Algorithmic Chaining):
   Per superare le limitazioni degli approcci standard "Follow-the-Leader" o "Hedge" (che falliscono in setting non stazionari o producono tassi subottimali come $O(T^{2/3})$ se applicati direttamente alla griglia), gli autori impiegano la catena algoritmica.

   • Costruiscono un Albero dei Meccanismi in cui i nodi al livello $h$ rappresentano meccanismi a griglia $2^{-h}$.
   • L'algoritmo mantiene multiple istanze locali dell'algoritmo HEDGE (una per ogni nodo interno nell'albero).
   • Ad ogni passo temporale, l'algoritmo esegue una passeggiata casuale lungo l'albero, selezionando un meccanismo foglia basandosi sulle distribuzioni locali HEDGE.
   • Questa struttura gerarchica imita l'effetto della catena probabilistica (usata nei setting stocastici) all'interno di un contesto avversario. Permette all'algoritmo di raggiungere un limite di tipo "Dudley", migliorando il limite standard $\sqrt{T \log N}$ degli esperti dove $N$ è il numero di esperti.

3. Riduzione dagli Annunci Congiunti (Joint Ads):
   Il lavoro stabilisce una riduzione formale dal problema degli Annunci Congiunti (dove due agenti collaborano per acquistare un bene non escludibile) al commercio bilaterale. Limitando il dominio del commercio bilaterale a un sottorettangolo specifico e applicando una trasformazione delle coordinate, mappano il problema degli Annunci Congiunti al setting del commercio bilaterale. Questa riduzione serve a due scopi:

   • Trasferisce il limite superiore $\tilde{O}(\frac{1}{\sigma}\sqrt{T})$ al problema degli Annunci Congiunti, migliorando il precedente limite $O(T^{2/3})$.
   • Fornisce un limite inferiore di $\Omega(\sqrt{T})$ per il commercio bilaterale, dimostrando che il tasso dell'algoritmo HIER-MECH è stretto (a meno di fattori polilogaritmici).

Risultati Chiave

• Limite di Rimpianto: L'algoritmo HIER-MECH raggiunge un limite di rimpianto di $O(\frac{1}{\sigma}\sqrt{T} \log T)$ contro un avversario $\sigma$-liscio.
• Strettezza: Questo tasso corrisponde al tasso minimax per il caso stocastico i.i.d. ed è separato dal caso avversario generale (dove il rimpianto sublineare è impossibile). Il limite inferiore $\Omega(\sqrt{T})$ conferma che la dipendenza da $T$ è ottimale.
• Annunci Congiunti: La riduzione produce un limite di rimpianto stretto $\tilde{O}(\frac{1}{\sigma}\sqrt{T})$ per il problema degli Annunci Congiunti, risolvendo una questione aperta nella letteratura precedente.

Significato e Affermazioni
Il lavoro afferma di ampliare significativamente la gamma di contesti in cui sono raggiungibili tassi di apprendimento rapidi nella progettazione di meccanismi economici. Estendendo garanzie di rimpianto forti dal setting i.i.d. all'avversario $\sigma$-liscio, gli autori dimostrano che la regolarità è uno strumento efficace per superare i risultati di impossibilità avversaria nei problemi economici.

Il lavoro rappresenta la prima applicazione della catena algoritmica a un problema di progettazione di meccanismi non parametrico, andando oltre il suo uso tradizionale nella regressione online. Gli autori evidenziano che, sebbene sia raggiunto il tasso statistico ($\sqrt{T}$), permane un divario computazionale: il tempo di esecuzione di HIER-MECH scala come $\exp(\sqrt{T})$, mentre il setting i.i.d. ammette un algoritmo a tempo polinomiale. Chiudere questo divario computazionale e stringere la dipendenza dal parametro di regolarità $\sigma$ sono identificati come le principali questioni aperte.

In sintesi, il lavoro caratterizza i limiti informazionali dell'apprendimento nel commercio bilaterale contro un avversario liscio, mostrando che, da una prospettiva statistica, l'avversario liscio è "tanto facile quanto" il setting i.i.d., nonostante richieda tecniche algoritmiche fondamentalmente diverse.