Initial commit

1 files changed, 59 insertions, 0 deletions

diff --git a/notes.tex b/notes.tex
new file mode 100644
index 0000000..2d6477d
--- /dev/null
+++ b/notes.tex
@@ -0,0 +1,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}