ASTE

Vincenzo Auletta Università di Salerno

STRUTTURA DELLE RETI SOCIALI

ASTE

¢   Le aste (auctions) sono un’altro importante ambito in cui possiamo applicare il framework della teoria dei giochi �   Come devo comportarmi nel fare un’offerta? �   Quale meccanismo debbo utilizzare per vendere un oggetto

tramite un’asta

¢   Le aste sono un meccanismo economico estremamente diffuso e sono diventate molto popolari in ambito e-commerce �   Vendita di obbligazioni e titoli di stato �   Affidamento di concessioni �   Vendita di beni di cui non è noto il valore �   Internet marketplace

¢   e-Bay ¢   Quasi tutta la raccolta pubblicitaria di giganti come Google avviene tramite

aste

¢   E’ un campo in cui la ricerca è stata molto attiva negli ultimi anni

Au

tun

no 2012

1

Stru

ttura delle R

eti Sociali

ASTE PER RICERCA SPONSORIZZATA A

utu

nn

o 2012

2

Stru

ttura delle R

eti Sociali

Risultati della ricerca Ads: ricerca sponsiruzzata

ASTE PER RICERCA SPONSORIZZATA

¢  Quando eseguiamo una ricerca su Google il sistema lancia un’asta online per vendere gli spazi pubblicitari all’interno della pagina dei risultati

¢  La pubblicità è particolarmente efficace se

�   È mirata �   È proposta all’utente quando più gli serve (sta cercando

informazioni)

¢   Il modello di business di Google è basato su aste

pay-per-click �   Il prezzo dell’inserzione viene definito dinamicamente �   L’inserzionista paga solo se l’utente effettivamente

visualizza il messaggio

Au

tun

no 2012

3

Stru

ttura delle R

eti Sociali

MARKET DESIGN

¢   L’advertisement è la voce di gran lunga più importante nel bilancio di Google e vale svariati miliardi di dollari �   L’implementazione del meccanismo di aste è fondamentale �   I dettagli su come sono implementate queste aste li vedremo in

una delle prossime lezioni

¢   Problemi non banali da risolvere �   Enormi problemi di scalabilità �   Gli inserzionisti sono egoisti e tendono a “manipolare” il

sistema

¢   Le principali aziende Internet stanno assumendo

economisti per disegnare correttamente I loro mercati utilizzando la teoria delle aste

Au

tun

no 2012

4

Stru

ttura delle R

eti Sociali

DEFINIZIONE DEL PROBLEMA

¢   Supponiamo di dover vendere un singolo oggetto �   Poi generalizzeremo al caso di più oggetti

¢   Non conosciamo il valore del bene in vendita �   Conosciamo il nostro valore personale �   Possiamo eventualmente fissare un prezo di riserva (prezzo al

di sotto del quale non si vende)

¢   Ogni inserzionista ha una sua propria valutazione dell’oggetto in vendita �   Rappresenta il massimo prezzo che è disposto a pagare �   I valori sono privati ed indipendenti

¢   È un gioco a informazione incompleta

¢   Come dobbiamo comportarci? �   Sia come inserzionista che venditore

Au

tun

no 2012

5

Stru

ttura delle R

eti Sociali

VALUTAZIONI NOTE

¢   Supponiamo di conoscere le valutazioni di tutti gli inserzionisti �   Non serve l’asta

¢   Se �   il valore per il venditore è x �   La valutazione dell’acquirente è y �   Surplus = y-x

¢   I giocatori si impegnano ad affidarsi ad un meccanismo �   Se uno dei due giocatori controlla il meccanismo si prende

tutto il surplus �   Se il meccanismo è controllato da entrambi i giocatori parte

una contrattazione (non coperta in questa lezione)

Au

tun

no 2012

6

Stru

ttura delle R

eti Sociali

VALUTAZIONI NON NOTE

¢   Il venditore non conosce le valutazioni dei giocatori e non sa quanto sono disposte a pagare

¢  Se fissa un prezzo potrebbe essere �   troppo alto e non trovare acquirenti �   Troppo basso e vendere l’oggetto a meno del suo valore

¢   Il venditore deve chiedere agli acquirenti quanto sono disposti a pagare �   Gli acquirenti potrebbero mentire per manipolare il

meccanismo in modo da guadagnare il surplus �   Come si fa a motivare gli acquirenti a dichiarare le loro

vere valutazioni?

Au

tun

no 2012

7

Stru

ttura delle R

eti Sociali

MECHANISM DESIGN

¢  La teoria delle aste è una parte del Mechanism Design �   Branca della Teoria dei Giochi che si occupa di come

progettare meccanismi in modo da avere come equilibri del gioco gli esiti desiderati

¢  Nel nostro caso vogliamo che per gli acquirenti dichiarare la propria vera valutazione sia una strategia dominante �   Truthful mechanism �   Rende ininfluente la mancanza di informazione sulle

valutazioni degli altri acquirenti

Au

tun

no 2012

8

Stru

ttura delle R

eti Sociali

OBBIETTIVI DELL’ASTA

¢   Il banditore può avere vari obbiettivi �   Influenzano il disegno del meccanismo

¢  Massimizzare il guadagno (revenue) ¢  Massimizzare il social welfare

�   Somma delle utilità ottenute da tutti i giocatori

¢  Massimizzare l’equità (fairness)

¢  Nel resto della lezione il nostro obbiettivo sarà il social welfare �   Massimizzare la valutazione dei giocatori che vincono

l’asta

Au

tun

no 2012

9

Stru

ttura delle R

eti Sociali

PRINCIPALI TIPI DI ASTE

Ascending auction (asta inglese)

Au

tun

no 2012

10

Stru

ttura delle R

eti Sociali

¢   Il venditore offre prezzi via via crescenti

¢   Ad ogni round quelli che non sono disposti a pagare quel prezzo si ritirano

¢   L’asta termina quando rimane un solo acquirente

Le aste su e-Bay sono un tipo particolare di asta inglese

PRINCIPALI TIPI DI ASTE

Descending auction (asta olandese)

Au

tun

no 2012

11

Stru

ttura delle R

eti Sociali

¢   Il venditore offre prezzi via via decrescenti

¢   Se nessuno accetta di pagare quel prezzo si prosegue

¢   L’asta termina quando un acquirente accetta il prezzo offerto

Il tesoro americano usa un’asta olandese per vendere i Buoni del Tesoro

PRINCIPALI TIPI DI ASTE

Sealed-bid Auctions

Au

tun

no 2012

12

Stru

ttura delle R

eti Sociali

¢   Gli acquirenti scrivono le loro offerte in busta chiusa e le danno al meccanismo

¢   Il venditore apre tutte le buste e decide chi vince e quanto paga

¢  Aste first-price �   Il vincitore paga quello che ha offerto

¢  Aste second-price �   Il vincitore paga la seconda offerta più alta

ASTE DI VICKREY

¢  Le aste di secondo prezzo sono anche dette aste di Vickrey �   Meccanismo di asta definito da William Vickrey nel

1961

¢  Vickrey ha vinto il Nobel per l’economia nel 1996

Au

tun

no 2012

13

Stru

ttura delle R

eti Sociali

RELAZIONI TRA I VARI TIPI DI ASTE

¢   Aste di primo prezzo sono strategicamente equivalenti alle aste olandesi �   Durante l’asta olandese il giocatore non apprende nulla sulle

valutazioni degli altri giocatori fino a quando qualcuno alza la mano

�   Ogni giocatore deve decidere a quale prezzo alzerà la mano sapendo che potrebbe doverlo pagare

�   Equivalente a decidere quale prezzo scrivere nella busta

¢   Aste di secondo prezzo sono strategicamente equivalenti alle aste inglesi �   Durante l’asta inglese il giocatore vede ad ogni round quanti si

ritirano �   Ad ogni giocatore conviene restare nel gioco fino a che il prezzo

raggiunge la propria valutazione �   Anche nell’asta di secondo prezzo conviene dichiarare la

propria vera valutazione

Au

tun

no 2012

14

Stru

ttura delle R

eti Sociali

ASTE SEALED-BIDS

¢  Senza perdita di generalità considereremo solo aste sealed bid

¢  Quale asta conviene utilizzare?

¢  Ad una prima occhiata sembrerebbe che �   Nell’asta di primo prezzo il venditore incassa di più … �   … ma i giocatori tendono a fare offerte inferiori alla loro

vera valutazione �   Nell’asta di secondo prezzo i giocatori sono incentivati a

dichiarare le loro vere valutazioni (truthful)

Au

tun

no 2012

15

Stru

ttura delle R

eti Sociali

ASTE COME GIOCHI STRATEGICI

¢   Gli n acquirenti sono i giocatori

¢   Le strategie sono le possibili offerte da mettere nella busta �   Tutti i giocatori fanno la loro offerta contemporaneamente �   Ogni giocatore fornisce al meccanismo un’offerta bi �   i giocatori giocano solo strategie pure

¢   Ogni giocatore ha la propria valutazione vi dell’oggetto in vendita �   La valutazione è privata

¢   Il meccanismo decide chi vince l’asta ed il prezzo p che deve pagare

¢   Il payoff del giocatore i è �   ui = vi – p (se vince l’asta) �   ui = 0 (se non vince l’asta)

Au

tun

no 2012

16

Stru

ttura delle R

eti Sociali

STRATEGIE

¢   Un acquirente deve decidere la propria strategia di offerta �   Cosa scrive nella busta? Dipende dalla valutazione

¢   Assumiamo valutazioni private ed indipendenti �   Ogni giocatore non sa nulla delle valutazioni degli altri

¢   Nel modello con common value le valutazioni sono estratte da una distribuzione di probabilità comune e nota a tutti �   I giocatori possono farsi un’idea delle valutazioni degli altri

¢   Possibili strategie �   bi(vi) = vi �   bi(vi) = vi/2 �   bi(vi) = vi/n �   If vi<10 bi(vi) = vi then bi(vi) = vi -10

Au

tun

no 2012

17

Stru

ttura delle R

eti Sociali

ASTE DI VICKREY SONO TRUTHFUL

¢   In un’asta di secondo prezzo dichiarare la propria vera valutazione è una strategia dominante �   Vale anche per aste inglesi se le valutazioni sono indipendenti

e private

¢   In un meccanismo truthful I giocatori non hanno nessun interesse a mentire indipendentemente da cosa fanno gli altri giocatori �   La scelta dell’offerta è semplice �   Consente al meccanismo di selezionare il giocatore con la

valutazione più alta

¢   Le aste di secondo prezzo sono �   truthful �   Semplici da implementare �   Massimizzano il social welfare

Au

tun

no 2012

18

Stru

ttura delle R

eti Sociali

PROVA DI TRUTHFULNESS

¢  Consideriamo il giocatore 1 con valutazione v1

�   bi(vi) = vi

¢  Se 1 vince guadagna ui = vi – p �   p = maxj≠i bj

�   Dichiarando bi(vi) > vi vince ottenendo la stessa utilità �   Dichiarando bi(vi) < vi o vince ottenendo la stessa utilità o

perde guadagnando 0

¢  Se 1 perde guadagna ui = 0 �   Dichiarando bi(vi) > vi o perde guadagnando 0 oppure

vince rischiando di pagare più della sua valutazione �   Dichiarando bi(vi) < vi perde comunque e guadagna 0

Au

tun

no 2012

19

Stru

ttura delle R

eti Sociali

ASTE DI PRIMO PREZZO

¢  Le aste di primo prezzo sono truthful? �   No �   L’utilità del giocatore dipende dalla propria offerta

¢  Se il giocatore dichiara la sua vera valutazione guadagnerà 0 �   Equivalente a perdere l’asta

¢   Il giocatore tende a fare un’offerta inferiore alla sua valutazione �   Di quanto inferiore?

¢  Esistono strategie in Equilibrio Nash per aste di primo prezzo?

Au

tun

no 2012

20

Stru

ttura delle R

eti Sociali

ASTE ALL-PAY

¢   Le aste all-pay sono un altro tipo di aste sealed-bid �   Tutti sottomettono un offerta �   Vince l’offerta più alta �   Ognuno paga l’offerta presentata

¢   Apparentemente controintuitive ma utilizzate in pratica �   Gare in cui bisogna sottomettere un progetto

¢   Tutti i partecipanti devono sostenere i costi di presentazione del progetto indipendentemente dall’esito

¢   Concettualmente simili alle aste di primo prezzo �   I giocatori tendono a fare offerte molto più basse della loro

valutazione

¢   Qual è la strategia ottimale?

Au

tun

no 2012

21

Stru

ttura delle R

eti Sociali

STRATEGIE PER ASTE DI PRIMO PREZZO CON 2 GIOCATORI

¢   Assumiamo che ogni giocatore conosca il numero dei giocatori ed abbia un’informazione parziale sulle loro valutazioni �   Valutazioni estratte da una distribuzione di probabilità nota a

tutti �   Le distribuzioni di probabilità possono essere diverse tra I

giocatori

¢   Assumiamo 2 giocatori e valutazioni distribuite indipendentemente e uniformemente tra 0 e 1

¢   Una strategia è una funzione s(v) che decide l’offerta in base alla valutazione

¢   Assumiamo che �   s() è una funzione strettamente crescente e differenziabile �   s(v) ≤ v (s(0) = 0)

Au

tun

no 2012

22

Stru

ttura delle R

eti Sociali

ANALISI BAYESIANA E REVELATION PRINCIPLE

¢  Poiché il gioco è a informazione incompleta il concetto di soluzione utilizzato è Bayesian-Nash Equilibrium �   La strategia di ogni giocatore massimizza il suo payoff

atteso rispetto alle strategie giocate dagli altri e alla distribuzione di probabilità che descrive la conoscenza parziale delle valutazioni

¢   Il Revelation Principle ci dice che ogni strategia alternativa a s() può essere vista come la strategia s() a cui forniamo una diversa valutazione �   Possiamo restringere la nostra analisi al caso in cui tutti

i giocatori giocano la stessa strategia ma con valutazioni differenti

Au

tun

no 2012

23

Stru

ttura delle R

eti Sociali

STRATEGIE IN EQUILIBRIO NASH PER ASTE DI PRIMO PREZZO

¢   2 giocatori e valutazioni distribuite indipendentemente e uniformemente tra 0 e 1

¢   bi= vi/2 è una soluzione BNE

¢  PROVA �   Assumiamo che il giocatore 2 usa la b2(v2)=v2/2 �   L’utilità attesa del giocatore 1 è

¢  Prob[ b1 > b2 ] × (v1-b1) = Prob[ b1 > v2/2 ] × (v1-b1) = 2b1 * (v1-b1)

¢  L’utilità attesa è massimizzata per b1(v1)=v1/2

Au

tun

no 2012

24

Stru

ttura delle R

eti Sociali

STRATEGIE IN EQUILIBRIO NASH PER ASTE DI PRIMO PREZZO

¢  n giocatori e valutazioni distribuite indipendentemente e uniformemente tra 0 e 1

¢   bi= vi (n-1)/n è una soluzione BNE �   Prova simile

¢  Commenti per distribuzione uniforme delle valutazioni: �   All’aumentare della competizione il giocatore tende a

fare offerte più vicine alla loro vera valutazione �   Nella soluzione in equilibrio l’asta è vinta dal giocatore

con la valutazione più alta (max social welfare) �   Anche se l’asta non è truthful possiamo aspettarci che al

crescere del numero di giocatori i giocatori si comporteranno correttamente

Au

tun

no 2012

25

Stru

ttura delle R

eti Sociali

STRATEGIE IN EQUILIBRIO NASH PER DISTRIBUZIONI ARBITRARIE

¢  Esistono strategie BNE anche nel caso di n giocatori e valutazioni distribuite arbitrariamente sull’insieme dei reali non-negativi

¢   possiamo fornire un metodo generale per individuare tali strategie �   Basato sulla soluzione di un sistema di equazioni

differenziali

¢  Per dare una formula chiusa di tale soluzione dobbiamo necessariamente definire la distribuzione di probabilità delle valutazioni

Au

tun

no 2012

26

Stru

ttura delle R

eti Sociali

EQUIVALENZA DEI GUADAGNI PER IL VENDITORE ¢   Quanto guadagna il venditore in ogni tipologia di asta e quale

tipo di asta gli conviene usare? �   Assumiamo valutazioni i.i.d in [0, 1]

¢   Nelle aste di primo prezzo e le aste olandesi �   I giocatori offrono (n-1)/n della loro valutazione �   L’offerta più alta attesa è n/(n+1) �   Il guadagno atteso è (n-1)/(n+1)

¢   Nelle aste di secondo prezzo e le aste inglesi �   Il venditore si impegna a far pagare solo la seconda offerta più

alta �   Fare offerte truthful è strategia dominante �   Considerando le due offerte più alte attese si ha che il guadagno

atteso è è (n-1)/(n+1)

Le due tipologie di asta sono equivalenti per il venditore Questa proprietà vale per molto tipologie di aste e classi di

distribuzioni di probabilità se I giocatori utilizzano le lstrategie in equilibrio

Au

tun

no 2012

27

Stru

ttura delle R

eti Sociali

RESERVE PRICE

¢   Abbiamo visto che per il venditore è conveniente scegliere di vendere un bene tramite un meccanismo di asta �   Si impegna a far pagare il bene quanto fissato dal meccanismo

¢   Il meccanismo deve essere vincolante per il venditore �   Se lui potesse rifiutarsi di vendere al prezzo fissato dal

meccanismo gli acquirenti non troverebbero più conveniente dichiarare le loro reali valutazioni e non è chiaro quale sarebbe la soluzione in equilibrio

¢   Il venditore può fissare un reserve price �   Prezzo al di sotto del quale il bene non è venduto �   Il prezzo di riserva deve essere comunicato in anticipo a tutti I

giocatori �   Per ogni distribuzione di probabilità delle valutazioni esiste un

valore del reserve price in BNE

Au

tun

no 2012

28

Stru

ttura delle R

eti Sociali

STRATEGIE BNE PER ASTE ALL-PAY

¢   Il tipo di analisi utilizzata per le aste di primo prezzo può essere applicato anche al caso all-pay

¢   L’utile atteso di un giocatore dichiarando vi è �   vi

n-1(vi-s(vi) + (1-vi n-1)(-s(vi)

�   Per il revelation principle devo far vedere che questo utile è non minore di quello ottenuto con qualsiasi altra valutazione

¢   Facendo un po’ di conti otteniamo che �   la strategia in equilibrio è s(vi) = (n-1)/n vi

n

�   L’utile atteso per il venditore è (n-1)/(n+1)

¢   Commenti: �   Per il venditore questa asta è equivalente a quella di primo

prezzo �   All’aumentare del numero dei competitori ogni giocatore

tenderà a ridurre la propria offerta ¢   Per esempio, ridurrà l’impegno profuso per presentare il progetto

Au

tun

no 2012

29

Stru

ttura delle R

eti Sociali

ASTE NEL MONDO REALE

¢   Abbiamo discusso un modello semplificato �   Nella vita reale le aste sono molto più complicate

¢   Spesso i giocatori conoscono le loro valutazioni e si lasciano

influenzare �   Se tante persone sono disposte a pagare 100€ per un oggetto

probabilmente vale quella cifra

¢   In genere le aste sono ripetute �   Il giocatore può imparare dai round precedenti e ottenere informazioni

sulle valutazioni e le strategie degli avversari

¢   I giocatori partecipano a più aste ed hanno dei budget limitati

¢   I giocatori possono manipolare il sistema anche in altri modi �   Collusioni �   offerte con falsi nomi

¢   I giocatori si comportano in maniera non totalmente razionale

Au

tun

no 2012

30

Stru

ttura delle R

eti Sociali