The Ordered Timeline Game: Strategic Posting Times Over a Temporally Ordered Shared Medium

We consider a game of timing between a random number of content creators, who compete for position and exposure time over an ordered shared medium such as an online classified list. Contents (such as ads, messages, multimedia items, or comments) are ordered according to their submission times, with more recent submissions displayed at the top (and better) positions. The instantaneous effectiveness of each item depends on its current display position, as well as on a time-dependent site exposure function which is common to all. Each content creator may choose the submission time of his or her item within a finite time interval, with the goal of maximizing the total exposure of this item. We formulate the problem as a noncooperative game and analyze its symmetric Nash equilibrium. We show existence of the equilibrium profile, characterize it in terms of a differential boundary value problem, provide sufficient conditions for its uniqueness, and devise a numerical scheme for its computation. We further compute the equilibrium profile explicitly for certain special cases, which include a two-player small match and a Poisson-distributed number of players, and evaluate the social efficiency of these equilibria.

1. Otherwise, all \(D+1\) players can arrive at \(t=0\) and remain in positions with maximal relative utility \(r_1\) all the way up to \(T\).

2. Recall from Sect. 2.3 that \(D\) and \(D_0\), the subjective and objective demands, have the same distribution in the Poisson case.

This research was supported by the Israel Science Foundation grant No. 1319/11. This work of the first author was supported by the European Commission within the framework of the CONGAS project FP7-ICT-2011-8-317672.

Authors and Affiliations

1. INRIA, 2004 Route des Lucioles, 06902, Sophia-Antipolis Cedex, France

   Eitan Altman

2. Department of Electrical Engineering, Technion—Israel Institute of Technology, Haifa, 32000, Israel

   Nahum Shimkin

Corresponding author

Correspondence to Eitan Altman.

Proofs for Section 3

We next present the proofs for our main results in the previous section, namely Theorems 1-2 and Proposition 1. We start with the latter, which is also needed for the proofs of the two other theorems.

Proof of Proposition 1 1

Fixing \(L\), we consider the differential Eq. (11) with the stated terminal conditions over \(t\in [t_L,L]\). Denote the right-hand side of (11) by \(H(t,F)\mathop {=}\limits ^{\triangle }r_1u(t)/g(t,F)\). Since \(H\) is nonnegative it follows that \(F'\ge 0\), and noting that \(F_L(L)=1\) we may restrict attention to nondecreasing functions \(F\) with values in \([0,1]\). For simplicity, when \(t_L>0\) we may set \(F_L(t)=0\) for \(t<t_L\). We further consider \(F_L\) to be a member of the Banach space of continuous functions on \([0,T]\), equipped with the sup-norm topology.

\((i)\) As mentioned, Eq. (11) is a retarded FDE in the sense of [6]. Existence and uniqueness of solutions follow by standard results for these equations, once we verify that the right-hand side has appropriate continuity and boundedness properties. Observing \(H\) above, recall that \(u(t)\) is a continuous and bounded function. It is easily verified by straightforward bounds that \(g\) in (8) is (Lipschitz) continuous in \(t\) and in \(F\) (with the sup-norm topology). Therefore, \(H(t,F)\) is also Lipschitz continuous provided that \(g(t,F)\) is bounded away from zero.

We first show that the latter property of \(g\) holds for any \(\epsilon >0\) over \(t\in [t_L(\epsilon ),L]\), where

Indeed, for such \(t\), we obtain from (8) that

where \(q(n)\mathop {=}\limits ^{\triangle }(n+1)p_D(n+1)>0\). Observe that \(r_1-r_2>0\) by assumption, and similarly \(q(n_0)>0\) for some \(n_0\ge 1\), since \(E(D)>0\) by assumption. Furthermore, \(F(s)=1\) for \(t\ge L\), \(F(t)\ge \epsilon \) for \(t\in [t_L(\epsilon ),L]\), and \(B_{0,n}(p) = (1-p)^n\) is decreasing in \(p\). Therefore,

If follows that \(H(t,F)\) is indeed continuous in \((t,F)\) for \(t\in [t_L(\epsilon ),L]\). Existence of a unique local solution to \(F'(t)=H(t,F)\) for \(t\le L\) now follows by Theorem 2.1 in [6]. Since \(H(t,F) \le r_1 u_{\max }/\zeta (\epsilon ,L)<\infty \), it follows by Theorem 3.1 there that the solution \(F(t)\) can be extended to \(t\in [t_L(\epsilon ),L]\). Finally, by taking \(\epsilon \rightarrow 0\), so that \(t_L(\epsilon )\rightarrow t_L\), it follow that a unique solution \(F\) exists on \([t_L,L]\).

\((ii)\) We wish to show that \(g(t,F_L)\) is bounded away from 0 over \(t\in [t_L,L]\). It was already shown in \((i)\) that \(g(t,F)\ge \zeta (\epsilon ,L)>0\) for \(t\in [t_L(\epsilon ),L]\) and any \(\epsilon >0\). However, since \(\zeta (\epsilon ,L)\rightarrow 0\) as \(\epsilon \rightarrow 0\), we need to strengthen this bound for the solution \(F_L\). Setting \(\epsilon =0.5\), we have from that bound that \( g(t,F_L)\ge \zeta (0.5,L)\mathop {=}\limits ^{\triangle }\delta _L >0\) for \(t\in [t_L(0.5),L]\). Clearly, if \(t_L(0.5)=0\), we are done. Otherwise, we still need to bound \(g(t,F)\) for \(t<t_L(0.5)\). Since \(F_L\) is a continuous function, there exists an interval \(I_L\subset [t_L(0.5),L]\) of length \(|I_L|>0\), over which \(F_L(t)\in [0.5,0.6]\). (In fact, since \(g(t,F)\ge \delta _L\) implies that \(F'(t)\le r_1 u_{\max }/\delta _L\), it may be seen that \(|I_L|>0.1 \delta _L/r_1 u_{\max }\).) Therefore, similar to (27), we obtain that

where we have used that fact that \(F_L(s)\le 0.6\) for \(s\in I_L\), so that \(F_L(s)-F_L(t)\le 0.6\) as well. Using the above-mentioned bound on \(|I_L|\), we finally obtain

This provides the required uniform bound over \(g(t,F_L)\) for \(t<t_L(0.5)\). Combining the above bounds on \(g\), we obtain that \(g(t,F_L)\ge \min \{\delta _L,\eta _L\}\mathop {=}\limits ^{\triangle }\epsilon _L>0\) for \(t\in [t_L,L]\), as stated.

\((iii)\) Continuity in \(L\) of the solutions \(F_L\) to our equation \(F'_L(t)=H(t,F_L)\) follows by Theorem 2.2 (Continuous dependence) in [6], once we show each \(L\in (0,T)\) has a neighborhood \(N_L=(L-\epsilon ,L+\epsilon )\) such that \(H(t,F_{L'})\) is uniformly bounded over all \(t\) and solutions \(F_{L'}\), \(L'\in N_{\epsilon }(L)\). Since \(H(t,F) \le r_1 u_{\max } / g(t,F)\), the required uniform boundedness follows by observing the bound \(g(t,F_L)\ge \epsilon _L>0\) developed in item \((ii)\) above, and further noting that \(\epsilon _L\) is continuous (in fact linear) in \(L\), as may be seen in the above proof. Continuity of \(t_L\) in \(L\) follows immediately from that of the solution \(F_L\).

This completes the proof of Proposition 1. \(\square \)

We next address the proof of Theorem 1, which relies on several Lemmas. The next two establish properties \((i)\), \((ii)\) and \((iv)\) of the theorem.

For a given distribution function \(F\), let \(\eta _F\) denote the corresponding probability measure on the reals. Recall that \({ supp}(F)\) denotes the support of \(\eta _F\), i.e., the smallest closed set of \(\eta _F\)-probability 1.

Lemma 1

Let \(F\) be an equilibrium profile. Then,

1. (i)

   \(F(t)\) is a continuous function of \(t\in [0,T]\) (i.e, \(\eta _F\) does not contain any point masses).

2. (ii)

   \(U(t,F)\) is a continuous function of \(t\in [0,T]\).

3. (iii)

   \({ supp}(F)\) is an interval \([0,L]\), with \(L<T\).

Proof

\((i)\) Suppose \(\eta _F\) contains a point mass at \(t\), namely \(F(t)-F(t-)=q>0\). We claim that, for \(\epsilon >0\) small enough, \(U(t+\epsilon ;F)\) will be strictly larger than \(U(t;F)\). But this contradicts the equilibrium properties in (5)-(6), since \(U(t,F)<u^*\mathop {=}\limits ^{\triangle }\max _s U(s,F)\) and \(\eta _F(\{t\})>0\).

To see that \(U(t;F)<U(t+\epsilon ;F)\) for \(\epsilon \) small enough, consider a specific player \(i\) who arrives at \(t\), and note that having a point mass at \(t\) implies that, with positive probability, at least one other player arrives at \(t\) simultaneously. Recall that the ordering of simultaneous arrivals is random, so that in that case player \(i\) has a probability of at least 0.5 to be immediately placed in position 2 or worse. On the other hand, arriving at a slightly later time \(t+\epsilon \) guarantees that the player will be placed higher than all other arrivals at \(t\), thereby strictly improving his expected utility over \([t+\epsilon ,T]\) relative to the previous case by a quantity \(\delta \) which is bounded away from 0 even as \(\epsilon \rightarrow 0\), while the utility loss over \([t,t+\epsilon ]\) is bounded by \(\epsilon r_1^*\), which is arbitrarily small. Here, \(r_1^* \mathop {=}\limits ^{\triangle }r_1\max _{t\in [0,T]}u(t)\).

\((ii)\) Again, we compare \(U(t;F)\) to \(U(t+\epsilon ;F)\). For \(\epsilon >0\), since there are no point masses in \(\eta _F\) (as just established), then \(\eta _F\{[t,t+\epsilon ]\} \rightarrow 0\) as \(\epsilon \rightarrow 0\), so that the probability \(\delta (\epsilon )\) of an arrival on that interval converges to 0 as \(\epsilon \rightarrow 0\). Now, a player that arrives at \(t+\epsilon \) rather than \(t\) will incur a utility loss of at most \(\epsilon r_1^*\) over \([t,t+\epsilon ]\), and a utility gain of \(\delta (\epsilon )T r_1^*\) at most over \([t+\epsilon ,T]\). Therefore, \(\lim _{\epsilon \rightarrow 0}|U(t+\epsilon ;F)-U(t,F)|\le r_1^* |\epsilon -\delta (\epsilon )T|\) converges to 0 as \(\epsilon \rightarrow 0\), establishing continuity from the right. A similar argument holds for \(\epsilon <0\).

\((iii)\) To show that the support \({ supp}(F)\) is an interval of the form \([0,L]\), suppose to the contrary that there exists an interval \((t,s)\), \(t<s\) such that \(\eta _F\{[t,s]\}=0\) and \(F(s)<1\). We can extend \(s\) to the right while keeping the above properties till it hits \({ supp}(F)\). Then, by property (5) of the NEP and the above-established continuity of \(U(\cdot ;F)\), it follows that \(U(s;F)=u^*\). But now, since there are no arrivals on \((t,s)\), an arrival at \(s-\epsilon \) will remain in position 1 until time \(s\), implying that \(U(s-\epsilon ;F)\ge U(s;F)+\epsilon r_1[\min _{t\in [s-\epsilon ,s]}u(t)] > u^*\), which contradicts the definition of \(u^*\).

Finally, we show that \(L<T\). It is clear that \(U(T-\epsilon ;F)\le \epsilon r_1^*\). Therefore, \(U(t;F)<u^*\) for \(t>t_0=T-u^*/r_1^*\), implying that \((t_0,T]\) does not belong to \({ supp}(F)\). \(\square \)

Lemma 2

Any equilibrium profile \(F\) satisfies properties \((i)\), \((ii)\), \((iv)\) of Theorem 1.

Proof

Property \((i)\) was established in Lemma 1. For property \((ii)\), suppose \(F\) is an equilibrium profile. Since \(U(\cdot ;F)\) is continuous by Lemma 1 \((ii)\), it follows by property \((i)\) and the definition of the equilibrium that \(U(t;F)=u^*_F\) on \([0,L]\), which is property \((ii)\). Conversely, suppose that some continuous strategy \(F\) satisfies property \((ii)\). By definition of the equilibrium, to establish that \(F\) is indeed an equilibrium strategy it only remains to show that \(U(t;F)\le u_L\) for \(t>L\). But since there are no other arrivals on \([L,T]\) under \(F\), then any arrival there would remain in the first position till \(T\), so that \(U(t;F)=r_1 \int _t^T r_1 u(s)\hbox {d}s\) for \(t\in [L,T]\). Since \(u(s)>0\) it follows that \(U(t;F)<U(L;F)=u_L\) for \(t>L\), as required, and property \((ii)\) is established. Property \((iv)\) follows by observing that \(u_L^*=U(L;F)\) and substituting the last integral. \(\square \)

It remains to establish the differential characterization of Theorem 1 \((iii)\), and the existence claim in that theorem. We begin by computing the time derivative of the utility function \(U(t;F)\) in (4).

Lemma 3

For any strategy \(F\), the following holds:

1. (i)

   At any point \(t\) at which \(F\) is differentiable,

   $$\begin{aligned} \frac{d}{\hbox {d}t}U(t;F) = -r_1 u(t)+F'(t)g(t,F) \,, \end{aligned}$$

   (28)

   where \(g\) is defined in Eq. (8).

2. (ii)

   Conversely, if \(U\) is differentiable at \(t\) and \(g(t,F)>0\) there, then \(F\) is differentiable at \(t\); hence, \(F'(t)\) satisfies Eq. (28).

3. (iii)

   The function \(g(\cdot ;F)\) is continuous over \(t\in [0,T]\), and strictly positive for all \(t<T\) (except for the degenerate case where \(F(T^-)=0\), in which \(g\equiv 0\)).

Proof

\((i)\) By formally differentiating (4) under the integral sign,

Further, observing (3),

Recalling the definition of \(B_{k,n}\) in (2),

(where we use the convention that \(B_{-1,n+1}=B_{n,n-1}=0\)), so that

It remains to simplify the sum in the last expression.

Denoting \(q_n=np_D(n)\), observe that

where the first equality follows by an index shift, and the second by observing again that \(B_{k,n}\equiv 0\) for \(n=k-1\) or \(k=-1\), while \(r_{K+1}=0\) by definition. Substituting (33) in (32) gives the equality in (28), with \(g\) as defined in (8).

Existence of the derivative of \(U\) at \(t\) now follows by observing that, on the right-hand side of (28), both \(u\) and \(g\) are continuous functions of \(t\) (the first by assumption, and the second by its definition as an integral).

\((ii)\) Recall that \(u(t)\) is continuous by assumption and so is \(g\) (as observed in \((iii)\)). Observing (28) and the assumed positivity of \(g(t,F)\), existence of \(F'(t)\) may now be inferred by basic calculus from the expression (4) for \(U\).

\((iii)\) Observing (8), continuity follows by the definition of \(g\) as an integral over a bounded function. Note that the sum \(\sum _{n\ge k}(n+1)p_D(n+1)\) is bounded by \(E(D)\), which is finite by assumption. Strict positivity of \(g(t,F)\) follows as in Proposition 1 \((ii)\). \(\square \)

The next Lemma establishes the differential characterization of the equilibrium in Theorem 1.

Lemma 4

Part \((iii)\) of Theorem 1 holds true. That is,

1. (i)

   A continuous distribution function \(F:[0,T]\rightarrow [0,1]\) that satisfies the properties in Theorem 1 \((iii)\) is an equilibrium profile.

2. (ii)

   Conversely, any equilibrium profile \(F\) satisfies the properties stated in Theorem 1 \((iii)\).

Proof

\((i)\) From (9) and (28) we obtain that \(\frac{d}{\hbox {d}t}U(t;F)=0\) for \(t\in (0,L)\). Since \(U\) is continuous it follows that \(U(t;F)=u\), \(t\in [0,L]\) for some constant \(u\). Therefore, by Theorem 1 \((ii)\), \(F\) is an equilibrium profile.

\((ii)\) Suppose \(F\) is an equilibrium profile. In view of Theorem 1 \((ii)\), it only remains to verify (9). Now, Theorem 1 \((ii)\) also implies that \(U(t;F)=u_F\) for \(t\in [0,L]\); hence, \(\frac{d}{\hbox {d}t}U(t;F)=0\) for \(t\in (0,L)\). Observing Lemma 3 \((ii)\)-\((iii)\) and Eq. (28), it follows that \(-r_1u(t)+F'(t)g(t,F)=0\) (with \(g(t,F)>0\)), and Eq. (9) follows. \(\square \)

Lemma 5

There exists an equilibrium profile \(F\).

Proof

We demonstrate existence of a distribution function \(F\) that satisfies the requirements of Theorem 1 \((iii)\). For each \(L\in (0,T)\), let \(F_L(t)\), \(t\in [t_L,T]\) denote the solution of Equation \(F_L(t)\) as defined in Proposition 1. Note that \(F_L(t_L)=0\) if \(t_L>0\). To simplicity the exposition, if \(t_L>0\) extend \(F_L\) linearly up to \(t=0\) using \(F_L(t)=-(t_L-t)\), \(t\in [0,t_L]\). By part \((iii)\) of Proposition 1, \(F_L(0)\) is continuous in \(L\). We show below that \(t_L>0\) (hence, \(F_L(0)<0\)) for \(L\) close enough to \(T\), while \(F_L(0)>0\) for \(L\) close enough to 0. By the above-mentioned continuity, this implies that \(F_L(0)=0\) for some intermediate \(L\in (0,T)\). It follows that for this value of \(L\), \(F_L\) satisfies all the requirements in Theorem 1 \((iii)\) and is therefore an equilibrium profile.

To verify that \(F_L(0)>0\) for \(L\) close enough to 0, observe that \(g(t,F)\) in (8) is bounded away from zero, while \(F(t)\) is positive: In particular, using the bound in Eq. (27), if \(L\le T/2\) and \(F(t)\ge 0.5\) we have

Therefore, \(F'_L(t)=r_1u(t)/g(t,F_L) \le r_1 u_{\max }/\zeta _0\) under these conditions, and since \(F_L(L)=1\) this implies that \(F_L(0)\ge 0.5\) if \(L<\frac{1}{2}\zeta _0/r_1u_{\max }\,\).

To verify that \(t_L>0\) for \(L\) close enough to \(T\), observe from (8) that \(g\) is upper bounded by

Therefore, by (9),

By integration, this implies

Since the last denominator is arbitrarily small for \(L\) close enough to \(T\), and recalling that \(u(s)>0\), it follows that \(F_L(t)=0\) for some \(t>0\) (namely \(t_L>0\)) for such \(L\).

This completes the proof of existence of an equilibrium profile. \(\square \)

Proof of Theorem 1 2

Items \((i)\)-\((iv)\) of this Theorem were proven in Lemmas 2 and 4, while existence of an equilibrium profile was established in Lemma 5. \(\square \)

We may now proceed to the proof of the uniqueness claim in Theorem 2. The proof relies on the following monotonicity properties of the function \(g\), as defined in (8).

Lemma 6

Let Assumption 2 hold.

1. (i)

   For each \(n\ge 0\), the function

   $$\begin{aligned} f_n(p) = \sum _{k=0}^{K-1} (r_{k+1}-r_{k+2}) B_{k,n}(p)\,,\quad p\in [0,1] \end{aligned}$$

   is nonincreasing in \(p\).

2. (ii)

   Consequently, let \(F_1\) and \(F_2\) be two strategy profiles (namely distribution functions over \([0,T]\)) such that, for some \(t\in [0,T)\),

   $$\begin{aligned} F_2(s)-F_2(t) \ge F_1(s)-F_1(t) \text { for all }s\in [t,T] . \end{aligned}$$

   (34)

   Then, \(g(t,F_2)\le g(t,F_1)\).

3. (iii)

   If, in addition, the inequality in (34) is strict over some nonempty interval \(I\subset [t,T]\), then either \(g(t,F_2) < g(t,F_1)\), or else \(g(\tau ,F_2)=g(\tau ,F_1)\) for all \(\tau \in [0,T]\).

Proof

\((i)\) Denote \(\delta _k=r_k-r_{k+1}\). A similar calculation to Eqs. (31) and (33) yields,

But Assumption 2 implies that \(\delta _{k+1}-\delta _{k}=2r_{k+1} - r_k - r_{k+2}\le 0\), so that \(f_n'(p) \le 0\).

\((ii)\) Changing the order of summation in (8), and recalling that \(B_{k,n}\equiv 0\) for \(k>n\), \(g\) may be rewritten as

where \(q_n=(n+1)p_D(n+1)\ge 0\). The claim now follows directly from \((i)\) and the assumed relation (34) between \(F_1\) and \(F_2\).

\((iii)\) For each \(n\ge 0\), it may be seen from (35) that either \(q_{n}f_n'(q)\equiv 0\) for \(q\in [0,1]\), or \(q_{n}f_n'(q) < 0\) for all \(q\in (0,1)\). Suppose first that the former holds for all \(n\ge 0\). Then, by (36), \(g(t,F)\) does not depend on \(F\), so that \(g(\cdot ,F_1)=g(\cdot ,F_2)\). Otherwise, suppose that the latter holds for some \(m\ge 0\), namely \(q_{m}f_{m}'(q) < 0\) for \(q\in (0,1)\). Then, wherever (34) holds with a strict inequality,

which holds over \(s\in I\). Substituting in (36) obtains \(g(t,F_2) < g(t,F_1)\). \(\square \)

Proof of Theorem 2 (uniqueness)

Recall that an equilibrium profile \(F\) satisfies the properties in Theorem 1 with some parameter \(L\). In particular, \(F(t)=1\) on \(t\in [L,T]\), \(F\) satisfies Eq. (9) on \([0,L]\), and \(F(0)=0\). Let \(F_1\) and \(F_2\) denote two equilibrium profiles with corresponding parameters \(L_1\) and \(L_2\). We will show below that \(L_1<L_2\) implies that \(F_2(0)<F_1(0)\), so that only one can be an equilibrium. Therefore, \(L_1=L_2\). But Proposition 1 implies that \(L\) defines \(F\) uniquely; hence, the equilibrium is unique.

Consider then \(F_1\) and \(F_2\) as above, and suppose that \(L_1<L_2\). Since \(F_1(s) = 1\) for \(s\in [L_1,T]\) and \(F_2\) is strictly increasing over \(t<L_2\), it follows that

and

Therefore, inequality (34) is satisfied with strict inequality for \(t=L_1\). By Lemma 6 \((iii)\), exactly one of the following two conclusions holds:

(a) \(g(t,F_2)=g(t,F_1)\) for all \(t\in [0,T]\). In that case it follows from (9) that \(F_2'(t) = F_1'(t)\) holds for \(t\le L_1\), so that

(b) \(g(t,F_2)<g(t,F_1)\) at \(t=L_1\). By (9), this implies that \(F_2'(L_1) > F_1'(L_1^-)\). We argue that this inequality extends to all \(t<L_1\). Suppose, to the contrary, that \(F_2'(\tau ) \le F_1'(\tau )\) for some \(\tau <L_1\). Noting that \(F_1'\) and \(F_2'\) are continuous on \([0,L_1)\) by (9), there must exist a time \(t_0<L_1\) so that \(F_2'(t_0) = F_1'(t_0)\), while \(F_2'(s) > F_1'(s)\) for \(s\in (t_0,L_1]\). By integration, it follows that

Combined with (38), we may apply Lemma 6 \((iii)\) to deduce that \(g(t_0,F_2)<g(t_0,F_1)\); hence, \(F_2'(t_0) > F_1'(t_0)\). But this contradicts the definition of \(t_0\). We have thus verified that \(F_2'(t) > F_1'(t)\) for all \(t<L\). But this implies that \(F_2(0)-F_1(0)<F_2(L_1)-F_1(L_1)<0\), where the first inequality follows by integration, and the second from (37).

We have thus shown that \(L_1<L_2\) implies \(F_2(0)<F_1(0)\), which completes the proof of Theorem 2. \(\square \)

Reprints and permissions