## Exercise 8

Recall the sponsored search setting, in which bidder i has a valuation $v_i$ per click. There are k slots with click-through-rates (CTRs) $α_1 ≥ α_2 ≥ · · · ≥ α_k$. Recall that the social surplus of an assignment of bidders to slots is $∑^n_{i=1} v_ix_i$, where $x_i$ equals the CTR of the slot to which $i$ is assigned (or 0 if bidder $i$ is not assigned to any slot). Prove that the social surplus is maximized by assigning the bidder with the jth highest valuation to the jth slot for $j = 1, 2, . . . , k$

---

Previously we had a social choice function, which maximized social surplus, and therefore the **sum** of all valuations of all players:

$f (v_1, . . . , v_n) ∈ argmax_a ∈A∑ v_i(a)$

with

$v_i(a) = \begin{cases}
v_i \quad \text{if } b_i = \max b\\
0 \quad \text{if } b_i \neq \max b
\end{cases}$

This shows, maximizing social surplus is defined by finding the right outcome(winner) for the auction.

$\text{argmax}_{a \in A} \sum v_i(a)$

The new condition in this setup, is an allocation rule instead of a scoial choice function.
This Rule $x_i$ defines for each player $i$, how much of the available goods the player recives from the mechanism.
In the given case of sponsored search auction, $x_i$ will be zero if the player don't receive any slot, or the CTR of the slot itself. This is the case, because the valuation is how much a bidder values to get clicked, and the CTR of the received slot defines with which probability the bidder gets the desired click and therefore his valuation.

**Social Surplus with allocation rule:**

$\sum_{1}^{n} v_i x_i$

We can also say that $x_i \in X \quad$ where $X$ is the set of allocations for all players, which cardinality is exactly the number of players: $|X| = i \quad$ and it has the right ordering to indicate players.

Some additional necessary notation, is the set of Valuation-Vectors $v_i \in V \quad$ which has exactly the same propertys as $X$

If we want to maximize Social Surplus, it comes down to ordering $X$ in a way, that maxmizes the dot-product of $V$ and $X$.
This will be expressed as: $\max_{V \cdot X}$

With this, the new Social Surplus maximization looks like this:

$\max_{V \cdot X} \sum v_i x_i$

and concludes the proof.

---

**🔴 Where do we go from here for the formal prove?**
It is obvious, that now where we have integrated the given circumstances in the social surplus maximization formula, pairing the highest values will achieve our goal, but is that enough?

**Angela:**
We can express the social surplus as
$∑^n_{i=1} v_ix_i$

In sponsored search, each slot is assigned at most one bidder and each bidder is assigned at most one slot. If bidder $i$ is assigned to slot $j$ , then the component $x_i$ equals the CTR $\alpha_j$ of its slot (see f13.pdf page 19)

$x_i = \alpha_j$

with the slots
$α_1 ≥ α_2 ≥ · · · ≥ α_k$

Since $v_i$ is defining the position of the slot, a higher $v_i$ results in a higher $\alpha_j$ (assigning the bidder with the jth highest valuation to the jth slot), and thus

the social welfare (sum of all valuations * CTR) is maximized:

$\max_x(b_i, b_{-i}) \sum v_i x(b_i, b_{-i})$

We can exchange the allocation function $x$ with $x_i$'s that get assigned to ech bidder from the function:

$\max_{x_i} \sum v_i x_i$

As mentioned above, the $x_i$'s are representing the CTR of the slot the player gets assigned, so we can replace the $x_i$ with the CTR $\alpha_j$ of the slot it represents:

$\max_{\alpha_j} \sum_{i = 1, ..., n; \; j=1, ..., k} v_i \alpha_j$

---

Greedy algorithm approach: proceed with an optimal allocation of 1 slot at a time, then show that you can't improve the result by exchanging allocation for any two of the bidders.

Lets assume we have 5 bidders and 3 slots

The slots: $\alpha_1, ..., \alpha_m \quad$ $\alpha_1 = 0.8, \alpha_2 = 0.6, \alpha_3 = 0.4$ , a slot is indicated by $_i$

The $n$ Bidders: $1, ..., n \quad$ ,
$s_1 = w_j * b_j = 0.9 * 22.2 = 20, s_2 = 0.7 * 24.28 = 17,$
$s_3 = 0.6 * 23.3 = 14, s_4 = 0.5 * 24 = 12, s_5 = 0.4 * 20 = 8$
are ordered by their scores, and indicated by their placement $_j$

Now we get a Matrix, for each Slot, if it is assigned to the players:

$A_1 = \begin{pmatrix}
0.72 & 0.56 & 0.48 & 0.4 & 0.32\\
0.54 & 0.42 & 0.36 & 0.3 & 0.24\\
0.36 & 0.28 & 0.24 & 0.2 & 0.16
\end{pmatrix}$

Previously we calculated the value like this: $\alpha_{1j} = \alpha_1 * w_j$
Now we have the case that: $w_j = \alpha_{1j}$
So we have to adjust the equation:
$\alpha_{1j} = w_j$

$A_2 = \begin{pmatrix}
0.9 & 0.7 & 0.6 & 0.5 & 0.4\\
\end{pmatrix}$