Dynamic timer adjustment in penny auctions

Prova

I giochi rivestono un ruolo fondamentale nella vita degli uomini: innescano delle dinamiche estremamente complicate a livello psicologico generando allo stesso tempo competizione ed aspettative spesso non attese. Con l'avvento della tecnologia e soprattutto di internet si e' prefigurata una nuova categoria di giochi che, nel tempo, ha riscosso incredibili successi: il gioco on-line. Appare certamente estremamente complesso cercare di individuare una singola causa dell'autentica esplosione di questo 'fenomeno'. Nel corso del 2007 sul web e' stato proposto un nuovo interessante meccanismo di asta noto con il nome Penny Auction (PA). Si tratta di un format innovativo di aste a pagamento capace di riscuotere ampi consensi fin dal principio e di crescere notevolmente in tempistiche decisamente ristrette. Le penny auction presentano delle caratteristiche innovative decisamente interessanti e meritevoli di essere analizzate con attenzione a livello scientifico. Il tuning dei parametri d'asta influenza notevolmente la partecipazione dei giocatori e dunque le revenue. Cio' comporta che settando in modo opportuno i parametri maggiormente nevralgici, si possano far crescere i guadagni in maniera consistente. Al fine di comprendere correttamente gli obiettivi di questo lavoro, occorre spiegare brevemente il funzionamento di una tipica penny auction. Per poter partecipare ad una PA il giocatore deve acquistare un pacchetto di crediti. La singola offerta, intuitivamente, comporta la deduzione di uno o piu' crediti a seconda della categoria dell'oggetto (ad esempio, la singola offerta in alcune aste corrisponde ad 1 credito, in altre a e cosi' via). Ciascuna offerta piazzada da un utente incrementa il prezzo attuale dell'asta, che parte da Euro 0.00 di 1 centesimo (di qui il nome Penny Auction). Inoltre, il tempo di chiusura di un'asta non e' statico. Infatti ciascuna bid fa shiftare in avanti il tempo di chiusura di un numero di secondi pare ad un parametro che prende il nome di timer d'asta . Inuitivamente un'asta si chiude quando il conto alla rovescia, perennemente attivo mentre l'asta e' attiva, raggiunge il valore 0 senza che nessun utente abbia piazzato una offerta. La maggior parte delle compagnie opta per un timer d'asta statico mentre altre, come la societa' che ha concesso il dataset per sviluppare il lavoro in oggetto, scelgono di affidarsi ad un timer dinamico che, quindi, richiede un sistema di 'aggiustamento' runtime. Il timer rappresenta un parametro critico per una compagnia di PA perche' se aggiornato secondo criteri eccessivamente 'rilassati' determina un'asta percepita come 'noiosa' mentre, se aggiornato in maniera 'aggressiva', porta gli utenti a smettere di piazzare delle offerte perche' spaventata dalla frequenza con la quale devono continuare ad offrire. Questo lavoro di tesi mira a generare un modello utile per 'aggiustare' automaticamente il timer di una penny auction massimizzando il profitto nell'unita' di tempo e, indirettamente, generando percio' un numero di vincitori 'unici' piu' elevato. Infatti, la maggior parte delle compagnie operanti nel settore impone dei tetti massimi settimanali/mensili di vincita in modo tale da favorire la user retention e quindi una soddisfazione maggiormente diffusa. Dunque, la massimizzazione delle revenue nell'unita' di tempo unita ai vincoli sulle vincite consente di diversificare i vincitori cogliendo un duplice fondamentale obiettivo: la user retention. Al fine di raggiungere il duplice obiettivo preposto, e' stato necessario dapprima studiare con attenzione le dinamiche sottese alle penny auction e quindi le tecniche di machine learning in modo da poter individuare quella maggiormente appropriata per risolvere un problema di questa tipologia. Si consideri che, dovendo apprendere una politica di aggiornamento del timer, il paradigma di apprendimento che si presta meglio a risolvere il task e' il reinforcement learning. In particolare, non avendo la possibilita' di interagire con l'ambiente per via dei rischi a livello economico che ne deriverebbero, e' stato necessario ricorrere ad una tecnica di apprendimento off-line (Batch Reinforcement Learning) che permettesse appunto di apprendere una politica ottima rispetto al problema considerato, sfruttando unicamente una base di conoscenza $D$. In tal caso, avendo a disposizione il log delle offerte ricevute nei 6 mercati in cui opera la societa' MadBid Ltd, e' stato possibile modellare il dataset in modo da renderlo compatibile agli scopi prefissati. Nel dettaglio, modellando il problema come un Markov Decision Process, e' stato generato un nuovo dataset che permettesse di esplicitare le transizione da uno stato all'altro ed la relativa funzione di rinforzo. Chiaramente, avendo a che fare con un problema ampio e la cui soluzione dipende da un insieme di parametri soggettivi, sono stati individuati 11 attributi utili per descrivere ciascuno stato dell'MDP, successivamente ridotti a 7 dopo aver eseguito un passo di feature selection mediante l'algoritmo Iterative Feature Rank. Per quanto concerne le azioni disponibili, invece, a partire da qualunque stato le uniche due disponibili sono:'lasciare il timer invariato' e 'ridurre il timer'. Le transizioni di stato sono state percio' modellate mediante 8 variabili di ingresso (7 variabili di stato + l'azione). Il banditore d'asta, oltre a ricevere un rinforzo compatibile con una funzione di rinforzo precedentemente definita, osserva anche il nuovo stato che e' chiaramente rappresentato dai nuovi valori delle variabili di stato. Definito l'MDP ed effettuato un passo di feature selection, la policy ottima e' stata computata massimizzando la Q-function ricavata tramite l'algoritmo Fitted Q-Iteration. In realta' sono state definite due funzioni di rinforzo e sono state apprese due politiche in modo tale da confrontarne il comportamento. Si consideri che, poiche' le politiche ottenute con i passi di cui sopra sono in forma implicita, si e' reso necessario apprendere la forma esplicita (albero decisionale) mediante l'algoritmo di apprendimento supervisionato SimpleCART. Tramite lo stesso principio e' stata inferita anche la policy correntemente impiegata dal banditore d'asta e, successivamente, e' stato definito un simulatore d'asta, creando 7 modelli (uno per ciascuna variabile) sul dataset a disposizione, in modo tale da testare le politiche in un ambiente simulato. I risultati pubblicati nell'ultimo capitolo mostrano che entrambe le policy inferite risultano migliorative in un ambiente simulato rispetto a quella correntemente utilizzata dalla compagnia.