diff options
Diffstat (limited to 'final/main.tex')
| -rw-r--r-- | final/main.tex | 33 |
1 files changed, 18 insertions, 15 deletions
diff --git a/final/main.tex b/final/main.tex index 066fabe..1a101f5 100644 --- a/final/main.tex +++ b/final/main.tex @@ -3,8 +3,11 @@ \usepackage[english]{babel} \usepackage{paralist} \usepackage[utf8x]{inputenc} -\usepackage[pagebackref=true,breaklinks=true,colorlinks=true]{hyperref} +\usepackage[pagebackref=true,breaklinks=true,colorlinks=true,citecolor=blue]{hyperref} \usepackage[capitalize, noabbrev]{cleveref} +\usepackage[square,sort]{natbib} + + % these are compressed lists to help fit into a 1 page limit \newenvironment{enumerate*}% @@ -58,7 +61,7 @@ for this project.} \subsection{Setup of the Problem} -The exposition in this section draws from \cite{hartlinebayes}. We consider the +The exposition in this section draws from \citep{hartlinebayes}. 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$. We use the notation $[m]$ for $\{1,...,m\}$. For an allocation $x = (x_1,\ldots,x_m)$ where $x_i$, $i\in[m]$, @@ -69,9 +72,9 @@ utility of an agent with type $t=(t_1,\ldots, t_m)$ is defined by: \end{displaymath} 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 +a pair $\left(x(\cdot), p(\cdot)\right)$ 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. +p(t)\big)$ is her preferred menu option (\citep{hartline}, Section 3.4). The revenue-optimal mechanism for this single-agent problem can be formally obtained as the solution to the following optimization problem: @@ -86,17 +89,17 @@ obtained as the solution to the following optimization problem: \end{split} \end{equation} where the first constraint expresses incentive compatibility and the second -constraint expresses individual rationality. As noted in \cite{hartlinebayes}, +constraint expresses individual rationality. As noted in \citep{hartlinebayes}, this formulation can easily be extended to support additional constraints which arise in natural scenarios: budget constraints or matroid constraints, for example. -If the distribution $F$ is correlated, a result from \cite{hart} shows that the +If the distribution $F$ is correlated, a result from \citep{hart} shows that the gap between the revenue of auctions with finite menu size and a revenue-maximizing auction can be arbitrarily large. When $F$ is a product distribution, however, there is a possibility of obtaining a simple auction with a constant approximation ratio to the optimal revenue. In fact, a result from -\cite{babaioff} shows that the maximum of \emph{item pricing}, where each item +\citep{babaioff} shows 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 as a single item, achieves a 6-approximation to the optimal revenue. @@ -113,7 +116,7 @@ Problem~\ref{eq:opt}: which expresses that the ex-ante allocation probability is upper-bounded by $\hat{x}$. -We use the notation from \cite{alaei}, where $R(\hat{x})$ denotes the revenue +We use the notation from \citep{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}. The main question underlying this work can then be formulated as: @@ -126,7 +129,7 @@ $\hat{x}$ and whose revenue is a constant approximation to $R(\hat{x})$?} \paragraph{}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 Equation \ref{eq:opt}, i.e. the constraint is trivially satisfied. In -this case, as discussed above, the mechanism described in \cite{babaioff} +this case, as discussed above, the mechanism described in \citep{babaioff} provides a 6-approximation to $R((1,...,1))$. \paragraph{Single-item case.} @@ -134,7 +137,7 @@ To make things more concrete, let us first look at the single-item case which is well understood. In this setting, $\hat{x}$ is a real number and the function $R(\hat{x})$ defined above is simply the revenue curve and turns out to be a very useful object to understand the revenue maximizing multiple-agent -single-item auction (see \cite{hartline}, Chapter 3). +single-item auction (see \citep{hartline}, Chapter 3). In particular, if the type of the agent (her value) is drawn from a regular distribution, the posted price revenue curve is concave and equal to the @@ -145,7 +148,7 @@ $p_{\hat{x}} = F^{-1}(1-\hat{x})$. \paragraph{Multiple-item case.} The multiple-agent multiple-item setting is not fully understood yet, but the revenue function $R(\hat{x})$ defined above still seems to play an important role in understanding the revenue optimal auction. -For example, it is noted in \cite{alaei} that $R(\hat{x})$ is a concave +For example, it is noted in \citep{alaei} that $R(\hat{x})$ is a concave function of $\hat{x}$. This allows us to define a convex optimization program (where the objective function is the sum of the revenue curves for all agents) whose optimal value is an upper bound on the expected value of the @@ -166,7 +169,7 @@ $\gamma$ is a constant which is at least $\frac{1}{2}$. Given the simplicity of posted-price mechanisms and the fact that they are optimal in the single-agent single-item setting (for a regular distribution $F$), it would be desirable to obtain a mechanism as close as possible to posted-price. -Unfortunately, Hart and Nisan \cite{hart-nisan} showed that even in the +Unfortunately, Hart and Nisan \citep{hart-nisan} showed that even in the unconstrained, regular case, no posted-price mechanism for the single-agent problem has an approximation ratio better than $\Omega(\log n)$. @@ -174,7 +177,7 @@ Instead, we consider the following candidate mechanism suggested by Jason Hartline: the buyer is charged a price $p_0$ to participate in the mechanism, and then is offered each item separately with posted prices $p_1,\ldots, p_m$. This is essentially the concept of a two-part tariff, as discussed in -\cite{armstrong}. +\citep{armstrong}. Note that as written above, the candidate mechanism is not individually rational because the agent gets charged $p_0$ regardless of her type. To @@ -208,7 +211,7 @@ where we use the notation $\I[\text{expression}]$ to denote the indicator variable for the expression, which takes on value 1 when the expression is true and 0 otherwise. We note that this mechanism is exactly the $\beta$-bundle mechanism from -\cite{yao}, even though the interpretation in terms of entrance fee plus posted +\citep{yao}, even though the interpretation in terms of entrance fee plus posted prices is not explicit in this paper. \subsection{$p$-exclusivity} @@ -236,6 +239,6 @@ Lemma. \end{lemma} -\bibliographystyle{abbrv} +\bibliographystyle{abbr} \bibliography{main} \end{document} |