Author |
Topic: Who's telling the truth problem? (Read 557 times) |
|
Rob L
Guest
|
Ok, I have an exercise for the interested reader. Anyone who recognises what I'm really on about is invited, a) to join me and b) not to let that cloud the issue.
Imagine a room with seven people in it.
At a given point in time they will all do something within a given framework - e.g. move in a certain way. (Yes, this comes down to game-theory type stuff but let's ignore that for now).
You are allowed to speak to any of them and ask any question. In a twist on the original riddle-style of people hanging around forks in the road, these people will respond to your questions with truth, falsehood or uncertainty.
Furthermore they will have a set belief in whether the statement they utter is what they believe it to be e.g. They may believe they are telling you the truth (but may be wrong). Or, may attach a probability to their response.
You may continue asking questions given the responses to your previous questions. The others in the room may do the same.
Now, the problem/aim here is to determine what is going to happen based on all these questions/answers.
My gut feeling is that this represents some kind of knowledge-base with associated 'certainty' values and assertions but I wondered what the great problem-solvers of the planet thought. Where do we begin?
|
|
 IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
Gender: 
Posts: 767
|
 |
Re: Who's telling the truth problem?
« Reply #1 on: Jan 16th, 2004, 5:52am » |
 Quote  Modify
|
Am I one of the seven people? Do I always tell the truth, or is there a probability associated with what I say? Am I in denial -- will I lie and think I tell the truth? If so, I can answer your problem very quickly :-D
Given that each one has a different probability of telling the truth, and this is different for each person (I assume), this becomes very complicated. You would need to ask a lot of questions to determine the probabilities. Are we limited to asking questions about other people (is person A telling the truth, did person B take this action in the room), or can we ask obvious ones to fish for who tells the truth (is the sky blue)? Will people collude? I.e. if I ask everyone the same question, and they are all liars, might they all tell the same lie so I think it is true?
I would probably begin by modeling this in software and taking about 1,000,000 samples.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
Rob L
Guest
|
|
Re: Who's telling the truth problem?
« Reply #2 on: Jan 16th, 2004, 7:26am » |
Quote Modify
 Remove
|
Yes, you are one of the seven.
You have full control of what you say.
I was hoping that the probability issue would diminish if you started to introduce statements, much like the fork-in-the-road examples, that invovle third parties (within the room).
e.g. "A has asserted to me X - do you, B, agree with X?"
or we know A has asserted X and B has asserted, independently X' thus we know one of them is wrong and/or lying.
I realise that this is a hugely open-ended problem - I'm really after opinions on how to attack such an issue. No doubt there is also a large psychological side-problem, one I'm trying to sideline for now 
|
|
IP Logged |
|
|
|
Rob L
Guest
|
|
Re: Who's telling the truth problem?
« Reply #3 on: Jan 21st, 2004, 5:57am » |
Quote Modify
Remove
|
OK, I guess this is a little hard to solve.
My research leads me to think that maybe bayesian (or belief) networks are required here but I have yet to figure these things out. Anyone used this stuff before?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Who's telling the truth problem?
« Reply #4 on: Jan 21st, 2004, 8:15am » |
Quote Modify
|
If this problem is what I think it basicly is, there is an algorithm that will resolve it if there are no more than two people lying.. But I'd have to dive into my notes/papers..
It would also assume everybody follows the same procedure, which may not be the case..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Who's telling the truth problem?
« Reply #5 on: Jan 22nd, 2004, 6:18am » |
Quote Modify
|
Here's the algorithm I was talking about.. I'll go see if I can find some more notes on it..
Code:
/* Fault-tolerant consensus, W.H. Hesselink, 2nd October 2003.
See the third problem of
P. Berman, J.A. Garay:
Asymptotically optimal distributed consensus (extended abstract). In G. Ausiello, M. Dezani-Ciancaglini, S. Ronchi Della Rocca (eds.):
Automata, Languages and Programming. LNCS 372, pp. 80--94 */
/* Use Spin's Advanced Verification Options:
Extra compile-Time Directives: -DCOLLAPSE, -DMA=188, or -DBITSTATE
Force the unreliable member always to send 0 */
#define Nproc 5 /* Number of processes */
#define UnReliable 1 /* Number of unreliable processes */
typedef ChanArr {
chan ch[Nproc] = [1] of {bit} ;
}
ChanArr chans [Nproc] ;
bit val [Nproc] ;
byte aktief = Nproc ;
proctype reliableMember (byte self) {
val[self] = (self != 3) ;
byte round = 0 ;
byte i, nr ;
bit nieuw ;
do
:: round <= UnReliable ->
atomic { /* sending in first phase */
i = 0 ;
do
:: i < Nproc ->
chans[self].ch[i] ! val[self] ;
i ++
:: i == Nproc -> break
od ;
nr = 0 ;
} ;
do /* receiving in first phase */
:: i > 0 ->
i -- ;
chans[i].ch[self] ? nieuw ;
nr = nr + nieuw
:: i == 0 -> break
od ;
if /* sending in second phase */
:: round == self ->
atomic {
do
:: i < Nproc ->
chans[self].ch[i] ! (2*nr - 1)/Nproc ;
i ++
:: i == Nproc -> break
od
}
:: else
fi ;
chans[round].ch[self] ? nieuw ; /* receiving in second phase */
if /* decision after second phase */
:: nr <= UnReliable -> val[self] = 0
:: nr >= Nproc - UnReliable -> val[self] = 1
:: else -> val[self] = nieuw /* no consensus yet */
fi ;
round ++
:: else -> break
od ;
aktief --
}
proctype unReliableMember (byte self) {
byte round = 0 ;
byte i ;
bit nieuw ;
do
:: round <= UnReliable ->
atomic { /* sending in first phase */
i = 0 ;
do
:: i < Nproc ->
chans[self].ch[i] ! 0 ;
i ++
/* :: i < Nproc ->
chans[self].ch[i] ! 1 ;
i ++ */
:: i == Nproc -> break
od ;
} ;
do /* receiving in first phase */
:: i > 0 ->
i -- ;
chans[i].ch[self] ? nieuw
:: i == 0 -> break
od ;
if /* sending in second phase */
:: round == self ->
atomic {
do
:: i < Nproc ->
chans[self].ch[i] ! 0 ;
i ++
/* :: i < Nproc ->
chans[self].ch[i] ! 1 ;
i ++ */
:: i == Nproc -> break
od
}
:: else
fi ;
chans[round].ch[self] ? nieuw ; /* receiving in second phase */
round ++
:: else -> break
od ;
val[self] = 0 ;
aktief --
}
init {
byte reliable = Nproc - UnReliable ;
byte unreliable = UnReliable ;
byte proc = 0 ;
atomic {
do
:: unreliable > 0 ->
run unReliableMember (proc) ;
proc ++ ;
unreliable --
:: reliable > 0 ->
run reliableMember (proc) ;
proc ++ ;
reliable --
:: proc == Nproc -> break
od
} ;
aktief == 0 ; /* wait for termination of all members */
atomic {
byte nr = 0 ; /* verify consensus over enough members */
/* proc = Nproc */ ;
do
:: proc > 0 ->
proc -- ;
nr = nr + val[proc]
:: else -> break
od ;
}
assert (nr <= UnReliable || nr >= Nproc - UnReliable) ;
// assert (nr >= Nproc - UnReliable )
}
/* Once the reliable processes have reached consensus, this consensus is preserved because of the first two alternatives of the last choice in reliableMember. There is at least one value for round that corresponds to a reliable process. In this round, consensus is reached:
Assume that round is the number of a reliable process.
Consider the precondition of this round: assume there are x reliable processes with val = 1 and y processes with val = 0.
Assume this round does not yield consensus among the reliable processes. Yet all reliable processes get the same value for nieuw in line 57, say 1.
This occurs iff process round has 2*nr > Nproc in line 50,
This is possible iff 2*(x+UnRel) > Nproc, or eq: x+UnRel > y.
Since no consensus is reached, some reliable processes have nr <= UnRel.
This is possible iff x <= UnRel.
The choice of such numbers x and y is possible iff Nproc < 4 * UnRel.
E.g. take x = UnRel, y = Nproc - 2 * UnRel.
*/ |
|
|
| « Last Edit: Jan 22nd, 2004, 6:50am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print