Buridan's Principle (1984) [pdf] | Hacker News Reader

Buridan's Principle (1984) [pdf]

microsoft.com

57 pointswaterhouse69 comments

This thing drove me wild for like 2 weeks, I was not sure it could be true. Until I realized that the composition of continuous functions is continuous.

But that makes me wonder ... how can we then have unstable problems in the real world? Google "unstable problem definition". If everything is continuous, then small enough changes in input always result in small changes in output. And yet, unstable problems are the opposite. If a pencil is released when standing on its point, it can fall to one side or another side, rather far away.

To me, this has to do also with comparing timestamps across distributed systems, like Spanner's database timestamping synchronization. When I started architecting distributed systems, and quorums, I had to deal with this.

I remember emailing Leslie Lamport a few times and arguing with him about this :)

Some people don't even believe Leslie Lamport's Buridan's Principle:

https://www.youtube.com/watch?v=dVkSJ0QWzXA

Even the video got 3 likes and 3 unlikes... so paradoxical!

Note: I believe the commentary here is copied from the Lamport's website, http://lamport.azurewebsites.net/pubs/pubs.html#buridan which has similar commentary alongside each of his papers.

This makes perfect sense classically, but the quantum argument I'm not sure about; as he admits, he only finds fault with a particular apparatus using quantum behavior. But it seems that any implementation of a quantum bit that is eventually "measured" would violate the principle--is there something I'm missing, or is the problem just smoothed over by the probabilistic error already assumed in quantum circuits?

"Buridan's ass" was a philosophical intuition pump to argue for the reality of free will. If we were really ultimately determined by our appetites, as the Neoplatonic determinists would have it, then we can construct a scenario where the perfectly determined ass would end up starving to death when surrounded by the foods it most craved.

Since there are not dead asses all over the place, the philosophers took this as evidence that free will exists, even in asses.

> Since there are not dead asses all over the place, the philosophers took this as evidence that free will exists, even in asses.

That falls apart as soon as you consider how frequently the precise scenario is expected to occur. I hope no philosopher made an ass of himself by vigorously defending this particular form of the argument.

That response is similar to the point made by one reviewer of an early version of the paper discussed here, that if this were a problem (in practice), it would have come to everyone's attention by now.

The Dining Philosophers problem is similar to Buridan's Ass, in that you have hyper-rational actors at risk of starvation in the presence of food, but the critical difference that makes this a model of something that could happen in practice is that it involves each actor having to make two temporally-separated decisions, thus avoiding a singularity in time (though such singularities appear when you apply a locking solution.)

I don't think the scholastic philosophers were thinking the precise balance would happen in reality, but rather the very concept seemed absurd. That's the nature of intuition pumps. Not exactly a cut and dry deductive argument, but they show certain conclusions are most compatible with what seems to be common sense. And a general principle in philosophy is to try disrupting common sense conservatively, that on balance if one worldview is much more at odds with common sense than another worldview, the latter is preferred.

"Another amusing example occurred in an article by Charles Seif titled Not Every Vote Counts that appeared on the op-ed page of the New York Times on 4 December 2008. Seif proposed that elections be decided by a coin toss if the voting is very close, thereby avoiding litiginous disputes over the exact vote count."

Interestingly enough, A.A. does this, where "very close" is deemed to be "less than a 2/3 majority". (Although rather than a coin flip, a name is drawn at random, usually from a hat).

Election by lot is a thing.

https://web.archive.org/web/20160320090358/https://aeon.co/e...

A jury is essentially election by lot. We should use juries for more oversight-type things.

Then you need a very precisely defined threshold of votes, if the person with the most votes has one vote less than that threshold then we use a coin toss. So now we have the same problem choosing that precise threshold and candidates will litigate over that instead. You've not really gained very much over using a strict majority of votes.

Here's a slightly more complicated variant: if the vote is close (for any reasonable definition of 'close') the outcome is decided by a random process, but one that does not always have a 50-50 outcome; instead it is biased, in proportion to the difference in votes, towards the side with the higher count. Only if the counts are equal are the probabilities equal, and if the difference in counts is close to the threshold for invoking this mechanism, it will almost certainly choose the side with the higher count.

For example, a series of coin flips, with each win being added to the toss-winner's vote count, until one has reached a value one greater than the higher vote count. This seems to be a natural extension of the sudden-death tie-breaker.

Because the counts are discrete, I do not think there is any sorites paradox here, and so long as more than a few votes were cast, there should be a reasonable definition of 'close'.

This would never work in practice, as the side with the larger count will always regard it as unfair, but could perfectly rational participants find this acceptable?

I don't think so, because there is no way to decide what constitutes perfect rationality.

Well, I certainly left myself open to that way of avoiding the issue.

I’m really not trying to avoid it. I can see your point and it’s a worthwhile thread to pull on, I’m just a bit skeptical. Elections are inherently fractious issues. Yes there is some random input into the outcome, which makes the process contentious, but I don’t think the solution to that is more randomness.

Read a story where President was chosen at random from all registered Voters.

So can someone help me with my understanding I read the paper and feel I have a grasp of it but there is still one thing I don't understand he says

>Buridan’s Principle. A discrete decision based upon an input having a continuous range of values cannot be made within a bounded length of time.

Shouldn't it instead read

> Buridan’s Principle. For a discrete decision based upon an input having a continuous range of values, there exists some values such that a discrete decision cannot be made within a bounded length of time.

Because clearly there are many instances that a discrete decision is made in a bounded length of time, as shown by the car does stop or goes for many values of x even though there is a bounded length of time; however there is certain values of x that result in the train running over the car, but not all.

Ergo, only some values of x will result in a decision being made impossible in a bounded period of time.

Can someone help me understand the flaws in my thinking or understanding?

The only difference between your phrasing and the paper's is terminology.

By definition, a "bound" is a limit, i.e. a range that the outcome falls into. Saying that the time to make a decision is bounded simply means that you can always rely on it to happen within that limit.

Okay so what I am to understand by the phrase

> cannot be made within a bounded length of time.

Is not that it will not happen within a certain time period but rather I cannot with certainty fix an upper or lower bound on the amount of time it will take to reach a decision for all possible values of the input X.

Thank you for your reply I had to noodle on it a bit but think I get it now.

Not bounded means that if you give me a number x then there is some y that is bigger than x.

So, in the context of the paper, if you thought that your computer always made a decision after a week, then there is some situation whereby the computer takes longer than a week.

For the record, I think the mathematics is sounder than the computer science which in turn is sounder than the social science. As the author admits when he mentions Kepler, we can't really prove Buridan's Principle. But I think it goes further than this in the social aspect: We don't know whether indecision at traffic lights is even accurately modeled by Buridan's Principle. Then the question becomes not whether it's true, but whether it is a good model. And these kind of models are always dangerous ground in the social sciences.

Edit: The reason why I say the mathematics is sound is because he rephrases the usual notion of compactness: https://en.wikipedia.org/wiki/Compact_space.

“ One reviewer made a marvelous comment in rejecting one of the early papers, saying that if this problem really existed it would be so important that everybody knowledgeable in the field would have to know about it, and “I’m an expert and I don’t know about it, so therefore it must not exist.” “

That’s gold. The hubris!

To their credit, the reviewer makes some valid points here.

And yet not sound, maybe the experts in the field didn't have all the answers. If they did, why are they still reviewing new ideas?

Or maybe the reviewer isn't an expert.

I’ve made similar arguments. I have a term for them, “economic reasoning.” The argument is basically that economic forces, from greed and survival to the basic underlying technical capabilities available would have ALREADY caused a proposition to succeed or fail. This is a powerful principle, and in my experience, does not mediate against innovation. That reviewer was using his version of it. Secondarily, Buridan’s principle fails. An important lesson in growing up is, sometimes you just have to choose, and if you waste enough time, the urgency of choice exceeds the urgency to be right. In technology, binary switches have an avalanche mechanism, and if properly designed, have built in hysteresis. Noise then makes the decision, and the hysteresis prevents “waffling” by turning off the ability to redecide. Read (older) data sheets on comparators. That a person could write a scholarly paper and not mention that indecision has been thought about, and workarounds have been assiduously developed IS probably cause for rejection.

That's why I don't believe in Einstein's theory of relativity. All the experts, at least the English speaking ones (my language), thought he was a quack. Ether all the way, baby!

I probably shouldn't do this, but, uh, you know about Rex Research, yeah? http://rexresearch.com/

I like you yters. You're crazier than I am and that's hard to do. But despite a rocky beginning (cheers!) Einstein turned out to be correct. We've measured and verified relativity to the heavens and back.

Really, it's a staggering feat what he did: you take two basic ideas, that the laws of Nature are the same in every (inertial reference) frame, and that Maxwell's equations (laws of Nature as far as we know) have a constant c, and everything else flows from there. The Universe is stranger and more wonderful than anyone has ever imagined.

I am putting my money on timecube for now.

https://www.microsoft.com/en-us/research/uploads/prod/2016/1...

The author specifically addressed “noise” in another paper. In this paper, the predecessor to the one linked, the author shows that noise doesn’t fix the problem, rather it makes it impossible to determine which inputs would make it hang for an arbitrary amount of time.

Are you referring to this passage?

2. Introducing noise to drive the device out of its metastable state.The noise can be considered to be just an unpredictable input.The introduction of noise cannot eliminate the possibility of the device hanging up for an arbitrarily long time, but can make it impossible to predict which inputs will cause it to do so.

While I do not disagree, introducing noise changes the issue from being stuck forever on a single decision, to being a series of decision points (each time the noise signal changes), with the chain being broken as soon as one results in a definite outcome. In practice, this allows us to engineer the risk of being stuck, for longer than some specified period, to an arbitrarily small probability - at the cost of a small loss of precision, and possibly much greater complexity in modeling the device.

Coincidentally, this is reminiscent of the usual solution to Paxos liveness violations: introduce randomness into the timing of the competing proposals.

True! Wouldn’t be surprised if that’s why Lamport was originally thinking about the problem.

No no no!

Using noise is useless without hysteresis. You must have a process, built in, which prevents re-decision or waffling for a time sufficient that conditions are so changed as to eliminate the original decision. Once you stop, you stop long enough for the train to pass. Or you close your eyes and floor it, and stand on the accelerator.

In actual practice, do you think he’s right?

I think it's an interesting proof in the context of distributed systems where delays can be interpreted in any number of different ways, and the paper shows pretty concretely the existence of at least one of these delay-causing inputs.

In most practical scenarios it's not an issue, sure, but I don't think that's what the author was trying to get across as the point of this.

However, the "dithering between choices" is a real problem with a real name in hardware design: metastability. It is precisely when sending a signal between two clock domains that it arises, because a flip-flop may be clocked while its input is transitioning, and that may put it into a "metastable" intermediate middle state. Prolonged metastability can destroy the device. And the usual solution is somewhat probabilistic: put a second flop behind the first.

> I have a term for them, “economic reasoning.”

I think this is known as the old joke about the efficient markets: an economist sees a $100 bill on the ground in a public (and frequently walked through) place and, instead of picking it up, decides they must be hallucinating; after all, if there was really a $100 bill on the ground, somebody would've already picked it up.

Real life situations vary in their degree of similarity to a perfectly efficient market, so the "economic reasoning" only makes sense in context. Does the situation involve an efficient enough market for the proposition to be of extremely low probability? In terms of reviewing scientific papers, I don't think you can assume that with enough confidence to use it as a sole reason to reject a paper.

I think Eliezer wrote a whole book on it: https://equilibriabook.com/. It's probably relevant to Leslie's situation.

My argument doesn’t particularly rely on the market mechanism per se, but rather, an estimate of the probability that something gets overlooked, or not tried.

"I find myself unable to decide for a fraction of a second whether to stop for a traffic light that just turned yellow or to go through"

I had a similar problem, and I resolved it by training myself to remind myself of a point of no return, that is, a distance from the light at which I will go no matter what. So every time I see a traffic light, I decide where is the point of no return.

I think establishing point of no return is the standard method of dealing with this. For example, parachute jumpers have a certain altitude at which they have to make the decision whether to land on the main parachute or backup parachute if something goes wrong with the main one.

The paper points out that this doesn't resolve the problem in the discussion about the crossing gate; all this approach does is move the decision from "do I jump" to "have I met the point of no return yet", which is still a discrete decision over a continuous input.

However, the further it goes, the more clear the second one gets. I.e. "am I already at the point of no return, I guess not, it's unclear. Oh wait, now I am, let's trigger."

So, Buridan’s Principle is correct for time-invariant systems. But as far as I can see you can totally build a time-dependent system which simply picks option 1 after being undecisive for time T.

I think the principle would state that by always picking option 1 you are no longer making a decision based on the input.

This is discussed in the paper under section 3: "Other Asses", in the paragraph starting "One way to circumvent Buridan’s Principle is to eliminate the decision".

The fact that we are discussing a yellow light and not a red one is because the yellow light is a mitigation that significantly reduces the risk of harm from making a wrong (or, shall we say, suboptimal?) decision.

Agreed - the majority of drivers will now be making the discrete decision "Is green or amber" not "Is amber or red".

That is to say, that the proportion of drivers having to make the risky decision (i.e. if they were to decide to accelerate through the amber) is significantly reduced... although interestingly I think the principle states that as T(amber) << T(green) the liklihood of indecision for that second case now does increase.

I don't think there is any doubt about what the color is (or, given color-blind drivers, which light is on); the only issue a law-abiding driver is supposed to consider, on seeing the yellow light come on, is whether one can stop within the remaining distance. Of course, in practice, it's more complicated...

The practice of putting cameras on lights and then reducing the duration of the yellow light is not only an abuse of power but also dangerous.

I can see why the author had difficulty publishing the article. If I didn't realise that he was talking about compactness I would have thought that he wasn't making sense.

The target audience is a nontrivial subset of people and it's difficult to optimise for everyone in the target audience. In any case I think that the real interesting thing here is not what lead to his observation. (Mathematicians have a tradition of not telling people what lead to their observations, for better or worse.) Rather, I think the mathematics behind this should be taken much further.

I guess it's off to the references.

>Buridan’s ass starves because it cannot make the discrete decision of which pile of hay to eat, a decision based upon an initial position having a continuous range of values, within the bounded length of time before it starves

I don't see how that follows. Seems like a sibling problem rather than a generalization.

The ass would starve even if the decision was among two same otherwise discrete options with no continuous range of values in between (e.g. state -1 (left hay), 0, and 1 (right hay)), since there still wouldn't be a reason to prefer -1 to 1.

The point is the underlying domain (physical space, in the donkey parable) is continuous, and it needs to be partitioned into discrete values. The paper is about the impossibility of constructing a device which does this within a bounded amount of time.

The problem gets more difficult because you also have to worry about measurement resolution. Anyway, rest assured this problem is very resistant to any "what if you just..." solutions you can come up with.

>The point is the underlying domain (physical space, in the donkey parable) is continuous, and it needs to be partitioned into discrete values.

I don't think that was part of Buridan's concept. The concept was simply the impossibility of choice between two same options -- the continuity of the domain didn't play any role (in fact the description focuses on the discreet binary choice alone).

>Anyway, rest assured this problem is very resistant to any "what if you just..." solutions you can come up with.

I'm sure, I don't propose a solution - just say that the problem is not about discreet/continuous.

Buridan's original problem is used here as an analogy for the problem, not really the basis.

Nice paradox, searching about it found another proposed solution:

http://steve-patterson.com/paradox-resolved-buridans-ass/

It says: "there’s no such thing as “identical options”. More specifically, there are no two separate things which are identical in every way. So when talking about choice, having “alternative” possibilities implies having “different” possibilities. We can not evaluate two things as both “identical and different”, as this would be a contradiction in terms. Therefore, any formulation of Buridan’s paradox which implies this contradiction runs into a basic framing error."

Seems wrong, in a lottery all options are “identical and different”. Identical since they have the same probability, different because only one has the price. The paradox undecidability is produced by the perfect balance of unknowns, the equilibrium must be broken to have a decision.

Buridan's can be combined with Xeno's as a 2D continous space/time paradox. So cool!

I'm working on a solution for Xeno's, that's why I find it interesting.

I’d say photocopies are identical in every way. Are we talking variances that can’t be seen by the naked eye? If so then what is observing this other than an ass? The ass doesn’t care about the micro differences in two like objects.

>It says: "there’s no such thing as “identical options”. More specifically, there are no two separate things which are identical in every way.

Doesn't have to be "identical in every way".

Just "identical in every way that matters (regarding the decision)" e.g. making the subject equally hesitant or equally willing to chose one or the other...

E.g. two potential love interests might be very different but equally tempting, and people have had that problem of choice (or regret when they chose) hit them very heavily...

Link with extra junk shaved off: https://www.microsoft.com/en-us/research/publication/buridan...

> In the early 70s, computer designers rediscovered that it’s impossible to build an arbiter that is guaranteed to reach a decision in a bounded length of time. (This had been realized in the 50s but had been forgotten.)

> a device for making a binary decision based on inputs that may be changing

So it's the result of the halting problem, applied to a continuous function in hardware?

It's an interesting thought but I'm not aware of any way to plausibly connect the two, mathematically.

> it’s impossible to build an arbiter that is guaranteed to reach a decision in a bounded length of time.

"To build" would be a series of logic gates, in hardware, which is why the halting problem could apply. The fact that the outputs are expected to be considered a continuous function is incidental and (as stated) can only be considered a discontinuous function, despite the target guarantees and specifications might state.

Right, but the reasons why are different from the halting problem. As stated in the OP, "the key assumption in this argument is continuity". I'm not sure what you mean by the outputs being "expected to be considered a continuous function". In both the halting problem and this case the outputs are discrete (e.g. binary: halts/does not halt, left/right, etc.)

There are other impossibilty results, e.g. the FLP theorem. Despite having computing-based interpretations they're not all related to the halting problem. :)

That being said, maybe it's possible to generalize the halting problem to a continuity in some reasonable way and get something like Buridan's principle. It's not obvious to me how that would be done but I'd be interested to see!

> this case the outputs are discrete (e.g. binary: halts/does not halt, left/right, etc.)

As you vary the inputs, the outputs change. This results in a continuity. There is a question of ranges, but this is handled by a type system (even if that type is a pointer, you run through all memory for your function inputs).

No, the halting problem says that one cannot determine whether an _arbitrary_ program halts, while this says that one cannot build a _particular_ physical device that is guaranteed to output in bounded time.

Flipping a coin if the vote is close seems to solve the voting dilemma... What am I missing?

So randomness produces free will?

It simply offloads the decision to a delegated authority, just one that happens to be random, so I'm afraid not.

The original paper specifically addresses “noise” as not a sufficient solution to the problem. I’d call a coin toss “noise” in the context of this paper.

Correct!

> Another often-suggested escape from Buridan’s Principle is noise—the introduction of randomness into the system. In theory, one can balance a ball on a knife edge; in practice, this is impossible because tiny random 2 vibrations will cause the ball to fall, despite our best efforts to balance it. Moreover, balancing the ball on a knife edge requires fixing very precisely both the position and the momentum of the ball, which is forbidden by Heisenberg’s Uncertainty Principle. A four-legged or human ass must also have random noise and be subject to the Uncertainty Principle, so it cannot be put into a situation where it will hang forever on a knife edge of indecision.

How do you determine whether the vote is close? Use a threshold like 66%? What if the vote is very close to 66%, and it's not entirely clear whether it's above or below? It's exactly the same problem as determining whether a candidate has gotten more than 50%, only shifted around.

That deciding to flip a coin to decide means you are already out of the dilemma...

Interesting that this is the meta-story of Buridan’s Principle, not the thing itself.

Click "View Publication", the text on the page is just some commentary by the author

I know. The commentary is the subject of the HN post, not the paper itself.

The meta-story is IMO just as fascinating if not more so than the principle itself.

> A little research revealed that psychologists are totally unaware of the phenomenon.

> The singularity at zero was never mentioned in the paper.

> Philosophers have discussed Buridan’s ass for centuries, but it apparently never occurred to any of them that the planet is not littered with dead asses only because the probability of the ass being in just the right spot is infinitesimal.

> I submitted it first to Science. The four reviews ranged from “This well-written paper is of major philosophical importance” to “This may be an elaborate joke.” One of the other reviews was more mildly positive, and the fourth said simply “My feeling is that it is rather superficial.” The paper was rejected.

> Throughout this exchange, I wasn’t sure if he was taking the matter seriously or if he thought I was some sort of crank.

> My problems in trying to publish this paper and [22] are part of a long tradition.

WTF is going on here? This thing on our lawn is a dragon, why do some many people think it's a cloud?

Fascinating.

Reply on news.ycombinator.com