Registro:
| Documento: | Tesis de Grado |
| Título: | Cálculo de pacing equilibriums para mercados de subastas vía Programación Lineal Entera |
| Título alternativo: | Pacing equilibriums for auction markets via Integer Linear Programming |
| Autor: | Hurovich, Gustavo Martín |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Fecha de defensa: | 2020-03-02 |
| Fecha en portada: | Marzo 2020 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias Matemáticas |
| Departamento Docente: | Departamento de Matemáticas |
| Director: | Miranda Bront, Juan José |
| Jurado: | Durán, Guillermo Alfredo; Soulignac, Francisco Juan |
| Idioma: | Español |
| Palabras clave: | PUBLICIDAD ONLINE; BUDGET MANAGEMENT; PACING EQUILIBRIUM; PROGRAMACION LINEAL ENTERA; TEORIA DE JUEGOS ALGORITMICAONLINE ADVERTISING; BUDGET MANAGEMENT; PACING EQUILIBRIUM; INTEGER LINEAR PROGRAMMING; ALGORITHMIC GAME THEORY |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nMAT000856_Hurovich |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nMAT000856_Hurovich.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nMAT000856_Hurovich |
| Ubicación: | Dep.MAT 000856 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Hurovich, Gustavo Martín. (2020). Cálculo de pacing equilibriums para mercados de subastas vía Programación Lineal Entera. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nMAT000856_Hurovich |
Resumen:
En el mundo de la publicidad online, un problema fundamental es el de decidir qué anuncio mostrarle a cada usuario. Actualmente, esta asignación se realiza a través de subastas, en las cuales se generan apuestas en nombre de los anunciantes. De resultar ganador en alguna de ellas, su anuncio será el que efectivamente se le presente al usuario. Uno de los mayores inconvenientes que tiene este esquema es que si un anunciante excede su presupuesto, pierde la oportunidad de participar en subastas subsecuentes. Es por eso que surge el budget management, un conjunto de diversas estrategias para regular el gasto de cada uno de los participantes, permitiéndole ganar aquellas oportunidades que le proveen mayor utilidad. Dentro de esta categoría se encuentra el pacing multiplicativo, el cual consiste en, para cada anunciante, reducir uniformemente sus apuestas originales. Dada esa metodología, es posible pensar al mercado como un juego, en el que cada participante tiene como estrategias posibles el elegir por qué factor reducir sus apuestas, y recibe utilidad por cada ítem que logra ganar. En estos juegos se puede definir un tipo de equilibrio, al que se denomina pacing equilibrium. Aunque encontrar un equilibrio que maximice revenue o social welfare es un problema NP-Completo, se puede formular un modelo de Programación Lineal Entera Mixta que sirva para encontrar dichos equilibrios o uno arbitrario. En este trabajo analizamos propiedades teóricas de dicho modelo, así como características de los equilibrios resultantes. Presentamos la definición de instancias ajustadas para aquellas en las cuales los presupuestos son, en algún sentido, reducidos, y mostramos empíricamente que son más difíciles de resolver para este modelo. A su vez, presentamos una serie de desigualdades válidas que refuerzan el modelo y tienen un impacto positivo, permitiendo resolver instancias de tamaños más grandes.
Abstract:
In the context of online advertising, a fundamental problem involves deciding which ad to show each user. Currently, this allocation is made through auctions, on which bids are generated on behalf of advertisers. In case of winning in any of them, their ad will be the one efectively shown to the user. One of the biggest obstacles of this scheme is that if an advertiser exceeds its budget, they lose the oportunity to participate in subsequent auctions. That is why budget management emerges, a set of various strategies to adjust the pace of budget consumption over time of each of the participants, allowing them to win those opportunities that might provide them higher utility. Within this category is the multiplicative pacing, which consists in, for each advertiser, reduce uniformly its original bids. Given this methodology, it is possible to model the market as a game, where players are allowed to choose a factor to scale their bids, and receive utility for each item they win. In this games we can define a specific type of equilibrium, which is called pacing equilibrium. Even though finding a revenue-maximizing or social welfare-maximizing pacing equilibrium is an NP-Complete problem, it is possible to formulate an equivalent mixed integer linear programming model to compute these equilibriums In this thesis, we analyze theoretical properties of such model, as well as several characteristics of the resulting equilibria. We present the definition of budget-tight instances for the ones on which budgets are, in some way, small, and we show empirically that tightness of the budgets has a direct impact on the computation time to solve the instance. Moreover, we present a set of valid inequalities that reinforce the model and have a positive impact, allowing it to solve larger instances.
Citación:
---------- APA ----------
Hurovich, Gustavo Martín. (2020). Cálculo de pacing equilibriums para mercados de subastas vía Programación Lineal Entera. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nMAT000856_Hurovich
---------- CHICAGO ----------
Hurovich, Gustavo Martín. "Cálculo de pacing equilibriums para mercados de subastas vía Programación Lineal Entera". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2020.https://hdl.handle.net/20.500.12110/seminario_nMAT000856_Hurovich
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nMAT000856_Hurovich.pdf
Distrubución geográfica
