Protocolos para la asignación de recursos

Protocolos para la asignación de recursos. “Subastas”.

Por Iván Huerta Corona

CINVESTAV. Unidad Guadalajara.

Agosto del 2015.

Subastas.

•  Las subastas suelen ser una buena solución al problema de la asignación de recursos.

• Veremos diferentes tipos de subastas incluyendo single-‐good, multiunit y combinacional.

Subastas.

•  Las subastas son importantes ya que son un buen método para pujar por un bien, son utilizados en la economía, en gobiernos entre muchos otros.

•  Proporcionan un marco teórico general para los problemas de asignación de recursos entre agentes con intereses propios.

Single-‐good auctions

•  Es uno de los tipos más simples de subastas, existe una venta, un vendedor y varios potenciales compradores, cada comprador tiene su propia valoración sobre el bien subastado y cada uno quiere comprar al precio más bajo posible.

•  Estas subastas son llamadas de una sola cara, porque hay múltiples agentes de un solo lado del mercado

Single-‐good auctions.

•  Es necesario diseñar protocolos que satisfagan ciertos criterios globales deseables.

•  Por ejemplo: podríamos querer un protocolo que maximiza los ingresos esperados por el vendedor.

Familias canónicas de subastas.

•  Entre las familias más famosas se encuentran: Inglesa, japonesa, holandesa y subastas de oferta sellada.

Familia de subastas Inglesas.

•  Es quizá la subasta más conocida de las familias de subastas ya que son las utilizadas en las casas de subastas de la vieja guardia, así como en la mayoría de los sitios de subastas on-‐line.

•  En este tipo de subastas el subastador establece una partida del precio del bien, y los agentes tienen la opción de anunciar las ofertas sucesivas, cada una de ellas debe ser mayor que la oferta anterior.

•  El termino de la subasta puede variar, en algunos casos la subasta termina a una hora en específico, en otros casos termina después de un período fijo durante el cual se llevan acabo nuevas ofertas.

•  La puja final , que es la oferta que el agente ganador hizo es la más alta de la subasta y el agente debe comprar el bien por el importe de su oferta final.

Familia de subastas japonesas.

•  Es una subasta de oferta ascendente, en este tipo de subasta el subastador establece un precio inicial por el bien el cual será el punto de partida de la subasta, cada agente decide si participará en la subasta o no, es decir si está dispuesto a comprar el bien en ese precio.

•  El subastador entonces dice en voz alta aumentando sucesivamente los precios de manera regular, después de cada uno de estos anuncios los agentes deben anunciar si están aún dentro de la subasta o si se retiran.

•  Cuando un agente se retira es irrevocable, y el agente no puede volver a entrar en la subasta.

•  La subasta termina cuando hay exactamente un agente dentro de la subasta; entonces el agente debe adquirir el bien por el precio actual.

Familia de subastas holandesas.

•  En una subasta holandesa el subastador comienza con el anuncio de un alto precio y luego procede a anunciar precios inferiores sucesivamente de manera regular.

•  Los precios descienden y existe un reloj que todos los agentes pueden ver. •  La subasta termina cuando el primer agente señala el subastador pulsando un timbre y parar el reloj, el agente de señalización debe entonces comprar el bien para el que se muestra precio.

Familia de subastas de sobre sellado.

•  Primera oferta mas alta-‐ Los concursantes ponen su oferta en un sobre cerrado y todos al mismo tiempo se la entregan al subastador. Los sobres se abren y el concursante con la puja más alta gana, pagando un precio igual a la cantidad exacta ofrecida. Este modelo es muy utilizado en licitaciones públicas.

•  Segunda oferta más alta-‐ Los ofertantes entregan simultáneamente un sobre cerrado con la oferta. Los sobres se abren y la persona con la puja más alta gana, pagando un precio igual al importe exacto de la segunda oferta más alta.

Segundo precio. Subastas japonesas e inglesas.

•  Veremos ahora las subastas de segundo precio y de oferta cerrada, que es un mecanismo directo y veraz ( es decir, proporciona incentivos para que los agentes hagan una oferta a sus verdaderos valores).


Teorema 11.1.1 En una subasta de segundo precio, donde los postores tienen valores privados independientes, decir la verdad es una estrategia dominante.

La subasta de segundo precio es un caso especial del mecanismo de Groves. Por lo tanto, el teorema 11.1.1 sigue directamente del Teorema 10.4.2.


•  Este tipo de remate induce a que los agentes revelen su verdadero valor de reserva porque como se paga el valor inmediato inferior al máximo, cada agente piensa que si su valoración es la mayor de todas, puede ofrecerla porque termina pagando solo el valor de reserva del agente con una oferta inferior a él.

Primer precio. Subasta Holandesa.

•  En ambas subastas cada agente debe seleccionar una cantidad sin saber sobre las selecciones de otros agentes; el agente con la cantidad más alta gana la subasta, y debe comprar el bien por esa cantidad.

•  Subastas de primer precio requieren cada postor para enviar un mensaje al subastador, que podría ser difícil de manejar con un gran número de oferentes.

•  Subastas holandesas requieren sólo un único bit de información que se comunicará al subastador, pero requiere el subastador para transmitir los precios.


•  Desafortunadamente, a diferencia del caso de las subastas de segundo precio, aquí no tenemos el lujo de estrategias dominantes, y por lo tanto tiene que recurrir a análisis de equilibrio de Bayes-‐Nash.


•  Supongamos que los agentes tienen valoraciones privadas independientes.

•  Por otra parte, en una subasta de primer precio, actitud ante el riesgo de un agente también importa.

•  Por ejemplo, un agente con aversión al riesgo estaría dispuesto a sacrificar parte de la utilidad esperada (por el aumento de su oferta por encima de lo que un agente neutral al riesgo haría una oferta), con el fin de aumentar su probabilidad de ganar la subasta.


•  Supongamos que los agentes son neutrales al riesgo y que sus valoraciones se dibujan de manera uniforme desde algún intervalo, decimos [0, 1].

•  Vamos si denotan la oferta del jugador i, y vi denotan su verdadera valoración.

•  Así, si el jugador con i victorias, su recompensa está dada por ui = vi -‐ si; si pierde, es ui = 0.

•  Las subastas de primer precio no son compatibles con los incentivos (y por tanto, como era de esperar, no son equivalentes a las subastas de segundo precio).

Equivalencia de ingresos.

•  La equivalencia de ingresos es un concepto que indica que dadas ciertas condiciones, cualquier mecanismo de subasta que se traduce en los mismos resultados (es decir, asigna los elementos a los mismos oferentes) también tiene el mismo ingreso esperado.


•  Las hipótesis que se deben cumplir son:

•  Participantes neutrales al riesgo. (Siguen la estrategia de puja que maximiza su beneficio esperado).

•  Participantes con valoraciones independientes y privadas. •  Participantes simétricos. (siguen la misma función de distribución).

•  Participantes sin restricciones presupuestarias.


•  Si bien es cierto que cumpliéndose las supracitadas hipótesis, todos los modelos de subasta aportarían el mismo ingreso esperado, la varianza en todos los modelos no es la misma.

Actitud al riesgo.

•  La actitud de riesgo de un agente puede ser entendida como la descripción de su preferencia entre un pago seguro y una apuesta con el mismo valor esperado.

•  (Agentes adversos al riesgo prefieren lo seguro; agentes neutrales al riesgo son indiferentes; agentes buscando por riesgo prefieren apostar.)

Actitud al riesgo.

•  Las variaciones en los pagos de los licitantes son mayores en las subastas de segundo precio de lo que son en las subastas de primer precio, ya que el primero depende de los dos más altos sorteos de la distribución de valoración, mientras que el segundo depende de la más alta . Sin embargo, estos pagos tienen la misma expectativa en ambas subastas. Por lo tanto, un vendedor de aversión al riesgo preferiría celebrar una subasta de primer precio, mientras que un vendedor de búsqueda de riesgo preferiría celebrar una subasta de segundo precio.

Variaciones de la subasta.

•  En esta sección consideramos tres variaciones sobre nuestro modelo de subasta.

•  En primer lugar, consideramos que la subasta inversa, en la que un comprador acepta las ofertas de un conjunto de vendedores.

•  En segundo lugar, se discute el efecto de los costes de entrada en estrategias de equilibrio.

•  Por último, consideramos subastas con números inciertos de postores.

Subastas inversas.

•  Hasta ahora, hemos considerado las subastas en las que hay un vendedor y un conjunto de compradores. ¿Qué hay de lo contrario: un entorno en el que hay un comprador y un conjunto de vendedores?

Subastas inversas.

•  Esto es lo que ocurre cuando un comprador se involucra en una solicitud de cotización (RFQ). En términos generales, esto se le llama una subasta inversa, ya que en su variedad a viva voz este escenario implica que descienden los precios en lugar de ascender.

Subastas inversas.

•  Resulta que todo lo que hemos dicho sobre las subastas también se aplica para volver subastas verso. Subastas inversas son simplemente las subastas en la que sustituimos la palabra "vendedor" de "comprador”.

Subastas con costos de entrada.

•  Esta es la introducción de un coste de entrada a una subasta. Imagine que una subasta de primer precio cuesta $ 1 a asistir. ¿Cómo deben los oferentes decidir si debe o no asistir?.

Subastas con costos de entrada. (Segundo precio).

•  Para decidir si participar, el licitante deberá evaluar su ganancia esperada de la participación. Esto significa que la estrategia de equilibrio en estas subastas ya no depende de la distribución de las valoraciones de otros agentes y del número de estos agentes. La buena noticia es que, una vez que han decidido hacer una oferta, se mantiene un equilibrio para los licitadores a pujar con sinceridad.

Subastas con costos de entrada. (Primer precio).

•  El licitante deberá hacer una evaluación entre su ganancia esperada de la participación en la subasta y el costo de hacerlo.

•  Una complicación es que no se sabe el número de participantes que habrá en la subasta.

•  Y eso, a su vez, hace que sea más difícil determinar la ganancia esperada de la participación en el primer lugar del agente.

Subastas con número incierto oferentes.

•  Nuestro modelo estándar de subastas ha presumido que el número de oferentes es de conocimiento común.

•  Sin embargo, puede darse el caso de que los licitadores no están seguros de que el número de competidores que se enfrentan, sobre todo en una subasta de oferta sellada o en internet.

Subastas con número incierto oferentes

•  Hay que tener cuidado con el hecho de que los licitadores podrán actualizar sus creencias previas sobre el número total de participantes por el condicionamiento en el hecho de su propia selección, y por lo tanto pueden llevar a una situación en la que las creencias licitantes sobre el número de participantes puede ser asimétrica.

Subastas con número incierto oferentes.

•  La equivalencia de ingresos no depende del número de agentes.

•  La estrategia dominante para la licitación en las subastas de segundo precio no depende del número de postores en la subasta.

•  Lo mismo no puede decirse de las subastas de primer precio.

Subastas óptimas.

•  Hasta ahora, en nuestro análisis teórico hemos considerado sólo aquellos subastas en las que el bien se asigna al mejor postor y el vendedor impone precio sin reserva.

•  El licitador puede estar dispuesto a correr el riesgo de no poder vender el bien, incluso cuando hay un comprador interesado, y, además, podría estar dispuesto a veces a vender a un comprador que no hizo la oferta más alta, con el fin de animar a los altos postores para hacer una oferta más agresiva.

Subastas óptimas.

• Mecanismos que están diseñados para maximizar los ingresos esperados del vendedor se conocen como las subastas óptimas.

•  Nosotros suponemos que el vendedor conoce la distribución de la que se extrae la valoración de cada licitante individual y por lo tanto es capaz de distinguir los postores fuertes de los licitantes débiles.

Subastas óptimas.

Donde: Vi es la valoración que hace cada solicitante. F(v) es la función de probabilidad acumulada. F(v) es la función de probabilidad asumida.

Estas declaraciones se utilizan para calcular una valoración virtual para cada agente. El bien se vende al agente i cuya virtuales valoración ψi (vi) es el más alto, siempre y cuando este valor es positivo. Si la valoración virtual de cada agente es negativo, el vendedor mantiene el bien y alcanza ingresos de cero.

Subastas óptimas.

•  Este tipo de subastas no son muy utilizadas en la práctica

•  El problema es que no son libres detalle: requieren al vendedor para incorporar información sobre las distribuciones de la valoración de los licitantes en el mecanismo.

Colusión.

•  Puesto que hemos visto que un subastador puede aumentar su ingreso esperado por el aumento de la competencia entre los oferentes, no es de extrañar que los licitadores, por el contrario, pueden reducir sus pagos previstos para el subastador al reducir la competencia entre ellos.

•  Esta cooperación entre los postores se llama colusión.

Colusión.

•  Curiosamente, también es notoriamente difícil para los agentes de lograr. La razón es conceptualmente similar a la situación que enfrentan los agentes que juegan el dilema del prisionero.

Colusión.

•  Supongamos que los compradores han llegado a un acuerdo. Han elegido un ganador que es el que más valora el objeto, han decidido qué estrategia debe seguir éste y se han comprometido a no pujar. Este tipo de acuerdos deben ser inmunes a desviaciones, puesto que en caso contrario, si algún individuo gana desviándose del acuerdo, lo hará.

Colusión.

•  Empezamos con la subasta holandesa. Al individuo designado como ganador se le indica que pare la subasta a un precio aproximadamente igual al precio mínimo del vendedor. Pero está claro que los demás, que deberían permanecer callados, pueden ganar parando antes la subasta. •  Por tanto, los individuos tienen incentivos a desviarse. De otra forma, no pueden

ser castigados por desviarse del acuerdo.

•  En el caso de la subasta al segundo precio, la estrategia propuesta es que el que más valora el objeto puje su valoración y que nadie más puje. Se llevará el objeto por un precio muy bajo. Nadie puede violar el acuerdo porque tendría que pujar más que la valoración más alta.

Subastas múltiples.

•  Hemos considerado hasta ahora el problema de la venta de un solo bien a un postor ganador. En la práctica, a menudo habrá más de un bien a asignar, y diferentes bienes puede terminar yendo a diferentes licitadores.

Subastas múltiples. Licitación a sobre sellado.

•  En primer lugar, tenga en cuenta las reglas de pago. Si hay tres artículos a la venta, y cada una de las tres mejores ofertas pide una sola unidad, entonces cada oferta va a ganar una bien.

•  Bajo la regla de fijación de precios uniforme , todos los ganadores pagan la misma cantidad; esto es por lo general ya sea el más alto entre las ofertas perdedoras o la más baja entre las ofertas ganadoras.

Subastas múltiples. Licitación a sobre sellado.

•  En caso de empate puede ser complicado cuando los postores pujar todos o nada.

•  Por ejemplo, considere una subasta por 10 unidades en las que las ofertas más altas son los siguientes, todos ellos de todo o nada: 5 unidades por $ 20 / unidad, 3 unidades por $ 15 / unidad, 5 unidades por $ 15 / unidad, y 1 unidad por $ 15 / unidad. Presumiblemente, la primera oferta debe ser satisfecha, así como dos de los tres restantes, pero que? Aquí uno ve diferentes reglas desempate por cantidad (ofertas más grandes ganan más de los más pequeños), por el tiempo (ofertas anteriores ganan sobre las ofertas posteriores), y sus combinaciones.

Subastas múltiples. Subasta Inglés.

•  Diseñadores de la subasta aún enfrentan la elección de si se debe tratar como ofertas de todo o nada, o divisible.

•  Considere el siguiente ejemplo, en el que hay un total de 10 unidades disponibles, y dos ofertas: una para 5 unidades a $ 1 / unidad, y una para 5 unidades a $ 4 / unidad. ¿Cuál es la siguiente oferta más baja aceptable? Intuitivamente, depende de la cantidad, una oferta por 3 unidades a $ 2 / unidad puede ser satisfecha, pero una oferta por 7 unidades a $ 2 / unidad no puede. Este problema se evita si la última oferta es divisible, y por lo tanto puede ser parcialmente satisfechas.

Subastas múltiples. Subasta japonés.

•  Ahora después de cada aumento de precios cada agente dice un número en lugar de la simple declaración de entrada / salida, lo que significa que el número de unidades que está dispuesto a comprar al precio actual.

•  Una restricción común es que el número debe disminuir con el tiempo; el agente no puede pedir comprar a un precio más alto de lo que hizo a un precio inferior.

•  La subasta termina cuando la oferta es igual o superior a la demanda.

Subastas múltiples. Subasta holandesa.

•  El vendedor dice por precios unitarios descendientemente , y los agentes deben aumentar sus señales con la cantidad que desean comprar.

•  Si eso no es toda la cantidad disponible, la subasta continúa. •  Aquí hay varias opciones, el precio puede continuar a descendiendo desde el nivel actual, se puede poner a un porcentaje fijo sobre el precio actual, o se puede restablecer al alto precio inicial.

Subastas de posición.

•  En las subastas de posición nunca se asignan más de un elemento por cada postor y piden postores para especificar sus preferencias mediante un único número real.

•  El ejemplo de motivación para estas subastas es la venta de anuncios clasificados en una página de resultados de búsqueda. (Por esta razón, estas subastas también se llaman las subastas de búsqueda patrocinados.)

Subastas de posición.

•  Dado que los bienes no son idénticos, no podemos considerar que sean varias unidades de un mismo bien.

•  En estas subastas, los motores de búsqueda ofrecen un conjunto de palabras clave específicas.

•  Ranuras" -‐normalmente una lista en la parte derecha de una página de resultados de búsqueda para la venta a los anunciantes interesados. Las ranuras se consideran más valiosas cuanto más cerca están de la parte superior de la página, ya que esto afecta a la probabilidad de que se ha pulsado por un usuario.

Subastas de posición

•  Los anunciantes pujan sobre palabras clave. •  Cada vez que un usuario realiza una búsqueda para una palabra clave en el que los anunciantes han pujar, se celebra una subasta.

•  El resultado de esta subasta es una decisión de que va a aparecer en la página de resultados de búsqueda y en qué orden.

•  Los anunciantes están obligados a pagar sólo si un usuario hace clic en su anuncio.

Subastas de posición

•  Al igual que en el caso de las subastas tradicionales, cuanto mayor sea el número de anunciantes que pujen por aparecer en sus páginas, mayor será la competencia por los bloques de anuncios y más ingresos podrá obtener. Cuantas menos restricciones aplique a los anuncios que pueden mostrarse en su sitio, más anuncios podrá ofrecer nuestro sistema, lo que contribuirá a incrementar sus ingresos.

•  Una vez que dispongamos de un grupo de anuncios aptos, la subasta de anuncios determina cuáles de ellos se mostrarán en las páginas y cuánto pagará cada anunciante. La clasificación de estos anuncios se calcula combinando su puja de CPC y su nivel de calidad. Puesto que los anuncios se clasifican según el ranking obtenido, un anunciante que haya realizado una puja de CPC baja, pero que tenga un nivel de calidad elevado, puede ganar la subasta a otro cuya puja de CPC sea superior, pero cuyos anuncios no ofrezcan una buena experiencia de usuario y tengan pocas posibilidades de recibir clics. Asimismo, en este sistema dinámico de subasta el precio que el anunciante ganador paga cambia de una subasta a otra, y de una impresión de anuncio a otra, en función del nivel de calidad del anunciante para esa página y de la competencia que exista en la subasta.

•  Texto tomado de : https://support.google.com/adsense/answer/160525?hl=es#2.

Intercambios

•  Hasta ahora, hemos estudiado un solo bien, multiunit y subastas combinatorias. A pesar de la gran variedad dentro de estas familias, que aún no han agotado el espacio de las subastas. Ahora discutiremos brevemente una última categoría importante de subastas, estos son los intercambios.

Intercambios.

•  subastas en las que los agentes son capaces de actuar como los compradores y vendedores

Intercambios. Subastas de dos caras.

•  En las subastas de dos caras, también conocidas como las subastas dobles, hay muchos compradores y vendedores.

•  Subasta continua doble (CDA). •  Subasta periódica doble.


•  Cada oferta se compone de un precio y cantidad, cuando la cantidad es positiva (lo que significa "comprar” ) o negativo (significa "vender").

•  No hay restricción ni en precio ni cantidad.

•  Las ofertas recibidas se ponen en un repositorio central. •  Tan pronto como se reciba la oferta, se hace un intento para que coincida con una o más ofertas en el libro de órdenes.


•  Por ejemplo, una nueva orden de venta de 10 unidades puede ser emparejada con una oferta ya existente de compra para 4 unidades y otra oferta para comprar 6 unidades, siempre y cuando tanto el precio de compra sea más alto que el precio de venta.


•  En los casos de coincidencias parciales, las unidades restantes (ya sea de la nueva oferta o de una de las ofertas para libros) se pusieron de nuevo en la cartera de pedidos.

•  Por ejemplo, si la nueva orden de venta es de 13 unidades y las únicas ofertas de compra de la cartera de pedidos con un precio más alto son los que describen (una oferta de compra de 4 unidades y otra oferta para comprar 6 unidades), dos operaciones están dispuestas uno para 4 unidades, y una para 6 y los restantes 3 unidades de la nueva oferta se ponen en la cartera de pedidos como una orden de venta.


•  CDA. •  En una subasta doble, todos los participantes envían sus pujas y ofertas en una única ronda y tras finalizar este período la cámara de compensación establece todos los bienes a intercambiar y el precio de venta.

•  En una subasta doble continua, se permite vender y comprar bienes a lo largo de diferentes rondas


•  Subasta periódica doble. •  En este caso, esto se hace

simplemente mediante la clasificación de las ofertas de venta en orden ascendente, las ofertas de compra en orden descendente, y encontrar el punto en el que la oferta satisface la demanda.

Mercados de predicción.

•  Los mercados de predicciones son mercados especulativos, es decir, de apuestas, creados con el objetivo de hacer predicciones.

•  Es una subasta de doble cara que se utiliza para las creencias agentes agregados "en lugar de bienes de la asignación.

•  Por ejemplo, un mercado de este tipo podría ser utilizado para evaluar posibilidades de diferentes candidatos en una elección presidencial próxima.


•  Para configurar un mercado de predicción, el diseñador de mercado establece contratos (C1,..., Ck), donde cada Ci contrato es un compromiso de pago al portador $1 si el candidato gana las elecciones, y $ 0 en caso contrario.

•  El diseñador de mercado no vende. En su lugar, simplemente abre su mercado, y permite a los agentes interesados ��a ambos comprar y vender contratos con los demás.


•  Si un postor cree que tiene información acerca de la elección que otros licitadores no tienen, y por lo tanto cree que tiene la probabilidad de ganar y es mayor que el precio de venta actual del contrato Ci , entonces va a querer comprar contratos.

•  Por el contrario, si un postor cree que la verdadera probabilidad de ganar es menor que el precio actual, él va a querer vender contratos.


•  Esto es similar a la idea de que el precio de las acciones de una empresa en un mercado de valores reflejará la creencia del mercado sobre la rentabilidad futura de la empresa.


•  Los individuos que compran barato y venden caro se ven así recompensados por mejorar la capacidad de predicción del mercado, mientras que aquellos que compran caro y venden barato son castigados por deteriorar la capacidad predictiva del mercado.

Mercados de predicción. (una mejor explicación).

•  Los denominados mercados de predicción funcionan como mercados virtuales, foros en los que los participantes dan su opinión sobre la probabilidad de que ocurra un evento futuro a través de un sistema de incentivos a las respuestas. Lo que se cotiza son contratos que se comprometen a pagar una cantidad en función de un determinado resultado, con lo que los precios que crecen o disminuyen, en función del número de usuarios que apuestan por una opción, se pueden interpretar como la probabilidad de que ocurra un determinado evento.

•  Texto tomado de: http://www.eldiario.es/alternativaseconomicas/Mercados-‐prediccion-‐politica_6_250984906.html

Referencias.

• MULTIAGENT SYSTEMS

•  Algorithmic, Game-‐Theoretic, and Logical Foundations

•  Yoav Shoham ,Stanford University

•  Kevin Leyton-‐Brown University of British Columbia

Engineering

Protocolos para la asignación de recursos