Latest changes

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}