A little operations research into TV programming: simulation and remarks

I wrote a little C++ program implementing the TV scheduling algorithm we devised a few entries ago and used it to do several calculations and get some intuition about how the optimum scheduling looks like.

The figure shows in solid beige an audience curve reaching its maximum around the central slot. The competition has placed its resources (amounting to a total C = 165) according to a sinusoidal function with maxima at slots 3-4 and minima at 8-9 (gray line). We have depicted the resulting OTVS distribution for M = 20, 120 and 220. When our resources are much less than the competition's, the optimum distribution concentrates on the slots of higher profitability from our point or view, i.e. those with higher a_i/c_i. As our resources grow the distribution progressively approaches the limit shape √(a_ic_i). This suggests the following rule of thumb for allocating resources: when you're a weak player, concentrate your resources on the competition's valleys.

What about the competition's optimum behavior, i.e. how to best distribute resources a priori without information on the opponent scheduling? Assuming the solution to OTVS is such that m_i ≥ 0 for all i, we have

S({m_i}) = A − (∑√(a_ic_i))²/(M+C),

where A = ∑a_i. It is then easy to see, using Cauchy's Inequality, that the best policy for the competition is to just follow the audience curve, i.e. set c_i = (C/A)a_i. In this case, the resulting scenario is disappointingly simple: our corresponding counter-scheduling is simply m_i = (M/A)a_i and we obtain our fair share of the audience, S({m_i}) = M/(M+C). It is only when the competition deviates from its natural distribution that we can get more than our money can buy, so to speak.

All the King's philosophers: part I

In one of the rare occasions when the mathematician Muhammad ibn Mūsā al-Khwārizmī travelled abroad from his homeland, the caravan he was joining made a stop at the ancient city of Samarkand. Upon being informed of his arrival, the King, who was a learned man and knew of the scientific reputation of the traveller, quickly summoned al-Khwārizmī to his palace and made him his guest for the night. After dinner both men engaged in conversation about scientifical subjects. Impressed by the erudition of al-Khwārizmī, the King then decided to confide the mathematician a problem that was troubling him for long.

"Muhammad ibn Mūsā al-Khwārizmī, as you see I hold the deepest reverence for science, and this devotion led me to the decision of ruling my kingdom according to the teachings of Philosophy. To that purpose, I gathered over the years a Council of Philosophers formed by some of the most learned men on the Earth. When I have some difficult decision to make, I summon the Council and ask them for advice. And here my problems begin: to whichever question I pose to the philosophers, each of them provides me with a different answer, and it is not uncommon that they begin quarreling among themselves about the subject, and I end up a little upset and without answers to my problem."

"I considered establishing some kind of rule by which to determine the conclusion to questions posed to the Council, like for instance taking the opinion held by the most philosophers, but I fear that such a rule could lead to contradictory judgements over time. While I undertand that each philosopher, taken in isolation, posseses a consistent view of the world and his tenets match that view, it is not clear how to combine all the different doctrines into a global set of precepts that can assist my heavy duties as the ruler of the country."

"I see that your skills in the ways of Mathematics are second to none, and a mathematical problem I have indeed. Would you help the King to find the Rule that will determine the outcome of questions posed to the Council of Philosophers? The compensation for your work would be in accordance with your mathematical eminence and my royal munificence" concluded the King, leaning back and slowly rubbing his jewellery-loaded hands.

The mathematician pondered the proposal for a mere few seconds and then replied "I am your servant, my lord", lowering his eyes, which were somewhat obfuscated by the wine and the glitter of the King's rings.

Lane inversion

I often observe the following when a highway with two lanes per direction approaches congestion: under light traffic conditions, most vehicles stay on the right track so that the left lane is used for passing, as it should be; as traffic increases, the chances are higher that one cannot use the left lane to pass a slow vehicle because a third one is passing both, so users of the passing lane perceive there is a penalty in returning to the right, and ultimately most vehicles stay on the left lane; when this happens, the right lane begins to be used as a passing lane (even though in Spain, and I guess in many other countries, passing on the right is forbidden), and it turns out that the left lane becomes the slowest one. I take this phenomenon of lane inversion to be a sure sign that total congestion is coming on.

I wonder how much the throughput (traffic before congestion) of the highway would be raised if passing on the right was allowed and either lane could be used in cruise conditions.

A little operations research into TV programming: analytical solution

We derive an analytical solution to the optimum TV scheduling (OTVS) problem posed at a prior entry. In the rest we assume a_i,c_i > 0 for all i=1,...,n. We begin by solving a generalization of OTVS that is amenable to a more regular treatment following techniques similar to those of Variational Calculus, and then seek ways to constrain this problem so as to find solutions to OTVS itself.

Definition. Given I a subset of {1,...,n}, the generalized OTVS problem on I, GOTVS(I), consists of finding a resource distribution {m_i, m_i > −c_i, i in I} with ∑_Im_i = M that maximizes S({m_i}) = ∑_Is(m_i) = ∑_Ia_im_i/(m_i+c_i). Note that in OTVS we imposed the tighter restriction m_i ≥ 0.

Lemma. Consider the space of all distributions {m_i, m_i > −c_i, i in I} with ∑_Im_i = M. The limit of S({m_i}) when min({m_i+c_i}) → 0 is −∞.

Proof. ∑_Is(m_i) can be split into its positive terms, whose sum is bounded by ∑_Ia_i, and its negative terms, among which at least one tends to −∞.

Corollary. GOTVS(I) has a solution.

Proof. Given the result above, GOTVS(I) is equivalent to finding a maximum value of the continuous function S inside the compact set {m_i, m_i ≥ −c_i+δ,i in I} with ∑_Im_i = M, for some fixed δ>0.

Theorem. Let d_i = ∂s(m_i)/∂m_i = a_ic_i/(m_i+c_i)². If {m_i} is a solution to GOTVS(I) , then

d_j = d_k, for all j,k in I.

Proof. If d_j > d_k, we could then obtain a net gain in S({m_i}) by transferring some quantity δ from m_k to m_j.

Corollary. GOTVS(I) has a unique solution of the form

m_i = k√(a_ic_i) − c_i, i in I,

where

k = (M+∑_Ic_j)/∑_I√(a_jc_j).

Proof. Solve d_i = a_ic_i/(m_i+c_i)² = 1/k², i in I, with the additional constraint ∑_Im_i = M.

Now, solving OTVS reduces to finding a solution to GOTVS(I) with no negative components for some maximal subset I of {1,...,n}. It turns out that finding the support of the solution to OTVS is fairly simple:

Theorem. Let {m_i} be a solution to OTVS and define t_i = (∂s(m_i)/∂m_i)_mi=0 = a_i/c_i. For all j,p in I, if t_j ≥ t_p and m_p > 0 then m_j > 0.

Proof. Let us suppose m_j = 0; as t_j = (∂s(m_j)/∂m_j)_mj=0 ≥ t_p = a_p/c_p > a_pc_p/(m_p+c_p)² = ∂s(m_p)/∂m_p, transferring some quantity δ from m_p to m_j would yield a solution without negative components and with greater S than {m_i}.

Corollary. Let σ: I → I be a permutation of I such that t_σ(1) ≥ t_σ(2) ≥ ··· ≥ t_σ(n). There is some τ in {1,...,n} such that the support of solutions to OTVS is {σ(1),...,σ(τ)}; moreover, t_σ(τ) is strictly greater than t_σ(τ+1) (except, of course, if τ = n).

Corollary. The solution to OTVS is unique.

The following pseudocode sketches an algorithm for computing OTVS.

OTVS({a_i}, {c_i}, M)
m₁,...,m_n ← 0
knum ← M
kden ← 0
τ ← n
compute σ
for i = 1 to n
····if (knum+c_σ(i))/(kden+√(a_σ(i)c_σ(i))) > c_σ(i)/√(a_σ(i)c_σ(i)) then
········τ ← i−1
········break
····else
········knum ← knum + c_σ(i)
········kden ← kden + √(a_σ(i)c_σ(i))
····end if
end for
k ← knum/kden
for i = 1 to τ
····m_σ(i) ← k√(a_σ(i)c_σ(i)) −c_σ(i)
end for

The idea is as follows: we keep visiting indices from the highest t_i downward and maintain the running numerator and denominator of the value that k would take if the elements visited so far were exactly those comprising the support of the solution to OTVS. When we come upon an element for which its computed m_i would be negative, we know we've gotten to the cutoff index τ and that the k calculated so far is the actual one, so we just use it for computing the final values of {m_i}.

Erasmus' slippages in math and logic

In Erasmus' satirical essay The Praise of Folly, Goddess Folly exposes in a jokingly manner how the entire humankind is subject to her dominion. Near the end of the book (chapter 63 according to the Spanish translation that I have) we read:

Ecclesiastes says in his first chapter, "The number of fools is infinite;" and when he calls it infinite, does he not seem to comprehend all men, unless it be some few whom yet 'tis a question whether any man ever saw?

Here Erasmus seems to imply that detracting an infinite quantity (the fool) from a set (all men) can only leave finitely many remaining elements, which of course is not true. About a hundred years later, Galileo shows a clearer understanding of a related problem in his celebrated paradox, which observes that natural numbers can be put in a one-to-one relation with square numbers, even though the latter form a strict subset of the former. Galileo prudently chooses to restrict terms like "greater" or "equal" to finite quantities alone so as to escape the riddle. We will have to wait another 250 years for Cantor to show us the way into the paradise of infinity; so, we can't really blame Erasmus too hard on this one.

A few sentences later we find the following apparent glitch:

For by the moon interpreters understand human nature, and by the sun, God, the only fountain of light; with which agrees that which Christ himself in the Gospel denies, that anyone is to be called good but one, and that is God. And then if he is a fool that is not wise, and every good man according to the Stoics is a wise man, it is no wonder if all mankind be concluded under folly.

The flawed reasoning can be rendered in logical notation like this (leaving out the bit on the goodness of God):

x −Good(x)
x −Wise(x) → Fool(x)
x Good(x) → Wise(x)
implies
x Fool(x)

which is a non sequitur: there could be evil wise. The argument would be correct, however, if we had the following instead of the third premise:

x Wise(x) → Good(x)

So, before declaring Erasmus guilty of logical mistake, let's examine the original latin source (bolds mine):

Siquidem Lunam humanam naturam interpretantur, Solem omnis luminis fontem, Deum. Huic adstipulatur quod ipse Christus in Euangelio negat, quemquam appellandum bonum, nisi Deum unum. Porro si stultus est, quisquis sapiens non est, et quisquis bonus, idem sapiens, auctoribus Stoicis, nimirum mortales omneis Stultitia complectatur necessum est.

As far as I can tell, the correct interpretation of the marked part is x Good(x) → Wise(x), so Erasmus got it wrong. Unlike the case with infinity, here we can't concede the author the excuse of having been born too early: he should have known better.

A little operations research into TV programming

Consider the following idealized model of a TV channel faced with the problem of allocating its resources in the optimum way to achieve as high an audience as possible: The TV scheduling grid is divided into n consecutive slots, each of which has a total audience a_i. The competition has distributed its resources (be it money or some intangible goods correlated with the appeal of the broadcast material) so that the i-th slot is devoted c_i resource units, the total amount of resources of the competition being C = ∑c_i. If we have M resource units to compete and allocate them as m_i, i=1,...,n, the following is a reasonable model of the audience we obtain at the i-th slot:

s(m_i)= a_i m_i/(m_i+c_i),

which is simply a measure of the resources we have put compared with the total resources allocated to the slot (ours and the competition's). The problem is then to find the scheduling {m_i} with ∑m_i = M and m_i ≥ 0 for i=1,...,n, that maximizes our global audience S({m_i}) = ∑s(m_i).

In later entries we'll derive an analytical solution to this problem.