De babbelende vriendinnen.

Project voor Multi Agent Systemen
Geertje Zwarts 0964239
Maartje van der Veen 0960683
augustus 2000

Inleiding
De Nationale Wetenschapsquiz 1999 bevatte de volgende vraag:
"Zes vriendinnen hebben ieder een roddel. Ze bellen elkaar. In elk gesprek wisselen ze alle roddels uit die ze op dat moment kennen. Hoeveel gesprekken zijn er minimaal nodig om iedereen op de hoogte te stellen van alle zes de roddels?
a. zeven
b. acht
c. negen "

Bij de televisieuitzending op Tweede Kerstdag gaf niemand het correcte antwoord, zelfs niet de hoogleraar wiskunde in het panel. Het correcte antwoord is te vinden op de nwo site, waar ook het minimale aantal gesprekken voor n agents met n roddels wordt gegeven.

Het leek ons leuk om hier een implementatie van te maken in de Logics Workbench. 6 vriendinnen was teveel om te implementeren, omdat het voor de LWB teveel rekentijd kost. Het probleem wordt ook wel duidelijk bij een implementatie van 4 vriendinnen.

Beschrijving Project
We hebben de volgende aannames gedaan:
- elke vriendin begint met minstens 1 nieuwtje
- er zijn steeds 2 vriendinnen met elkaar in gesprek, niet meer.
- als 2 vriendinnen elkaar bellen, weten de anderen niet dat dit telefoontje gepleegd is.
- als 2 vriendinnen elkaar bellen, vertellen ze alle nieuwtjes die ze weten.
- als 2 vriendinnen elkaar bellen, vertellen ze alleen de nieuwtjes en niet van wie ze de nieuwtjes gehoord hebben.

Helaas konden we het niet ingewikkelder maken, omdat er in de LWB maar een beperkte rekentijd te verkrijgen is, waarin de logische formules bewezen of weerlegd moeten worden. We hebben nog geprobeerd de LWB-programmatuur op linux aan de praat te krijgen, maar dat is niet gelukt.
De implementatie is  hier  te vinden. Ga naar  http://www.lwb.unibe.ch/run.html . Kopieer de source code in het raampje en run.

Verder hebben we de volgende vragen onderzocht:
1. Wordt met de aannames die we hebben gedaan, de kennis ooit common knowledge?

2. Als iedereen bij alle telefoontjes meeluistert, wordt de kennis dan common knowledge?

3. Als k < n, is het dan mogelijk dat de n agents via een aantal telefoontjes met k luisteraars common knowledge over de nieuwtjes verkrijgen?

Uitwerking
1. Voordat kennis common knowledge is, moet gelden dat iedereen weet dat iedereen weet dat iedereen weet ...... dat iedereen die bepaalde kennis heeft.
Na de vier telefoontjes uit de implementatie, weet iedereen alle nieuwtjes ('everybody knows' E)
Sommige agents weten van andere agents dat zij de nieuwtjes ook weten. Bijvoorbeeld:

provabele(situation_4 -> box4 box1 nieuwtjec, nieuwsrondje);
#true
provabele(situation_4 -> box3 box4 nieuwtjea, nieuwsrondje);
#true

Maar er zijn ook agents die niet van elkaar weten dat ze alle nieuwtjes weten. Bijvoorbeeld:
provabele(situation_4 -> box4 box3 nieuwtjec);
#false
provabele(situation_4 -> box1 box2 box3 nieuwtjec);
#false

Omdat steeds maar 2 agents met elkaar in gesprek zijn, zijn de nieuwtjes die zij elkaar vertellen alleen tussen die 2 agents common knowledge. Omdat de agents niet van elkaar weten wie wie opbelt, (de laatste aanname) De agents kunnen elkaar nog allemaal een keer opbellen, zodat ze daarna weten dat iedereen alle nieuwtjes weet, maar dan is het nog onbekend of iedereen weet dat iedereen de nieuwtjes weet. etc. Omdat een telefoongesprek maar tussen 2 agents plaatsvindt, blijven er altijd buitenstaanders die niet delen in de common knowledge.

2. Als iedereen meeluistert met de telefoongesprekken en iedereen ook van elkaar weet dat iedereen meeluisterd, worden de nieuwtjes wel common knowledge. In feite wordt een telefoongesprek met iedereen tegelijk gevoerd. En weet iedereen dat iedereen weet dat iedereen weet ... het nieuwtje.

3. Ook hier zal er nooit common knowledge onstaan tussen alle agents, wel tussen degene die bellen en meeluisteren, maar er blijft altijd minstens 1 buitenstaander.
Maar als de bellende en luisterende agents een protocol afspreken, bijvoorbeeld; "nu gaan we de niet-meeluisterende agents opbellen en ze vertellen wat de kennis is, die onder ons nu common knowledge is." dan wordt hun kennis wel common knowledge, omdat in de volgende belronde de niet-meeluisterende agents op de hoogte zijn van het gesprek dat zal plaatsvinden.
Eigenlijk is het protocol dan de common knowledge. Een probleem wat echter dan opduikt is hoe de niet-meeluisterende agents weten dat het gesprek daadwerkelijke plaatsvindt.
Hiervoor moeten dan ook weer oneindig telefoontjes gepleegd worden, waardoor de common knowledge dus alsnog niet bereikt is.