diff options
Diffstat (limited to 'project2')
| -rw-r--r-- | project2/main.tex | 40 |
1 files changed, 21 insertions, 19 deletions
diff --git a/project2/main.tex b/project2/main.tex index daf7411..77ceb9f 100644 --- a/project2/main.tex +++ b/project2/main.tex @@ -52,11 +52,13 @@ \section{Introduction to the Problem} -\blfootnote{We are deeply grateful to Jason Hartline who provided the original idea for this project.}We consider the problem of selling $m$ heterogeneous items to a single agent -with additive utility. The type $t$ of the agent is drawn from a distribution -$F$ over $\R_+^m$. For an allocation $x = (x_1,\ldots,x_m)$ where $x_i$, -$i\in[m]$, denotes the probability of being allocated item $i$ and payment $p$, -the utility of an agent with type $t=(t_1,\ldots, t_m)$ is defined by: +\blfootnote{We are grateful to Jason Hartline who provided the original idea +for this project.}We consider the problem of selling $m$ heterogeneous items to +a single agent with additive utility. The type $t$ of the agent is drawn from +a distribution $F$ over $\R_+^m$. For an allocation $x = (x_1,\ldots,x_m)$ +where $x_i$, $i\in[m]$, denotes the probability of being allocated item $i$ and +payment $p$, the utility of an agent with type $t=(t_1,\ldots, t_m)$ is defined +by: \begin{displaymath} u(t, x, p) = \left(\sum_{i=1}^m x_i t_i\right) - p \end{displaymath} @@ -105,9 +107,9 @@ Problem~\ref{eq:opt}: which expresses the assumption that the ex-ante allocation rule is upper-bounded by $\hat{x}$. -We use the notation from \cite{alaei} where $R(\hat{x})$ denotes the revenue obtained by the optimal mechanism -solution to Problem~\ref{eq:opt} with ex-ante allocation constraint $\hat{x}$. -\eqref{eq:ea}. +We use the notation from \cite{alaei} where $R(\hat{x})$ denotes the revenue +obtained by the optimal mechanism solution to Problem~\ref{eq:opt} with ex-ante +allocation constraint $\hat{x}$ given by \eqref{eq:ea}. \paragraph{Problem.} \emph{Given an ex-ante allocation constraint $\hat{x}$, is there a simple mechanism whose ex-ante allocation rule is upper-bounded by @@ -130,21 +132,21 @@ answer to our problem: 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 to $R((1,...,1))$. - \item when $\hat{x} = \left(\frac{1}{m},\ldots,\frac{1}{m}\right)$, by summing the - constraint \eqref{eq:ea} for all $i\in[m]$, we see that the ex-ante - allocation constraint implies that in expectation, no more than - one-item is sold to the agent. This is exactly the unit-demand case for - which TODO:cite provides a 2 approximation to $R\left( \left(\frac{1}{m},\ldots,\frac{1}{m}\right)\right)$. + \item when $\hat{x} = \left(\frac{1}{m},\ldots,\frac{1}{m}\right)$, by + summing the constraint \eqref{eq:ea} for all $i\in[m]$, we see that the + ex-ante allocation constraint implies that in expectation, no more than + one-item is sold to the agent. This is exactly the ex-ante relaxation + of the unit-demand case for which a 2-approximation to $R\left( + \left(\frac{1}{m},\ldots,\frac{1}{m}\right)\right)$ is already known. \end{itemize} In the general case, a candidate simple mechanism suggested by Jason Hartline is the following: 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$. -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}. +mechanism, and then is offered each item separately with a posted prices +$p_1,\ldots, p_m$. This is essentially the concept of a two-part tariff, as +discussed in \cite{armstrong}. Our problem is then to understand how to set +$p_0$ and the posted prices $p_1,\ldots, p_m$ such that in expectation over the +agent's type, item $i$ is sold with probability $x_i\leq \hat{x}_i$. \bibliographystyle{abbrv} \bibliography{main} |