-2
$\begingroup$

In the euclidean plane an common heuristic for the TSP is to start with the convex hull of the point set and then successively integrate as the next point and insertion position the combination that incurs least tour expansion.

If all points except one are in convex configuration then the greedy insertion strategy yields the optimal tour; even more is true: if we remove (i.e. shortcut) a single vertex and then reinsert it with the greedy insertion strategy, the resulting tour will also be the optimal one.

Let's now interpret the points of a planar euclidean TSP instance as days, expanding a tour via according to the greedy insertion strategy as the passing of the day corresponding to the integrated point, then let your survival depend on being able to arrive at the optimal tour with the insertion of the last vertex.

Question:

does the above resemble the Unexpected Hanging Paradox because the reasoning is analogous in that we base our induction hypothesis on not having made any mistakes in any prior tour expansion as the analogue of not having been killed till the end of Thursday. The backward induction to the first tour expansion, resp. surviving Monday also seems to follow the same "logic".
And finally isn't the disappointment with the reliability of that kind of backward induction is comparable in both cases?

It should be noted that greedy tour expansion also meets the aspect of unexpected failure, independent of whether or not we make the flawed backward analysis: suppose we tell someone familiar with heuristic and its bad performance that we are about to solve a very large planar euclidean tsp instance with the greedy tour-expansion heuristic and start with the convex hull, just to hear "you will surely make a wrong insertion, but you will not know when"

$\endgroup$

2 Answers 2

2
$\begingroup$

There are many different ways of approaching the unexpected hanging paradox, some of which I describe in my paper on the subject, but I agree with Steven Landsburg that there is no useful sense in which the paradox can be regarded as an erroneous backward induction argument of the type you are describing in connection with the TSP.

Roy Sorensen, in his book Blindspots, does suggest that the argument in the unexpected hanging paradox is in some sense "the same" as various other backward induction arguments, such as the argument that in an iterated prisoner's dilemma with a bounded number of rounds, one should always defect. I personally don't think that these two arguments are as similar as Sorensen makes them out to be, but even if you agree with Sorensen, the backward induction argument in the iterated prisoner's dilemma contains no mathematical fallacy, whereas your TSP argument is fallacious. So again, I don't see any way of drawing a good analogy here.

$\endgroup$
2
$\begingroup$

First: As I said in my answer here, the unexpected hanging paradox has nothing to do with backward induction. The paradox --- if that's what you want to call it --- survives even if you reduce the number of days to one ("Tomorrow I will hang you, but you won't expect it"), thereby eliminating any need for any sort of induction.

One might think that comparing the TSP argument to the unexpected hanging argument is like comparing one careless use of a hammer to a different careless use of the same hammer. A better analogy would be that comparing the TSP argument to the unexpected hanging argument is like comparing the use of a hammer to a circus parade. One simply has nothing to do with the other.

$\endgroup$
2
  • $\begingroup$ Sure the unexpected hanging paradox is more than just the backward induction, but the backward induction itself is also interesting because the reasoning "if I survive till..." is half baked because it totally igores the question "...and if not?". $\endgroup$ Jan 22, 2023 at 16:14
  • $\begingroup$ Whether you answered my original question correctly is up for grabs. Many seem to think you haven't $\endgroup$
    – wlad
    Jan 23, 2023 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.