1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
\documentclass{article}
\usepackage[utf8]{inputenc}
\begin{document}
\paragraph{General problem} A user is evolving in an environment, understand how to place ads in this environment.
\paragraph{Model} The environment is a weighted directed graph, the vertices are called the \emph{scenes} (aisles in a store, web pages). The outgoing edges of a vertex are the actions the user can do at this vertex. The weight of an edge is the probability of chosing this action. A user \emph{session} is a Markov process over the graph (shopping session, web browsing session).
\emph{Could be added later: each scene has a duration, the average time spent by a user on this scene.}
On each scene an ad can be displayed. Advertisers want to place their ad on the graph. Each advertiser's request is characterized by the following parameters:
\begin{itemize}
\item a per-impression value
\item a subset of the nodes where the ad can be displayed
\item the expected number of times the ad will be seen
\item \emph{could be added later: the expected duration of exposure to the user}
\item \emph{could be added later: a multiplying factor for the per-impression value if the ad is displayed on consecutive scenes}
\end{itemize}
Two different types of problem:
\begin{itemize}
\item there is a flow of request, only one request can be granted at the same time: when a request arrives, it can either be granted or delayed (with a cost). This yields an online scheduling problem.
\item all the request arrive at the same time, several requests can be granted at the same time, an auction is runned to select the winning advertisers.
\end{itemize}
\paragraph{Related work}
\begin{itemize}
\item \cite{cm} “Slated Cascade model”: the graph is a matrix, the user starts at the top of a column and goes down it, only at the end of the column can he switch to another one. There is a PTAS to compute the assignment which maximizes the social welfare.
\item \cite{oad} the graph is an infinite path and is a modelisation of a web browsing session: on each page their is a constant probability of continuation. The 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}.
\paragraph{Starting problem} 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.
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:
\begin{displaymath}
f(T)= f(r) + \sum_{v\in C(u)} p_v f(T(v))
\end{displaymath}
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.
An assignment of advertisers is a collection of subsets of $T$: $(S_i)_{1\leq i \leq n}$. The elements of $S_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}_{S_i}(u)$.
The goal is to find an assignment which maximizes the social welfare:
\begin{displaymath}
W = \sum_{i=1}^n R_i = \sum_{i=1}^n b_i \mathbf{1}_{S_i}(T)
\end{displaymath}
\bibliographystyle{plain}
\bibliography{papers.bib}
\end{document}
|
