summaryrefslogtreecommitdiffstats
path: root/final/main.tex
diff options
context:
space:
mode:
authorThibaut Horel <thibaut.horel@gmail.com>2015-05-12 17:34:20 -0400
committerThibaut Horel <thibaut.horel@gmail.com>2015-05-12 17:34:20 -0400
commitf24ca02d053fde9b26034b6512786cb642f0e9b3 (patch)
treef247251fd89a8368856e0f6526a6fe9e367d9e71 /final/main.tex
parenta4790082c27063a67837263cd68e27e5b6010e6c (diff)
downloadecon2099-f24ca02d053fde9b26034b6512786cb642f0e9b3.tar.gz
Reorder 1.1 to make it understandable
Diffstat (limited to 'final/main.tex')
-rw-r--r--final/main.tex29
1 files changed, 14 insertions, 15 deletions
diff --git a/final/main.tex b/final/main.tex
index 4ff3c12..57a3645 100644
--- a/final/main.tex
+++ b/final/main.tex
@@ -112,15 +112,6 @@ is priced separately at its monopoly reserve price, and \emph{bundle pricing},
where the grand bundle of all items is priced and sold as a single item,
achieves a 6-approximation to the optimal revenue.
-Following \citep{hartline}, we use the notation $R(\hat{q})$ to denote the revenue obtained by the optimal mechanism as a function of equality constraint $\hat{q}$.
-We slightly modify the notation from \citep{alaei} by replacing his $R$ with $\Rev$ and always making
-the type distribution $F$ explicit; so we will write $\Rev(\hat{x}, F)$, letting this denote 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}. Finally, when
-the ex-ante allocation constraint \eqref{eq:ea} is not present, we use $\Rev(F)
-\eqdef \Rev((1,\dots, 1), F)$ to denote the revenue of the revenue optimal IR-IC
-mechanism.
-
We propose to extend the result of \citep{babaioff} by considering a more general version of
Problem~\ref{eq:opt} where there is an additional \emph{ex-ante allocation
constraint}. Formally, we are given a vector $\hat{x}
@@ -132,13 +123,21 @@ Problem~\ref{eq:opt}:
\end{equation}
which expresses that the ex-ante allocation probability is upper-bounded by
$\hat{x}$. Note that when $\hat{x} = (1,\ldots,1)$, the ex-ante allocation
-constraint \eqref{eq:ea} does not further constrain the optimization problem
-given by Problem \ref{eq:opt}, i.e. the constraint is trivially satisfied. In
-this case, as discussed above, the mechanism described in \citep{babaioff}
-provides a 6-approximation to $\Rev((1,...,1),F)$.
-The main question
-underlying this work can then be formulated as:
+Following \citep{hartline}, we use the notation $R(\hat{q})$ to denote the
+revenue obtained by the optimal mechanism which serves with ex-ante allocation
+probability equal to $\hat{q}$. We slightly modify the notation from
+\citep{alaei} by replacing his $R$ with $\Rev$ and always making the type
+distribution $F$ explicit; so we will write $\Rev(\hat{x}, F)$, letting this
+denote 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}. Finally, when the ex-ante allocation constraint \eqref{eq:ea} is
+not present, we use $\Rev(F) \eqdef \Rev((1,\dots, 1), F)$ to denote the
+revenue of the revenue optimal IR-IC mechanism. In this case, this case, as
+discussed above, the mechanism described in \citep{babaioff} provides
+a 6-approximation to $\Rev((1,...,1),F)$.
+
+The main question underlying this work can then be formulated as:
\paragraph{Question.} \emph{Given an ex-ante allocation constraint $\hat{x}$ and a type distribution $F$, is
there a simple mechanism whose ex-ante allocation rule is upper-bounded by