Bayesian Regret Baseline

58 views
Skip to first unread message

Brian Kelly

unread,
Oct 21, 2016, 3:15:10 PM10/21/16
to The Center for Election Science
I know Bayesian Regret is a metric some people like to use to judge the effectiveness of a voting system.  I have concerns with it because it uses a utility score baseline for a voter's true position.  With that as a source of truth, it only makes sense that score voting systems would rank high.

Has there been any Bayesian Regret analysis done of voting systems using a different baseline measurement of truth?  For example, I would be interested in the results with a Condercet/score ballot where a voter indicates their strength of preference for every combination of two candidates on the ballot.

Jameson Quinn

unread,
Oct 21, 2016, 5:20:49 PM10/21/16
to electionsciencefoundation
First off: I'm trying to encourage people to say "VSE" instead of "BR". If the BR of system s is E(U(ideal))-E(U(s))  (the expectation of the utility of the ideal candidate minus the expectation of the utility of the winner under s), then BR is [E(U(s))-E(U(random ballot))]/[E(U(ideal))-E(U(random ballot))], expressed as a percentage; by definition, an ideal mind-reading voting system would have a VSE of 100%, while random-ballot has a VSE of 0%. Note that in order to calculate this, you still need to make assumptions about the distribution of utilities, knowledge, and strategies.

As for Brian's question: I'm not sure it really makes sense. For one thing, VSE is not as biased towards score voting as you might think; it's definitely possible to make non-absurd assumptions about utilities, knowledge, and strategies that leave other systems doing better than score. Because of normalization, it's even possible to do this with honest voting. Warren didn't make this kind of assumption in his original BR work, but it can be done.

For another, the whole point of VSE is that it reduces everything to a single number. That really pushes you towards utilitarianism or to something which is equivalent to order statistics. The other options, such as maximin or other order statistics, can too-easily reward strategic vulnerabilities. There's a reason economists and game theorists do so much around utility; however imperfect the framework is, the alternatives are worse.

So, while I'm definitely not a utilitarian absolutist as it seems Clay is, I think that VSE is where it's at. I am working on a paper improving on Warren's 2000 results, and yes, I do manage to vary the assumptions by enough to see that score voting no longer dominates. And yet, there are still clear take-aways; plurality is clearly horrible, IRV is not much better, and Borda does badly with strategy.

2016-10-21 15:15 GMT-04:00 Brian Kelly <bkell...@gmail.com>:
I know Bayesian Regret is a metric some people like to use to judge the effectiveness of a voting system.  I have concerns with it because it uses a utility score baseline for a voter's true position.  With that as a source of truth, it only makes sense that score voting systems would rank high.

Has there been any Bayesian Regret analysis done of voting systems using a different baseline measurement of truth?  For example, I would be interested in the results with a Condercet/score ballot where a voter indicates their strength of preference for every combination of two candidates on the ballot.

--
You received this message because you are subscribed to the Google Groups "The Center for Election Science" group.
To unsubscribe from this group and stop receiving emails from it, send an email to electionscience+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Brian Kelly

unread,
Oct 21, 2016, 5:45:32 PM10/21/16
to The Center for Election Science
On Friday, October 21, 2016 at 3:20:49 PM UTC-6, Jameson Quinn wrote:
For one thing, VSE is not as biased towards score voting as you might think; it's definitely possible to make non-absurd assumptions about utilities, knowledge, and strategies that leave other systems doing better than score. Because of normalization, it's even possible to do this with honest voting.

Jameson,I do not understand what you mean here about normalization and honest voting.  Could you elaborate?

 
I am working on a paper improving on Warren's 2000 results, and yes, I do manage to vary the assumptions by enough to see that score voting no longer dominates. And yet, there are still clear take-aways; plurality is clearly horrible, IRV is not much better, and Borda does badly with strategy.

I would be interested to see the changes you make.  Please keep us posted.

Clay Shentrup

unread,
Oct 21, 2016, 10:25:20 PM10/21/16
to The Center for Election Science
> With that as a source of truth, it only makes sense that score voting systems would rank high.

Well, no. Scores are not utilities. They are the result of mutating real utilities with ignorance, strategy, and normalization. It was not at ALL obvious that Score Voting would win prior to Warren's calculations. Many people naively assumed that it would perform quite poorly in the presence of strategic voting.

> Has there been any Bayesian Regret analysis done of voting systems using a different baseline measurement of truth?

Utilities ARE the "measurement of truth".

Brian Kelly

unread,
Oct 21, 2016, 11:36:41 PM10/21/16
to The Center for Election Science
On Friday, October 21, 2016 at 8:25:20 PM UTC-6, Clay Shentrup wrote:

Utilities ARE the "measurement of truth".

 Clay, your proof assumes it's conclusion at the Continuity Axiom.

If A⊃B and B⊃C then B ∼ p?A:C for at least one p with 0<p<1.

That line assumes human preferences are liner and transitive.  With that assumption, utility functions are easily derived.

Jameson Quinn

unread,
Oct 22, 2016, 11:03:11 AM10/22/16
to electionsciencefoundation

Imagine that honest utilities are as follows:

40: A60 B50 C50
60: A50 B60 C10

"Honest" score ballots would be normalized to a 0-100 scale:
40: A100 B0 C0
60: A80 B100 C0

Totals: A8800, B6000, C0

A wins in this "honest" score election despite being a decisive loser in both utility and Condorcet.

That's what I mean by normalization.


--

Brian Kelly

unread,
Oct 22, 2016, 11:13:03 AM10/22/16
to The Center for Election Science
Makes sense.  Thanks Jameson.
To unsubscribe from this group and stop receiving emails from it, send an email to electionscien...@googlegroups.com.

Clay Shentrup

unread,
Oct 22, 2016, 12:14:39 PM10/22/16
to The Center for Election Science
On Friday, October 21, 2016 at 8:36:41 PM UTC-7, Brian Kelly wrote:
If A⊃B and B⊃C then B ∼ p?A:C for at least one p with 0<p<1.

That line assumes human preferences are liner and transitive.  With that assumption, utility functions are easily derived.

I don't think it assumes linearity. Linearity comes from:

Lottery utilities are expected utilities (Lin):
u(p?a:b) = p·u(a) + (1-p)·u(b).

Transitivity is necessary for any meaningful definition of welfare. Otherwise you could make yourself happier by constantly cycling through X/Y/Z/X..

Clay Shentrup

unread,
Oct 22, 2016, 12:26:41 PM10/22/16
to The Center for Election Science
On Saturday, October 22, 2016 at 9:14:39 AM UTC-7, Clay Shentrup wrote:
I don't think it assumes linearity. Linearity comes from:

Lottery utilities are expected utilities (Lin):
u(p?a:b) = p·u(a) + (1-p)·u(b).

Sorry, that's just a statement of the theorem. I can't remember how the stated axioms above imply that. I seem to remember something about how non-linear utilities would mean you could add a constant to the utilities in two compared lotteries and change which one was preferred.

Brian Kelly

unread,
Oct 22, 2016, 6:23:30 PM10/22/16
to The Center for Election Science
On Saturday,October 22, 2016 at 9:14:39 AM UTC-7, Clay Shentrup wrote:
On Friday, October 21, 2016 at 8:36:41 PM UTC-7, Brian Kelly wrote:
If A⊃B and B⊃C then B ∼ p?A:C for at least one p with 0<p<1.

That line assumes human preferences are liner and transitive.  With that assumption, utility functions are easily derived.

Quick note: I see a problem with my statement (beyond spelling).  The second sentence should say "With that assumption, linear utility functions are easily derived." 
 

I don't think it assumes linearity.

It requires it.  You can define a line with points A and C.  This axiom says point B must be between A and C.  Any point between A and C is on the AC line.


Transitivity is necessary for any meaningful definition of welfare. Otherwise you could make yourself happier by constantly cycling through X/Y/Z/X..

Not at all.  I think your perspective stems from a belief that welfare and utility must be on a one-dimensional spectrum.  If you accept the notion that Humans have three or more independent desires then it is easily provable that such concepts are more complicated than that.


On Saturday, October 22, 2016 at 10:26:41 AM UTC-6, Clay Shentrup wrote:
I don't think it assumes linearity. Linearity comes from:

Lottery utilities are expected utilities (Lin):
u(p?a:b) = p·u(a) + (1-p)·u(b).

Sorry, that's just a statement of the theorem. I can't remember how the stated axioms above imply that.

It is pretty clear to me this proof assumes that Human preference is linear.  I only object at the continuity axiom because it is the first place where more than two points are considered.


I seem to remember something about how non-linear utilities would mean you could add a constant to the utilities in two compared lotteries and change which one was preferred.

Which still makes perfect sense to me.  Remember I wrote to you about the Ultimatum Game (https://en.wikipedia.org/wiki/Ultimatum_game)?  People are less likely to reject proposals when the amount of money offered increases.  That is an example of how adding a constant can change people's preferences.

Jameson Quinn

unread,
Oct 22, 2016, 6:27:53 PM10/22/16
to electionsciencefoundation
It's certainly possible to have coherent accounts of human preferences that are not linear utilities. But any such coherent account involves making additional assumptions about when and how linearity is broken; assumptions which invite argument from both empirical and ethical standpoints. Utilitarianism may not be the truth, but I think it's the most we can hope to agree on, and even that agreement will be only for the sake of argument. Still, that makes it very useful, and the right standard for measuring VSE.

--
You received this message because you are subscribed to the Google Groups "The Center for Election Science" group.
To unsubscribe from this group and stop receiving emails from it, send an email to electionscience+unsubscribe@googlegroups.com.

Brian Kelly

unread,
Oct 22, 2016, 7:37:00 PM10/22/16
to The Center for Election Science
On Saturday, October 22, 2016 at 4:27:53 PM UTC-6, Jameson Quinn wrote:
It's certainly possible to have coherent accounts of human preferences that are not linear utilities. But any such coherent account involves making additional assumptions about when and how linearity is broken; assumptions which invite argument from both empirical and ethical standpoints.

Agreed.  It sounds like we might both agree that the true nature of Human preference is probably unknowable.
 
Utilitarianism may not be the truth, but I think it's the most we can hope to agree on, and even that agreement will be only for the sake of argument. Still, that makes it very useful, and the right standard for measuring VSE.

I'm actually a big fan of Utilitarianism and think it belongs in consideration of a voting system.  My point to Clay is that despite his proofs, simplifications and assumptions are still needed to reach a linear utility score.  If you do adopt a linear utility score for the next version of VSE then it won't be compelling for anyone who doesn't also accept those assumptions and simplifications.

This was my line of thinking in my original question.  A ballot that asks a voter to quantify the distance between every combination of two candidates in his/her N-dimensional preference space avoids the need to ask the voter to flatten that space into one dimension.  I am curious how much broken linearity we would see and it would be a better baseline to evaluate voting systems.

 

2016-10-22 18:23 GMT-04:00 Brian Kelly <bkell...@gmail.com>:
On Saturday,October 22, 2016 at 9:14:39 AM UTC-7, Clay Shentrup wrote:
On Friday, October 21, 2016 at 8:36:41 PM UTC-7, Brian Kelly wrote:
If A⊃B and B⊃C then B ∼ p?A:C for at least one p with 0<p<1.

That line assumes human preferences are liner and transitive.  With that assumption, utility functions are easily derived.

Quick note: I see a problem with my statement (beyond spelling).  The second sentence should say "With that assumption, linear utility functions are easily derived." 
 

I don't think it assumes linearity.

It requires it.  You can define a line with points A and C.  This axiom says point B must be between A and C.  Any point between A and C is on the AC line.


Transitivity is necessary for any meaningful definition of welfare. Otherwise you could make yourself happier by constantly cycling through X/Y/Z/X..

Not at all.  I think your perspective stems from a belief that welfare and utility must be on a one-dimensional spectrum.  If you accept the notion that Humans have three or more independent desires then it is easily provable that such concepts are more complicated than that.


On Saturday, October 22, 2016 at 10:26:41 AM UTC-6, Clay Shentrup wrote:
I don't think it assumes linearity. Linearity comes from:

Lottery utilities are expected utilities (Lin):
u(p?a:b) = p·u(a) + (1-p)·u(b).

Sorry, that's just a statement of the theorem. I can't remember how the stated axioms above imply that.

It is pretty clear to me this proof assumes that Human preference is linear.  I only object at the continuity axiom because it is the first place where more than two points are considered.


I seem to remember something about how non-linear utilities would mean you could add a constant to the utilities in two compared lotteries and change which one was preferred.

Which still makes perfect sense to me.  Remember I wrote to you about the Ultimatum Game (https://en.wikipedia.org/wiki/Ultimatum_game)?  People are less likely to reject proposals when the amount of money offered increases.  That is an example of how adding a constant can change people's preferences.

--
You received this message because you are subscribed to the Google Groups "The Center for Election Science" group.
To unsubscribe from this group and stop receiving emails from it, send an email to electionscien...@googlegroups.com.

Clay Shentrup

unread,
Oct 22, 2016, 9:03:10 PM10/22/16
to The Center for Election Science
On Saturday, October 22, 2016 at 3:23:30 PM UTC-7, Brian Kelly wrote:
It requires it.  You can define a line with points A and C.  This axiom says point B must be between A and C.  Any point between A and C is on the AC line.

Consider the social welfare function is sum of utility^2. That's not linear.

Transitivity is necessary for any meaningful definition of welfare. Otherwise you could make yourself happier by constantly cycling through X/Y/Z/X..

Not at all.  I think your perspective stems from a belief that welfare and utility must be on a one-dimensional spectrum.  If you accept the notion that Humans have three or more independent desires then it is easily provable that such concepts are more complicated than that.

It doesn't matter how many independent desires you have, when you make decisions you have to sum them all up into a single overall value.

Brian Kelly

unread,
Oct 22, 2016, 10:02:06 PM10/22/16
to The Center for Election Science
On Saturday, October 22, 2016 at 7:03:10 PM UTC-6, Clay Shentrup wrote:
On Saturday, October 22, 2016 at 3:23:30 PM UTC-7, Brian Kelly wrote:
It requires it.  You can define a line with points A and C.  This axiom says point B must be between A and C.  Any point between A and C is on the AC line.

Consider the social welfare function is sum of utility^2. That's not linear.

I agree but I do not understand why you are using a social welfare function as an example.  I do not see how that shows B does not have to be linear to AC in B ~ p?A:C.

Just to restate my position, I believe you would reject a social welfare function that is the sum of utility^2 because it is not linear.  Your reason for this is that utility axioms on http://scorevoting.net/UtilFoundns.html say the function must be linear.  My position is that the axioms come to that conclusion only because it was built into the initial assumptions.  I point to the assumption B ~ p?A:C as an example of an assumption that requires linearity.  I am expecting from you a reason why that is not the case.

 
Transitivity is necessary for any meaningful definition of welfare. Otherwise you could make yourself happier by constantly cycling through X/Y/Z/X..

Not at all.  I think your perspective stems from a belief that welfare and utility must be on a one-dimensional spectrum.  If you accept the notion that Humans have three or more independent desires then it is easily provable that such concepts are more complicated than that.

It doesn't matter how many independent desires you have, when you make decisions you have to sum them all up into a single overall value.

I agree that to compare desires you need to flatten the data to a single value.

Do you agree that mapping an individual's preference onto a one-dimensional utility scale is a lossy operation?

Jameson Quinn

unread,
Oct 22, 2016, 11:07:10 PM10/22/16
to electionsciencefoundation

I agree that to compare desires you need to flatten the data to a single value.

Do you agree that mapping an individual's preference onto a one-dimensional utility scale is a lossy operation?

Um... yes? Anything in voting theory is a lossy operation. There is no function which takes a bunch of ballots, of any type, and uses them to provide molecule-by-molecule precise clones of all the voters.

But the idea of VSE is to help make a decision: which voting system is better, X or Y? A multidimensional answer — "Well, X is more awesome, but Y is more superb" — is less helpful, not more so.

Clay Shentrup

unread,
Oct 23, 2016, 11:00:08 AM10/23/16
to The Center for Election Science
On Saturday, October 22, 2016 at 8:07:10 PM UTC-7, Jameson Quinn wrote:
I agree that to compare desires you need to flatten the data to a single value.

Do you agree that mapping an individual's preference onto a one-dimensional utility scale is a lossy operation?

Um... yes? Anything in voting theory is a lossy operation.

Well, it's not lossy because it's voting theory. It's lossy because your utility as a function of any state of the world is the sum of a myriad of sub-utilities.

Jameson Quinn

unread,
Oct 23, 2016, 11:23:50 AM10/23/16
to electionsciencefoundation
Right. The whole point of the utility function is to be lossy: to reduce entire states of the world to actionable decisions. If it weren't lossy, you'd run into problems like Sen's theorem and worse.

--
You received this message because you are subscribed to the Google Groups "The Center for Election Science" group.
To unsubscribe from this group and stop receiving emails from it, send an email to electionscience+unsubscribe@googlegroups.com.

Neal McBurnett

unread,
Oct 23, 2016, 8:03:24 PM10/23/16
to electio...@googlegroups.com
The field of AI, and various schools of philosophy, also have to grapple with the complexities of utility and rationality from a human perspective. Here are some references that flesh that out.

Normative Theories of Rational Choice: Expected Utility (Stanford Encyclopedia of Philosophy)
http://plato.stanford.edu/entries/rationality-normative-utility/

Expected utility hypothesis - Wikipedia
https://en.wikipedia.org/wiki/Expected_utility_hypothesis

There's too much to summarize there easily, but I'd say that assuming utilities are linear is of course much simpler, but that some real humans won't be comfortable with that approach and it won't match their actual behavior all the time.

All of which is of course not news to social choice aficionados.

Neal McBurnett http://neal.mcburnett.org/
> To unsubscribe from this group and stop receiving emails from it, send an email to electionscien...@googlegroups.com
> .
> For more options, visit https://groups.google.com/d/optout.
>
>
> --
> You received this message because you are subscribed to the Google Groups "The Center for Election Science" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to electionscien...@googlegroups.com.
Reply all
Reply to author
Forward
0 new messages