Order dependence in preference elicitation

The Von Neumann-Morgenstern utility theorem effectively states that you can get a utility function from someone by forcing them to make a series of “this or that” questions (you actually need potentially an infinite number of questions, but this isn’t that interesting because you can get an arbitrarily good approximation in a finite number of steps). It requires you to satisfy a bunch of axioms with (one of the) argument(s) that you should satisfy those axioms being that otherwise you are vulnerable to Dutch book problems where you get pumped for infinitely large amounts of money.

(The above is a hopefully accurate but very simplified summary. Feel free to tell me if you think it’s unfair and I will update it).

The VNM axioms are generally presumed to apply to “logically omniscient” beings. i.e. entities who have fully thought through all the implications of their belief and can instantly answer any purely logical question. This post is purely about what happens when you try to apply them to non-logically-omniscient beings, which is all we have access to when implementing decisions on actual people. It could be regarded as exploring the boundaries of just how logically omniscient you have to actually be in order to use these axioms in certain contexts.

One of the problems for applying this process to us non logically omniscient beings is that it ignores the fact that these questions have to be asked in actual time – it switches between an instantaneous notion of preference and the Dutch book sequence which happens in time, during which you might update your preference (in the Dutch book context this doesn’t even require a failure of omniscience because you’re getting new information – that someone is prepared to make this bet, but I’m going to focus on the failure of logical omniscience).

In particular it ignores that merely asking the question can change your preferences. I have spotted a nice example of this:

You: “Would you like $100?”
Me: *reaches for money*
You: Orrrrr…. you can have TWO HUNDRED dollars, but you’ll only get it if this set of 1000 boolean formulae is simultaneously satisfiable.
Me: Yes I am totally going to do an NP-hard problem for the possibility of an extra $100. Give me the easy money.

Alternatively:

You: “Would you like $100?”
Me: *reaches for money*
You: Orrrrr…. you can have TWO HUNDRED dollars, but you’ll only get it if this set of 1000 boolean formulae is satisfied by this set of assignments.
Me: Hmm. That’s just about worth it. *does the calculation*. Oh, cool. Yes that’s totally a satisfaction. I’ll take $200 please.
You: Cool. Now for the second question. $100 or $200 if (the same boolean problem) is satisfiable?
Me: … welll…. I’ve literally just seen a satisfaction for this, so I’ll take the $200 please.

This is essentially transitivity at work: It is clear that the answer to the question “Is this satisfiable?” is true if the answer to “Is this a satisfaction?” is ever true, but you have to find the right instance of the latter class of question in order to make this implication. Essentially, requiring transitivity forces you to turn a reasonable amount of computation into an unreasonable amount of computation if you want all your preferences to be consistent in advance. Otherwise you introduce path dependence into the value function you get out of a sequence of questions.

If we insisted on maintaining the same order over all time and that you had to be transitive, if we’d asked the two questions in the other order consistency would have forced you to not do the calculation and just take the $100. A decision to always take the $100 is of course perfectly consistent, but then you’re losing out in some cases where you could have turned an easy profit.

Note: This example extracted from my answer to this question I asked on the cstheory stack exchange, which I probably wouldn’t have spotted without the answers from Emil and Denis coming first.

This entry was posted in Uncategorized on by .