<p>I think you are probably looking for "On playing “Twenty Questions” with a liar", Dhagat, Gacs, and Winkler, SODA 1992, <a href="http://portal.acm.org/citation.cfm?id=139404.139409" rel="nofollow">http://portal.acm.org/citation.cfm?id=139404.139409</a></p>

<p>The <a href="https://scholar.google.com/scholar?cites=3224472332412293525" rel="nofollow">many other papers that cite this one</a> probably include additional relevant hits.</p>

CC BY-SA 3.0
2015-02-16T23:05:44.787Z
Does anyone have a source for the 2nd link? It is not available anymore.
Ryan Dougherty
CC BY-SA 3.0
2015-02-17T02:17:33.430Z
The second link was obtained by going to Google scholar, finding the first paper, and then clicking on the "cited by NN" link that it shows for its results (where NN is the number of papers that cite this one). Presumably that procedure still works, even if Google has changed their URL format.
David Eppstein
CC BY-SA 3.0
2011-01-29T23:23:20.083Z
2015-02-17T02:18:29.197Z
2015-02-17T02:18:29.197Z
David Eppstein
<p>The title speaks for itself. Here are <a href="http://en.akinator.com/">Akinator</a> and <a href="http://www.20q.net">20Q</a>.</p>

<p>The principle of these games is to ask a user a number of questions relating to some entity chosen by the user. And then find out what is this entity. The core of the algorithm is to find the "most useful question" at each round, while dealing with a user who might not answer all questions correctly.</p>

<p>"most useful question" being defined as the question that give the most information, in the optimal case splitting the audience (or number?) of candidate entities into two equal halves.</p>

<p>I found a paper that described some algorithms (well the word "algorithm" was not used, but the proofs could be turned into algorithms). Unfortunately I cannot find this paper again :( . The paper described the problem with game theory concepts, with some levels of lying allowed to the user (it discussed  3 levels of lying). Please post if you think you know the paper.</p>

CC BY-SA 2.5
2011-01-30T11:59:34.657Z
http://stats.stackexchange.com/questions/6074/akinator-com-and-naive-bayes-classifier Here is discussion on stats.SE
Tomek Tarczynski
<ds.algorithms>
What algorithm is behind akinator or 20q?
BenoitParis
# What algorithm is behind akinator or 20q?

(Asked by: username_0 on 2011-01-29)

The title speaks for itself. Here are [Akinator](http://en.akinator.com/) and [20Q](http://www.20q.net).

The principle of these games is to ask a user a number of questions relating to some entity chosen by the user. And then find out what is this entity. The core of the algorithm is to find the "most useful question" at each round, while dealing with a user who might not answer all questions correctly.

"most useful question" being defined as the question that give the most information, in the optimal case splitting the audience (or number?) of candidate entities into two equal halves.

I found a paper that described some algorithms (well the word "algorithm" was not used, but the proofs could be turned into algorithms). Unfortunately I cannot find this paper again :( . The paper described the problem with game theory concepts, with some levels of lying allowed to the user (it discussed 3 levels of lying). Please post if you think you know the paper.

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: http://stats.stackexchange.com/questions/6074/akinator-com-and-naive-bayes-classifier Here is discussion on stats.SE  

---

## 1 answers

### Answer by username_2 on 2011-01-29. Score: 14

I think you are probably looking for "On playing “Twenty Questions” with a liar", Dhagat, Gacs, and Winkler, SODA 1992, <http://portal.acm.org/citation.cfm?id=139404.139409>

The [many other papers that cite this one](https://scholar.google.com/scholar?cites=3224472332412293525) probably include additional relevant hits.

> **Comments:**
> **username_3**: Does anyone have a source for the 2nd link? It is not available anymore.  
> **username_2**: The second link was obtained by going to Google scholar, finding the first paper, and then clicking on the "cited by NN" link that it shows for its results (where NN is the number of papers that cite this one). Presumably that procedure still works, even if Google has changed their URL format.  

---

