Speltheorie helpt software-agenten competitief denken

Non-coöperatieve agenten, ook wel kortweg competitieve agenten genoemd, zijn pas de laatste jaren meer in de belangstelling komen te staan. Dergelijke agenten hebben hun eigen (mogelijk conflicterende) doelen, en zijn uit op (slechts) lokale optimalisatie op basis van deze doelen. Dergelijke agenten zijn niet ontworpen voor een gemeenschappelijke hoofddoelstelling, maar voor een specifiek eigen doel, mogelijk die van de bezitter van die enkele software-agent. De bezitters van deze agenten kunnen bijvoorbeeld concurrerende bedrijven zijn, maar ook autonome business units of afdelingen binnen eenzelfde (grote) organisatie. Bij gebruik van competitieve agenten in een systeem, is de vraag hoe een dergelijk systeem goed kan werken. Hier is inspiratie uit de economische wetenschap belangrijk: denk maar aan concurrerende bedrijven in een markt waar interactie verloopt via bepaalde spelregels. Voorbeelden hiervan zijn onder meer de wijze van onderhandelen en veilen, of ‘business rules’ en wetgeving. Dit heeft binnen de economie geleid tot het ontstaan van de speltheorie, een gebied dat ondertussen ook te vinden is in de wiskunde en politieke wetenschappen. Een spel wordt bepaald door zijn regels omtrent een aantal spelers die interactie met elkaar hebben. Dit betreft met name aspecten als wie op welk moment wat mag doen, en wie aan het eind van het spel iets (en: wat) krijgt. Uitgaande van dergelijke regels, is voor ieder van de spelers een spelstrategie van belang: een specificatie van de acties die een speler zal doen, voor elk van de mogelijke momenten waar een actie van hem verlangd wordt. Dit om zo goed mogelijk de voor hem gewenste uitkomsten van het spel te bereiken. Voorbeelden van spelen zijn onder meer onderhandelen, veilen, netwerkvorming (tussen partijen), productiebeslissingen (in een oligopolie-economie) of het kiezen van resources, tegelijk met concurrerende partijen (zie kader). Spelregels Om een multi-agentsysteem met competitieve agenten goed te kunnen laten werken, moeten twee belangrijke zaken worden ontwikkeld: de spelregels voor de interactie tussen de agenten, en de strategieën voor de afzonderlijke agenten om binnen de spelregels optimaal te werken. Het eerste betreft het ontwerp (of de keuze) van het spel, ook wel bekend als ‘mechanism design’. Hiervoor moet een geschikte keuze worden gemaakt, die leidt tot de hoofddoelstellingen van het agentsysteem als geheel. Het tweede betreft het ontwerp van de inhoud van de agenten: adaptieve (intelligente) software die uiteindelijk de strategieën bepaalt, aanpast en leert. Hier zijn modellen en ‘gewoon uitprogrammeren’ alleen zeker niet genoeg, maar moet werk en vooral ook onderzoek worden gestoken in het maken van goed werkende oplossingen. Dergelijke agenten moeten hier dus echt iets doen en kunnen. De adaptiviteit en het lerend vermogen van agenten is in veel gevallen zeer nodig, zoals onder andere is aangetoond in de literatuur, voor onder meer verscheidene vormen van onderhandelen. Hiertoe moet kennis uit twee gebieden worden gebruikt en ontwikkeld. Enerzijds de informatica, in het bijzonder de intelligente algoritmiek, ‘computational intelligence’ en agentsystemen. Anderzijds de economie, voor wat betreft spelen, marketing, utiliteitsfuncties en dergelijke. Bovendien zijn goede evaluatietechnieken belangrijk. Voor een aantal gevallen kan dat bijvoorbeeld mathematische analyse zijn, maar voor uitgebreidere (fundamentele) gevallen zijn grondige computerexperimenten (simulaties) het geëigende middel (zie kader). Technieken De adaptiviteit van agenten is nodig voor de juiste werking van (grootschalige) multi-agentsystemen. Belangrijke technieken hiervoor zijn met name adaptieve algoritmische technieken en computational-intelligencetechnieken, zoals evolutionaire (genetische) algoritmen, neurale netwerken of hybride heuristische methoden. Dit betreft geen standaardwerk of -onderzoek, maar een relatief jong gebied dat zich bezighoudt met hoe deze technieken zijn in te zetten voor dergelijke (economische) spelen in multi-agentsystemen. Adaptiviteit van agenten kan met name worden bereikt door middel van bijvoorbeeld een aantal parameters (variabelen, waarden) of functies die door de agent moeten worden geleerd of online berekend, als onderdeel van een geschikt model dat de agent gebruikt. Dit kan gebeuren door middel van online leren, online-heuristieken, of met behulp van geaggregeerde en geüpdate data uit het verleden. Voorbeelden van dergelijke parameters zijn biedwaarden in onderhandelingen en veilingen, waarderingen van ‘trade-offs’ tussen verschillende aspecten, keuzeparameters voor afwisselend gebruik van verscheidene policies, of parameters betreffende modellering en classificatie van tegenspelers. De beoogde adaptiviteit kan alleen worden verkregen indien de beslissingen die door agenten in een spel moeten worden genomen, voldoende concreet en beperkt zijn. Dit betekent dat de modellering de juiste abstracties moet hebben en vooral ook, dat het aantal parameters dat moeten worden aangepast (geleerd of geüpdate), van geschikte omvang moet zijn. Hierbij is de keuze van de ‘sweet spot’ van belang: een juiste combinatie van modellering, keuzen van parameters en intelligente technieken. Criteria voor deze keuze zijn onder meer dat wetenschappelijk, experimenteel onderzoek aan dergelijke systemen mogelijk is en dat de resultaten realistisch en relevant zijn. Aanpak De aanpak voor het ontwerpen van agentsystemen met competitieve agenten is anders dan vaak wordt gedaan, in een aantal opzichten. Allereerst staat het concept van competitieve agenten toe, dat agenten voor hun eigen doelen optimaliseren (of die van hun eigenaren), zolang ze zich maar aan de spelregels houden. Hierdoor is het ontwerp van spelen als middel om het systeem te reguleren, zeer belangrijk. Ontwerp en keuze van dergelijke spelen werd al veel langer gedaan in de economie. Vandaar dat enerzijds de (economische) speltheorie van belang is in deze aanpak, en anderzijds computerexperimenten (simulaties), om de gevolgen van de spelkeuze op het totale systeemgedrag te kunnen bepalen. Belangrijker verschil ligt in de inhoud van de agent. Niet (alleen) wordt gekeken naar modellen voor een agent, op grond waarvan die (inter)acties uitvoert, maar met name ook naar specifieke oplossingen om dit daadwerkelijk te doen. Dit op een manier zoals ook gebruikelijk is in de (toegepaste) algoritmiek en computational intelligence. Hierbij wordt gefocust op ‘low-level’- in plaats van ‘high-level’-intelligentie en modellen. Low-level-intelligentie correspondeert met leermechanismen als bijvoorbeeld genetische algoritmen of neurale netweken. Dergelijke intelligentie heeft hanteerbaarheid en haalbaarheid als belangrijk voordeel (mits parameters en het bovenliggende model juist gekozen zijn). Deze technieken worden al geruime tijd met succes ingezet op probleemgebieden als patroonherkenning of optimalisering. Daarmee appelleren we niet aan het idee van de agent die verregaand kan redeneren op ‘hoog-niveau’, maar leggen we de ‘lat’ op een wat realistischere hoogte. Dergelijke software-agenten zijn daarmee vooral geschikt voor het zeer frequent uitvoeren van microtransacties. Ofwel: acties die vaak moeten worden uitgevoerd, en die per stuk slechts een klein onderdeel vormen van het grotere geheel. Juist dan kunnen deze technieken goed leren en effectief werken: zij kunnen online steeds kleine verbeteringen maken, terwijl de kosten van kleine fouten in totaal beperkt blijven. Zodoende kunnen zij hun meerwaarde leveren. Bijvoorbeeld omdat het te duur of vervelend voor mensen kan zijn om deze microtransacties uit te voeren, of omdat de risico’s op fouten van fatale omvang (bijvoorbeeld leidend tot faillissement) lager zijn dan bij agenten die weinig transacties van zeer grote omvang uitvoeren. Tenslotte, om goede resultaten te krijgen, is een stevige vorm van evaluatie noodzakelijk. Vandaar ook het belang van meetbare waarden, bijvoorbeeld in termen van nutsfuncties, efficiëntie, (pareto-)optimaliteit, benchmarks of complexiteit. Dit is zoals gebruikelijk in gebieden als de algoritmiek, computational intelligence en operations research. Kortom: meten en benchmarking, en waar mogelijke mathematische analyse, is hierbij het devies. Toepassingen Typische toepassingen voor agentsystemen met competitieve agenten liggen op verschillende gebieden. Het meest voor de hand liggende gebied is dat van de e-commerce, de handel op elektronische markten. Hier kunnen agenten verschillende entiteiten in de echte wereld representeren, zoals bijvoorbeeld klanten, winkels of concurrerende bedrijven. Agenten kunnen worden ingezet voor onderhandelen, bieden, contracteren en dergelijke. Een ander gebied is dat van de coördinatie tussen verschillende organisaties. Hierbij valt te denken aan logistiek en planning, als onderdeel van e-business. Bijvoorbeeld door te onderhandelen over afspraken en tijdstippen. Concrete toepassingen liggen onder meer in ‘supply chains’, resource-allocatie, planning en ‘scheduling’ of voorraadbeheer. Agenten kunnen worden ingezet om binnen de spelregels een planning te regelen, bijvoorbeeld een onderhandelingsspel. Een derde belangrijk gebied ligt minder voor de hand, maar is potentieel wel belangrijk: dat van de netwerkorganisaties, virtuele organisaties en organisaties met een relatief ‘losse’ hiërarchische structuur. Hierbij valt te denken aan organisaties waarbinnen een grote diversiteit is waar te nemen of waar suborganisaties in hoge mate autonoom zijn, zoals business units, afdelingen in ziekenhuizen en professionals. Kader 1: Onderhandelen Er zijn vele vormen van onderhandelen, en als zodanig ook beschreven in een spelvorm met spelregels. Een algemeen bekende vorm is het alternating-offers-onderhandelingsspel voor twee agenten, ofwel ‘handjeklap’. Dit verloopt als volgt, bijvoorbeeld voor de verdeling van een taart over twee spelers. Speler 1 doet een bod. Dat bod kan geaccepteerd worden door speler 2, waarmee het spel beëindigd is. Zo niet, dan kan speler 2 een tegenbod doen, en zo verder. Het spel eindigt ook na een vooraf ingesteld maximum aantal ronden, als nog geen bod is geaccepteerd. Stel nu dat er tien ronden worden doorlopen. Speler 2 is dan degene die het laatste bod kan doen. Met behulp van de speltheorie volgt nu, dat speler 2 zo goed als alles voor zichzelf op kan eisen (bijna de hele taart) en ook krijgt: door middel van een take-it-or-leave-it-bod. Speler 1 kan namelijk alleen dit bod accepteren of anders het spel beëindigen, waarbij geen van beide spelers iets krijgen. Door deze machtspositie van speler 2 als ‘stok-achter-de-deur’ te zien, zal speler 2 deze machtspositie ook in eerdere ronden hebben. Hij krijgt (bijna) de hele taart. Andere vormen van onderhandelen zijn bijvoorbeeld ‘1-to-many onderhandelen’ (bijvoorbeeld een verkoper met vele kopers), of ‘multiple-issue onderhandelen’ (bijvoorbeeld onderhandelen over vele aspecten van een transactie tegelijk, zoals een auto met optionele accessoires: kan er ook nog een airco, een spoiler en een kokosmat bij voor een heel bescheiden meerprijs?). Een gerelateerde vorm van ‘onderhandelen’ zijn veilingen. Van veilingen bestaan zeer vele typen, met verschillende eigenschappen voor uitkomsten, complexiteit en robuustheid. Kader 2: Geavanceerde modellen In de praktijk zullen mensen vaak niet tot de uitkomsten komen zoals beschreven in het kader over onderhandelen. Bijvoorbeeld vanwege normen als redelijkheid en billijkheid, of omdat in het onderhandelingsspel speler 1 ook nog mogelijkheden ziet om met andere agenten dan speler 2 over een andere taart te onderhandelen. Soortgelijke opmerkingen kunnen worden gemaakt voor bijvoorbeeld veilingen: hoe zullen spelers bieden in geval van herhaalde veilingen? Daamee komen we op enige algemene eigenschappen van spelen, die zeer relevant zijn voor gebruik in agentsystemen voor toepassingen, en die het gebruik van zowel adaptieve agenten als computerexperimenten noodzakelijk maken, ook omdat er geen algemene speltheoretische resultaten voor ‘goede’ strategieën bestaan. Dergelijke eigenschappen zijn onder meer: - herhaalde spelen; deze vormen een tot op heden moeilijk toegankelijk gebied. Als bijvoorbeeld een tafel in een veiling wordt aangeboden, kan een bieder er rekening mee houden dat er even later weer een tafel in een volgende veiling wordt aangeboden, en daarom eerst maar eens ‘rustig’ bieden. - beperkte informatie en beperkte rationaliteit: agenten weten (normaliter) niet alles van elkaar of van andere issues in het spel. - externaliteiten, zoals afhankelijkheden van waardering door spelers van zaken die niet direct in het spel zijn gegeven, bijvoorbeeld: wat is iets waard als een aantal agenten iets soortgelijks kunnen bemachtigen? - afhankelijkheden, bijvoorbeeld tussen meerdere spelen. Denk hierbij aan het combineren van services: verkrijgen van de ene service kan invloed hebben op de andere (bijvoorbeeld bij het samenstellen van een reis: data van vliegticket en hotelboeking moeten overeenkomen). Kader 3: Actuele projecten Enige projecten op het gebied van non-coöperatieve agenten van onder andere het CWI en TU/e (lopend, startend of recentelijk afgerond: veelal samen met andere partijen): - Deal: Distributed Engine for Advanced Logistics. Dit is een groot project betreffende logistiek en het wegvervoer. Hierin wordt onder meer onderhandeld over de allocatie van goederen over vrachtwagens en derde partijen (waaronder outsourcing). - Asta: Autonomous Systems of Trade Agents in E-Commerce. Hierin werd onder meer onderzoek verricht aan en prototypes gemaakt voor onderhandelen en bundelen van informatiegoederen, alsmede het gepersonaliseerd plaatsen van advertenties op websites middels veilingen. - Eesem: Evolutionary Exploration Systems for Electronic Markets. Dit project betreft onderzoek, met behulp van simulaties, naar elektronische markten, met betrekking tot onder meer intermediairs en netwerk-economieën. - Agi-Care: Agent-based Intelligent Health Care. Dit project betreft planning en logistiek in de zorg (het primaire proces). - Iabs: Interactivity in Agent-Based Simulation. In dit project worden interactieve simulatiesystemen ontworpen voor supply-chains. Prof. dr. ir. Han La Poutré (hlp@cwi.nl) is als hoogleraar e-business en informatica verbonden aan de faculteit Technologie Management van de Technische Universiteit Eindhoven. Hij is bovendien themaleider van de onderzoeksgroep ‘Evolutionary Systems and Applied Algorithmics’ bij het Centrum voor Wiskunde en Informatica (CWI) te Amsterdam. Dit artikel is een verkorte versie van zijn vandaag gehouden intreerede aan de TU/e: ‘Adaptieve systemen: intelligentie in software-agenten en economische spelen’.