Persbericht CWI WIN 01/2
december 2001
De logica van eerlijk kiezen en delen
Stemmen vormt het hart van onze democratie. Het komt voor in alle geledingen van de maatschappij, van het kiezen van de voorzitter van de buurtvereniging tot de Kamerverkiezingen. Goede en eerlijke stemprocedures zijn dus van groot belang. Het blijkt echter heel moeilijk om hier het begrip 'eerlijk' goed te definiëren. De samenleving kent veel meer van dergelijke 'sociale keuze' problemen, bijvoorbeeld de verdeling van een erfenis of de procedure bij veilingen. In de praktijk gaat het vaak om ingewikkelde procedures. Wij willen dan graag weten hoe correct en efficiënt die zijn. Om daarover zinvolle uitspraken te kunnen doen moeten wij er op een zuivere manier over kunnen redeneren. Dat kan met behulp van de logica, een tak van de wiskunde die bij uitstek geschikt is voor dergelijke problemen.
Logicus Marc Pauly promoveert op donderdag 13 december op de betekenis van de logica voor 'sociale software' -- de analyse van sociale processen met formele methoden uit de informatica. In zijn op het CWI in Amsterdam verrichte onderzoek heeft hij daartoe twee talen ontworpen: een Spel-logica voor toewijzingsproblemen, en een Coalitie-logica voor verkiezingsproblemen. Deze eerste stap kan leiden tot een systeem dat automatisch de eerlijkste stemprocedure genereert. Zo ver is het echter nog lang niet.
Je kunt de krant niet opslaan of er staat wel iets over verkiezingen. Om lid te worden van de EU moet een land democratische verkiezingen kunnen garanderen. Binnen enkele jaren moeten in 'tabula rasa' Afghanistan zulke verkiezingen de grondslag leggen voor een nieuwe staat. Aan elk van de in het Westen in de loop der jaren ontworpen verkiezingsprocedures kleeft echter wel een bezwaar. Met een iets ander, maar nog steeds plausibel verkiezingssysteem in de VS, zou nu niet Bush, maar Gore in het zadel zitten. Een bekend geval was de Bonn vs Berlijn kwestie van tien jaar geleden: moeten parlement en/of ministeries al dan niet naar Berlijn verhuizen? Ook hier gaf niet de voorkeur van de burger de doorslag, maar de gevolgde stemprocedure, die echter was vastgesteld door een commissie van 'wijze mannen' ... .
Vijftig jaar geleden gaf de Amerikaan Kenneth J. Arrow een wiskundig bewijs dat het, gegeven een aantal plausibel klinkende randvoorwaarden, onmogelijk was om een algemeen bruikbare, volkomen eerlijke stemmethode te vinden. Er zal dus in de praktijk altijd water bij de wijn moeten. (De 'wil van het volk' was trouwens al sinds zijn invoering ruim twee eeuwen geleden een problematisch begrip.) Een zo'n voorwaarde is dat de uitslag niet uitsluitend mag afhangen van het stemgedrag van één individu (de'dictator'). Een andere is het uitsluiten van 'strategisch stemmen'. Hierbij kan een groep bijvoorbeeld de aanname van een wet verhinderen door niet volgens de eigen voorkeur te stemmen, maar zo dat het stemproces in een oneindige kringloop terechtkomt, en er nooit een beslissing wordt bereikt.
Pauly heeft nu een wiskundige taal (logica) ontworpen waarin begrippen als 'coalitie' zijn gedefinieerd, met bijbehorende spelregels. Hierdoor is het nu mogelijk een stemprocedure te onderzoeken op ongewenste eigenschappen als bovengenoemde.
Verder heeft Pauly ook een Spel-logica onderzocht, waarmee men kan redeneren over toewijzingsproblemen. Moeder heeft voor haar twee kinderen een taart gebakken die zij zelf maar onderling moeten verdelen. De methode (algoritme): 'Ik snij, jij kiest' geeft beide kinderen de zekerheid dat zij minstens de helft kunnen krijgen. Met meer kinderen is een soortgelijke algoritme te bedenken die elke deelnemer een strategie biedt om een eerlijk deel van de taart te bemachtigen. Ook toewijzingsproblemen doen zich voor in allerlei belangrijke situaties, bijvoorbeeld de toewijzing van restzetels bij de Kamerverkiezingen.
Pauly's nieuwe logica's zijn uitbreidingen van logica's die worden gebruikt om over computerprogramma's te redeneren. Daar worden dergelijke formele methoden toegepast om aan te tonen dat een programma ook echt 'doet wat het moet doen'. Opgevat als een spel is een computerprogramma echter vrij primitief: er is maar één speler, de programmeur. Met de Spel-logica en Coalitie-logica kan men redeneren over sociale processen of spelen waarbij twee of meer personen een rol spelen.
(WIN01/2)
Henk Nieland
Beschrijving van het Telefoon-Democratie probleem in Pauly's Coalitie-logica.
Een vader wil opnieuw trouwen en heeft twee kandidaten op het oog. Hij wil dat zijn drie dochters (per meerderheid) daarover beslissen. Omdat die alle drie ver weg wonen besluit hij ze op te bellen. Gevraagd een telefoonprocedure die ertoe leidt dat elke twee van de drie dochters elke kandidaat kunnen kiezen, met zo weinig mogelijk kosten voor de vader. Deze vraag, opgeschreven in Coalitie-logica, kan als invoer aan een computer worden gegeven, die dan automatisch een procedure genereert. De naieve oplossing is dat de vader ze gewoon begint te bellen, en als de eerste twee van mening verschillen bel hij de derde. Maar je kunt ook met twee telefoontjes toe: de vader belt de eerste dochter en vraagt deze welke van haar twee zusters hij moet bellen. Dit garandeert nog steeds dat elke twee dochters elk van de twee potentiële stiefmoeders kunnen 'bereiken'. Wel moeten hier de dochters eventueel met elkaar bellen om hun preferenties te weten te komen, waardoor de telefoonkosten in feite van de vader naar de dochters worden geschoven.
Mededelingen voor de redactie:
- Als U gebruik maakt van dit artikel, stellen wij toezending van een exemplaar van Uw uitgave zeer op prijs.
- Marc Pauly verdedigt zijn proefschrift op donderdag 13 december om 10.00 uur aan de Universiteit van Amsterdam (aula Oude Lutherse Kerk, Spui 411).
De promovendus is als volgt bereikbaar:
020 - 625 3433(privé)
020 - 592 4227 (CWI)
020 - 525 6925 (Universiteit van Amsterdam)
E-mail: Marc.Pauly@cwi.nl
WWW: http://www.cwi.nl/~pauly
Wetenschapsvoorlichting CWI:
Henk Nieland, tel. 020 - 592 4092, e-mail: Henk.Nieland@cwi.nl
Annette Kik, tel. 020 - 592 4248, e-mail: Annette.Kik@cwi.nl
Het CWI is een nationaal instituut voor onderzoek in de wiskunde en de informatica. Er werken ca. 165 onderzoekers. De nadruk ligt op grensverleggend onderzoek voor praktische vraagstukken en de overdracht van nieuwe kennis naar de maatschappij. Het instituut onderhoudt een breed scala aan contacten met universiteiten, industrieën, grote technologische instituten, en particuliere en overheidsinstellingen. Het CWI is een der oprichters van ERCIM, het European Research Consortium for Informatics and Mathematics, en neemt deel in het Telematica Instituut.
---