diff options
| -rw-r--r-- | .gitignore | 3 | ||||
| -rw-r--r-- | notes.tex | 59 | ||||
| -rw-r--r-- | papers.bib | 53 | ||||
| -rw-r--r-- | papers/cascade.pdf | bin | 0 -> 163558 bytes | |||
| -rw-r--r-- | papers/story_scheduling.pdf | bin | 0 -> 232708 bytes |
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 Binary files differnew file mode 100644 index 0000000..b0ec5f6 --- /dev/null +++ b/papers/cascade.pdf diff --git a/papers/story_scheduling.pdf b/papers/story_scheduling.pdf Binary files differnew file mode 100644 index 0000000..74cfdab --- /dev/null +++ b/papers/story_scheduling.pdf |