Is there any way to incentivize a voter (by asking her a single question) to state her sincere normalized utilities for the N candidates, e.g. X=10, Y=3, Z=0? We know that in this case the voter would consider a 30% chance of getting X instead of Z to be equal in value to a guarantee of getting Y. But can we use that kind of knowledge to solve this problem?
Puzzle posed by Clay Shentrup, then solved by Warren D. Smith March 2009.
To make this solution work, we shall need the underlying supposition (which may or may not be realistic – we will re-examine it at the end and show how to set up an artificial "voting system" contrived to make it be valid) that, if you cast a vote S (where S is some signed real number) your probability of altering the result of a 2-choice election, is C·|S|, where C is a small constant (depending on the number of other voters only). [Or at least, this is true to arbitrarily small relative error.]
OK. Here are the rules of a (rather bad) voting system. This voting system, we claim, will inspire honesty among strategic voters in a manner such that we can deduce from the votes, their honest utilities.
Claim: Your best voting strategy in a multicandidate election conducted under that system, is to make all your scores proportional to honest utility differences.
Proof: You (the voter) want to maximize your expected utility, which is proportional to
From the honest S[AB]s I thus-got from you, it then therefore is easy for me to deduce all your utilities (up to an overall scaling factor and translation by an additive constant). [Further, if two of the "candidates" happen to have difference presumably viewed as the same by all (such as if the event "you die" is a "candidate") then the scaling/normalizing factor would also be known.] And note this works in elections with any number of candidates, not just 3-candidate elections.
But why was the underlying assumption valid? Well... maybe it isn't... but we can artificially force it to be valid by actually making the election system now not have any "other voters" besides you; instead it just uses your vote and some random number generation to decide on the winner. For example, system artificially assigns (1/C) times a random normal as its initial score-difference between A and B (where A,B is the random candidate-pair it selected), then it adds your S[AB] to that, then if the resulting value is positive then A wins, otherwise B wins. (Here C is a small constant; this then becomes valid in the limit C→0+, i.e. is valid to better and better approximation the smaller C is made. Equivalently, all the "other voters" are just identical independent random-number generators and there are a vast number of other voters.)