2
$\begingroup$

Suppose we have $N$ users that can vote for a given question by "Yes" or "No". Each user have a probability which is considered as the confidence that we have in that user (e.g. a user may have a probability of 0.8 to answer the question correctly, and a probability of 0.2 to answer it wrongly). Each user requesst an amount of money as a reward for answering the question. I (as the asker of the question) have a limited budget for paying the users.

Given this budget, which users should I ask to maximize the final answer to be correct (i.e. the answer obtained after aggregating the asked answers)?

Additional informations:

"what does it mean for a vote to be correct": if the question is "does 10/2 equals 5?" then "Yes" is a correct answer to this question; now if the probability associated to the user is 1, that means that the user will answer this question correctly because it have a very good knowledge of the domain of the question (mathematics); if the probability associated to the user is 0, this means that the user will answer this question wrongly; if the probability associated to the user is 0.5, then his answer may be correct ("Yes 10/2=5") with a probability of 0.5, or maybe wrong wt probability 1-0.5.

What I want is to maximize the fact of getting the good final answer by aggregating the obtained answers (want to know that the answer to my question is "Yes" 10/2=5). For this, which users should I ask (given my budget, and given that each user request a given amount of money to accept to answer my question), and how to aggregate their answers in order to have the correct one.

What is called "vote" is the classical aggregation of the answers, by taking the most common answer among the received ones (if there is more "Yes" answers then ok I will consider the final result as "Yes), but in my real example I have some constraints: probabilities associated to users, ammount of money requested by each user to answer my question, and the total amount of money that I have, so I need to also consider these constraints. If you want, forget about the word "vote" in the question, just tell me who to ask and how to aggregate the answers that I get.

$\endgroup$
8
  • 3
    $\begingroup$ Several interpretations of the objective are possible. For instance, do you want to maximize the expected number of correct answers? Or perhaps you want to maximize the chance that every answer is correct? Or the chance that the number of correct answers equals or exceeds a minimum threshold? Also, what role does "voting" have in this question? And what does it mean for a vote to be "correct"? What is the distinction between a "vote" for and an "answer" to a question? It is hard to see how your question can reliably or objectively be answered until you clarify these issues. $\endgroup$
    – whuber
    Dec 5 '12 at 17:36
  • $\begingroup$ @whuber "what does it mean for a vote to be correct": if the question is "does 10/2 equals 5?" then "Yes" is a correct answer to this question; now if the probability associated to the user is 1, that means that the user will answer this question correctly because it have a very good knowledge of the domain of the question (mathematics); if the probability associated to the user is 0, this means that the user will answer this question wrongly; if the probability associated to the user is 0.5, then his answer may be correct ("Yes 10/2=5") with a probability of 0.5, or maybe wrong wt proba 1-0.5 $\endgroup$
    – shn
    Dec 5 '12 at 19:00
  • $\begingroup$ @whuber What I want is to maximize the fact of getting the good final answer by aggregating the obtained answers (want to know that the answer to my question is "Yes" 10/2=5). For this, which users should I ask (given my budget, and given that each user request a given amount of money to accept to answer my question), and how to aggregate their answers in order to have the correct one. $\endgroup$
    – shn
    Dec 5 '12 at 19:04
  • $\begingroup$ @whuber What is called "vote" is the classical aggregation of the answers, by taking the most common answer among the received ones (if there is more "Yes" answers then ok I will consider the final result as "Yes), but in my real example I have some constraints: probabilities associated to users, ammount of money requested by each user to answer my question, and the total amount of money that I have, so I need to also consider these constraints. If you want, forget about the word "vote" in the question, just tell me who to ask and how to aggregate the answers that I get. Is it clear ? $\endgroup$
    – shn
    Dec 5 '12 at 19:14
  • 1
    $\begingroup$ @whuber You are right, how you determine the "reliability" of voters is another somehow complicated problem which depend on many indices like behaviour of voters... For the current question I'll just assume that the probabilities that we are talking about are indeed "probabilities of answering the question correctly". $\endgroup$
    – shn
    Dec 5 '12 at 21:10
1
$\begingroup$

You can think of the "expected number of correct answers" for each user--for example, your hypothetical user with probability 0.8 of answering correctly has an expected number of correct answers equal to 0.8, when you give him a single question.

Then, divide by your cost for each user. Suppose your user with probability 0.8 asks for \$2 dollars. When you divide, you get an "expected number of correct answers per dollar" of 0.4 for that user. A user with probability 0.6 of answering correctly but who asked for only \$1 would have an "expected number of correct answers per dollar" of 0.6.

Now you have a few possible approaches. The simplest is to use a greedy algorithm, and go through an select as many users as you can within your budget starting with the highest "expected number of correct answers per dollar." This is an approximate algorithm.

A better approach is to treat this as a variant of the knapsack problem. Solving it is NP-hard, but there are polynomial time approximations which are better than the greedy algorithm above.

$\endgroup$
16
  • $\begingroup$ (Note that I'm talking just about one question to ask to users). If for example I have a very big budget (say infinit) which is sufficient to ask all the users, then if I ask all the users, the final answer that I aggregate/deduce may be worse (have less chance to be correct) than the case where I just ask only the first user which have an ENCAD equals to 0.98 (very hight) ... Your approximate algorithm is not considering such cases. $\endgroup$
    – shn
    Dec 5 '12 at 19:48
  • $\begingroup$ The answer you deduce will only be worse after asking all the users if you do a naive analysis of the answers you get, in which case it's best to just ask the one best user you can afford. Since you have information on how reliable each user is, you can do an analysis using that information such that every additional answer you get from a user, no matter how unreliable that user is, will help you estimate a better overall answer. $\endgroup$ Dec 5 '12 at 19:56
  • $\begingroup$ Of course, at some point it's just not worth asking more users, but that's a separate question. $\endgroup$ Dec 5 '12 at 19:57
  • $\begingroup$ This is also a part of my question, and of your approximate algorithm: Using the information on how reliable each user is, how can you check that every additional answer you get from a user, will help you estimate a better overall answer ? $\endgroup$
    – shn
    Dec 5 '12 at 20:03
  • $\begingroup$ From an information-theoretic perspective, the user is a noisy channel. The "truth" is input at one end, and the user outputs their answer which is equal to the truth with probability $p$ and not equal to the truth with probability $1-p$. The only case in which the user transmits no information at all is if $p = 0.5$ exactly. Unless you already have perfect information (i.e., you have a user who answers correctly with probability one), then the information received from the user will help you answer the question, assuming that different users are independent. $\endgroup$ Dec 5 '12 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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