Initial commit

5 files changed, 115 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..e10afc6
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,3 @@
+*~
+
+
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}
diff --git a/papers.bib b/papers.bib
new file mode 100644
index 0000000..e0793f2
--- /dev/null
+++ b/papers.bib
@@ -0,0 +1,53 @@
+@inproceedings{cm,
+  author    = {David Kempe and
+               Mohammad Mahdian},
+  title     = {A Cascade Model for Externalities in Sponsored Search},
+  booktitle = {WINE},
+  year      = {2008},
+  pages     = {585-596},
+  ee        = {http://dx.doi.org/10.1007/978-3-540-92185-1_65},
+  bibsource = {DBLP, http://dblp.uni-trier.de}
+}
+
+
+
+@inproceedings{oad,
+  author    = {Anirban Dasgupta and
+               Arpita Ghosh and
+               Hamid Nazerzadeh and
+               Prabhakar Raghavan},
+  title     = {Online story scheduling in web advertising},
+  booktitle = {SODA},
+  year      = {2009},
+  pages     = {1275-1284},
+  ee        = {http://doi.acm.org/10.1145/1496770.1496908},
+  bibsource = {DBLP, http://dblp.uni-trier.de}
+}
+
+@proceedings{DBLP:conf/soda/2009,
+  editor    = {Claire Mathieu},
+  title     = {Proceedings of the Twentieth Annual ACM-SIAM Symposium on
+               Discrete Algorithms, SODA 2009, New York, NY, USA, January
+               4-6, 2009},
+  booktitle = {SODA},
+  publisher = {SIAM},
+  year      = {2009},
+  ee        = {http://dl.acm.org/citation.cfm?id=1496770},
+  bibsource = {DBLP, http://dblp.uni-trier.de}
+}
+
+@proceedings{DBLP:conf/wine/2008,
+  editor    = {Christos H. Papadimitriou and
+               Shuzhong Zhang},
+  title     = {Internet and Network Economics, 4th International Workshop,
+               WINE 2008, Shanghai, China, December 17-20, 2008. Proceedings},
+  booktitle = {WINE},
+  publisher = {Springer},
+  series    = {Lecture Notes in Computer Science},
+  volume    = {5385},
+  year      = {2008},
+  isbn      = {978-3-540-92184-4},
+  ee        = {http://dx.doi.org/10.1007/978-3-540-92185-1},
+  bibsource = {DBLP, http://dblp.uni-trier.de}
+}
+
diff --git a/papers/cascade.pdf b/papers/cascade.pdf
new file mode 100644
index 0000000..b0ec5f6
--- /dev/null
+++ b/papers/cascade.pdf
diff --git a/papers/story_scheduling.pdf b/papers/story_scheduling.pdf
new file mode 100644
index 0000000..74cfdab
--- /dev/null
+++ b/papers/story_scheduling.pdf