%% ToC 3/9 2007 Balcan - Blum au revised 9-20 bio rev 9-25 LB re-rev 9-26 %% ToC-typeseeting; ACR completed 10/3/07. %% ACR 10/3/07. Aravind/LB comments. %% ACR 10/3/07. Bibliographic fixes, including extra "and" and %% FOCS eprint entry. %% LB: pub date --> Oct 3 \documentclass{toc} \usepackage{graphicx} \newcommand{\ignore}[1]{} \newcommand{\val}{w} \newcommand{\valueb}{w} \newcommand{\alfloor}[1]{\lfloor #1 \rfloor_{\alpha}} \newcommand{\ceiling}[1]{\lceil #1 \rceil} \newcommand{\auction}{{\cal A}} \newcommand{\regret}{r} \newcommand{\expect}[1]{{\mathbf E}\left[ #1 \right]} \newcommand{\setsize}[1]{\left| #1\right|} \newcommand{\suchthat}{\,:\,} \DeclareMathOperator{\argmax}{argmax} \newcommand{\half}{\frac{1}{2}} \newcommand{\inv}[1]{\frac{1}{#1}} \newcommand{\alg}{{\mathcal{A} }} \newcommand{\distr}{{\mathcal{D} }} \newcommand{\Qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \medskip} \newcommand{\Mathqed}{\mbox{\ \ \ \rule{6pt}{7pt}}} \renewcommand{\Pr}{{\bf Pr}} \newcommand{\E}{{\bf E}} \newcommand{\D}{{\mathcal{D} }} \newcommand{\mycomment}[1]{} \newcommand{\YMcomment}[1]{{\tiny #1 }} \newcommand{\Ncomment}[1]{{\tiny #1 }} \newcommand{\bracket}[1]{\langle #1 \rangle} \newenvironment{proofsketch}{\emph{Proof Sketch:}}{\qed} \newenvironment{proofof}[1]{\emph{Proof of #1:}}{\qed} \newcommand{\eps}{\varepsilon} \newcommand{\reals}{{\mathbb R}} \newcommand{\hF}{\hat{F}} \newcommand{\PP}{\mathcal{P}} \newcommand{\Xcomment}[1]{} \newcommand{\setitems}{V} \newcommand{\bundle}{s} \newcommand{\setbidders}{E} \newcommand{\hyper}{E} \newcommand{\bigo}{O} \newcommand{\profit}{\textrm{Profit}} \newcommand{\OPT}{{\rm OPT}} \newcommand{\ALG}{{\rm ALG}} \newcommand{\nitems}{n} \newcommand{\ncust}{m} \newcommand{\pvect}{{\bf p}} \newcommand{\pv}{\pvect} \newcommand{\p}{{\bf p}} \newcommand{\vv}{{\bf v}} \newcommand{\pvoptn}{\tilde{\pv}^*} \newcommand{\pvopt}{\pv^*} \newcommand{\identity}{{\bf i}} \newcommand{\sump}{s} \newcommand{\values}{Val} \newcommand{\subsetitems}{W} \newcommand{\wopt}{opt} \newcommand{\Nina}[1]{{\bf [[N: #1]]}} \tocdetails{volume=3, number=9, year=2007, firstpage=179, received={March 29, 2007}, published={October 3, 2007}} \runningauthor{M.-F. Balcan and A. Blum} \runningtitle{Approximation Algorithms and Online Mechanisms for Item Pricing} \copyrightauthor{Maria-Florina Balcan and Avrim Blum} \begin{document} \begin{frontmatter} \title{Approximation Algorithms and Online Mechanisms for Item Pricing\thanks{A preliminary version of this paper appeared in Proc. 7th ACM Conf. on Electronic Commerce (EC'06), pp.29-35, 2006.}} \tocpdftitle{Approximation Algorithms and Online Mechanisms for Item Pricing} \tocpdfauthor{Maria-Florina Balcan, Avrim Blum} \author[nina]{Maria-Florina Balcan\thanks{Supported in part by NSF grants CCF-0514922, CCR-0122581, and IIS-0121678.}} \author[avrim]{Avrim Blum\footnotemark[2]} \begin{abstract} We present approximation and online algorithms for problems of pricing a collection of items for sale so as to maximize the seller's revenue in an unlimited supply setting. Our first result is an $O(k)$-approximation algorithm for pricing items to single-minded bidders who each want at most $k$ items. This improves over work of Briest and Krysta (2006) who achieve an $O(k^2)$ bound. For the case $k=2$, where we obtain a $4$-approximation, this can be viewed as the following \emph{graph vertex pricing} problem: given a (multi) graph $G$ with valuations $\val_{ij}$ on the edges, find prices $p_i \geq 0$ for the vertices to maximize $$\sum\limits_{\{(i,j):\val_{ij} \geq p_i+p_j\}} \left(p_i + p_j \right)\,.$$ We also improve the approximation of Guruswami et al.~(2005) for the ``highway problem'' in which all desired subsets are intervals on a line, from $O(\log {\ncust} + \log {\nitems})$ to $O(\log {\nitems})$, where $\ncust$ is the number of bidders and $\nitems$ is the number of items. Our approximation algorithms can be fed into the generic reduction of Balcan et al.~(2005) to yield an incentive-compatible auction with nearly the same performance guarantees so long as the number of bidders is sufficiently large. In addition, we show how our algorithms can be combined with results of Blum and Hartline~(2005) and Kalai and Vempala~(2003) to achieve good performance in the online setting, where customers arrive one at a time and each must be presented a set of item prices based only on knowledge of the customers seen so far. \end{abstract} \tockeywords{Combinatorial Auctions, Pricing Problems, Revenue Maximization, Approximation Algorithms, Online Optimization} \tocacm{F.2, J.4} \tocams{68W25, 68W20, 68Q32, 91B26} \end{frontmatter} \section{Introduction} \label{s:intro} Consider the problem of a retailer trying to price its products to make the most profit. If customers had valuations over individual items only, then the problem of setting prices would be relatively easy: for each product $i$, the optimal price for that product is such that the profit margin $p_i$ per item sold, times the number of customers who would buy at that price, is maximized. So, each item can be considered separately, and assuming the company knows its market well, the \emph{computational} problem of setting prices is fairly trivial. However, suppose that customers have valuations over \emph{pairs} of items (e.g., a computer and a monitor, or a tank of gas and a cup of coffee), and will only purchase if the combined price of the items in their pair is below their value. In this case, we can model the problem as a (multi) \emph{graph}, where each edge $e$ has some valuation $\val_e$, and our goal is to set prices $p_i \geq 0$ on the vertices of the graph to maximize total \emph{profit}: that is,\footnote{This formula corresponds to a model in which items have zero marginal cost to the retailer (digital goods) so that an item sold at price $p_i$ generates profit $p_i$. Alternatively, if products have a fixed marginal cost, and we cannot sell them below cost (say, due to the presence of resellers), then we can think of $p_i$ as the profit margin on item $i$ and simply subtract our costs for the endpoints from each valuation $\val_e$.} \[ \profit(\pvect) = \sum_{e:w_e \geq \textrm{price}(e)} \textrm{price}(e)\,, \] where price$(e) = \sum_{i \in e} p_i$, and $\pvect$ is the vector of individual prices. We call this the \emph{graph vertex pricing} problem. More generally, if customers have valuations over larger subsets, we can model our computational problem as one of pricing vertices in a \emph{hypergraph}, or in more standard terminology, the problem of pricing items in an unlimited-supply combinatorial auction with single-minded bidders. Guruswami et al.~\cite{GHKKKS-05} show an $O(\log {\ncust} + \log {\nitems})$-approximation for the general problem, where $n$ is the number of items (vertices) and $m$ is the number of customers (hyperedges). They also show that even the \emph{graph} vertex pricing problem is APX-hard --- and this is true even when all valuations are identical (if customers wanting just one item are allowed) or all valuations are either $1$ or $2$ (if such customers are not allowed). In related work, Hartline and Koltun \cite{HK05} give a $(1+\epsilon)$-approximation that runs in time exponential in the number of vertices, but that is near-linear time when the total number of vertices in the hypergraph is constant. Recently, Demaine et al.~\cite{DFHS-06} have shown that it is hard to approximate the hypergraph vertex pricing problem within a factor of $\log^{\delta}\nitems$, for some $\delta>0$, assuming that NP $\not\subseteq$ BPTIME$\left(2^{\nitems^\epsilon}\right)$ for some $\epsilon >0$. In this paper, we give a $4$-approximation for the graph vertex pricing problem, and more generally we present an $O(k)$-approximation for the case of hypergraphs in which each edge has size at most $k$ (\ie, all customers' valuations are over subsets of size at most $k$). The latter result improves over the work of Briest and Krysta~\cite{BK-06} who give a bound of $O(k^2)$. We also consider the highway problem studied in \cite{GHKKKS-05}. This problem is the special case of the hypergraph pricing problem where vertices are numbered $1, \ldots, \nitems$ and each customer wants an interval $[i,j]$.\footnote{Previous work \cite{HK05,GHKKKS-05} uses ``$\ncust$'' to denote the number of items and ``$\nitems$'' to denote the number of customers, viewing the \emph{items} as edges in some network. Since we are viewing items as vertices and customers as (hyper)edges, we have reversed this notation.} For this problem, we give an $O(\log \nitems)$-approximation, improving slightly over the $O (\log {\ncust} + \log {\nitems})$ approximation of \cite{GHKKKS-05}, and also give an $O(1)$-approximation for the case that all users want the \emph{same number} of items up to a constant factor. In addition, we give a fully polynomial time approximation scheme (FPTAS) for the case that the desired subsets of different customers form a hierarchy (this is defined more precisely in \expref{Section}{hierarchy}). Finally, we consider the question of what happens if we are allowed to price some items \emph{below} their cost, and give an example in the context of graph vertex pricing in which such pricing can produce an $\Omega(\log n)$ factor more profit than possible if all items must be priced above cost. However, we do not have any good ($o(\log n)$) approximation algorithms for that setting. \paragraph{Incentive-compatibility} %\label{incentive-online} Our results described above assume the seller ``understands the market'': how many customers will buy different sets of items and at what prices. Thus, we are simply left with a computational problem. If we do not understand the market and are in the setting of an unlimited-supply combinatorial auction, we would instead want an algorithm that is {\em incentive-compatible}, meaning that it is in the bidders' self-interest to reveal their true valuations. Fortunately, a generic reduction of \cite{bbhm-05} shows that if there are sufficiently many bidders, then for problems of this type one can convert any approximation to the computational problem into a nearly-as-good approximation to the incentive-compatible auction problem. In particular, $\tilde{O}\left(h\nitems / \epsilon^2\right)$ bidders are sufficient for this reduction to produce only a factor $(1+\epsilon)$ loss in approximation ratio when all valuations lie in the range $[1,h]$. Essentially, the idea of the reduction is to randomly partitions bidders into two sets $S_1$ and $S_2$, run the approximation algorithm separately on each set, and then use the prices found for $S_1$ on $S_2$ and vice-versa (making the process incentive-compatible); the results in \cite{bbhm-05} then show that $\tilde{O}\left(h\nitems / \epsilon^2\right)$ bidders are sufficient to ensure that the resulting profit is nearly as large as if one had used prices determined on each $S_i$ on that set itself. Related results of \cite{GHW-01,GHKSW-02} give bounds of this form for the case of a single digital good. Thus, if one has sufficiently many bidders, one can focus attention on the computational approximation problem. The above results assume a one-shot mechanism (sealed-bid auction) in which all bidders are present at the same time. We also consider the more demanding case that bidders arrive online, and one must present to each bidder a set of item prices that depend only on bidders seen in the past. We show how methods of \cite{BlumHartline,BKRW} for the online digital-good auction can be applied to our algorithms for graph (or $k$-hypergraph) vertex pricing to achieve good performance for these problems in the online setting as well. For the highway problem, we need a somewhat more involved argument using an algorithm of Kalai and Vempala \cite{KV03}. \paragraph{Organization} The rest of this paper is organized as follows. We begin with basic definitions in \expref{Section}{defs}. We then present our $4$-approximation algorithm for the graph vertex problem in \expref{Section}{sec:graph} and our $O(k)$-approximation algorithm for the $k$-Hypergraph Vertex Pricing problem in \expref{Section}{sec:hyper}. We discuss pricing below cost in \expref{Section}{sec:below-cost}, and present an $O(\log \nitems)$ approximation for the highway problem in \expref{Section}{sec:highway}. We present a fully polynomial time approximation scheme (FPTAS) for the case that the desired subsets of different customers form a hierarchy in \expref{Section}{hierarchy}, and we show how our algorithms can be adapted to achieve good performance in the online setting in \expref{Section}{online}. We finish with a discussion of open questions in \expref{Section}{sec:conclusions}. \section{Notation and Definitions} \label{defs} We consider the following model introduced by Guruswami et al.~\cite{GHKKKS-05}. We assume we have $\ncust$ customers (or ``bidders'') and $\nitems$ items (or ``products''). We are in an \emph{unlimited supply} setting, which means that the seller is able to sell any number of units of each item, and they each have zero marginal cost to the seller (or if they have some fixed marginal cost, we have subtracted that from all valuations and the seller may not sell any item below cost). We consider {\em single-minded bidders}, which means that each customer is interested in only a single bundle of items and has valuation $0$ for all other bundles. Therefore, valuations can be summarized by a set of pairs $(e, \val_e)$ indicating that a customer is interested in bundle (hyperedge) $e$ and values it at $\val_e$. Given the hyperedges $e$ and valuations $\val_e$, we wish to compute a pricing of the items that maximizes the seller's profit. We assume that if the total price of the items in $e$ is at most $\val_e$, then the customer $(e,\val_e)$ will purchase all of the items in $e$, and otherwise the customer will purchase nothing. That is, we want the price vector $\pv=(p_1, \ldots, p_{\nitems})$ with $p_i \geq 0$ for all $i$ that maximizes \[ \profit({\pv}) = \sum_{e:w_e \geq \textrm{price}(e)} {\rm price}(e), \qquad \text{where\ } \textrm{price}(e) = \sum_{i \in e} p_i\,. \] Let $\pvopt$ be the price vector with the maximum profit and let $\OPT=\profit({\pvopt})$. Let us denote by $\setbidders$ the set of customers, and $\setitems$ the set of items, and let $h = \max_{e \in \hyper}{\val_e}$. Let $G=(\setitems, \hyper)$ be the induced hypergraph, whose vertices represent the set of items, and whose hyperedges represent the customers. Notice that $G$ might contain multi-edges since several customers might want the same subset of items. In the special case that all customers want at most two items, so $G$ is a multi-graph (possibly with self-loops), we call this the \emph{graph vertex pricing} problem. As mentioned in \expref{Section}{s:intro}, this pricing problem was shown to be APX-hard in \cite{GHKKKS-05}. If all customers want at most $k$ items, we call this the {\em $k$-hypergraph vertex pricing} problem. Guruswami et al.~\cite{GHKKKS-05} present a simple $O(\log {\ncust} + \log {\nitems})$ approximation algorithm for the general hypergraph vertex pricing problem.\footnote{In fact, it has been shown recently in~\cite{BBM-07} that one can achieve an $O(\log {\ncust} + \log {\nitems})$ approximation for bidders with \emph{general valuation functions} (not only single-minded bidders).} Our goal is to achieve better guarantees for the graph or $k$-hypergraph case when $k = o(\log n)$. \section{Graph Vertex Pricing} \label{sec:graph} We begin by considering the Graph Vertex Pricing problem, and show a factor $4$ approximation. \begin{theorem} \label{thm:graph} There is a $4$-approximation for the Graph Vertex Pricing problem. \end{theorem} \begin{proof} First notice that if $G$ is \emph{bipartite} (with self-loops allowed as well), then there is a simple $2$-approximation algorithm. Specifically, consider the optimal price-vector $\pvopt$ and let $\OPT_L$ be the amount of profit it makes from selling nodes on the left, and $\OPT_R$ be the amount it makes from selling nodes on the right (so $\OPT = \OPT_L + \OPT_R$). Notice that if one takes $\pvopt$ and zeroes out all prices for nodes on the right, then this has profit at least $\OPT_L$ since all previous buyers still buy (and some new ones may too).\footnote{Note that it is essential in this argument that $p_i^* \geq 0$ for all $i$.} Therefore, we can algorithmically make profit at least $\OPT_L$ by setting all prices on the right to $0$, and then separately fixing prices for each node on the left so as to make the most profit possible from each node. That is, for each node $i$, we simply order the buyers who want $i$ by valuation $w_{e_1} \geq w_{e_2} \geq w_{e_3} \ldots$, and choose the price $p_i = w_{e_j}$ maximizing $j w_{e_j}$. (Since the graph is bipartite, the profit made from some node $i$ on the left does not effect the optimal price for some other node $i'$ on the left.) Similarly we can make at least $\OPT_R$ by setting prices on the left to $0$ and optimizing prices of nodes on the right. So, taking the best of both options, we make \[ \max{ \left(\OPT_L, \OPT_R\right)} \geq \frac{\OPT}{2}\,. \] Now consider the general (non-bipartite) case. Define $\wopt_e$ to be the amount of profit that $\OPT$ makes from edge $e$. We will think of $\wopt_e$ as the \emph{weight} of edge $e$, though it is unknown to our algorithm. Let $\hyper_2$ be the set of edges that have two distinct endpoints, and let $\hyper_1$ be the set of self-loops. Let $\OPT_1$ be the profit made by $\pvopt$ on edges in $\hyper_1$ and let $\OPT_2$ be the profit made by $\pvopt$ on edges in $\hyper_2$, so $\sum_{e \in \hyper_i} {\wopt_e} = \OPT_i$ for $i=1,2$ and $\OPT_1+\OPT_2=\OPT$. Now, \emph{randomly} partition the vertices into two sets $L$ and $R$. Since each edge $e \in \hyper_2$ has a 50\% chance of having its endpoints on different sides, in expectation $\frac{1}{2}\OPT_2$ weight is on edges with one endpoint in $L$ and one endpoint in $R$. Thus, if we simply ignore edges in $\hyper_2$ whose endpoints are on the same side and run the algorithm for the bipartite case, the profit we make in expectation is at least \[ \frac{1}{2}\left[\OPT_1 + \frac{\OPT_2}{2}\right] \geq \frac{\OPT}{4}\,. \] This proves the desired result. \end{proof} \paragraph{Derandomization} If desired, the above algorithm can be derandomized using the fact that our analysis only needs the partitioning distribution to be pairwise-independent. In particular, pairwise-independent distributions can be realized using small (polynomial-size) sample spaces~\cite{LW95,MR}. Thus, given a problem instance, one can simply try each possibility in the sample space and then choose the one that produces the highest profit. \section{$k$-Hypergraph Vertex Pricing} \label{sec:hyper} We now show how to extend the algorithm in \expref{Theorem}{thm:graph} to get an $O(k)$-approximation when each customer wants at most $k$ items. This improves over the $O(k^2)$ bound of \cite{BK-06}. \begin{theorem} \label{thm:hypergraph1} There is an $O(k)$-approximation algorithm for the $k$-Hypergraph Vertex Pricing problem. \end{theorem} \begin{proof} We can use the following procedure. \begin{description} \item[Step 1] Randomly partition $V$ into $V_L$ and $V_{rest}$ by placing each node into $V_L$ with probability $\frac{1}{k}$. \item[Step 2] Let $E'$ be the set of edges with \emph{exactly} one endpoint in $V_L$. Ignore all edges in $E - E'$. \item[Step 3] Set prices in $V_{rest}$ to $0$ and set prices in $V_L$ optimally with respect to edges in $E'$. \end{description} To analyze this algorithm, let $\OPT_{i,e}$ denote the profit made by $\pvopt$ selling item $i$ to bidder $e$. (So $\OPT_{i,e} \in \{0, p^*_i\}$ and $\OPT = \sum_{i\in V, e\in E} \OPT_{i,e}$.) Notice that the total profit made in Step 3 is {\em at least} $\sum_{i \in V_L, e \in E'} \OPT_{i,e}$ because setting prices in $V_{rest}$ to $0$ can only increase the number of sales made by $\pvopt$ to bidders in $E'$. Thus, we simply need to analyze the quantity $\E\left[\sum_{i \in V_L, e \in E'} \OPT_{i,e}\right]$. Define indicator random variable $X_{i,e} = 1$ if $i \in V_L$ and $e \in E'$, and $X_{i,e}=0$ otherwise. We have: \begin{equation} \E[X_{i,e}] = \Pr[i \in V_L \mbox{ and } e \in E'] \geq \frac{1}{k}\left(1 - \frac{1}{k}\right)^{k-1}\,. \label{eq:1} \end{equation} Therefore, \begin{eqnarray*} \E\left[\sum_{i \in V_L, e \in E'} \OPT_{i,e}\right] & = & \E\left[\sum_{i\in V, e\in E} X_{i,e}\OPT_{i,e}\right]\\ & = & \sum_{i\in V, e\in E} \E\left[ X_{i,e} \right] \OPT_{i,e} \\ & \geq & \frac{1}{k}\left(1 - \frac{1}{k}\right)^{k-1}\OPT \\ & \geq & \frac{\OPT}{ke}\,. \end{eqnarray*} \end{proof} \paragraph{Derandomization} As with the algorithm of \expref{Theorem}{thm:graph}, the above algorithm for $k$-hypergraph vertex pricing can also be derandomized if desired, but in this case we need the tools of Even et al.~\cite{eglnv98}. First, note that we are only interested in the case that $k$ is $o(\log {\nitems} + \log {\ncust})$, since for larger values of $k$ we can switch to the generic algorithm of Guruswami et al.~\cite{GHKKKS-05}. Thus, we can allow for a blowup of $2^{O(k)}$ in our running time. Now, consider the algorithm in \expref{Theorem}{thm:hypergraph1} and define indicator random variables $X_i=1$ if $i \in V_L$ and $X_i=0$ otherwise. So, each $X_i=1$ with probability $1/k$, and notice that we need only $k$-wise independence among the $X_i$ to calculate $\E[X_{i,e}]$ in Equation~\eqref{eq:1}. Even et al.~\cite{eglnv98} give a construction of small sample spaces that is especially well-suited to our needs. Their construction runs in time polynomial in $2^k$, $\nitems$, and $1/{\epsilon}$, and produces an explicit sample space with the following property: for any $k$-tuple $(X_{i_1}, \ldots, X_{i_k})$ of the random variables $X_i$ and any assignment $(v_1, \ldots, v_k)$ to their values, the fraction of points in their sample space under which these variables all take on those values is within $\pm \epsilon$ of the probability of this event under our product distribution. In particular, the $k$-tuples we care about are those corresponding to edges $e\in E$, with values of the form $(1,0,\ldots,0)$ corresponding to the event that $X_{i,e}=1$. Setting $\epsilon = o\left(1/ k\right)$, we get that under the uniform distribution over their sample space, Equation~\eqref{eq:1} holds up to $1-o(1)$, which suffices for our bounds. Thus, we simply run the construction of Even al.~\cite{eglnv98} using such a value of $\epsilon$, and try each partitioning in their explicit sample space, choosing the one that produces the highest profit. \section{Pricing below Cost} \label{sec:below-cost} Following prior work \cite{GHKKKS-05} we have so far required solutions to satisfy $p_i \geq 0$ for all $i$. In fact, for the case of digital goods, it does not make sense to allow negative prices since even customers $e$ for whom $i \not\in e$ would purchase item $i$ if $p_i < 0$ (and moreover purchase infinitely many copies). However, in the case of products of nonzero marginal cost, where we view $p_i$ as a {\em profit margin} (the difference between sales price and the retailer's cost) it could make sense to allow $p_i$ to be negative. In fact, a retailer might wish to do so in order to induce more purchases of bundles containing both those and other more expensive products. For example, consider four items $A$, $B$, $C$, and $D$, and three customers: one who values $\{A,B\}$ at \$10 above their combined cost, one who values $\{B,C\}$ at \$40 above their cost, and one who values $\{C,D\}$ at \$10 above their cost. If no item can be priced at a loss, then it is not possible to have all three customers buy at their valuations. On the other hand, by pricing $A$ and $D$ at \$10 below cost, and $B$ and $C$ at \$20 above cost, the seller could extract full profit (assuming all costs are at least \$10). More generally, we present an $\Omega(\log n)$ ``positivity gap'': a (bipartite) graph in which there is an $\Omega(\log \nitems)$ gap between the optimal profit achievable without any items priced at a loss and the optimal profit if such pricing is allowed. Specifically: %(see theorem~\ref{gap} below) \begin{theorem} \label{gap} For the graph vertex pricing problem, there exists an $\Omega(\log n)$ gap between the profit achievable when pricing below cost is allowed and the profit achievable when pricing below cost is not allowed. \end{theorem} \begin{proof} Consider a bipartite graph with vertices $\ell_1, \ldots, \ell_n$ on the left and $r_1, \ldots, r_n$ on the right, where for convenience let $n$ be a power of 2. A set $S_1$ of bidders each want bundles of the form $\{\ell_i, r_{i+1}\}$ at \$1 above cost, a set $S_2$ of bidders each want bundles of the form $\{\ell_i, r_{i+2}\}$ at \$2 above cost, a set $S_4$ of bidders each want bundles of the form $\{\ell_i, r_{i+4}\}$ at \$4 above cost, and so forth, up to $S_{n/2}$. Suppose there are $(n-1)n$ bidders in $S_1$ ($n$ for each value of $i\in\{1,\ldots,n-1\}$), there are $(n-2)n/2$ bidders in $S_2$ ($n/2$ for each value of $i\in\{1,\ldots,n-2\}$), there are $(n-4)n/4$ bidders in $S_4$ ($n/4$ for each value of $i\in\{1,\ldots,n-4\}$) and so on, down to $(n/2)2$ bidders in $S_{n/2}$ ($2$ for each $i\in\{1,\ldots,n/2\}$). In this case, if negative profit margins are allowed, then one can price each $\ell_i$ at profit $-i$ and each $r_i$ at profit $i$ and have all bidders buy at exactly their valuations, extracting full profit $\Theta(n^2 \log n)$. On the other hand, the structure of bidders is such that the set of bidders who want any given item form an ``equal revenue distribution.'' In particular, for any pricing in which all items on one side (say on the right) are priced at zero, any pricing of items on the other can produce at most $\Theta(n)$ profit per item, or $\Theta(n^2)$ total. This in turn implies that it is not possible to get more than $\Theta(n^2)$ profit using only non-negative profit margins, since we know the optimal profit achievable using non-negative profit margins is within a factor of 2 of the profit achievable when setting all items on one side of the graph to 0. \end{proof} Notice that our approximation algorithms in Sections~\ref{sec:graph} and~\ref{sec:hyper} only provide good guarantees with respect to the best profit achievable when pricing below cost is not allowed. We do not know whether it is possible to achieve a $o(\log n)$ approximation when pricing below cost is allowed, even for the case of bipartite graphs. For the rest of the paper, we resume considering only the case that all prices must be nonnegative. \section{The Highway Problem} \label{sec:highway} A particular interesting case of the hypergraph pricing problem considered in \cite{GHKKKS-05} is the \emph{highway} problem. In this problem we think of the items $1,2,\ldots,n$ as segments of a highway, and each desired subset $e$ is an interval $[i,j]$ of the highway. A special case of this problem shown in \cite{GHKKKS-05} to be solvable in polynomial time is the case when all path requests share one common end-point $r$. For this case, Guruswami et al.~\cite{GHKKKS-05} give an $O({\ncust}^2)$ exact dynamic programming algorithm, which we will call $\alg$. They also give pseudo-polynomial dynamic programming algorithms for two particular cases: an $O(h^{h+2}{\ncust}^{h+3})$-time exact dynamic programming algorithm for the case when all valuations are integral, and an $O(h^{k+1}\ncust)$ time exact dynamic programming algorithm for the case that furthermore all requests have path lengths bounded by some constant $k$. The highway problem was recently shown to be weakly NP-hard by Briest and Krysta \cite{BK-06}. We present below (\expref{Theorem}{thm:highway}) an $O(\log \nitems)$ approximation algorithm for the highway problem, improving %somewhat over the $O(\log \nitems + \log \ncust )$ approximation guarantee of Guruswami et al.~\cite{GHKKKS-05}. \begin{theorem} \label{thm:highway} There is an $O(\log \nitems)$-approximation algorithm for the highway problem. \end{theorem} \begin{proof} For convenience we assume $n$ is a power of 2 (which we can always achieve by padding). We begin by partitioning the customers into $\log_2 \nitems$ groups. Specifically, let $S_1$ be the set of all customers who want item $\nitems / 2$. Let $S_2$ be the set of all customers not in $S_1$ who want either item $\nitems/4$ or item $3/4$. More generally, let $S_i$ be the set of customers not in $S_1 \cup \cdots \cup S_{i-1}$ who want some item in \[ \left\{ \frac{\nitems}{2^i}, \frac{3\nitems}{2^i}, \ldots, \frac{(2^i-1)\nitems}{2^i} \right\}\,. \] Now, for each set $S_i$ we can use algorithm $\alg$ from \cite{GHKKKS-05} to get a $2$-approximation to the optimal profit over $S_{i}$. Specifically, for each $j \in \{1, \ldots, 2^i-1\}$ let $S_{ij}$ be the subset of customers in $S_i$ who want item $j\nitems/2^i$. Notice that by design, customers in set $S_{ij}$ do not have any desired item in common with customers in $S_{ij'}$ for $j'\neq j$, which means we can consider each of them separately. Now, for each $S_{ij}$ we get a $2$-approximation to $\OPT(S_{ij})$ by running $\alg$ twice, first zeroing out all prices for items $z < j\nitems/2^i$ and then again zeroing out all prices for items $z > j\nitems/2^i$ and taking the best of the two cases. Since there are only $\log_2 \nitems$ groups $S_i$, we simply use the algorithm $\alg$ from \cite{GHKKKS-05} to get a $2$-approximation to the optimal profit over $S_{i}$, and then take the best of all options, thus obtaining a $2\log_2 \nitems$ approximation overall. \end{proof} \subsection{Special cases} Using algorithm $\alg$ we can also get a constant-factor approximation in the special case that everyone wants exactly $k$ items, for any (not necessarily constant) $k$. To see this, split the items into groups $G_1, G_2, \ldots, G_{\nitems/k}$ of size $k$, where $G_1$ consists of the first $k$ items, $G_2$ consists of the next $k$ items and so on, and let $\OPT_{even}$ and $\OPT_{odd}$ be the amount of money that $\OPT$ makes from the even-numbered groups and from the odd-numbered groups respectively. We can make at least $\OPT_{even}/ 2$ as follows. We first set all the prices on items in the odd groups to zero. Now notice that each customer wants items in at most one even-numbered group: let us associate that customer with that group. We can now partition the customers in each even group into two types: those who want the leftmost item in the group and those who want the rightmost item in the group (customers who want both can be assigned arbitrarily). We then run the dynamic program separately over each type, and take the best outcome. In a similar way, we can make at least $\OPT_{odd}/2$ by setting prices for items in the even groups to 0. So we try both and take the best, thus obtaining a factor of $4$ algorithm. Similarly we can get a factor of $4c$ approximation algorithm if for some value of $k$, all customers want between $k/c$ and $k$ elements. \section{When bidders form a hierarchy} \label{hierarchy} We present a fully polynomial time approximation scheme for the case that the desired subsets of different (single-minded) customers form a hierarchy, also known as a laminar family of sets.\footnote{Independently, Briest and Krysta~\cite{BK-06} show a similar result. They also show that this problem in NP-hard.} Specifically, we consider the case of a hypergraph where for any two edges $e,e'$, we have $e \subseteq e'$ or $e \supseteq e'$ or $e \cap e' = \emptyset$. This means that the edges themselves can be viewed as forming a tree structure (actually, a forest) ordered by containment. Let $T_e$ be the set of all bidders whose desired subset is contained in $e$. Note that we can assume for simplicity that we have a binary hierarchy (if the hierarchy is not binary, then we can transform it into a binary hierarchy by adding fake edges $e$, increasing the size of the hypergraph by at most a constant factor). We start by presenting a pseudopolynomial algorithm for the case that the bidders have integral valuations (between $0$ and $h$). In this case, by the integrality lemma in \cite{GHKKKS-05} there exists an integral optimal solution. %%Let $\values $ denote the set $\{0,1, \ldots, \nitems h\}$. For each $e \in \hyper$ and nonnegative integer $\sump \leq h$, let us denote by $n_{\sump}^{e}$ the number of bidders with desired set $e$ whose valuations are at least $\sump$. Now, for each $e \in \hyper$ and nonnegative integer $\sump \leq nh$, let $A[\sump,e]$ represent the maximum possible profit we get from bidders in $T_e$ when the total sum of the prices on items in $e$ is exactly $\sump$. Our dynamic programming algorithm for computing the quantities $A[\sump,e]$ can be now specified as follows. \begin{description} \item[Step 1] For each ``leaf'' $e$ in the hierarchy (an edge $e$ that does not contain any other edges $e'$) initialize $A[\sump,e]= \sump \cdot n_{\sump}^{e}$. \item[Step 2] Consider any edge $e$ with children $e_1$ and $e_2$ whose $A$-values have been computed. Compute \[ A[\sump,e] = \max\limits_{\sump_1+\sump_2 = \sump }{\left(A[\sump_1, e_1] + A[\sump_2, e_2]\right)+\sump n_{\sump}^e}\,. \] \item[Step 3] Return $\max\limits_{\sump \leq nh}{A[\sump,r]}$. (Here $r$ is the root of the hierarchy). \end{description} After computing the $A$-values, we can then easily determine the optimal pricing vector by backtracking. Clearly, the overall procedure above runs in time polynomial in $\nitems$, $\ncust$ and $h$. If we do not want to have a polynomial dependence on $h$, we can instead use the above pseudopolynomial algorithm to obtain an FPTAS in a fairly standard way as follows. \begin{description} \item[Step 1] Given $\epsilon >0$, let $\ell= \frac{\epsilon h}{\nitems \ncust}$. \item[Step 2] Define $\val'_e= \left\lfloor {\frac{\val_e}{\ell}} \right\rfloor$, for each hyperedge $e \in \hyper$. \item[Step 3] Run the dynamic programming algorithm on the instance specified by $G=(\setitems, \hyper)$ and valuations $\val'_e$, and let $\pv'$ be the returned price vector. \item[Step 4] Output the price vector $\tilde{\pv}$ defined as $\tilde{p}_i= \ell \cdot p'_i$, for $i \in \setitems$. \end{description} \begin{theorem} The above algorithm is an FPTAS, achieving profit at least $(1-\epsilon)\OPT$ in time polynomial in $n$, $m$, and $\frac{1}{\epsilon}$. \end{theorem} \begin{proof} In the following discussion, let $\profit_{\val'}(\pv)$ denote the profit made by using the price vector $\pv$ in the rounded instance specified by $G=(\setitems, \hyper)$ and valuations $\val'_e$. In order to prove that the profit we obtain by using $\tilde{\pv}$ in the original instance (given by $G=(\setitems, \hyper)$ and valuations $\val_e$) is at least $(1- \epsilon) \OPT$, we first make some observations. Let $\pv$ be a price vector and let $\subsetitems$ be the set of winners under the pricing scheme $\pv$ in the original instance. If $\pv''$ is the pricing vector defined as $p''_i=\left\lfloor {p_i/\ell} \right\rfloor$ for $i \in \setitems$, then $\profit_{\val'}(\pv'') \geq (1/\ell) \cdot \profit(\pv)-\nitems \ncust$. To see why this is true, notice first that $\subsetitems \subseteq \subsetitems''$, where $\subsetitems''$ is the set of winners under the pricing scheme $\pv''$ in the rounded instance (specified by $G=(\setitems, \hyper)$ and the valuations $\val'_e$). This follows from the fact that $\sum\limits_{i \in e} p_i \leq \val_e$ implies $\sum\limits_{i \in e} p''_i =\sum\limits_{i \in e} {\left\lfloor {p_i/\ell} \right\rfloor} \leq \left\lfloor {\val_e/\ell} \right\rfloor = \val'_e$. This implies \[ \profit_{\val'}(\pv'')=\sum\limits_{e \in \subsetitems''}{ \sum\limits_{i \in e} {p''_i}} \geq \sum\limits_{e \in \subsetitems}{ \sum\limits_{i \in e} {\left(\frac{p_i}{\ell}-1 \right)}} \geq \frac{1}{\ell} \cdot \profit(\pv)- \nitems \ncust\,, \] as desired. Let $\pv'$ be a pricing vector and let $\subsetitems'$ be the set of winners under the pricing scheme $\pv'$ in the rounded instance. If $\tilde{\pv}$ is the pricing vector defined as $\tilde{p}_i= \ell \cdot p'_i $ for $i \in \setitems$, then $\profit(\tilde{\pv}) \geq \ell \cdot \profit_{\val'}(\pv')$. To see why this is true, notice first that $\subsetitems' \subseteq \subsetitems$, where $\subsetitems$ is the set of winners under $\tilde{\pv}$ in the original instance. This follows from the fact that $\sum_{i \in e} p'_i \leq \val'_e$ implies $\sum_{i \in e} \tilde{p}_i =\ell \cdot \sum_{i \in e} { p'_i} \leq \ell \cdot \val'_e= l \left\lfloor {\val_e/\ell} \right\rfloor \leq \val_e$. This implies \[ \profit(\tilde{\pv})=\sum\limits_{e \in \subsetitems}{ \sum\limits_{i \in e} {\tilde{p}_i}}= \sum\limits_{e \in \subsetitems}{ \sum\limits_{i \in e} {\ell \cdot p'_i}} \geq \sum\limits_{e \in \subsetitems'}{ \sum\limits_{i \in e} {\ell \cdot p'_i}}= \ell \cdot \profit_{\val'}(\pv')\,, \] as desired. We are now ready to show that $ \profit(\tilde{\pv}) \geq (1-\epsilon) \OPT$. Let $\pvopt$ and $\pv'$ be the price vectors with the maximum profit in the original and rounded instances respectively, and let $\subsetitems^*$ and $\subsetitems$ be the corresponding set of winners. Let $\tilde{\pv}$ be the price vector defined as $\tilde{p}_i= \ell \cdot p'_i $ for $i \in \setitems$ and let $\pv''$ is the pricing vector defined as $p''_i=\left\lfloor {p^*_i/\ell} \right\rfloor$ for $i \in \setitems$. According to the previous observations we have $\profit(\tilde{\pv}) \geq \ell \cdot \profit_{\val'}(\pv')$. Since $\pv'$ is the price vector with the maximum profit in the rounded instance we have $\profit_{\val'}(\pv') \geq \profit_{\val'}(\pv'')$. Combining these together with the fact that $ \profit_{\val'}(\pv'') \geq (1/\ell) \cdot \profit(\pvopt)- \nitems \ncust$, we get $\profit(\tilde{\pv}) \geq \profit(\pvopt)-\ell \nitems \ncust $, which implies $ \profit(\tilde{\pv}) \geq (1-\epsilon) \OPT$, as desired. Since $\val'_e \leq \nitems \ncust/\epsilon$ for all $e \in \hyper$, we also have that our procedure runs in polynomial time in $\nitems$, $\ncust$, and $1/\epsilon$, thus being an FPTAS for the hierarchy case. \end{proof} \section{Online Pricing} \label{online} As mentioned in \expref{Section}{s:intro}, results of Balcan et al.~\cite{bbhm-05} can be used to convert our algorithms into incentive-compatible mechanisms in the offline ``batch'' setting (\ie, a sealed-bid auction). In this section we consider a natural, more demanding \emph{online} setting in which customers arrive one at a time, and we must assign prices to the items for customer $t$ based only on information about customers $1, \ldots, t-1$. \subsection{The model} We assume customers arrive one at a time. Each customer will be shown a set of item prices, and will then decide whether to purchase or not at those prices. We assume customers cannot return and cannot control their time of arrival, so any take-it-or-leave-it set of prices for customer $t$ based only on information received from customers $1,\ldots,t-1$ is incentive-compatible. In addition, we assume an \emph{oblivious adversary} model: that is, our objective is to achieve good expected performance for any sequence of customers, but this sequence cannot depend on the outcome of any probabilistic choices made by our algorithm. As before, we use $m$ to denote the total number of customers. We consider two information models. In the \emph{full information} model, we assume that after the $t$th customer departs, we learn his desired set $e_t$ and valuation $v_t$. In the more difficult \emph{posted-price} model, we assume we only find out whether and what the customer purchased but not his actual valuations. That is, if he purchases a subset at the current prices, we do not know if he still would have purchased at higher prices, and if he does not purchase at the current prices, we do not know if (or what) he would have purchased at lower prices. In both models, we will be interested in algorithms that perform well compared to the best fixed setting of prices for the entire sequence. Thus, we are comparing to the same notion of $\OPT$ as in the offline case. \medskip \subsection{The Online Graph and $k$-Hypergraph Pricing Problems} \label{online-graph} Our $4$-approximation for graph vertex-pricing, and our $O(k)$-approximation for $k$-hypergraph vertex pricing, can be directly adapted to the online setting by using the results of \cite{BlumHartline,BKRW} for the online digital-good auction. In particular, for the full-information setting, Blum and Hartline \cite{BlumHartline} show the following: \begin{theorem}[\cite{BlumHartline}] Consider the online pricing problem for a single item ($n=1$) in the full-information setting. There exists an online algorithm such that for any given $\epsilon>0$, its expected profit on any input sequence of maximum valuation $h$ is at least \[ (1-\epsilon)\OPT - O\left(\frac{\nitems h}{\epsilon}\log \frac{1}{\epsilon}\right)\,. \] \label{BHthm} \end{theorem} We can now use this to prove the following result. \begin{theorem} Consider the online hypergraph vertex pricing problem in the full-information setting. There exists an online algorithm such that for any given $\epsilon>0$, its expected profit on any input sequence is at least \[ (1-\epsilon)\ALG - O\left(\frac{\nitems h}{\epsilon}\log \frac{1}{\epsilon}\right)\,, \] where $\ALG$ is is the profit of the \emph{offline} approximation algorithm in \expref{Section}{sec:hyper} on that input. \end{theorem} \begin{proof} Note that our algorithms in Sections~\ref{sec:graph} and~\ref{sec:hyper} begin by selecting a subset $V_L$ of items to have non-zero prices, and then achieve their approximation guarantees considering only profit made from customers who want exactly one item in $V_L$. Thus, we can view these algorithms as effectively performing $|V_L|$ separate digital-good auctions, ignoring customers who want zero, or more than one, item from $V_L$. In particular, to apply these algorithms to the full-information online setting, we begin by randomly choosing the set $V_L$ as described in the algorithms, setting prices for items in $V - V_L$ to $0$. We then instantiate a separate copy of the online digital-good auction from~\cite{BlumHartline} for each item $i \in V_L$. When a customer arrives, if the customer wants exactly one item $i$ from $V_L$, then his valuation is given to the associated online auction algorithm. Let $\OPT_i$ denote the optimal profit achievable using a fixed price for item $i$ from customers whose bundles contain item $i$ but no other item in $V_L$. By \expref{Theorem}{BHthm}, the expected profit of the online auction for item $i$ will therefore be at least $(1-\epsilon)\OPT_i - O((h/\epsilon)\log 1/\epsilon)$. %, where $\epsilon>0$ is an input to the online %algorithm and $h$ is the maximum valuation of any customer seen so %far. Thus, overall, we achieve profit at least \[ (1-\epsilon)\sum_{i\in V_L} \OPT_i - O\left(\frac{\nitems h}{\epsilon}\log \frac{1}{\epsilon}\right)\,, \] where $\sum_{i\in V_L} \OPT_i$ is the profit of the \emph{offline} approximation algorithm. Note that we need the assumption of an oblivious adversary for the approximation ratios proved in Sections~\ref{sec:graph} and~\ref{sec:hyper} to apply. \end{proof} In particular, so long as the offline algorithm's profit is $\Omega((\nitems h/ \epsilon^2) \log 1/\epsilon)$, we lose only a $(1 + O(\epsilon))$ factor in the conversion to the online setting. In the posted-price setting, we can obtain a similar result: we only need to apply the associated posted-price algorithms of~\cite{BlumHartline,BKRW}. The only tricky issue is that a customer who chooses not to buy anything must be fed in as a non-buyer to \emph{all} of the online algorithms, in order to ensure that the sequence of customers fed into algorithm $i$ is a superset of the true customers for that item (so that the value of $\OPT$ for the sequence fed to the algorithm is at least as large as the true $\OPT$ for that item). In addition, the algorithms for the posted-price scenario require that the upper-bound $h$ on the maximum valuation be known in advance. \medskip \subsection{The Online Highway Problem} \label{online-highway} For the highway problem, we cannot decompose our solution into a collection of independent digital-good auctions, so the reduction in \expref{Section}{online-graph} does not apply. However, we \emph{can} convert to the online setting by placing this problem in the framework of \emph{online geometric optimization} studied by Kalai and Vempala \cite{KV03} as extended to the case of approximation algorithms by Kakade et al.~\cite{KKL07}. In particular, \cite{KKL07} gives a method to convert any efficient approximation algorithm for offline optimization into an efficient algorithm for \emph{online} optimization with asymptotically the same approximation ratio, for any problem of the following type: \begin{enumerate} \item There is a set $S \subseteq \reals^d$ of \emph{feasible points}. At each time step $t$ we must pick some point $\p^t \in S$; we are then given an objective function $\vv^t \in \reals^d$, and we obtain profit $\p^t \cdot \vv^t$. \item Our goal is to perform nearly as well as the best point $\p \in S$ in hindsight. That is, we want $\sum\limits_t \p^t \cdot \vv^t$ to be nearly as large as $\max\limits_{\p \in S} \sum\limits_t \p \cdot \vv^t$. \item We have an efficient $\alpha$-approximation algorithm for the \emph{offline} optimization problem: given objective function $\vv \in \reals^d$, find the point $\p \in S$ that maximizes $\p \cdot \vv$. \end{enumerate} Kalai and Vempala~\cite{KV03} (for the case of exact offline algorithms) and Kakade et al.~\cite{KKL07} (for the case of approximation algorithms) give a procedure for choosing points $\p^t$ online for any problem of the above type such that the total profit obtained, $\sum_t \p^t \cdot \vv^t$, is within a $(1-\epsilon)/\alpha$ factor of the profit of the best $\p \in S$ in hindsight, minus an additive term that is polynomial in the diameter of $S$ and the maximum $L_1$ magnitude of any $\vv^t$. We can place the highway problem %in which all path requests are of the form $\{1, \ldots, i\}$ into the above setting as follows. First, for simplicity of exposition, let us assume all bidders have integral valuations between $0$ and $h$, and that we are willing to have an algorithm that runs in time polynomial in $h$ as opposed to $\log h$ (the general case can be handled by rounding and scaling as in \expref{Section}{hierarchy}). Now, let $S$ be the set of all possible item prices represented in the following way. Given a pricing of the $n$ items, let $q_{ij}$ denote the total cost of the bundle $[i,j]$. We represent $q_{ij}$ as a vector of length $h$ consisting of $q_{ij}-1$ zeros followed by $h-q_{ij}+1$ entries at value $q_{ij}$. To represent the entire pricing of the $n$ items, we just concatenate these $n^2$ vectors together to create a point in $\reals^d$ for $d = n^2h$. A bidder who desires bundle $[i,j]$ at value $\valueb$ is represented as a vector of all zero entries except for a $1$ in the $\valueb$-th coordinate of the block corresponding to $q_{ij}$. By design, the dot product of this vector with a vector $\p \in S$ is exactly the profit that would be obtained from this bidder by the item-pricing corresponding to $\p$. Finally, we can use the optimization algorithm from \expref{Section}{sec:highway} or from \cite{GHKKKS-05} as our offline optimization oracle. Since the diameter of $S$ is polynomial in $n$ and $h$, and the maximum $L_1$ magnitude of any $\vv^t$ is at most $1$, the total profit obtained will be within a $1+\epsilon$ factor of the approximation ratio guaranteed by the optimization algorithm, minus an additive loss term which is polynomial in $n$ and $h$. Note that for the posted-price version, we just need to apply known extensions of the Kalai-Vempala algorithm to the bandit setting \cite{AwerbuchKleinbergSTOC04,McMahanBlumCOLT04,DaniHayesSODA06,KKL07} in which only the profit $\p^t \cdot \vv^t$ and not the actual vector $\vv^t$ is revealed to the algorithm. \medskip \section{Conclusions} \label{sec:conclusions} We present approximation and online algorithms for a number of problems of pricing items to consumers so as to maximize seller's revenue in an unlimited supply setting. We achieve an $O(k)$-approximation algorithm for the case of single-minded bidders where each consumer wants at most $k$ items, an $O(\log \nitems)$ approximation for the highway problem from \cite{GHKKKS-05}, and a constant factor approximation to the highway problem when all bidders want approximately (up to a constant factor) the same number of items. We also show how some of our approximation algorithms can be adapted to the more demanding online setting in which customers arrive one at a time, in both the full-information and posted-price settings. \subsection{Subsequent Work} \label{subsequent} Following the initial publication of our work, Krauthgamer, Mehta and Rudra~\cite{KMR-07} have provided improved approximation guarantees for the graph vertex pricing problem in the special case when the range of bidders' valuations is small. Briest and Krysta observe~\cite{BB-07} that our algorithms in Sections~\ref{sec:graph} and~\ref{sec:hyper} can be adapted to obtain similar guarantees for the case of unlimited supply \emph{unit-demand} combinatorial auctions. Balcan et al.~\cite{BBCH-07} further study how pricing certain items below their marginal cost can lead to an improvement in overall profit. In particular, they develop the \emph{rebate} and \emph{coupon} models for analyzing this issue and examine ``profitability gaps'' (to what extent can pricing below cost help to improve profit) as well as algorithms for pricing. Elbassioni et al.~\cite{ESZ} give a quasi-polynomial time approximation scheme for the highway problem. \subsection{Open Questions} There are several natural open problems left by this work. First, can one improve on the factor of $4$ for the graph vertex-pricing problem? Any method able to reduce the factor of $2$ for the bipartite case would immediately result in an improved bound. Alternatively, perhaps the reduction to the bipartite case can be improved. Second, can one achieve $o(k)$ for the hypergraph vertex-pricing problem? Even for the general case there remains a gap between the known upper bounds and the lower bound of~\cite{DFHS-06}. Finally, an intriguing question related to this work is: what kind of approximation guarantees are achievable if one allows the seller to price some items below cost (\ie, to have ``loss leaders'')? Some progress on this direction has been made in~\cite{BBCH-07}; however, we still do not know if there exists a constant-factor approximation for the graph vertex pricing problem (even the bipartite case) when negative profit margins on some items are allowed. \section*{Acknowledgements} We would like to thank Jason Hartline for posing the graph vertex-pricing problem to us and for helpful discussions. We would also like to thank the referees for their helpful comments and suggestions. \bibliographystyle{tocplain} \bibliography{a009} \newpage \begin{tocauthors} \begin{tocinfo}[nina] Maria-Florina Balcan \tocabout{}\\ Computer Science Department\\ Carnegie Mellon University\\ Pittsburgh, PA 15213\\ ninamf\tocat{}cs\tocdot{}cmu\tocdot{}edu\\ \url{www.cs.cmu.edu/~ninamf/} \end{tocinfo} \begin{tocinfo}[avrim] Avrim Blum \tocabout{}\\ Computer Science Department\\ Carnegie Mellon University\\ Pittsburgh, PA 15213\\ avrim\tocat{}cs\tocdot{}cmu\tocdot{}edu\\ \url{www.cs.cmu.edu/~avrim/} \end{tocinfo} \end{tocauthors} \begin{tocaboutauthors} \begin{tocabout}[nina] \textsc{Maria-Florina Balcan} is a \phd\ candidate at \href{http://www.cs.cmu.edu/}{Carnegie Mellon University} under the supervision of \href{http://www.cs.cmu.edu/~avrim/}{Avrim Blum}. Everyone who knows her calls her ``Nina,'' a tradition originally started by her brother Marius when he was too young to appreciate longer names. Nina received B.\,S. and M.\,S. degrees from the University of Bucharest, \href{http://fmi.unibuc.ro/}{Faculty of Mathematics and Informatics}, Romania. Her primary research interests are Computational and Statistical Machine Learning, computational aspects of Economics and Game Theory, and Algorithms. She owes much of her interest in Computer Science to Professors Luminita State, her undergraduate mentor, and \href{http://fmi.unibuc.ro/en/cv.php/cs/hristea_florentina_en}{ Florentina Hristea}, her role model at the time, who offered Nina the opportunity of her first \href{http://fmi.unibuc.ro/ro/biblioteca/intrari/imagini/2005/03/mare_470_1.jpg}{ textbook} co-authorship. \end{tocabout} \begin{tocabout}[avrim] \textsc{Avrim Blum} grew up in Berkeley, California, and then went to MIT for undergraduate and graduate school. He received his Ph.\,D.~in Computer Science under supervision of \href{http://theory.lcs.mit.edu/~rivest}{Ron Rivest}, and is now Professor of Computer Science at \href{http://www.cs.cmu.edu}{Carnegie Mellon University}. His research interests include Approximation Algorithms, Algorithmic Game Theory, and Machine Learning Theory. He has two children, Alex and Aaron, who may or may not go into the \href{http://www.cs.cmu.edu/~mblum}{family} \href{http://www.cs.cmu.edu/~lblum}{business}. \end{tocabout} \end{tocaboutauthors} \end{document}