Subasta doble

Proceso de compra y venta de bienes

Una subasta doble es un proceso de compra y venta de bienes con múltiples vendedores y múltiples compradores. ^[1] Los compradores potenciales presentan sus ofertas y los vendedores potenciales presentan sus precios de venta a la institución del mercado, y luego la institución del mercado elige un precio p que vacía el mercado: todos los vendedores que pidieron menos de p venden y todos los compradores que ofrecieron más de p compran a este precio p . Los compradores y vendedores que ofertan o piden exactamente p también están incluidos. Un ejemplo común de una subasta doble es la bolsa de valores .

Además de su interés directo, las subastas dobles recuerdan a la subasta walrasiana y se han utilizado como herramienta para estudiar la determinación de los precios en los mercados ordinarios. Una subasta doble también es posible sin ningún intercambio de moneda en el comercio de trueque . Una subasta doble de trueque es una subasta en la que cada participante tiene una demanda y una oferta que consisten en múltiples atributos y no hay dinero involucrado. ^[2] Para el modelado matemático del nivel de satisfacción se utiliza la distancia euclidiana , donde la oferta y la demanda se tratan como vectores.

Un ejemplo simple de una subasta doble es un escenario de comercio bilateral , en el que hay un solo vendedor que valora su producto como S (por ejemplo , el costo de producir el producto) y un solo comprador que valora ese producto como B.

Análisis económico

Desde la perspectiva de un economista, el problema interesante es encontrar un equilibrio competitivo : una situación en la que la oferta es igual a la demanda.

En el escenario de comercio bilateral simple, si B ≥ S entonces cualquier precio en el rango [ S , B ] es un precio de equilibrio, ya que tanto la oferta como la demanda son iguales a 1. Cualquier precio por debajo de S no es un precio de equilibrio ya que hay un exceso de demanda, y cualquier precio por encima de B no es un precio de equilibrio ya que hay un exceso de oferta. Cuando B < S , cualquier precio en el rango ( B , S ) es un precio de equilibrio, ya que tanto la oferta como la demanda son iguales a 0 (el precio es demasiado alto para el comprador y demasiado bajo para el vendedor).

En una subasta doble más general, en la que hay muchos vendedores, cada uno de los cuales posee una sola unidad, y muchos compradores, cada uno de los cuales quiere una sola unidad, se puede encontrar un precio de equilibrio utilizando el orden natural de los compradores y vendedores:

Ordenamiento natural

• Ordene a los compradores en orden decreciente de su oferta: b ₁ ≥ b ₂ ≥...≥ b _n .
• Ordene a los vendedores en orden creciente de su oferta: s ₁ ≤ s ₂ ≤...≤ s _n .
• Sea k el índice más grande tal que b _k ≥ s _k (el "índice de equilibrio").

Todo precio en el rango [max( s _k , b _k+1 ),min( b _k , s _k+1 )] es un precio de equilibrio, ya que tanto la demanda como la oferta son k . Es más fácil ver esto considerando el rango de precios de equilibrio en cada uno de los 4 casos posibles (nótese que por definición de k , b _k+1 < s _k+1 ):

Análisis de teoría de juegos

Una subasta doble puede analizarse como un juego. Los jugadores son compradores y vendedores. Sus estrategias son precios de oferta para los compradores y precios de venta para los vendedores (que dependen de las valoraciones de los compradores y vendedores). Los pagos dependen del precio de la transacción (determinado por el subastador) y de la valoración de un jugador. El problema interesante es encontrar un equilibrio de Nash , una situación en la que ningún comerciante tiene un incentivo para cambiar unilateralmente su precio de oferta/venta.

Consideremos el escenario de comercio bilateral, en el que el comprador presenta una oferta de b y el vendedor presenta s .

Supongamos que un subastador fija el precio de la siguiente manera:

• Si s > b entonces no se produce ningún intercambio (el vendedor quiere más de lo que paga el comprador);
• Si s ≤ b entonces p =( b + s )/2.

La utilidad del comprador es:

• 0 si s > b ;
• Bp si s ≤ b (donde B es el valor real del comprador).

La utilidad del vendedor es:

• 0 si s > b ;
• pS si s ≤ b (donde S es el valor real del vendedor).

En un caso de información completa cuando las valoraciones son de conocimiento común para ambas partes, se puede demostrar que el continuo de equilibrios de Nash eficientes de estrategia pura existe con Esto significa que, si B>S , no habrá ningún equilibrio en el que ambos jugadores declaren sus valores verdaderos: o el comprador podrá ganar declarando un valor más bajo, o el vendedor podrá ganar declarando un valor más alto. ${\displaystyle b=s=p\in [B,S].}$

En un caso de información incompleta (información asimétrica), un comprador y un vendedor conocen únicamente sus propias valoraciones. Supongamos que estas valoraciones se distribuyen uniformemente en el mismo intervalo. Entonces se puede demostrar que dicho juego tiene un equilibrio de Nash bayesiano con estrategias lineales. Es decir, existe un equilibrio cuando las ofertas de ambos jugadores son funciones lineales de sus valoraciones. También genera mayores ganancias esperadas para los jugadores que cualquier otro equilibrio de Nash bayesiano (véase el teorema de Myerson-Satterthwaite ).

Diseño de mecanismos

¿Cómo debe determinar el subastador el precio de venta? Un mecanismo ideal cumpliría las siguientes características:

1. Racionalidad individual (RI): ninguna persona debería perder por participar en la subasta. En particular, para cada comprador: p ≤ B , y para cada vendedor: p ≥ S .

2. El presupuesto equilibrado (PE) se presenta en dos variantes:

• Presupuesto fuerte y equilibrado (SBB): todas las transferencias monetarias deben realizarse entre compradores y vendedores; el subastador no debe perder ni ganar dinero.
• Presupuesto equilibrado débil (WBB): el subastador no debería perder dinero, pero puede ganar dinero.

3. Compatibilidad de incentivos (CI), también llamada veracidad o compatibilidad de estrategias : también se presenta en dos variantes (cuando la CI no calificada generalmente significa la versión más fuerte):

• La noción más fuerte es la de compatibilidad de incentivos entre estrategia dominante (DSIC), que significa que informar el valor real debería ser una estrategia dominante para todos los jugadores. Es decir, un jugador no debería poder obtener ganancias espiando a otros jugadores e intentando encontrar una declaración "óptima" que sea diferente de su valor real, independientemente de cómo jueguen los demás jugadores.
• El concepto más débil es el de compatibilidad de incentivos en el equilibrio de Nash (NEIC), que significa que existe un equilibrio de Nash en el que todos los jugadores informan sus verdaderas valoraciones. Es decir, si todos los jugadores excepto uno son veraces, es mejor que el jugador restante también lo sea.

4. Eficiencia económica (EE): el bienestar social total (la suma de los valores de todos los participantes) debe ser el mejor posible. En particular, esto significa que, una vez finalizado todo el intercambio, los bienes deben estar en manos de quienes más los valoran.

Lamentablemente, no es posible cumplir todos estos requisitos en el mismo mecanismo (véase el teorema de Myerson-Satterthwaite ), pero hay mecanismos que satisfacen algunos de ellos.

Mecanismo medio

El mecanismo descrito en la sección anterior se puede generalizar a n jugadores de la siguiente manera.

• Ordene a los compradores y vendedores en el orden natural y encuentre el índice de equilibrio k .
• Establezca el precio en el promedio de los k valores: p = ( b _k + s _k )/2.
• Deje que los primeros k vendedores vendan el bien a los primeros k compradores.

Este mecanismo es:

• IR - porque según el ordenamiento, los primeros k jugadores valoran cada artículo como mínimo p y los primeros k vendedores valoran cada artículo como máximo p .
• SBB - porque todas las transferencias monetarias son entre compradores y vendedores.
• EE - porque los n artículos están en manos de los n jugadores que más los valoran.
• No IC - porque el comprador k tiene un incentivo para informar un valor más bajo y el vendedor k tiene un incentivo para informar un valor más alto.

Mecanismo VCG

Un mecanismo VCG es un mecanismo genérico que optimiza el bienestar social al tiempo que logra la veracidad, y lo hace haciendo que cada agente pague por el “daño” que sus deseos causan a la sociedad.

En el contexto del comercio bilateral simple, esto se traduce en el siguiente mecanismo:

• Si b ≤ s entonces no se realiza ninguna transacción y el producto permanece con el vendedor;
• Si b > s entonces el producto va al comprador, el comprador paga s y el vendedor recibe b .

Este mecanismo es:

• IR, ya que el comprador paga menos de su valor y el vendedor recibe más de su valor.
• IC, ya que el precio que paga el comprador lo determina el vendedor y viceversa. Cualquier intento de informar incorrectamente hará que la utilidad del informante sea nula o negativa.
• EE, porque el producto va a quien más lo valora.
• Ni SBB ni WBB, porque el subastador tiene que pagar b - s . El subastador tiene que subsidiar el comercio.

En el escenario general de subasta doble, el mecanismo ordena a los compradores y vendedores en el orden natural y encuentra el índice de equilibrio k . Luego, los primeros k vendedores entregan el artículo a los primeros k compradores. Cada comprador paga el precio de equilibrio más bajo max( s _k , b _k+1 ), y cada vendedor recibe el precio de equilibrio más alto min( b _k , s _k+1 ), como se muestra en la siguiente tabla:

Similar al escenario de comercio bilateral, el mecanismo es IR, IC y EE (optimiza el bienestar social), pero no es BB: el subastador subsidia el comercio.

El teorema de unicidad de precios ^[3] implica que este problema de subsidio es inevitable: cualquier mecanismo veraz que optimice el bienestar social tendrá los mismos precios (hasta una función independiente de los precios de oferta y demanda de cada comerciante). Si queremos mantener la veracidad del mecanismo sin tener que subsidiar el comercio, debemos comprometer la eficiencia e implementar una función de bienestar social que no sea óptima.

Mecanismo de reducción del comercio

El siguiente mecanismo renuncia a un único trato para mantener la veracidad: ^[4]

• Ordene a los compradores y vendedores en el orden natural y encuentre el índice de equilibrio k .
• Los primeros k -1 vendedores entregan el artículo y reciben s _k del subastador;
• Los primeros k -1 compradores reciben el artículo y pagan b _k al subastador.

Este mecanismo es:

• IR, como antes.
• IC: los primeros k -1 compradores y vendedores no tienen incentivos para cambiar su declaración ya que esto no tendrá efecto en su precio; el k ésimo comprador y vendedor no tienen incentivos para cambiar ya que de todos modos no comercian, y si entran en la negociación (por ejemplo, b _k aumenta su declaración por encima de b _{k -1} ), su ganancia por la negociación será negativa.
• No es SBB, porque el subastador se queda con un excedente de ( k -1)( b _k - s _k ). Pero es WBB, ya que el subastador al menos no tiene que subsidiar el comercio.
• No EE, porque b _k y s _k no comercian, aunque el comprador k valora el artículo más que el vendedor k .

Si intentáramos hacer que este mecanismo sea eficiente permitiendo que el k -ésimo comprador y el vendedor negocien, esto lo haría falso porque entonces tendrían un incentivo para cambiar sus precios.

Aunque el bienestar social no es óptimo, está cerca de serlo, ya que el acuerdo prohibido es el menos favorable. Por lo tanto, la ganancia derivada del comercio es al menos óptima. ${\displaystyle 1-1/k}$

Obsérvese que en el contexto de comercio bilateral, k = 1 y renunciamos al único acuerdo eficiente, por lo que no hay comercio en absoluto y la ganancia derivada del comercio es 0. Esto está de acuerdo con el teorema de Myerson-Satterthwaite .

Babaioff, Nisan y Pavlov ^[5] generalizaron el mecanismo de reducción del comercio a un mercado distribuido espacialmente , es decir, los compradores y vendedores están en varios lugares diferentes y algunas unidades del bien pueden tener que ser transportadas entre estos lugares. El costo del transporte se suma así al costo de producción de los vendedores.

El mecanismo de McAfee

McAfee ^[4] presentó la siguiente variación del mecanismo de reducción del comercio:

• Ordene a los compradores y vendedores en el orden natural y encuentre el índice de equilibrio k .
• Calcular: p =( b _{k +1} + s _{k +1} )/2.
• Si b _k ≥ p ≥ s _k , entonces los primeros k compradores y vendedores intercambian el bien al precio p .
• De lo contrario, los primeros k -1 vendedores negocian por s _k y los primeros k -1 compradores negocian por b _k como en el mecanismo de reducción del comercio.

De manera similar al mecanismo de reducción del comercio, este mecanismo es IR, IC, WBB pero no SBB (en el segundo caso) y no EE (en el segundo caso). Suponiendo que los valores de los compradores y vendedores están todos acotados por encima de cero, McAfee demuestra que la pérdida de eficiencia comercial está acotada por 1/min (número de compradores, número de vendedores). ^[4]

Mecanismos de reducción probabilística

Dado un p ∈[0,1], después de que se envían las ofertas, se utiliza el mecanismo de reducción de operaciones con probabilidad p y el mecanismo VCG con probabilidad 1- p . ^[6] Este mecanismo hereda todas las propiedades de sus padres, es decir, es IR e IC. El parámetro p controla la compensación entre EE y BB:

• La pérdida de ganancias provenientes del comercio es 0 (lograda por VCG) o 1/ k (lograda por reducción del comercio); por lo tanto, la pérdida esperada en ganancias provenientes del comercio es como máximo: p / k .
• El excedente del subastador es negativo (en el caso de VCG) o positivo (en el caso de reducción del comercio); por lo tanto, el excedente esperado es p * (excedente en la reducción del comercio) - (1- p ) * (déficit en VCG). Si los valores de los comerciantes provienen de una distribución conocida, p puede seleccionarse de manera que el excedente esperado sea 0, es decir, el mecanismo es SBB ex ante.

En una variante de este mecanismo, ^[6] después de que se presentan las ofertas, los k -1 vendedores baratos comercian con los k -1 compradores caros; cada uno de ellos recibe/paga el pago esperado del mecanismo original, es decir, cada comprador paga y cada vendedor recibe . Luego, con probabilidad p , el comprador k paga y compra el bien al vendedor k que recibe . Al igual que la primera variante, esta variante es IR y tiene la misma eficiencia y excedente esperados. Su ventaja es que "oculta" su carácter aleatorio a casi todos los comerciantes. La desventaja es que ahora el mecanismo es veraz solo ex ante; es decir, un comerciante neutral al riesgo no puede ganar en expectativas informando mal su valor, pero después de conocer los resultados del lote, podría arrepentirse de no informar de otra manera. ${\displaystyle pb_{k}+(1-p)\max {(b_{k+1},s_{k})}}$ ${\displaystyle ps_{k}+(1-p)\min {(s_{k+1},b_{k})}}$ ${\displaystyle \max {(b_{k+1},s_{k})}}$ ${\displaystyle \min {(s_{k+1},b_{k})}}$

Mecanismo SBBA

Segal-Halevi, Hassidim y Aumann ^[7] presentan un mecanismo de reducción comercial que es SBB, además de ser IR e IC y alcanza (1-1/k) del GFT óptimo.

Comparación

Babaioff y Nisan ^{[6] : El capítulo 4} proporciona una comparación teórica y una comparación empírica de los diversos mecanismos.

Enfoque modular

Dütting, Roughgarden y Talgam-Cohen ^[8] propusieron un enfoque modular para el diseño de subastas dobles. Su marco considera que las subastas dobles están compuestas por algoritmos de clasificación para cada lado del mercado y una regla de composición, y se pueden aplicar a mercados complejos. Una consecuencia inmediata de este marco es que los mecanismos clásicos de subasta doble, como el mecanismo de reducción del comercio, no solo son a prueba de estrategias, sino también débilmente a prueba de estrategias grupales (lo que significa que ningún grupo de compradores y vendedores puede beneficiarse de un informe conjunto erróneo de sus preferencias).

Más allá de dos categorías

El modelo básico de subasta doble involucra dos categorías de comerciantes: compradores y vendedores. Babaioff y Nisan ^[6] lo extendieron para manejar una cadena de suministro - una cadena de mercados, en la que los compradores en un mercado se convierten en vendedores en el siguiente mercado. Por ejemplo, los agricultores venden frutas en el mercado de frutas; los fabricantes de jugo compran frutas en el mercado de frutas, hacen jugo y lo venden en el mercado de jugos a los consumidores. Babaioff y Walsh ^[9] lo extendieron para manejar mercados en un grafo acíclico dirigido arbitrario .

Gilor, Gonen y Segal-Halevi ^[10] estudian un mercado multilateral, con un conjunto G de categorías de agentes. El mercado se caracteriza por un vector entero r de tamaño | G |, llamado la receta del mercado. Cada transacción en el mercado involucra r _g agentes de categoría g , para cada g en G . El mercado estándar de doble subasta es un caso especial en el que hay dos categorías (compradores y vendedores), y la receta es r = (1,1). Presentan algoritmos que son SBB, IC, IR y alcanzan (1-1/ k ) del GFT óptimo. Un algoritmo es un mecanismo de revelación directa basado en la reducción de transacciones, y el otro es un mecanismo de precio ascendente que no solo es IC sino también obviamente IC .

Gilor, Gonen y Segal-Halevi ^[11] estudian un mercado multilateral más general, en el que existen múltiples recetas diferentes, organizadas como un bosque , donde cada receta es un camino desde una raíz hasta una hoja. Presentan mecanismos aleatorios de precios ascendentes que son universalmente IR, obviamente IC, SBB y alcanzan una GFT asintóticamente óptima.

Véase también

• Subasta de cadena de suministro : una generalización de la subasta doble a más de dos categorías de agentes.
• Teorema de Myerson-Satterthwaite : ningún mecanismo es IR, IC, BB y EE, incluso cuando solo hay un comprador, un vendedor y un artículo.

Notas

1. Friedman, Daniel (1992). La institución del mercado de subasta doble: un estudio (PDF) .
2. Tagiew, Rustam (22 de mayo de 2009). "Hacia la subasta doble de trueque como modelo para la cooperación social bilateral". arXiv : 0905.3709 [cs.GT].
3. Nisan, Noam (2007). "Introducción al diseño de mecanismos para científicos informáticos". En Nisan, Noam; Roughgarden, Tim; Tardos, Eva; Vazirani, Vijay (eds.). Teoría de juegos algorítmicos . págs. 230–231. doi :10.1017/CBO9780511800481.011. ISBN 978-0521872829.S2CID 154357584  .
4. McAfee, RP (1992). "Una subasta doble con estrategia dominante". Journal of Economic Theory . 56 (2): 434–450. doi :10.1016/0022-0531(92)90091-u.
5. Babaioff, M.; Nisan, N.; Pavlov, E. (2004). "Mecanismos para un mercado distribuido espacialmente". Actas de la 5.ª conferencia de la ACM sobre comercio electrónico - EC '04 . pág. 9. doi :10.1145/988772.988776. ISBN 1-58113-771-0.
6. M. Babaioff; N. Nisan (2004). "Subastas concurrentes a lo largo de la cadena de suministro". Revista de investigación en inteligencia artificial . 21 : 595–629. arXiv : 1107.0028 . doi :10.1613/jair.1316. S2CID  58535404.
7. Segal-Halevi, Erel; Jasidim, Avinatan; Aumann, Yonatan (2016). "SBBA: un mecanismo de doble subasta con un presupuesto fuertemente equilibrado". En Gairing, Martín; Savani, Rahul (eds.). Teoría algorítmica de juegos . Apuntes de conferencias sobre informática. Berlín, Heidelberg: Springer. págs. 260–272. arXiv : 1607.05139 . doi :10.1007/978-3-662-53354-3_21. ISBN 978-3-662-53354-3.
8. Dütting, Paul; Roughgarden, Tim; Talgam-Cohen, Inbal (2014). Modularidad y codicia en subastas dobles (PDF) . Actas de la 15.ª Conferencia sobre Economía y Computación (EC'14). pp. 241–258. doi :10.1145/2600057.2602854. ISBN 9781450325653.
9. Babaioff, M.; Walsh, WE (2005). "Subastas compatibles con incentivos, equilibradas en términos presupuestarios y, sin embargo, altamente eficientes para la formación de cadenas de suministro". Decision Support Systems . 39 : 123–149. CiteSeerX 10.1.1.4.4123 . doi :10.1016/j.dss.2004.08.008. 
10. Gilor, Dvir; Gonen, Rica; Segal-Halevi, Erel (1 de noviembre de 2021). "Subastas con un presupuesto fuertemente equilibrado para mercados multilaterales". Inteligencia artificial . 300 : 103548. arXiv : 1911.08094 . doi :10.1016/j.artint.2021.103548. ISSN  0004-3702.
11. Gilor, Dvir; Gonen, Rica; Segal-Halevi, Erel (1 de diciembre de 2023). "Mecanismo de precios ascendentes para mercados generales de múltiples caras" . Inteligencia artificial . 325 : 104022. doi :10.1016/j.artint.2023.104022. ISSN  0004-3702.

Referencias

• Fudenberg, Drew; Tirole, Jean (1991). Teoría de juegos . Prensa del MIT. ISBN 978-0-262-06141-4.
• Gibbons, Robert (1992). Teoría de juegos para economistas aplicados . Princeton University Press. ISBN 978-0-691-00395-5.