Introducci´ on Modelo Ejemplos Oferta residual Ejemplos Equilibrio: Subasta de Vickrey Subasta de Ausubel

Introducci´on a las Subastas de M´ultiples Unidades Alvaro J. Riascos Villegas

Abril 16 de 2013

Universidad de los Andes y Quantil | Matem´ aticas Aplicadas

Subastas M´ ultiples Objetos

Introducci´ on Modelo Ejemplos Oferta residual Ejemplos Equilibrio: Subasta de Vickrey Subasta de Ausubel

Contenido 1

Introducci´on

2

Modelo

3

Ejemplos

4

Oferta residual

5

Ejemplos

6

Equilibrio: Subasta de Vickrey

7

Subasta de Ausubel

Universidad de los Andes y Quantil | Matem´ aticas Aplicadas

Subastas M´ ultiples Objetos

Introducci´ on Modelo Ejemplos Oferta residual Ejemplos Equilibrio: Subasta de Vickrey Subasta de Ausubel

Introducci´on

Los principales formatos son: 1 2 3

Discriminatoria (cerrada) y Holandesa (abierta) Uniforme (cerrada) y Inglesa (abierta) Vickrey (cerrada) y Ausubel (abierta)

Universidad de los Andes y Quantil | Matem´ aticas Aplicadas

Subastas M´ ultiples Objetos

Introducci´ on Modelo Ejemplos Oferta residual Ejemplos Equilibrio: Subasta de Vickrey Subasta de Ausubel

Contenido 1

Introducci´on

2

Modelo

3

Ejemplos

4

Oferta residual

5

Ejemplos

6

Equilibrio: Subasta de Vickrey

7

Subasta de Ausubel

Universidad de los Andes y Quantil | Matem´ aticas Aplicadas

Subastas M´ ultiples Objetos

Introducci´ on Modelo Ejemplos Oferta residual Ejemplos Equilibrio: Subasta de Vickrey Subasta de Ausubel

Modelo Consideramos subastas simult´aneas de m´ ultiples unidades del mismo bien. Suponemos que no hay complementaridades entre los objetos: La valoraci´on marginal de ganar un segundo objeto es menor que la del primer objeto. Vamos a considerar los tres formatos m´as importantes para subastar K objetos id´enticos: discriminatoria, Vickrey y uniforme. Cada jugador debe mandar K ofertas bki que satisfacen i . b1i ≥ b2i ≥ ..., ≥ bK bji es la disponibilidad de i a pagar por la j ´esima unidad. Sea B i el conjunto de todas las ofertas v´alidas de i. B i ⊂ RK +. Universidad de los Andes y Quantil | Matem´ aticas Aplicadas

Subastas M´ ultiples Objetos

Modelo KI Sea c : RKI + → R+ el vector ordenado (de mayor a menor) de las I × K ofertas. K (I −1)

Sea c −i : RKI el vector de K × (I − 1) de ofertas + → R+ ordenado (de mayor a menor) que enfrenta i. ck−i es la k-´esima oferta m´as alta que enfrenta i. Regla de asignaci´ on: Si i tiene exactamente k ≤ K de la K ofertas m´as altas (entonces se le asigan k objetos), es decir si i bki > cK−i−k+1 and bk+1 < cK−i−k , y definimos:



i q i (b) = q i b1i , ..., q i bki , ...q i bK

donde q i bji = 1 ∀j ≤ k de lo contrario q i bji = 0 En caso de empate por una unidad, se asigna con la misma probabilidad a los agentes que empatan.

Modelo

Esta estrutura es com´ un a los tres tipos de subastas que vamos a considerar. La diferencia entre ellas se debe a la regla de asignaci´on (en particular, la componente que determina el pago esperado de cada agente). En la subasta dsicriminatoria si el agente i gana exactamente ki P k i unidades entonces paga, bki . k=1

Obs´ervese que cuando K = 1 es la subasta al primer precio.

Modelo En la subasta uniforme todas las unidades son vendidas al precio que agota la oferta y la demanda (precio de equilibrio). Suponemos que este precio es el m´as alto perdedor Puesto que i gana exactamente k i > 0 unidades si y s´olo si: bki i > cK−i−k i +1 y bki i +1 < cK−i−k i Entonces la oferta m´as alta perdedora es: n o −i p(b) = m´ax bki i +1 , bK i −k +1 Luego cada agente paga por cada unidad ganada p(b). Obs´ervese que cuando K = 1 ´esta se reduce al a subasta al segundo precio. Sin embargo NO es una generalizaci´on apropiada a m´ ultiples unidades.

Modelo

En la subasta de Vickrey i gana exactamente k i > 0 unidades si y s´olo si: bki i > cK−i−k i +1 y bki i +1 < cK−i−k i y paga por la k ´esima unidad cK−i−k i +k . Luego su pago total es: i

k X

cK−i−k i +k

k=1

La subasta de Vickrey es la generalizaci´ on apropiada de la subasta al segundo precio.

Introducci´ on Modelo Ejemplos Oferta residual Ejemplos Equilibrio: Subasta de Vickrey Subasta de Ausubel

Contenido 1

Introducci´on

2

Modelo

3

Ejemplos

4

Oferta residual

5

Ejemplos

6

Equilibrio: Subasta de Vickrey

7

Subasta de Ausubel

Universidad de los Andes y Quantil | Matem´ aticas Aplicadas

Subastas M´ ultiples Objetos

Introducci´ on Modelo Ejemplos Oferta residual Ejemplos Equilibrio: Subasta de Vickrey Subasta de Ausubel

Ejemplos Example Supongamos que K = 6 y tenemos 3 agentes participando. Supongamos que las ofertas son: b 1 = (50, 47, 40, 32, 15, 5) b 2 = (42, 28, 20, 12, 7, 3) b 3 = (45, 35, 24, 14, 9, 6) Denotamos por c el vector ordenado de mayor a menor de todas las ofertas: c = (50, 47, 45, 42, 40, 35, 32, ...) 1

1

3

Universidad de los Andes y Quantil | Matem´ aticas Aplicadas

2

1

3

Subastas M´ ultiples Objetos

Ejemplos

Example Ofertas y ordenamiento: b 1 = (50, 47, 40, 32, 15, 5) b 2 = (42, 28, 20, 12, 7, 3) b 3 = (45, 35, 24, 14, 9, 6) c = (50, 47, 45, 42, 40, 35, 32, ...) 1

1

3

2

1

3

Las seis m´as altas son las ganadoras. Por lo tanto el agente 1 gana 3 unidades, el agente 2 gana 1 unidad y el agente 3 gana 2 unidades. El precio de cierre es 32 (el m´as alto perdedor).

Introducci´ on Modelo Ejemplos Oferta residual Ejemplos Equilibrio: Subasta de Vickrey Subasta de Ausubel

Contenido 1

Introducci´on

2

Modelo

3

Ejemplos

4

Oferta residual

5

Ejemplos

6

Equilibrio: Subasta de Vickrey

7

Subasta de Ausubel

Universidad de los Andes y Quantil | Matem´ aticas Aplicadas

Subastas M´ ultiples Objetos

Oferta residual

Otra forma de determinar el precio de cierre es utilizando la oferta residual que enfrenta el agente i,     X d j (p), 0 s −i (p) = m´ax K −   j6=i

El precio de cierre (el m´as alto perdedor) se puede definir como el m´as alto tal que: s −i (p) < d i (p)

Introducci´ on Modelo Ejemplos Oferta residual Ejemplos Equilibrio: Subasta de Vickrey Subasta de Ausubel

Contenido 1

Introducci´on

2

Modelo

3

Ejemplos

4

Oferta residual

5

Ejemplos

6

Equilibrio: Subasta de Vickrey

7

Subasta de Ausubel

Universidad de los Andes y Quantil | Matem´ aticas Aplicadas

Subastas M´ ultiples Objetos

Introducci´ on Modelo Ejemplos Oferta residual Ejemplos Equilibrio: Subasta de Vickrey Subasta de Ausubel

Ejemplos El agente gana exactamente k i unidades cuando: bki i

> cK−i−k i +1

bki i +1 < cK−i−k i Cuando bki i = cK−i−k i +1 hay empate entre dos agentes por las u ´ltimas unidades. El precio de corte se puede escribir como: n o  p = m´ax bki i +1 , cK−i−k i +1 = m´ax bki i +1 i

Universidad de los Andes y Quantil | Matem´ aticas Aplicadas

Subastas M´ ultiples Objetos

Ejemplos Example En el ejemplo anterior: c3−1 = 35, c4−1 = 28 y el agente 1 gana exactamente 3 unidades porque: b3−1 = 40 > c4−1 = 28 b4−1 = 32 < c3−1 = 35 y el precio de cierre es:  p = m´ax b41 , c4−1 = m´ax {32, 28} = 32

Ejemplos

Example El pago en la subasta de Vickrey para el agente i es: c6−i + c5−i + c4−i = b32 + b33 + b22

Introducci´ on Modelo Ejemplos Oferta residual Ejemplos Equilibrio: Subasta de Vickrey Subasta de Ausubel

Contenido 1

Introducci´on

2

Modelo

3

Ejemplos

4

Oferta residual

5

Ejemplos

6

Equilibrio: Subasta de Vickrey

7

Subasta de Ausubel

Universidad de los Andes y Quantil | Matem´ aticas Aplicadas

Subastas M´ ultiples Objetos

Introducci´ on Modelo Ejemplos Oferta residual Ejemplos Equilibrio: Subasta de Vickrey Subasta de Ausubel

Subasta de Vickrey En la subasta de Vickrey es un equilibrio en estrategias dominantes (d´ebil) revelar la verdadera valoraci´on, b V (x1 , ..., xn ) = (x1 , ..., xn ). En particular, la subasta de Vickrey asigna de forma eficiente. Como veremos en la demostraci´ on el argumento no depende de que los agentes sean sim´etricos. Obs´ervese que el pago del agente no depende de su oferta sino solamente de b −i y del n´ umero de unidades ganadas. Sea k i el n´ umero de unidades que el gana cuando oferta b i y los dem´as ofertan b −i . Universidad de los Andes y Quantil | Matem´ aticas Aplicadas

Subastas M´ ultiples Objetos

Subasta de Vickrey

Un agente nunca ofertar´a por ninguna unidad por encima de su valoraci´on. Supongamos que por la unidad k el agente oferta m´as (escojamos k como el mayor n´ umero para el que esto pasa); considere la oferta que se diferencia de la anterior solo en la unidad k en donde es la verdadera valoraci´ on. Con esta oferta el gana el mismo n´ umero de unidades o menos. Si gana el mismo entonces es indiferente entre ambas. Si gana menos quiere decir que xki ≤ cK−i−k+1 y k = k i , es decir k era su u ´ltima ganadora antes de cambiar la oferta (si i k < k entonces no puede ser que pierda la unidade k pero gane la k + 1).

Subasta de Vickrey

El excedente por las unidades que gana sigue siendo el mismo. Ahora, para la unidad k i deja de percibir un excedente de xki i − cK−i−k i +1 ≤ 0. Luego en efecto al ganar menos unidades aumenta su excedente. La idea del argumento anterior se extiende f´acilmente para demostrar que ofertar sinceramente es un estrategia dominante (dado b −i suponga que al ofertar sinceramente el agente gana k i unidades y ahora estudiar el caso en que uno se desvia de esa estrategia).

Subasta de Vickrey

La subasta de Vickrey puede resultar en asignaciones ¨ınjustas”. Supongamos que K = 2, x 1 = (10, 6), x 2 = (9, 2). En este caso, cada agente se lleva una unidad.

Introducci´ on Modelo Ejemplos Oferta residual Ejemplos Equilibrio: Subasta de Vickrey Subasta de Ausubel

Contenido 1

Introducci´on

2

Modelo

3

Ejemplos

4

Oferta residual

5

Ejemplos

6

Equilibrio: Subasta de Vickrey

7

Subasta de Ausubel

Universidad de los Andes y Quantil | Matem´ aticas Aplicadas

Subastas M´ ultiples Objetos

Introducci´ on Modelo Ejemplos Oferta residual Ejemplos Equilibrio: Subasta de Vickrey Subasta de Ausubel

Subasta de Ausubel

Es una subasta alternativa a la inglesa de precio ascendente. Comenzando con un precio muy bajo p = p0 , s −i (p0 ) = 0. La siguiente ronda p = p1 y a´ un s −i (p1 ) = 0. El proceso continua hasta que por primera vez, en la ronda n1 , para alg´ un i1 , s −i1 (pn1 ) > 0. El agente i1 gana las −i primeras s 1 (pn1 ) unidades y paga pn1 por unidad. Si la condici´on se cumple para varios agentes, a cada uno se le da las unidades correpondientes.

Universidad de los Andes y Quantil | Matem´ aticas Aplicadas

Subastas M´ ultiples Objetos

Subasta de Ausubel

El proceso continua hasta que por la primera vez, en la ronda n2 , para alg´ un agente i2 , s −i2 (pn2 ) > s −i1 (pn1 ) . El agente i2 gana las primeras s −i2 (pn2 ) − s −i1 (pn1 ) unidades y paga pn2 por unidad. Si la condici´ on se cumple para varios agentes, a cada uno se les da las unidades correpondientes.