diff options
Diffstat (limited to 'notes.tex')
| -rw-r--r-- | notes.tex | 116 |
1 files changed, 70 insertions, 46 deletions
@@ -4,7 +4,7 @@ \begin{document} \section{Introduction} -\paragraph{General problem} A user is evolving in an environment, understand how +\paragraph{General problem} A user is moving in an environment, understand how to place ads in this environment. \paragraph{Model} The environment is a weighted directed graph, the vertices are @@ -47,72 +47,87 @@ Two different types of problem: paper gives a 7-competitive algorithm against the optimal offline solution. \end{itemize} -\paragraph{Restriction} The graph is a DAG: if the environment is well designed, -the user shouldn't be passing through the same vertex twice. Start first with a -tree or even path and see if all the advertiser's requirements can be matched. - -Muthu's strategy: \emph{find the first non trivial problem and solve it}. - \section{Static ads placement on a tree} \subsection{Notations} -Let $T$ be a weighted tree: for each $u\in T$, $C(u)$ is the set of children of -$u$. For all $v$ in $C(u)$, $p(v)$ will denote the probability of transition -from vertex $u$ to vertex $v$. $T(u)$ is the tree rooted at $u$. $r$ is the root -of the tree. +Let $T$ be a weighted tree. For a node $u\in T$: +\begin{itemize} +\item $C(u)$ is the set of children of $u$ +\item $p(u,v)$ is the transition probability from $u$ to $v\in C(u)$ +\item $r$ is the root of the tree +\end{itemize} For any function $f$ of the nodes, $f(T)$ will denote the expected return of a -random walk on the tree starting at $r$, stopping when it reaches a leaf and -where passing through vertex $v$ adds $f(u)$ to the return: +random walk on the tree starting at $r$, stopping when it reaches a +leaf and earning $f(u)$ for any visited node $u$: \begin{displaymath} - f(T)= f(r) + \sum_{v\in C(u)} p_v f(T(v)) + f(T)= f(r) + \sum_{v\in C(r)} p(r,v) f\big(T(v)\big) \end{displaymath} Introducing the cumulative probabilities yields a simple expression for $f(T)$. Let $\lambda_u$ denote the probability of walking from the root of the -tree to node $u$: $\lambda_u=\Pi_{i=1}^k p(u_k)$, with $u_1, \ldots, u_k$ the +tree to node $u$: $\lambda_u=\Pi_{i=1}^{k-1} p(u_i,u_{i+1})$, with $u_1, \ldots, u_k$ the path from the root to $u$, then: - \begin{displaymath} f(T)= \sum_{u\in T}\lambda_u f(u) \end{displaymath} +note that the lambdas are decreasing along the branches of $T$. + +For our purpose, $f$ will be the indicator function of a subset of +nodes in $T$. For any $S\subset T$, $\mathbf{1}_S$ is defined by: +\begin{displaymath} + \mathbf{1}_S(u) = \left\{ + \begin{array}{ll} + 1\quad \mathrm{if}\; u\in S\\ + 0\quad\mathrm{otherwise} + \end{array} + \right. +\end{displaymath} +$\mathbf{1}_S(T)=\sum_{u\in S}\lambda_u$ is simply the expected number +of views of nodes in $S$ for a user walking in the tree. The lambdas +can then be seen as capacities in terms of number of views. $B$ will +denote the overall capacity of the tree: $\mathbf{1}_T(T)$. \subsection{Problem} -There is a set of $n$ advertisers. $b_i$ is the per-impression value -of advertiser $i$ and $n_i$ the expected number of times advertiser -$i$ would like his ad to be seen. +There is a set of $n$ advertisers. For advertiser $i$: +\begin{itemize} +\item $b_i$ is his per-impression value +\item $n_i$ is his requested number of impressions +\end{itemize} An assignment is a subset $A$ of advertisers and a collection of subsets of $T$: $(A_i)_{i\in S}$. The elements of $A_i$ are the vertices of $T$ where the ad of advertiser $i$ will be displayed. The overall return of advertiser $i$ is simply -$R_i = f_i(T)$ with $f_i:u\mapsto b_i\mathbf{1}_{A_i}(u)$. +$R_i = \mathbf{1}_{A_i}(T)$. The goal is to find an assignment which maximizes the social welfare: \begin{equation}\label{eq:opt} W = \sum_{i\in A} R_i = \sum_{i\in A} b_i \mathbf{1}_{A_i}(T) -\end{equation} with respect to the constraint: - +\end{equation} with respect to the constraints: \begin{equation}\label{eq:constraint} \forall A_i,\; \mathbf{1}_{A_i}(T)\geq n_i \end{equation} - -If \eqref{eq:constraint} is the only constraint, then the optimization problem -is trivial: select the advertiser whose $b_i n_i$ is the greatest and place his -ad on all the nodes of the tree. However, by doing this $\mathbf{1}_{A_i}(T)$ -could be much greater than $n_i$. There are three ways of further refining the -problem to get a reasonable solution: +\begin{equation} + \sum_{i\in A} \mathbf{1}_{A_i}(T) \leq B +\end{equation} +without any other constraint, the optimization problem is trivial: +select the advertiser whose $b_i n_i$ is the greatest and place his ad +on all the nodes of the tree. However, by doing this +$\mathbf{1}_{A_i}(T)$ could be much greater than $n_i$. There are +three ways of further refining the problem to get a reasonable +solution: \begin{enumerate} -\item\label{over-serve} replacing $\mathbf{1}_{A_i}(T)$ by $n_i$ in +\item\label{over-serve} \emph{Free disposal:} replacing $\mathbf{1}_{A_i}(T)$ by $n_i$ in \eqref{eq:opt}. In other words, even if the publisher over-serve an advertiser's request, he will not receive more than what the advertiser was initially willing to pay for. -\item\label{min-screen} adding the constraint $\mathbf{1}_{A_i}(T)\leq n_i + +\item\label{min-screen} \emph{One screen margin:} adding the constraint $\mathbf{1}_{A_i}(T)\leq n_i + \max_{x\in A_i} \lambda_x$: this simply expresses that removing any screen to the set of screens assigned to advertiser $i$ will lead to under-serving his request. -\item\label{fractional} allow fractional occupation of a screen by an ad: in +\item\label{fractional} \emph{Fractional allocation:} allow fractional occupation of a screen by an ad: in addition to choosing a set of screen for advertiser $i$, you can also choose for each screen a fraction of the time this ad will be displayed on the screen. This way, the screen can be share between several ads by doing a @@ -121,16 +136,11 @@ problem to get a reasonable solution: request. \end{enumerate} -Solutions \ref{over-serve}. and \ref{min-screen}. seem to lead to very -complex combinatorial problems (dynamic programming gives a running -time of $O(n2^{|T|})$). Solution \ref{fractional}. seems to be more -realistic: what is the point of having screens if you do not leverage -their ability to change their content frequently? - -Without taking the constraint of the advertisers into account (for -each advertiser, there is a subset of node where his ad can be -displayed), the optimization problem is simply choosing a subset of -advertisers $A$ that maximizes: +\subsection{Trivial Case} +For now we will assume \emph{Fractional allocation}. In this case we +can now serve each request exactly, \eqref{eq:constraint} is +automatically true, and we only need to find a subset $A$ of +advertisers that maximizes: \begin{displaymath} \sum_{i\in A} b_i n_i \end{displaymath} @@ -138,19 +148,33 @@ subject to the constraint: \begin{displaymath} \sum_{i\in A} n_i \leq B \end{displaymath} -where $B$ is the number of views' capacity of the tree. This is -nothing else than a Knapsack Problem. +This is nothing else than a knapsack problem where $b_i n_i$ is the +value of object $i$, $n_i$ is its weight and $B$ is the capacity of +the knapsack. \paragraph{Remarks} \begin{itemize} \item the placement of ads has no importance: the tree is simply seen as a pool of available number of views that can be filled - continuously. -\item the topology of the graph has no impact on the problem, only the - number of nodes does. + continuously in any order. +\item the topology of the graph has no impact on the problem. +\end{itemize} + +\subsection{Contiguous placement} + +To make the problem more interesting we add the following two +constraints: +\begin{itemize} +\item if one ad appears on more than one screen in a branch of the + tree, the screens must be contiguous +\item no ad must be seen on more than two screens \end{itemize} +\subsubsection{Case of the path} + + + Articles to read: \cite{Johnson:PCKP,DBLP:journals/telsys/ShawCC97} \bibliographystyle{plain} |