Meccanismi e aste

Quando scrivi le regole di un’asta, stai facendo ingegneria inversa della razionalità: vuoi che la mossa egoistica di ogni partecipante coincida con la mossa che a te conviene. È più difficile di quanto sembri, ed è la matematica nascosta dietro ogni marketplace agentico.

Perché questo capitolo

Ogni piattaforma che alloca risorse scarse tra agenti che hanno preferenze private è, formalmente, un’asta. Google AdWords è un’asta, miliardi di volte al giorno. Lo spettro radio della FCC è un’asta da decine di miliardi di dollari. Una coda di task in un cluster Kubernetes che assegna GPU a job con priorità è un’asta. Un marketplace MCP che indirizza la richiesta di un client verso il tool fornitore più adatto, scegliendo tra provider che competono su costo e qualità, è un’asta. Un sistema federato di ospedali che paga ciascun partecipante per i dati conferiti è un’asta inversa.

Non capire la teoria delle aste significa progettare questi sistemi cieco. Si finisce per scegliere le regole “intuitive” — chi offre di più paga quanto offre, semplice — e si scopre dopo mesi che gli agenti non riportano valori veri, che il revenue è una frazione di quello possibile, che pochi attori dominanti gaming il sistema. La maggior parte dei marketplace agentici che falliscono nel 2026 fallisce non per ragioni tecniche ma per mechanism design sbagliato.

Il capitolo fa tre cose. Primo: introduce i quattro formati classici (english, dutch, first-price, second-price) e mostra perché la second-price di Vickrey è uno dei pochi miracoli di questa disciplina — un meccanismo dove dire la verità conviene sempre, dimostrabile in tre righe. Secondo: generalizza alla famiglia VCG (Vickrey-Clarke-Groves) e al teorema di revenue equivalence di Myerson, due risultati che insieme spiegano perché le aste reali prendono certe forme e non altre. Terzo: connette ad applicazioni AI/agent — ad auctions con bidder RL, marketplace di tool MCP, allocazione di compute, incentive in federated learning — segnalando dove la teoria si rompe e cosa serve oltre ad essa.

I sei capitoli precedenti — giochi-definizione, somma-zero-non-zero, equilibrio-nash, minimax, giochi-cooperativi, dilemma-prigioniero — hanno descritto giochi dati: regole fisse, si studia come giocare. Qui si inverte: le regole sono l’incognita. È reverse game theory, ed è il sotto-campo della teoria dei giochi che ha il maggior numero di Nobel pro-capite (Vickrey 1996; Hurwicz, Maskin, Myerson 2007; Roth, Shapley 2012; Milgrom, Wilson 2020).

Contesto

Una manciata di nomi e date orientano l’intero campo.

• William Vickrey (economista canadese-americano, Columbia University, premio Nobel 1996): nel 1961 pubblica Counterspeculation, Auctions, and Competitive Sealed Tenders sul Journal of Finance. Vi descrive la second-price sealed-bid auction e dimostra che il bidding truthful è dominant strategy. Viene poi chiamata “Vickrey auction” in suo onore.
• Edward Clarke (economista americano): nel 1971 con Multipart Pricing of Public Goods (Public Choice) generalizza l’idea ai beni pubblici: ogni agente paga il danno che impone agli altri.
• Theodore Groves (economista americano, UCSD): nel 1973 con Incentives in Teams (Econometrica) descrive una famiglia generale di meccanismi truthful per allocazioni efficienti con utilità quasi-lineari. Insieme: il meccanismo VCG.
• Roger Myerson (economista americano, premio Nobel 2007 con Hurwicz e Maskin): nel 1981 con Optimal Auction Design (Mathematics of Operations Research) introduce il teorema di revenue equivalence e la teoria della optimal auction. Il framework delle virtual valuations è alla base di praticamente ogni discussione moderna su aste.
• Allan Gibbard (filosofo americano) e Mark Satterthwaite (economista americano): nel 1973-75 dimostrano indipendentemente il teorema di Gibbard-Satterthwaite, un risultato negativo che mostra perché la moneta è essenziale al mechanism design pratico.
• Benjamin Edelman, Michael Ostrovsky, Michael Schwarz: nel 2007 sull’American Economic Review analizzano la generalized second-price auction usata da Google AdWords. Mostrano che NON è truthful, ma ha un equilibrio ragionevole.
• Noam Nisan (informatico israeliano, Hebrew University) e Amir Ronen: nel 1999 con Algorithmic Mechanism Design (STOC ‘99) fondano l’incrocio tra computer science e mechanism design, dove la complessità computazionale dell’allocazione conta quanto le proprietà di incentivo.

Decoder dei termini di base che useremo:

• Asta (auction): protocollo per allocare un bene in cui i partecipanti dichiarano (in vario modo) quanto sono disposti a pagare.
• Meccanismo (mechanism): generalizzazione, anche multi-bene, anche non monetario; una funzione che da dichiarazioni produce un’allocazione e un vettore di pagamenti.
• Mechanism design: progettare il meccanismo affinché esiti desiderabili (efficienza, revenue, fairness) emergano dal comportamento egoistico.
• Truthful / incentive-compatible / strategy-proof / DSIC (dominant-strategy incentive-compatible): un meccanismo è truthful se per ogni agente, dichiarare il vero valore è una strategia dominante (sempre la migliore, qualunque cosa facciano gli altri).
• Individual rationality (IR): nessun agente ottiene utility negativa partecipando.
• Budget balance: il meccanismo non ha bisogno di sussidi esterni e non genera surplus arbitrario.
• Welfare (social welfare): somma delle utilità degli agenti. Un meccanismo è efficiente se massimizza il welfare.
• Revenue: pagamenti totali raccolti dal venditore.

Cross-reference verso il resto della Parte V: useremo l’idea di equilibrio di equilibrio-nash (per analizzare aste non-truthful come la first-price), il framework di Bayesian belief sui valori altrui da bayes-base (in preparazione), e il valore di Shapley di giochi-cooperativi verrà richiamato per data valuation.

Storicamente le aste sono molto più antiche della loro teoria. Le aste schiavili a Babilonia sono attestate dal 500 a.C. circa (resoconti di Erodoto). L’asta inglese ascendente si sviluppa nei mercati medievali europei. La formalizzazione matematica arriva tardi: la prima trattazione moderna è in Theory of Games and Economic Behavior di von Neumann e Morgenstern (1944), ma il vero salto è il paper di Vickrey nel 1961 sul Journal of Finance. Per quasi vent’anni il paper di Vickrey resta una curiosità accademica; si comincia a usare seriamente solo dopo che Myerson nel 1981 mostra che la second-price è un caso particolare di una teoria molto più generale e che molte aste reali sono equivalenti a essa in espettazione. La FCC adotta aste basate su questa teoria nel 1994, e il campo esplode da lì: spectrum auctions, online ad auctions, market design come disciplina (Roth, Milgrom, Wilson, tutti Nobel successivi).

Per gli scopi di questo capitolo, il punto chiave è che il mechanism design moderno nasce all’incrocio tra economia matematica e computer science. Quando Nisan e Ronen pubblicano Algorithmic Mechanism Design nel 1999, il loro contributo è ridefinire le proprietà desiderabili di un meccanismo includendo la complessità computazionale: non basta che sia truthful, deve essere calcolabile in tempo polinomiale. Questa prospettiva è quella rilevante per agent platforms moderne, dove il bottleneck non è quasi mai la teoria del meccanismo ma l’efficienza dell’implementazione e la robustezza a comportamenti avversariali fuori-modello.

L’intuizione

Angolo 1: l’asta come oracolo

Pensa a una venditrice che vuole vendere un quadro raro. Non sa quanto i potenziali compratori siano disposti a pagare. Sa solo che i tre offerenti hanno valutazioni private — un numero in testa che lei non vede. Ha due problemi simultanei: trovare a chi vendere (idealmente a chi lo apprezza di più) e a quanto vendere (idealmente al prezzo più alto possibile).

Un’asta è un oracolo per estrarre informazione privata sotto incentivo. Le regole dell’asta sono il contratto: “se mi dichiari il tuo valore, io ti garantisco questo allocazione e questo pagamento”. Il problema è che gli agenti sono strategici: un’agente sa che la regola dipende da quello che dichiara, e quindi la sua dichiarazione non è il valore vero ma il best response alla regola.

Vickrey scopre nel 1961 una regola con una proprietà magica: per ogni configurazione delle regole con cui ti puoi confrontare, dichiarare la verità è la mossa migliore — qualunque cosa facciano gli altri. La venditrice ottiene così l’informazione di chi-vale-di-più senza dover indovinare distribuzioni a priori, senza dover fare assunzioni su come gli agenti si comporteranno tra loro. È un raro caso di prior-free truthfulness: niente Bayes, solo dominanza.

Il prezzo (letteralmente) di questa magia è che la venditrice non incassa il primo bid ma il secondo. Ha estratto chi-vale-di-più ma non ha estratto quanto valesse. Il teorema di revenue equivalence di Myerson ci dirà che, in espettazione, non poteva fare meglio comunque (sotto certe ipotesi).

Angolo 2: scrivere le regole del gioco

Cambia prospettiva. Sei il progettista del marketplace. Hai N venditori che competono per un cliente. Vuoi che il cliente paghi un prezzo equo, che i venditori non possano gaming i metadati, che tutto chiuda in 50ms. Il mechanism design ti dice: scegli prima la regola di allocazione (chi vince) e la regola di pagamento (chi paga quanto), poi verifica che siano compatibili con la truthfulness.

C’è una sorta di teorema di Ackermann nascosto qui: data una regola di allocazione monotona (chi alza il bid non perde mai), esiste al più una regola di pagamento che la rende truthful (Myerson 1981). E c’è una formula esplicita per quel pagamento. Una volta decisa l’allocazione, il pagamento è obbligato — non hai libertà di design.

Per ANALOGIA: il mechanism design è come scrivere una costituzione per un gioco. La forza non viene dal bandire i comportamenti opportunistici (sarebbe inforceable) ma dal renderli irrazionali. La venditrice non dice “non barare”, dice “barare ti danneggia, qualunque cosa faccia chiunque altro”. È enforcement by incentive.

Estendendo all’agent coding: quando progetti un protocollo MCP per agent-to-agent (in preparazione), non chiederti “come faccio a fidarmi di un tool provider esterno?”. Chiediti: “quale regola di allocazione + pagamento rende non conveniente al provider mentire?”. È mechanism design, e ha una matematica formale dietro.

Angolo 3: l’esternalità come tassa

Una terza lente sul VCG. Immagina di entrare in una stanza dove c’è una torta da 10 euro che gli altri si stavano per spartire. Tu hai una valutazione personale per la torta, mettiamo 7. Il banditore dice: “ti do la torta se ti piace di più che agli altri”. Ma quanto paghi? Non 7 (sarebbe first-price, ti incentiva a mentire), né il bid del successivo (sarebbe Vickrey su singolo oggetto, ma qui c’è di più). Paghi esattamente quanto la tua presenza ha tolto agli altri: se senza di te si sarebbero spartiti la torta da 10, e con te ne ricevono 4 (perché tu prendi una fetta da 6), tu paghi 10 − 4 = 6.

Per ANALOGIA sociologica: il VCG fa pagare ad ogni vincitore non quanto valuta il bene, ma quanto la sua vittoria danneggia il collettivo. È una tassa di Pigou interna al meccanismo. Chi non sposta nulla non paga nulla. Chi sposta tanto, paga tanto. Questa è la lettura “etica” che rende VCG popolare in mechanism design: chi vince paga il prezzo del proprio impatto sul resto del gruppo. EQUIVALENZA argomentabile, non analogia: la formula Clarke è letteralmente la perdita di welfare degli altri causata dalla presenza dell’agente.

La meccanica

I quattro formati classici

Un singolo bene da vendere, n bidder con valutazioni private v_1, …, v_n. Quattro formati canonici:

English (ascending) auction. Il banditore alza progressivamente il prezzo. Ogni bidder resta finché il prezzo è sotto la sua valutazione, poi si ritira. L’ultimo rimasto vince e paga il prezzo a cui il penultimo si è ritirato. Risultato in pratica: vince chi vale di più, paga circa la seconda valutazione più alta.

Dutch (descending) auction. Il prezzo parte alto e scende a velocità costante (in olanda, un orologio analogico). Il primo che preme il pulsante vince e paga il prezzo corrente. Storicamente usata al mercato dei fiori di Aalsmeer.

First-price sealed-bid (FPSB). Ogni bidder mette il proprio bid in busta chiusa. Vince il più alto, paga il proprio bid. Strategia: dichiarare meno della propria valutazione (bid shading). All’equilibrio Bayesian-Nash con n bidder iid uniformi su [0, V]: b(v) = v · (n−1)/n.

Second-price sealed-bid (Vickrey). Bid in busta chiusa, vince il più alto, paga il secondo bid più alto. Strategia dominante: b_i = v_i.

EQUIVALENZE strategiche (con prova in Krishna 2009, Cap. 2-3):

• Dutch e FPSB sono strategicamente equivalenti: in entrambi devi committere a un bid senza vedere quello degli altri.
• English e Vickrey sono “outcome-equivalent” sotto independent private values: in entrambi vince chi vale di più e paga circa la seconda valutazione.

TEOREMA: la truthfulness di Vickrey

CLAIM. Nella second-price sealed-bid auction con valutazioni private, dichiarare b_i = v_i è strategia dominante per ogni agente i, qualunque cosa facciano gli altri.

PROVA. Fissa un agente i. Sia M = max_{j != i} b_j (massimo dei bid degli altri). L’esito di i dipende solo da M, non dalla distribuzione: o i vince (se b_i > M) e paga M, oppure i perde e paga 0.

Caso 1 — v_i > M. Bidando b_i = v_i: vince, paga M, utility v_i − M > 0. Bidando b’ < v_i: se b’ > M vince ancora pagando M (utility identica), se b’ < M perde (utility 0, peggio). Bidando b’ > v_i: vince ancora (utility identica). In nessun caso si fa meglio del truthful.

Caso 2 — v_i < M. Bidando b_i = v_i: perde, utility 0. Bidando b’ > M: vince e paga M > v_i, utility v_i − M < 0. Bidando b’ < M: perde ancora, utility 0. Anche qui truthful è almeno pari.

In entrambi i casi, b_i = v_i è weakly dominant. QED.

L’argomento è notevole per quello che NON usa: nessuna distribuzione, nessuna assunzione su Bayesianità o razionalità degli altri, nessuna conoscenza comune. La dominanza è prior-free.

VCG: pagare l’esternalità

Generalizzare Vickrey a casi multi-bene o multi-allocazione richiede una formula. La famiglia Vickrey-Clarke-Groves la fornisce.

Setup: insieme A di possibili allocazioni, ogni agente i ha una valutazione v_i da A in R. Allocazione efficiente:

$$x* = argmax_{x in A} Σ_i v_i(x)$$

Pagamento di Clarke (versione “pivot”):

p_i = Σ_{j != i} v_j(x*_{-i})  −  Σ_{j != i} v_j(x*)

dove x*_{-i} è l’allocazione che sarebbe efficiente se i non esistesse. Riga per riga: il primo termine è “il welfare degli altri senza di me”, il secondo è “il welfare degli altri con me”, la differenza è quanto il mio essere qui sta togliendo agli altri — la mia esternalità negativa. Il meccanismo me la fa pagare.

EQUIVALENZA argomentabile: VCG ↔ “ogni agente paga l’esternalità che impone”. Non è una metafora libera: è la lettura precisa della formula Clarke. La somma dei pagamenti VCG è la perdita di welfare imposta dalla presenza dei bidder agli altri bidder.

Su single item, VCG si riduce esattamente a Vickrey: l’esternalità del vincitore è il valore del runner-up, che è quanto paga.

Proprietà di VCG (sotto utilità quasi-lineari):

• Truthfulness DSIC: dimostrazione analoga al case analysis su Vickrey, formalizzata da Groves 1973.
• Allocazione efficiente: per costruzione massimizza welfare.
• Individual rationality (sotto ipotesi di no-loss esterna).

TEOREMA: revenue equivalence (Myerson 1981, Riley-Samuelson 1981)

CLAIM. Sotto le ipotesi (a) bidder simmetrici con valutazioni iid da una distribuzione F continua e crescente, (b) risk-neutrality, (c) independent private values, (d) regola “vince il bid più alto”, (e) un bidder con valutazione minima ha utility attesa zero in equilibrio, allora ogni meccanismo “standard” produce lo stesso revenue atteso al venditore.

Conseguenza pratica: english, dutch, FPSB, Vickrey, in equilibrio, generano lo stesso expected revenue. La scelta del formato è guidata da robustezza, semplicità, costi di implementazione, vulnerabilità a collusione — non dal revenue medio.

TEOREMA: Gibbard-Satterthwaite (1973, 1975)

CLAIM. In social choice deterministica con almeno tre alternative, ogni meccanismo onnivalente (cioè la cui immagine copre tutte le alternative) e strategy-proof è dittatoriale (esiste un agente la cui preferenza determina l’esito).

In altre parole, nel mondo del voto puro senza moneta, non si può avere truthfulness senza dittatura. Per questo i meccanismi pratici (asta, market design) usano i soldi: aggiungendo utilità quasi-lineare e pagamenti, si scappa fuori dall’ipotesi di Gibbard-Satterthwaite. La moneta è l’attrezzo che consente truthfulness in mechanism design pratico. È la ragione tecnica per cui i marketplace agentici hanno bisogno di crediti, token o pagamenti reali, e non solo di voto/score qualitativi.

Optimal auction (cenno)

Quando il venditore conosce un prior F sulle valutazioni e vuole massimizzare expected revenue, Myerson (1981) introduce le virtual valuations:

$$psi_i(v) = v − (1 − F_i(v)) / f_i(v)$$

dove f_i è la densità. La asta ottima alloca al bidder con virtual bid massimo, purché positivo, e applica un payment rule che rende il vincitore appena indifferente.

Caso simmetrico con F = uniform su [0, 1]: psi(v) = 2v − 1, positiva sse v >= 1/2. L’asta ottima è quindi una Vickrey con reserve price 1/2. Lezione operativa: quando hai un prior, aggiungi un reserve price ben tarato a Vickrey e vai vicino all’ottimo.

Pseudocodice

# Vickrey (second-price sealed bid)
def vickrey(bids):
    # bids: dict {agent_id: bid}
    sorted_bids = sorted(bids.items(), key=lambda kv: -kv[1])
    winner, _ = sorted_bids[0]
    price = sorted_bids[1][1] if len(sorted_bids) > 1 else 0
    payments = {a: 0 for a in bids}
    payments[winner] = price
    return winner, payments

# First-price sealed-bid
def first_price(bids):
    winner = max(bids, key=bids.get)
    return winner, {a: (bids[a] if a == winner else 0) for a in bids}

# Generalized Second-Price (k slots, ad auctions)
def gsp(bids, ctr):
    # ctr: list of click-through rates alpha_1 > alpha_2 > ... > alpha_k
    sorted_bids = sorted(bids.items(), key=lambda kv: -kv[1])
    k = len(ctr)
    allocation = sorted_bids[:k]
    payments = {}
    for j, (agent, _) in enumerate(allocation):
        next_bid = sorted_bids[j+1][1] if j+1 < len(sorted_bids) else 0
        payments[agent] = ctr[j] * next_bid  # paid per expected click
    return allocation, payments

Per VCG generale, lo pseudocodice richiede un risolutore di allocazione efficiente come oracolo:

# VCG generale — single-shot, asta combinatoriale
# bidders: lista di (id, valuation_function: bundle -> R)
# items: lista di item disponibili
def vcg(bidders, items, solve_efficient):
    # solve_efficient(B, I) -> (allocation, welfare) con bidder set B su item set I
    x_star, w_star = solve_efficient(bidders, items)
    payments = {}
    for b in bidders:
        others = [x for x in bidders if x is not b]
        # welfare degli altri se b non c'e
        x_minus, w_minus = solve_efficient(others, items)
        # welfare degli altri quando b c'e
        w_others_with_b = sum(b2.value(x_star.get(b2.id, set())) for b2 in others)
        payments[b.id] = w_minus - w_others_with_b
    return x_star, payments

Il costo dominante è chiamare $solve_efficient$ n+1 volte. Per single-item, $solve_efficient$ è argmax (lineare in n) e VCG si riduce a Vickrey. Per combinatorial con valutazioni generiche, $solve_efficient$ è NP-hard, e il costo VCG complessivo è O(n) volte il costo di un solver — proibitivo oltre piccole istanze.

Combinatorial auctions: cenno

Generalizziamo ulteriormente. Non un singolo bene ma m beni distinti; ogni bidder i ha una valutazione v_i: 2^M to R su ogni possibile sottoinsieme (bundle) di beni. I beni possono essere complementari (le tre licenze radio adiacenti valgono di più insieme che separate) o sostituti (una sola licenza basta, le altre non aggiungono valore). Il problema è scegliere una partizione di M tra i bidder che massimizza Σ_i v_i(S_i).

Questo è formalmente equivalente a weighted set packing, NP-hard in generale. Anche peggio: lo spazio di descrizione delle valutazioni v_i è 2^m valori per agente, esponenziale; in pratica si usano linguaggi di bidding compatti (XOR-bids, OR-bids, package bidding) che limitano l’espressività ma rendono trattabile il problema.

Quando l’allocazione efficiente è intrattabile, la family VCG perde la truthfulness esatta: se al posto di x* uso un’allocazione approssimata x̃, le formule di pagamento Clarke non sono più DSIC. Si rinuncia o all’efficienza esatta o alla truthfulness in dominant strategies (rimanendo magari truthful in Bayesian-Nash). È il trade-off centrale dell’algorithmic mechanism design (Nisan-Ronen 1999).

In pratica le aste combinatoriali reali (FCC spectrum dal 2008, alcune sourcing auctions in supply chain) usano formati iterativi (clock auctions) che approssimano l’allocazione efficiente senza richiedere la rivelazione completa delle valutazioni. La truthfulness esatta è sostituita da “activity rules” che limitano i comportamenti strategici peggiori.

Posted-price e double auctions: due cenni

Non tutti i meccanismi sono aste in senso stretto. Due formati pratici importanti:

Posted-price mechanism. Il venditore annuncia un prezzo p; ogni bidder che arriva accetta se v_i >= p, rifiuta altrimenti. È DSIC banalmente (l’agente non ha leva strategica), ma generalmente non efficiente. Sotto certe ipotesi, posted-price approssimano Myerson optimal entro una costante (Chawla-Hartline-Malec-Sivan 2010), e sono particolarmente popolari in marketplace digitali per la loro semplicità.

Double auction. Acquirenti e venditori bid simultaneamente; un mechanism trova un prezzo di clearing che bilanci domanda e offerta. Le borse finanziarie sono double auctions continue. McAfee 1992 dà il primo double auction truthful, IR e budget-balanced ma non efficiente — coerente con l’impossibilità di Myerson-Satterthwaite.

Esempi

Esempio 1: numerico Vickrey vs first-price

Tre bidder con valutazioni private v_A = 100, v_B = 80, v_C = 60.

Vickrey. Strategia dominante: bid truthful (100, 80, 60). Vince A, paga 80. Utility A = 100 − 80 = 20. Welfare = 100 (allocato a chi vale di più). Revenue per la venditrice = 80.

First-price con strategia di equilibrio simmetrica sotto l’assunzione di valutazioni uniformi su [0, V] e n = 3: ciascuno bidda b(v) = v · (n−1)/n = 2v/3. Bid effettivi (66.7, 53.3, 40). Vince A, paga 66.7. Utility A = 33.3. Revenue realizzato = 66.7.

In questa specifica realizzazione, Vickrey raccoglie più di first-price. Ma in espettazione (su tutte le possibili realizzazioni di v iid uniformi), il revenue equivalence theorem garantisce che siano uguali. Il singolo draw è rumoroso; l’aspettativa coincide. Nota anche che in entrambi i meccanismi il vincitore è A — l’allocazione è efficiente in entrambi.

Effetto reserve price. Aggiungiamo un reserve price r = 50 a Vickrey. Bid (100, 80, 60), tutti sopra reserve. Vince A, paga max(80, 50) = 80. Aggiungiamo r = 70: bid validi (100, 80), C escluso. Vince A, paga max(80, 70) = 80. Aggiungiamo r = 90: vince A, paga 90. La virtual-valuation analysis di Myerson dice esattamente quale r massimizza expected revenue per ogni F.

Esempio 2: codice — simulazione Vickrey vs first-price con bidder che imparano

Mostriamo che con bidder no-regret, Vickrey converge istantaneamente a truthful mentre first-price oscilla verso lo shading di equilibrio.

import numpy as np

def simulate_auction(mechanism, n_rounds=1000, n_agents=3, V=100):
    # Valuations fissate; ogni round i bidder scelgono un bid e ricevono utility.
    np.random.seed(0)
    valuations = np.random.uniform(0, V, n_agents)
    # Strategie: parametrizzate da uno "shading factor" s_i in [0,1]
    # bid_i = v_i * s_i. Ogni round s_i si aggiorna verso il valore che
    # ha dato utility più alta nei round passati (best-response).
    s = np.full(n_agents, 0.5)
    history = []
    for t in range(n_rounds):
        # esplorazione: ogni agente prova s_i + epsilon, valuta utility
        eps = 0.05 * np.random.randn(n_agents)
        bids_now = valuations * s
        bids_alt = valuations * np.clip(s + eps, 0.01, 1.5)
        # confronta utility "ora" vs "alternativa"
        u_now = mechanism_utility(mechanism, bids_now, valuations)
        u_alt = mechanism_utility(mechanism, bids_alt, valuations)
        # update verso l'alternativa migliore (no-regret semplificato)
        improve = u_alt > u_now
        s = np.where(improve, np.clip(s + eps, 0.01, 1.5), s)
        history.append(s.copy())
    return np.array(history), valuations

def mechanism_utility(mech, bids, vals):
    if mech == "vickrey":
        idx = np.argmax(bids)
        sorted_b = np.sort(bids)[::-1]
        price = sorted_b[1] if len(sorted_b) > 1 else 0
        u = np.zeros_like(bids)
        u[idx] = vals[idx] - price
        return u
    elif mech == "first_price":
        idx = np.argmax(bids)
        u = np.zeros_like(bids)
        u[idx] = vals[idx] - bids[idx]
        return u

Eseguendo $simulate_auction("vickrey", ...)$ e poi $simulate_auction("first_price", ...)$, si osserva che gli s_i in Vickrey convergono a 1.0 (truthful) entro poche centinaia di round. In first-price convergono attorno a 0.66 = (n−1)/n per n=3, in linea con la teoria. Il messaggio: Vickrey è prior-free e DSIC, quindi imparare la strategia ottima è banale; first-price richiede di imparare anche la distribuzione altrui, quindi è fragile.

Esempio 3: scenario reale — Google AdWords e GSP

Google nel 2002 adotta la generalized second-price auction (GSP) per allocare slot di annunci in SERP (search engine results page). Setup: k slot pubblicitari con click-through rate decrescente alpha_1 > alpha_2 > … > alpha_k. n inserzionisti bid b_i (per click). Allocazione: ordina bid decrescenti, il j-esimo bid prende slot j. Pagamento per slot j (per click): b_{j+1}, cioè il bid del successivo.

Esempio: slot CTR (0.10, 0.05, 0.02). Bidder con bid (3.00, 2.50, 1.80, 1.20). Allocazione: A allo slot 1, B allo slot 2, C allo slot 3. Pagamenti per click: A paga 2.50, B paga 1.80, C paga 1.20. Pagamento atteso per impressione: A paga 0.25, B paga 0.09, C paga 0.024.

CLAIM. GSP NON è truthful. Controesempio. Stessi CTR. Bidder X con valutazione per click 4.00, due competitor con bid 3.50 e 1.00. Bid truthful: X bidda 4.00, vince slot 1, paga 3.50/click; utility per impressione = 0.10 · (4.00 − 3.50) = 0.05. Bid strategico: X bidda 2.00 (sotto valutazione), prende slot 2 (perché 3.50 > 2.00 > 1.00), paga 1.00/click; utility per impressione = 0.05 · (4.00 − 1.00) = 0.15. Bidding meno guadagna di più. La truthfulness fallisce.

Allora perché Google (e Yahoo, Bing) usano GSP e non VCG, che sarebbe truthful? Tre ragioni storiche e tecniche:

1. Semplicità di spiegazione agli inserzionisti: “paghi il bid di chi ti segue” è didatticamente più facile di “paghi l’esternalità che imponi”.
2. Path-dependency: nel 2002 l’industria veniva da meccanismi first-price (Overture/GoTo), e GSP era un’evoluzione minima.
3. In equilibrio “locally envy-free” — un equilibrio Nash plausibile in cui nessuno vuole scambiare slot con chi sta sopra — il revenue è simile o superiore a VCG su molte istanze.

Edelman-Ostrovsky-Schwarz 2007 dimostrano l’esistenza di tale equilibrio e lo caratterizzano. Facebook nel 2010+ ha sperimentato VCG per certe tipologie di ad; i risultati pratici hanno mostrato trade-off complicati e il dibattito GSP vs VCG persiste.

Cosa cambia per agent marketplaces? Se progetti un MCP marketplace dove provider competono per servire una richiesta, GSP è semplice ma non truthful: i provider svilupperanno strategie di shading. VCG dà truthfulness ma è più complesso da implementare e vulnerabile a sybil. La scelta non è ovvia e dipende da chi sono i bidder (umani sofisticati? agenti automatici?), dalla frequenza delle aste, dalla tolleranza a inefficienza.

Esempio 4: VCG su due item — calcolo dell’esternalità

Due item distinti X e Y, tre bidder con valutazioni su bundle:

Bidder	v({X})	v({Y})	v({X,Y})
1	10	0	10
2	0	8	8
3	0	0	14

Allocazioni possibili: dare {X,Y} a 3 (welfare 14), oppure X a 1 e Y a 2 (welfare 18), oppure X a 1 e nulla a 2 (welfare 10), eccetera. Allocazione efficiente x*: X a 1, Y a 2, welfare = 18.

Pagamento di 1. Senza 1, l’allocazione efficiente x*_{-1}: dare {X,Y} a 3 (welfare 14) batte dare Y a 2 (welfare 8). Quindi welfare degli altri senza 1 = 14. Welfare degli altri con 1 = v_2(Y) + v_3(nulla) = 8 + 0 = 8. Pagamento di 1: 14 − 8 = 6.

Pagamento di 2. Senza 2: x*_{-2} dare {X,Y} a 3 (welfare 14) o X a 1 (welfare 10). Vince welfare 14. Welfare degli altri con 2 = v_1(X) + v_3(nulla) = 10. Pagamento di 2: 14 − 10 = 4.

Pagamento di 3. Senza 3: x*_{-3} = X a 1 + Y a 2, welfare 18. Welfare degli altri con 3 = v_1(X) + v_2(Y) = 18. Pagamento di 3: 18 − 18 = 0.

Riepilogo: 1 vince X paga 6 (utility 4), 2 vince Y paga 4 (utility 4), 3 perde paga 0. Revenue del venditore = 10. Welfare = 18.

Note didattiche. Il pagamento di 3 è zero perché 3 non sposta l’allocazione efficiente: anche senza di lui, X e Y sarebbero comunque andati a 1 e 2. 3 non impone esternalità. Ma 1 e 2 spostano l’allocazione (senza di loro 3 avrebbe vinto entrambi gli item), quindi pagano un’esternalità positiva. Questo coglie l’intuizione “VCG ↔ paga il danno che imponi”: se la tua presenza non cambia il welfare degli altri, paghi zero, anche se vinci. Il meccanismo non ti tassa per il fatto di vincere ma per il fatto di scalzare qualcun altro.

Applicazioni pratiche

flowchart LR
  Client[Client agent] -- richiesta del task --> Mech[Meccanismo d'asta]
  P1[Provider 1: bid q1, c1] --> Mech
  P2[Provider 2: bid q2, c2] --> Mech
  P3[Provider 3: bid q3, c3] --> Mech
  Mech -- provider selezionato --> Client
  Mech -- pagamento VCG --> P_winner[Provider vincente]

Figura 5 — agent marketplace come asta inversa — client agent richiede un task, i provider offrono prezzo e qualità, il meccanismo seleziona e applica un pagamento VCG

Online ad auctions e RL bidders. Google, Meta, Amazon eseguono miliardi di aste GSP/VCG al giorno. Ogni “real-time bidding” è una mini-asta che chiude in <100ms. I bidder sono agenti reinforcement-learning (Cai et al. 2017): la valutazione di un’impressione è l’expected revenue da quella conversione, calcolato da una pipeline ML. L’agente impara bid shading, gestione del budget, sfruttamento di pattern temporali. Per il progettista di piattaforma: scegliere regole truthful (per non incentivare gaming complesso) e robuste a non-stazionarietà.

Spectrum auctions. La FCC (Federal Communications Commission USA) usa aste combinatoriali dal 1994 per allocare licenze radio. Inizialmente simultaneous multi-round (SMR), dal 2008 anche combinatorial clock auctions (CCA) progettate da Paul Milgrom. Hanno raccolto oltre 200 miliardi di dollari nei primi vent’anni. Il caso d’uso ha ispirato gran parte della teoria moderna di combinatorial auction.

Agent marketplaces (MCP, agent2agent). Una piattaforma agent platforms (in preparazione) tipica espone N tool, e un client agent deve sceglierne uno per un task. Se i tool hanno costi e qualità variabili e i provider competono, la struttura naturale è un’asta inversa (procurement auction) o un VCG-like routing. Il design deve garantire (a) che il client non sovra-paghi, (b) che i provider non possano gaming i metadati di latenza/qualità, (c) che il sistema scali.

Federated learning incentive. Quando più organizzazioni contribuiscono dati a un modello federato, come pagarle? Un’asta inversa con valore = miglioramento marginale del modello (data Shapley di giochi-cooperativi). VCG payment garantirebbe truthfulness sui report ma non è budget-balanced — qualcuno deve sussidiare.

Compute / GPU allocation interna. Dentro grandi organizzazioni, allocare GPU tra team in modo manipulation-proof. Un’asta interna con virtual valuations (revenue come “internal credits”) è una soluzione studiata da diverse big tech.

LLM auction frameworks. Sun et al. (2024) studiano LLM che agiscono da bidder in aste sintetiche. Risultati: gli LLM bidder spesso non rispettano dominant strategies, sono manipolabili via prompt injection nelle “regole d’asta” mostrate, e mostrano bias di anchoring sul primo numero visto. Implicazione per agent coding: usare LLM come bidder in mechanism dove la truthfulness conta richiede validazione formale, non basta dire al modello “sii truthful”.

Reverse auctions per crowdsourcing. Mechanical Turk e simili in versione strutturata: il requester fissa il task, i worker bid il prezzo minimo a cui lo eseguirebbero, vincono i k bid più bassi. VCG-like reverse auction.

Energy markets. Le borse elettriche europee (EPEX, Nord Pool) usano double auctions giornaliere e infra-giornaliere per il day-ahead market. Centinaia di gigawatt si allocano con clearing price. Stesso framework, scala industriale.

Sponsored content e attention markets. Oltre alle SERP ad, ogni feed sociale è una continua asta tra contenuti per attenzione utente. Formalmente è una variante di GSP con CTR personalizzati per utente. La regola di allocazione include termini di “qualità” (per limitare lo spam) che sono in tensione con la truthfulness — se la qualità è auto-riportata, è gameabile.

On-chain auctions. In ambito Ethereum, il “block proposer” raccoglie transazioni in ordine di gas price (first-price auction). Da EIP-1559 (2021) si è passati a un meccanismo più simile a posted-price con base fee dinamica + tip. Il dibattito MEV (maximum extractable value) ha riacceso l’interesse per VCG-on-chain e per sealed-bid mempool.

Dove si rompe

Le aste sono il sotto-campo della teoria dei giochi con i risultati positivi più puliti, ma la lista delle assunzioni che cadono in pratica è lunga. Conoscerle è essenziale per non auto-ingannarsi quando si progetta un marketplace agentico.

Collusione in VCG. Due bidder possono colludere dichiarando v = 0 a turno e spartendosi il surplus. Vickrey su singolo item è meno vulnerabile (la collusione richiede side-payments enforceable), ma in combinatorial VCG anche piccoli ring di collusione possono ridurre il revenue a una frazione del vero welfare. In agent marketplaces, due provider che colludono per spartirsi il volume sono difficili da individuare se non si ha trust infrastructure (vedi sotto).

Combinatorial auctions sono NP-hard. Determinare l’allocazione efficiente con valutazioni su bundle è weighted set packing, NP-hard. In pratica si usano LP-relaxation, approssimazioni, o iterative auctions (clock auctions). Ma appena si rinuncia all’allocazione ottima esatta, la truthfulness in dominant strategy si perde (Nisan-Ronen 1999): non si possono avere simultaneamente truthfulness, efficienza, polynomiality nel caso generale.

Revenue equivalence cade. Le ipotesi del teorema sono fragili: bidder asimmetrici (distribuzioni diverse tra bidder), risk-aversion (i bidder odiano l’incertezza), common values (la valutazione dipende da informazione condivisa, come petrolio in un giacimento), budget constraints. Ognuna di queste assenze rompe l’equivalence. In pratica, in marketplace reali, le ipotesi non valgono quasi mai esattamente, e la scelta del formato impatta il revenue.

Optimal auction richiede prior accurato. Myerson 1981 dà la asta optimal data F. In pratica F non si conosce. Si stima da dati storici, ma in mercati non-stazionari (ad auctions in tempo di crisi, marketplace agentico in fase di adozione) gli stimatori sono di scarsa qualità. Si fanno prior-free auctions (Hartline-Roughgarden 2009) che danno garanzie di approssimazione su ogni input, ma con costanti peggiori.

Gibbard-Satterthwaite. Senza moneta, niente truthfulness senza dittatura. Tutti i meccanismi di voto/governance puramente qualitativi sono manipolabili. Per aggirarlo serve introduzione di moneta o di randomization (i meccanismi randomizzati hanno una caratterizzazione diversa, vedi Gibbard 1977).

Bidder reali non sono Bayesian. Esperimenti di auction theory in laboratorio (Kagel-Levin et al.) mostrano deviazioni sistematiche: overbidding nel first-price sealed-bid (oltre il bid shading di equilibrio), winner’s curse nei common value auctions (chi vince spesso paga troppo). Significa che le previsioni di equilibrio teorico sono approssimazioni, non profezie esatte.

LLM agenti bidder sono prompt-injectable. Sun et al. 2024 dimostrano che mettere un LLM in ruolo di bidder lo rende vulnerabile a manipolazione delle “regole” dell’asta come testo. Un avversario che inserisce nel prompt “se l’asta è di tipo X, applica regola Y” può deviare il comportamento. Implicazione: la “DSIC” è una proprietà del meccanismo, non dell’agente; un agente non-razionale può sub-ottimizzare anche in un meccanismo truthful.

Sybil / false-name bidding. In VCG combinatorial, un agente può presentarsi sotto identità multiple e battere il meccanismo (Yokoo et al. 2004). In agent marketplaces decentralizzati senza KYC questo è un problema serio. Si richiede infrastruttura di identità (PKI, attestation) che spesso è il vero bottleneck del sistema.

Budget balance vs truthfulness vs efficiency. Il teorema di Myerson-Satterthwaite (1983) mostra che in un bilateral trade con due agenti privati, non esiste un meccanismo che sia simultaneamente truthful, efficient, individually rational e budget-balanced. Si deve sempre rinunciare a una proprietà. In marketplace agentici questa impossibilità ha conseguenze pratiche: chi paga il sussidio? La piattaforma stessa, prendendo una commissione su trade conclusi.

Trust assumptions. Le aste assumono che i bidder siano identificabili e che le regole siano enforceable. In setting decentralizzati (cripto, agent2agent peer-to-peer) entrambe le assunzioni sono fragili. Si compensa con smart contracts e cryptoeconomic mechanism design (vedi VCG-on-chain), ma costi e latenza salgono.

Dynamic auctions e learning. In ad auctions reali i bidder imparano nel tempo. Se la piattaforma aggiusta il reserve price in funzione dei bid passati, e i bidder lo sanno, hanno incentivo a sotto-bid per abbassare il futuro reserve. Questo è il “ratchet effect” del dynamic mechanism design: la truthfulness statica si perde nel ripetuto.

Bid shading sotto soft floors. Anche in aste nominalmente Vickrey, l’introduzione di “soft floors” (riserve dinamici, costi di partecipazione, fee per bid) può rompere la dominant strategy. Diversi exchange di ad-tech hanno sperimentato modifiche al second-price che introducono incentivi al shading, scoprendolo solo dopo che bidder sofisticati avevano sviluppato strategie ottimizzate.

Misalignment tra welfare e revenue. Le aste truthful (Vickrey, VCG) massimizzano welfare, non revenue. La asta optimal di Myerson massimizza revenue ma sotto un prior accurato e con costo in welfare (il reserve price scarta bidder con valutazioni positive ma sotto soglia). In molti contesti pratici (ad auctions, marketplace agentici) la piattaforma deve scegliere quale obiettivo perseguire e accettarne le conseguenze. Una piattaforma agentica che ottimizza solo per revenue si comporta come un monopolista, e perde adozione di lungo termine; una che ottimizza solo welfare lascia denaro sul tavolo. Il design pratico è spesso un’ibridazione.

Inefficienza della asta optimal. Sotto Myerson, alcuni bidder con valutazione positiva ma virtual valuation negativa vengono esclusi (reserve price). Questo è inefficiente: non vendere a chi vorrebbe comprare. La differenza tra Vickrey (efficiente) e Myerson optimal (revenue-massimizzante) è la deadweight loss del monopolio. In agent marketplaces, il design di reserve “intelligenti” (learnati per categoria di task) cerca di limitare questa perdita, ma è un trade-off intrinseco.

Asimmetria informativa lato venditore. Tutta la teoria classica assume che il venditore sappia cosa vende; i bidder hanno valutazioni private. In agent marketplaces è frequente la situazione inversa: il client (compratore) sa cosa vuole, ma il provider (venditore) ha qualità privata che il client non può verificare ex-ante. Si entra nel terreno di adverse selection e dei meccanismi alla Akerlof-Spence: serve un’altra teoria (signaling, screening) parente del mechanism design ma con assunzioni diverse. La maggior parte dei marketplace agentici reali confonde i due piani e ne paga le conseguenze.

Rischio reputazionale lato piattaforma. Anche un meccanismo provatamente truthful può fallire se i bidder credono che la piattaforma trucchi il conteggio. Senza trasparenza dei bid (cosa di moltissime piattaforme proprietarie), il bidder non può verificare di non essere stato barato dal venditore stesso. La truthfulness teorica è condizionata alla fiducia nell’esecuzione del meccanismo. Le aste on-chain affrontano questo problema attraverso commit-reveal e verificabilità crittografica, a costo di latenza e gas fee.

Chiusura della sezione. La lista non è esaustiva; ognuna di queste rotture è un sotto-campo con la sua letteratura. Quando progetti un agent marketplace, il workflow razionale non è “scegli VCG perché è truthful”. È: identifica le ipotesi del tuo dominio (informazione asimmetrica? identità verificabile? aste ripetute?), mappa quali rotture sono attive, e scegli il meccanismo che minimizza il danno atteso, non quello con la più bella proprietà teorica.

Collegamenti

• giochi-definizione: formalizza il concetto di gioco e payoff su cui si fondano le aste.
• somma-zero-non-zero: le aste sono giochi non a somma zero (il welfare totale dipende dall’allocazione).
• equilibrio-nash: l’analisi di first-price e GSP usa equilibri Bayesian-Nash; Vickrey ha invece equilibri in dominant strategy, più forti.
• giochi-cooperativi: per attribuire valore a componenti di un sistema (data Shapley) serve la trattazione cooperativa, complementare al non-cooperativo delle aste.
• dilemma-prigioniero: la collusione in VCG è un’istanza di coordinamento sotto incentivi mal allineati.
• bayes-base (in preparazione): per Bayesian-Nash equilibria e Myerson optimal serve il framework Bayesian.
• agent platforms (in preparazione): le piattaforme MCP e agent2agent sono i marketplace agentici dove queste regole vivono.
• federated learning (in preparazione): incentive mechanism per federated learning usano data Shapley + aste inverse.
• RL-online (in preparazione): bidder RL in ad auctions; bandits e auctions si intrecciano (bandit auctions).
• ucb-thompson (in preparazione): per esplorazione/sfruttamento nel bidding ripetuto.

Per andare oltre

• Krishna, Vijay (2009). Auction Theory (2nd ed.), Academic Press. Trattato standard di auction theory: independent private values, common values, multi-unit, mechanism design.
• Nisan, Noam; Roughgarden, Tim; Tardos, Eva; Vazirani, Vijay V. (eds.) (2007). Algorithmic Game Theory, Cambridge University Press. Capitoli 9-13 coprono mechanism design, combinatorial auctions, ad auctions; libero online.
• Myerson, Roger B. (1981). Optimal Auction Design, Mathematics of Operations Research, 6(1), 58-73. Il paper fondante della teoria moderna; tecnico ma leggibile.
• Roughgarden, Tim (2016). Twenty Lectures on Algorithmic Game Theory, Cambridge University Press. Stile didattico, copertura compatta di Vickrey, VCG, reserve price, prior-free auctions.
• Edelman, B.; Ostrovsky, M.; Schwarz, M. (2007). Internet Advertising and the Generalized Second-Price Auction, American Economic Review, 97(1), 242-259. Per chi vuole capire perché Google fa quello che fa.