diff options
Diffstat (limited to 'project2/main.tex')
| -rw-r--r-- | project2/main.tex | 101 |
1 files changed, 87 insertions, 14 deletions
diff --git a/project2/main.tex b/project2/main.tex index f83f79b..cfc3831 100644 --- a/project2/main.tex +++ b/project2/main.tex @@ -1,9 +1,10 @@ \documentclass[10pt]{article} -\usepackage{fullpage} \usepackage{amsmath,amsfonts,amsthm} \usepackage[english]{babel} -\usepackage[capitalize, noabbrev]{cleveref} \usepackage{paralist} +\usepackage[utf8x]{inputenc} +\usepackage[pagebackref=true,breaklinks=true,colorlinks=true]{hyperref} +\usepackage[capitalize, noabbrev]{cleveref} % these are compressed lists to help fit into a 1 page limit \newenvironment{enumerate*}% @@ -41,28 +42,100 @@ \maketitle -\section{Problem} - -We are interested in a multi-item auction for agents with submodular -preferences. +\section{Introduction} -If we denote by $m$ the number of items, we look at a specific case where the -type $t$ of an agent is a vector $t=(t_1,\ldots,t_m)$ drawn from a distribution -$F$ over $\mathbb{R}_+^m$ and for an allocation $x$ and price -$p$, the utility of the agent is: +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) = \sum_{S\subseteq 2^m} x(S)g\left(1+\sum_{j\in S} t_j\right)-p + u(t, x, p) = \left(\sum_{i=1}^m x_i t_i\right) - p \end{displaymath} -where $g$ is a concave function from $\mathbb{R}_+$ to $\mathbb{R}_+$ with -$g(0) = 0$. +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(t)\big)$ is her preferred menu option. + +The revenue-optimal mechanism for this single-agent problem can be formally +obtained as the solution to the following optimization problem: +\begin{equation} + \label{eq:opt} + \begin{split} + \max_{(x, p)} & \E_{t\sim F}\big[p(t)\big]\\ + \text{s.t.} &\, u(t, x(t), p(t)) \geq u(t', x(t'), p(t')),\quad + \forall t, t'\in\R_+^m\\ + &\, u(t, x(t), p(t)) \geq 0,\quad\forall t\in\R_+^m\\ + &\,x_i(t)\leq 1,\quad \forall t\in\R_+^m,\,\forall i\in[m] +\end{split} +\end{equation} +where the first constraint expresses incentive compatibility and the second +constraint expresses individual rationality. + +Unfortunately, it has been shown in \cite{hart} that even in this simple case +and as soon as $m\geq 2$, the optimal mechanism can have a menu size which is +exponential in $m$. Therefore it is important to understand to which extent +simple mechanisms can approximate the revenue-optimal mechanism. + +A remarkable result of \cite{babaioff} proves that a simple mechanism provides +a constant approximation to Problem~\ref{eq:opt}. More precisely, it is shown +that the maximum of \emph{item pricing} where each item is priced separately at +its monopoly reserve price and \emph{bundle pricing} where the grand bundle of +all items is priced and sold together achieves a 6-approximation to the optimal +mechanism. + +We propose to extend this result 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} += (\hat{x}_1,\ldots,\hat{x}_m)$ and we add the following constraint to +Problem~\ref{eq:opt}: +\begin{equation} + \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 +$\hat{x}$. + +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}. + +\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 +$\hat{x}$ and whose revenue is a constant approximation to $R(\hat{x})$?} + +\paragraph{} One reason why one might want to consider this problem is that it +can be used as a building block for more general mechanisms. Indeed, in +\cite{alaei}, Alaei shows that under fairly general assumptions, given an +$\alpha$-approximate mechanism for the single-agent, ex-ante allocation +constrained problem it is possible to construct in polynomial time a mechanism +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 +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 + 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 + 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. +\end{itemize} \section{Related Work} -In \cite{babaioff}, the authors describe a setting with a monopolist seller, offering $n$ heterogeneous goods, and a single buyer. +In \cite{babaioff}, the authors describe a setting with a monopolist seller, +offering $n$ heterogeneous goods, and a single buyer. \cite{hart} \cite{hartline} \cite{yao} +\cite{armstrong} +\cite{alaei} \bibliographystyle{abbrv} \bibliography{main} |