Mechanism to auction off multiple resources given fixed budgets

Question

I am trying to sell ad time on a screen to a bunch of advertisers. The advertisers tell me (or a salesperson keys in) how much a given advertiser is willing to pay for time in a one hour block. Each one hour block may be subdivided arbitrarily among multiple advertisers.

To formalize, the inputs are:

• A set of advertisers $a_i$, with their maximum budgets $D_i$ (positive integers or reals, whichever makes it easier)
• For each advertiser $a$, for each hour $h$ in the upcoming month, an amount $d_{a,h}$ that $a$ is willing to pay per hour for time during $h$. So $a$ might pay $\frac{d_{a,h}}2$ for 30 minutes of $h$, or $\frac{d_{a,h}}3$ for 20 minutes of $h$.

The output I would like is a list of tuples $(i, h, t, p)$, which tells me that the $i$th advertiser should get $t \in [0,1]$ share of hour $h$, for which they should pay a per-hour rate of $p$.

• Exhausts every advertiser's budget. For marketing reasons beyond the scope of mechanism design, that is actually important.
• Given that constraint, maximizes my revenue. For this purpose we can consider my costs 0, so this is equivalent to maximizing profit.

What is the appropriate mechanism for this? Is there a way to get the output I want by solving some sort of LP, QP, or other convex optimization problem? I have no training in economics or optimization, just a bachelors' in computer science, so please go easy on me :-).

Answer 1

There's a chance that there won't be a solution; and if there is one, it may not be unique.

Nevertheless, we can at least express the problem formally:

You've got a set of constraints: $$(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$$

That formulation is usually going to be enough to enable you to feed it into some kind of solver, in Matlab, GAMS, python+numpy+minuit, R, or maybe even Excel with its built-in solver.

However, the problem is that you've indicated no costs, so we can't maximise profits. We can maximise revenues - but given constraint (1) above, revenue is fixed at $\sum_{i}{D_i}$ anyway.

There is an optimisation problem in there, if you can relax condition 1, so that we're not looking to exhaust all advertisers' budgets, but just maximise total revenue. However, if you do relax 1, you might then want extra conditions about exhausting at least some (any in particular?) of the advertisers' budgets.