Mecanismo para subastar múltiples recursos dados presupuestos fijos

Question

Estoy tratando de vender tiempo del anuncio en una pantalla con un montón de anunciantes. Los anunciantes me dicen (o un vendedor claves en) la cantidad de un determinado anunciante está dispuesto a pagar por el tiempo en un bloque de horas. Cada uno de los bloque de horas puede ser dividido arbitrariamente entre varios anunciantes.

Para formalizar, las entradas son:

• Un conjunto de anunciantes $a_i$, con máximo de sus presupuestos $D_i$ (enteros positivos o reales, lo que hace que sea más fácil)
• Para cada anunciante $a$, por cada hora $h$ en el próximo mes, una cantidad $d_{a,h}$ que $a$ está dispuesto a pagar por hora por el tiempo durante el $h$. Por lo $a$ podría pagar $\frac{d_{a,h}}2$ durante 30 minutos de $h$ o $\frac{d_{a,h}}3$ durante 20 minutos de $h$.

La salida que me gustaría es una lista de tuplas $(i, h, t, p)$, lo cual me dice que el $i$th anunciante debe obtener $t \in [0,1]$ de cuota de horas $h$, por lo que se debe pagar por hora tasa de $p$.

• Tubos de escape de cada anunciante del presupuesto. Por razones de marketing más allá del ámbito del diseño de mecanismos, que en realidad es importante.
• Dada esta restricción, maximiza mis ingresos. Para este propósito se puede considerar mi costes de 0, lo que es equivalente a la maximización de las ganancias.

¿Cuál es el mecanismo adecuado para esto? Hay una manera de obtener el resultado que quiero mediante la resolución de algún tipo de LP, QP, u otro problema de optimización convexa? Yo no tengo formación en economía o la optimización, sólo una licenciatura' en ciencias de la computación, así que por favor ir fácil en mí :-).

Answer 1

Existe una posibilidad de que no habrá una solución, y si no es uno, no puede ser único.

Sin embargo, al menos podemos expresar el problema formalmente:

Tienes un conjunto de restricciones: $$(1) ~~ D_i=\sum_{h}{(d_{i,h}t_{i,h})}~~~ \forall i$$ $$(2) ~~ \sum_{i}{t_{i,h}}=1~~~ \forall h$$ $$(3) ~~ 0 \le t_{i,h} \le 1~~~ \forall i,h$$

La formulación general va a ser suficiente para poder darle de comer en algún tipo de solver, en Matlab, GAMS, python+colección+de minuit, R, o tal vez incluso de Excel con su función de solver.

Sin embargo, el problema es que no se indican los costos, por lo que no puede maximizar sus beneficios. Podemos maximizar los ingresos -, pero dada la restricción (1) anterior, los ingresos se fija en$\sum_{i}{D_i}$, de todos modos.

Hay un problema de optimización en allí, si usted puede relajarse en la condición 1, por lo que no estamos tratando de agotar todos los anunciantes de los presupuestos, pero sólo de maximizar el ingreso total. Sin embargo, si usted relajarse 1, usted tal vez quiera condiciones adicionales acerca de agotar al menos algunos (alguna en particular?) de los anunciantes en los presupuestos.