What algorithm is behind akinator or 20q? The title speaks for itself. Here are Akinator and 20Q.

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.
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 probably include additional relevant hits.