¿Existe un algoritmo para encontrar el mayor número posible de NE en esta subasta de segundo precio generalizada?

Question

Supongamos que tres anunciantes, I, II y III, participan en una subasta para tres posiciones de publicidad online, la superior, la intermedia y la inferior. Supongamos que los clics por segundo para una posición no se ven afectados por quién pone un anuncio allí. Para la parte superior, la tasa de clics es de 3 clics por segundo, para la parte media, es de 2, para la parte inferior, es de 1. Pero los anunciantes tienen un valor privado por clic. Para I, es \$16 per click. For II, it's \$ 15. Para el III, es \$14. The one who submits the highest wins the top position and pays the second highest bid, second highest bidder got the middle position and pays the third highest bid. The third highest bidder end up with bottom position, but pays zero. If there's a tie, then choose the winner ramdomly by a fair dice. The strategy space for each bidder is $ \N -mathbb{R}_{+}$.

Hay un montón de NE para este juego. Por ejemplo, I,II,III presentan simultáneamente ofertas de, \$7 per click, \$ 9 por clic, \$11 per click respectively. Their payoff will be $ 1 \N - (16-0) $ dollars, $ 2\N-tiempos (15-7) $ dollars, and $ 3 veces (14-9)$ dólares respectivamente.

$$ \begin{array}{c|l|c|r} \hline &(0,7) & (7,9) & (9,11) & (11, +\infty)\\ \hline \text{player I}& \color{blue}{16} & \color{blue}{16} & 2(16-9)=14& 3(16-11)=15 \\ \hline \text{player II}& 15 & 2(15-7)=\color{blue}{16} & 2(15-7)=\color{blue}{16}& 3(15-11)=12 \\ \hline \text{player III}& 14 & 2(14-7)=14 & 3(14-9)= \color{blue}{15} & 3(14-9)= \color{blue}{15}\\ \hline \end{array} $$

¿Cómo encontrar otras NE?

Añadido : Quiero estudiar este ejemplo numérico, porque quiero entender mejor la motivación de este documento .

Answer 1

Este es un algoritmo bastante general, probablemente puedas adaptar uno mejor a tu problema específico.

Si te ciñes a este espacio de estrategias discretas, me parece que tendrías que encontrar los equilibrios por fuerza bruta. Básicamente, se mirarían todos los perfiles de oferta $(x_1,x_2,x_3)$ y comprobar si es un equilibrio. Para ello, habría que comprobar si el jugador 1 estaría mejor haciendo otra oferta. Denotemos la ganancia del jugador 1 por $\pi_1$ . Esto es una función de las ofertas. Supongamos que $x_2 > x_3 + 1$ . Entonces tendría que comprobar \begin{eqnarray*} \pi_1(x_1,x_2,x_3) & \geq & \pi_1(x_2+1,x_2,x_3) \\ \\ \pi_1(x_1,x_2,x_3) & \geq & \pi_1(x_2-1,x_2,x_3) \\ \\ \pi_1(x_1,x_2,x_3) & \geq & \pi_1(x_3-1,x_2,x_3) \\ \\ \end{eqnarray*} Si todo esto y las correspondientes desigualdades para otros jugadores se mantienen, entonces se ha encontrado un equilibrio.

Si $x_2 = x_3 + 1$ hay que tener en cuenta la regla de desempate.

Puedes limitar el número de perfiles $(x_1,x_2,x_3)$ se comprueba razonando sobre los precios de las reservas. (Por ejemplo, para cualquier N.E. en el que alguien puje por encima de su precio de reserva tienes un N.E. en el que puje justo eso).