Sometimes a problem pounces upon your brain...

Sometimes a mathematics / computer science problem pounces upon your brain, and takes possession of it for half the day -- at least until you figure out that its general case does have a solution. Then you finally escape its clutches, feeling that you haven't accomplished much; but you've brushed off some dust of that old math/CS knowledge that sometimes gets asked at software development job interviews. So it's not all a waste.

The problem was posted on Facebook by a friend who encountered it in his engineering work.

Suppose you have tasks A, B, and C. Task A occurs n_A times in a given time period, task B occurs n_B times, and task C occurs n_C times. Let's say n_A is 7, n_B is 2, and n_C is 1. The time between any two tasks is the same. Let's call it a unit time interval. These tasks repeat endlessly in a loop. The problem is to arrange the tasks in such a way that the number of time intervals between any two tasks of the same type will be minimized.

It may seem simple, but... it's not.

Ideally, any two A-tasks will be separated by at most ceil((nA + nB + nC) / nA) intervals, any two B-tasks are separated by at most ceil((nA + nB + nC) / nB), and any two C-tasks are separated by at most ceil((nA + nB + nC) / nC) intervals, where ceil() is ceiling, a function that rounds up a number to the nearest integer larger than it.

I came up with an example (or a counterexample, if you will) where it is impossible to find a schedule that satisfies those constraints.

Say task A occurs 19 times in a given time period, task B 13 times, and task C 3 times. Then nA + nB + nC = 35. ceil(35/19) = 2, so A-tasks should be separated by no more than 2 intervals. B-tasks need to be no more than ceil(35/13) = 3 intervals apart. Now, if you put a C-task between two A-tasks, then B-constraint will be violated. Any segment A-A is surrounded by B's, i.e. it will be a subset of B-A-A-B, and those two B's are 3 intervals apart. Put a C in the middle, and B-tasks will be 4 intervals apart. That's greater than ceil(35/13) = 3. If you put a C between A and B-tasks, then A-constraint will be violated, because you'll have a sequence A-C-B, so an A following that sequence will be 3 intervals away from the first A. That's greater than ceil(35/19) = 2.

Of course, there are many combinations of frequencies for which it IS possible to find an optimal schedule, for example 19-11-5. Also, if the numbers are multiples of other numbers, this problem may have additional properties that may make it solvable. Then again, engineers usually don't care about exact solutions, rather than "good enough" approximate solutions. If you require that the number of intervals between two tasks of the same type exceed the optimal only a certain percentage of times, the problem becomes complex enough to be a fodder for master's thesis. I wouldn't be surprised if it has been already solved in the academic literature. I just don't know of a good enough way to search for papers or theses that may have been published on this topic.

Further thoughts: you could map this problem to a graph theory problem. Each task can be a node in a graph, and you would need to find a shortest route for visiting all the nodes -- "shortest" as determined by the costs required to visit each node. This would be the traveling salesman problem, which is NP-complete. But this proves nothing, because this particular problem might map to a special instance of traveling salesman problem that's solvable in polynomial time.

"Logical" may be in the eye of the beholder

There is this interesting article in this month's Scientific American.

The Traveler's Dilemma by Kaushik Basu

"When playing this simple game, people consistently reject the rational choice. In fact, by acting illogically, they end up reaping a larger reward -- an outcome that demands a new kind of formal reasoning"

Here is a long quote from the article, describing the game and the "paradox". (I put "paradox" in quotes because I don't think the behavior the author characterizes as illogical is at all illogical.) The quote is long, and the article itself is 5 times as long, but I found it rather interesting, myself, and the mathematics involved in it is very simple; it does not contain a single equation. :-)

The rules of the Traveller's Dilemma game

Lucy and Pete, returning from a remote Pacific island, find that the airline has damaged the identical antiques that each had purchased. An airline manager says that he is happy to compensate them but is handicapped by being clueless about the value of these strange objects. Simply asking the travelers for the price is hopeless, he figures, for they will inflate it.

Instead he devises a more complicated scheme. He asks each of them to write down the price of the antique as any dollar integer between 2 and 100 without conferring together. If both write the same number, he will take that to be the true price, and he will pay each of them that amount. But if they write different numbers, he will assume that the lower one is the actual price and that the person writing the higher number is cheating. In that case, he will pay both of them the lower number along with a bonus and a penalty--the person who wrote the lower number will get $2 more as a reward for honesty and the one who wrote the higher number will get $2 less as a punishment. For instance, if Lucy writes 46 and Pete writes 100, Lucy will get $48 and Pete will get $44.

What numbers will Lucy and Pete write? What number would you write?

Scenarios of this kind, in which one or more individuals have choices to make and will be rewarded according to those choices, are known as games by the people who study them (game theorists). I crafted this game, "Traveler's Dilemma", in 1994 with several objectives in mind: to contest the narrow view of rational behavior and cognitive processes taken by economists and many political scientists, to challenge the libertarian presumptions of traditional economics and to highlight a logical paradox of rationality.

Traveler's Dilemma (TD) achieves those goals because the game's logic dictates that 2 is the best option, yet most people pick 100 or a number close to 100--both those who have not thought through the logic and those who fully understand that they are deviating markedly from the "rational" choice. Furthermore, players reap a greater reward by not adhering to reason in this way. Thus, there is something rational about choosing not to be rational when playing Traveler's Dilemma.

I was stunned that the author would consider the number 2 to be the rational choice.

This is how the authors explains it

To see why 2 is the logical choice, consider a plausible line of thought that Lucy might pursue: her first idea is that she should write the largest possible number, 100, which will earn her $100 if Pete is similarly greedy. (If the antique actually cost her much less than $100, she would now be happily thinking about the foolishness of the airline manager's scheme.)

Soon, however, it strikes her that if she wrote 99 instead, she would make a little more money, because in that case she would get $101. But surely this insight will also occur to Pete, and if both wrote 99, Lucy would get $99. If Pete wrote 99, then she could do better by writing 98, in which case she would get $100. Yet the same logic would lead Pete to choose 98 as well. In that case, she could deviate to 97 and earn $99. And so on. Continuing with this line of reasoning would take the travelers spiraling down to the smallest permissible number, namely, 2. It may seem highly implausible that Lucy would really go all the way down to 2 in this fashion. That does not matter (and is, in fact, the whole point)--this is where the logic leads us.

But logic doesn't really lead us where the author says it does

Logic would lead us there only if Lucy's goal wasn't simply to get a big sum of money for her antique, but to get more, or at least no less, than Pete, at any cost, even at the cost of impoverishing herself.

The rest of this long article attempts to explain why most people, when play this game, behave "illogically", and -- gasp -- reap bigger rewards than if they were behaving "logically" and named 2 as their number. To me, the reason seems both obvious and easy to summarizein a couple of sentences. Most people's goal when playing this game isn't to beat the other guy, but to maximize the amount of money they get. I suppose they are perfectly fine with naming 100 and getting 98, while the other guy names 99 and gets 101. It's still a much better outcome for them than naming 2 and getting 2.

"Maximize" is probably the wrong word here. As long as they can get "close enough" to the maximum possible sum any one player could get (101), they don't care about attaining the absolute maximum. Of course, "close enough" is not easy to quantify mathematically, even though it can be interesting to try. My master's thesis was about heuristic algorithms in mathematical optimization, and heuristics are all about finding a "good enough" solution without worrying about the best.

Anyway, just because the actual human behavior can't be easily (or at all) explained by game theory, it simply means game theory is not perfect at modeling human behaviors (even in very simple scenarios such as this), not that humans behave irrationally.