diff options
| -rw-r--r-- | project2/main.tex | 12 |
1 files changed, 8 insertions, 4 deletions
diff --git a/project2/main.tex b/project2/main.tex index cfc3831..dc863df 100644 --- a/project2/main.tex +++ b/project2/main.tex @@ -55,7 +55,7 @@ the utility of an agent with type $t=(t_1,\ldots, t_m)$ is defined by: By the taxation principle, a mechanism for this setting can be described by a pair $x(\cdot), p(\cdot)$ where the allocation rule $x$ and the payment rule -$p$ are indexed by the agent's type. For an agent with type $t$, $\big(x(t), +$p$ are indexed by the agent's type. For an agent with type $t$, $\big(x(t), p(t)\big)$ is her preferred menu option. The revenue-optimal mechanism for this single-agent problem can be formally @@ -94,9 +94,12 @@ Problem~\ref{eq:opt}: \label{eq:ea} \E_{t\sim F}\big[x_i(t)] \leq \hat{x}_i,\quad\forall i\in[m] \end{equation} -which simply expresses that the ex-ante allocation rule is upper-bounded by +which expresses the assumption that the ex-ante allocation rule is upper-bounded by $\hat{x}$. +To provide some more intuition about this, we assume that the buyer is charged a price $p_0$ to participate in the mechanism, +and then is offered a menu of goods with prices $p_1,...,p_m$. The buyer's utility over the goods is additive, as above. However, there is an ex-ante constraint of being allocated a given good $i$, given by $\hat{x}_i$. For each good, if the buyer is allocated the good, which he is with probability $x_i \leq \hat{x}_i$, then he pays $p_i$; otherwise, he pays nothing. This is essentially the concept of a two-part tariff, as discussed in \cite{armstrong}. + Let us denote by $R(\hat{x})$ the revenue obtained by the optimal mechanism solution to Problem~\ref{eq:opt} with ex-ante allocation constraint \eqref{eq:ea}. @@ -114,11 +117,12 @@ for the multi-agent problem which is a $\gamma\cdot\alpha$ approximation to the revenue-optimal mechanism where $\gamma$ is a constant which is at least $\frac{1}{2}$. -It is interesting to consider two specific case for which we already have an +It is interesting to consider two specific cases for which we already have an answer to our problem: \begin{itemize} \item when $\hat{x} = (1,\ldots,1)$, \eqref{eq:ea} does not further - constrain Problem~\ref{eq:opt}. In this case, as discussed above, the + constrain Problem~\ref{eq:opt}, i.e. the constraint is trivially satisfied. + In this case, as discussed above, the mechanism described in \cite{babaioff} provides a 6-approximation. \item when $\hat{x} = (\frac{1}{m},\ldots,\frac{1}{m})$, by summing the constraint \eqref{eq:ea} for all $i\in[m]$, we see that the ex-ante |