IT helpt onderhandelaar

IT helpt onderhandelaar
Welke bijdrage kan IT leveren aan onderhandelingen? In zijn scriptie onderzocht Mark Hendrikx ‘tegenstandermodellen’: leertechnieken die automatische onderhandelaars toepassen om te schatten hoe aantrekkelijk een bod is voor de tegenstander.
Mark Hendrikx
Onderhandelen vormt in het dagelijks leven een belangrijk onderdeel van besluitvorming. Onderhandelen gebeurt op verschillende schalen: van de aankoop van een auto, tot de fusie tussen multinationals. Verschillende disciplines hebben onderzoek gedaan naar onderhandelen, waaronder (sociale) psychologie, speltheorie en kunstmatige intelligentie. Binnen de kunstmatige intelligentie is het afgelopen decennium onderzocht of het mogelijk is om complexe onderhandelingen uit te laten voeren door computers. Hierbij worden één of meer partijen vervangen door een automatische onderhandelingsstrategie, een strategie die onderhandelt op basis van de preferenties van uitkomsten die door de gebruiker zijn gespecificeerd. Dit biedt een aantal voordelen, waaronder kostenreductie door automatisering, betere resultaten door intelligentere biedingen, en het verminderen van sociale confrontatie.
Hoewel is aangetoond dat computers een positieve bijdrage kunnen leveren, zijn er nog verschillende uitdagingen. Een belangrijk probleem is dat in een onderhandeling de partijen vaak zo min mogelijk informatie uitwisselen (om exploitatie te voorkomen), hoewel het delen van informatie kan leiden tot een overeenkomst die voor alle partijen voordelig is. Een oplossing hiervoor is het gebruik van een mediator, maar dit is niet altijd mogelijk of wenselijk; de onpartijdigheid van een mediator is namelijk niet altijd te garanderen.
In mijn scriptie ‘Evaluating the Quality of Opponent Models in Automated Bilateral Negotiations’ behandel ik het fenomeen ‘tegenstandermodellen’: dit zijn leertechnieken die worden toegepast door automatische onderhandelaars om de intenties van de tegenstander in te schatten. Ik beschouw verschillende typen leertechnieken, waaronder technieken die voorspellen wat voor biedingen de tegenstander gaat maken en modellen die schatten wat de kans is dat een bieding zal worden geaccepteerd. Ik leg de nadruk op leertechnieken die op basis van de biedingshistorie schatten hoe aantrekkelijk een bod is voor de tegenstander, zogenaamde preferentiemodellen. Deze modellen kunnen helpen bij het maken van biedingen die interessant zijn voor alle partijen.
Mijn werk draagt op vier vlakken bij aan het onderzoeksveld. Ten eerste classificeer ik bestaande leertechnieken in een compacte taxonomie en geef ik een overzicht van de status van het onderzoeksveld. Ten tweede heb ik bijgedragen aan de ontwikkeling van een architectuur om de componenten van een onderhandelingsstrategie onafhankelijk te bestuderen. Ten derde heb ik deze architectuur toegepast om de kwaliteit van geavanceerde modellen te vergelijken. Tot slot heb ik meegewerkt aan de ontwikkeling van een onderhandelingsstrategie, die meerdere prijzen heeft gewonnen in een internationale onderhandelingscompetitie.
 
 
Figuur 2. De BOA-architectuur splitst een onderhandelingsstrategie op in het preferentiemodel, de biedingsstrategie, en de acceptatiestrategie
 
 
Vier componenten
De scriptie betreft leertechnieken die van toepassing zijn op onderhandelingen met twee deelnemende partijen. Formeel gezien bestaat een onderhandeling uit vier typen componenten (figuur 1) : het domein, de agents, het protocol, en de preferentieprofielen.
Het domein formaliseert over welke onderwerpen er wordt onderhandeld, bijvoorbeeld de kleur en prijs van een tweedehands auto. De agents zijn de entiteiten die onderhandelen door acties uit te voeren. Een agent kan zowel een mens zijn als artificieel. De mogelijke acties − zoals het uitbrengen of accepteren van een bod – zijn vastgelegd in het protocol. Het protocol beschrijft ook hoe de agents de acties uitwisselen, bijvoorbeeld alternerend. Het preferentieprofiel van een agent beschrijft zijn preferentie van de mogelijke biedingen. De uitdaging ligt in het feit dat een agent niet op de hoogte is van de preferenties en de toekomstige acties van zijn tegenstander. Een groot aantal modellen werd ontwikkeld om de preferenties van de tegenstander te schatten op basis van de acties van de tegenstander. Deze modellen zijn echter in isolatie ontwikkeld, voor verschillende protocollen ontworpen en op verschillende manieren geëvalueerd. Het gevolg is dat het onduidelijk is hoe betrouwbaar de modellen zijn en hoe de prestaties met elkaar te vergelijken zijn. Voor de ontwikkeling van nieuwe onderhandelingsstrategieën heeft dit tot gevolg dat het onduidelijk is welke leertechniek tot het beste resultaat leidt. Betrouwbare informatie over de kwaliteit van een leertechniek is essentieel: een inaccuraat model kan leiden tot verminderde prestaties.
Het kwantificeren van de kwaliteit van een onderhandelingsmodel is complex, omdat het model één onderdeel vormt van de complete strategie van een agent. Een model kan bijvoorbeeld zeer accuraat zijn, maar desondanks nauwelijks leiden tot een verbetering in prestatie omdat de agent het model slecht benut. Een betrouwbare meetmethode moet dus de potentiële meerwaarde van de toepassing van een model meten, evenals de accuraatheid van het model. In mijn scriptie ga ik in op de leertechnieken die worden toegepast door de agents om de preferenties van de tegenstander te leren, zogenaamde preferentiemodellen. Hiervoor maak ik gebruik van de agents die deelnamen aan de Automated Negotiation Agents Competition (ANAC), een jaarlijkse competitie waarin artificiële onderhandelaars strijden op verschillende onderhandelingsdomeinen die vooraf onbekend zijn. De agents zijn ontwikkeld voor Genius, een onderhandelingssimulator die wordt toegepast door verschillende academische instellingen. De reden om voor de ANAC-agents te kiezen, is dat ze zijn ontwikkeld voor een vergelijkbaar protocol en dat ze een goede representatie zijn van de status van het onderzoeksveld.
Preferentiemodel isoleren
Om de kwaliteit van de leertechnieken voor het leren van de preferenties van de tegenstander te vergelijken dienen deze eerst geïsoleerd te worden van de onderhandelingsstrategieën. Om dit te bereiken droeg ik bij aan de ontwikkeling en implementatie van de BOA-architectuur voor de Genius-onderhandelingssimulator. Het onderliggende idee van deze architectuur is een onderhandelingsstrategie te beschouwen als een verzameling van componenten met een specifieke taak die samenwerken.
De BOA-architectuur splitst een onderhandelingsstrategie op in drie componenten (figuur 2) : het preferentiemodel, de biedingsstrategie, en de acceptatiestrategie. Voor deze indeling is gekozen omdat elke aan de ANAC deelnemende agent bestaat uit een biedings- en acceptatiestrategie en vaak gebruik maakt van een preferentiemodel. Het preferentiemodel model leert de voorkeur van de tegenstander wat betreft de mogelijke uitkomsten van de onderhandeling. Dit model wordt na elk bod van de tegenstander bijgewerkt. Het model kan door de biedings- en acceptatiestrategie worden gebruikt om te bepalen hoeveel waarde de tegenstander hecht aan een bod. De biedingsstrategie bepaalt welk bod er mogelijk zal worden gedaan aan het eind van een ronde. De acceptatiestrategie beslist of het huidige bod van de tegenstander acceptabel is. Mocht de acceptatiestrategie besluiten dat er geen overeenkomst is, dan wordt het voorgenomen bod gepresenteerd aan de tegenstander. De reden dat de acceptatiestrategie pas na het genereren van een tegenbod beslist over het accepteren van het bod van de tegenstander, is omdat de acceptatie van het bod kan afhangen van het voorgenomen tegenbod. Om een nieuwe onderhandelingsstrategie aan te maken kiest een gebruiker eenvoudig een component voor elk van de drie types. Vervolgens wordt automatisch een onderhandelingsstrategie gegenereerd.
Om te bewijzen dat de architectuur geen strenge beperkingen oplegt aan de mogelijke strategieen, zijn de componenten van de meerderheid van de ANAC-agents geïsoleerd en toegevoegd aan het archief van beschikbare componenten. Dit archief bestaat ondertussen uit meer dan honderd unieke componenten. Voor bijna elke ANAC-agent bleek dat de prestatie van de agent, die is gecreëerd door de combinaties van de oorspronkelijke agent te selecteren, statistisch vergelijkbaar is met de originele agent. Ook bleek het mogelijk te zijn om de prestatie van de BOA-architectuurvarianten van de oorspronkelijke agents te verbeteren door de acceptatiestrategie en/of het preferentiemodel van deze agents te vervangen.
 
Modelkwaliteit kwantificeren
Uit voorgaand experiment is gebleken dat het mogelijk is om de prestatie van de meeste ANAC-agents te verbeteren door deze te voorzien van een alternatief preferentiemodel. Dit onderstreept het belang van inzicht in de kwaliteit van een preferentiemodel alvorens deze toe te passen.
Om de kwaliteit van de preferentiemodellen van de ANAC-agents te bepalen ontwikkelde ik twee meetmethodes. De eerste methode meet de potentiële meerwaarde van het gebruik van een model in een strategie. Het onderliggende idee van deze methode is om de prestaties van een verzameling agents te vergelijken in een wedstrijd, waarbij de agents met behulp van de BOA-architectuur steeds uitgerust worden met een ander preferentiemodel. De toepassing van deze meetmethode resulteerde voor elke preferentiemodel in een kwantificering van de meerwaarde van het gebruik van het model relatief aan andere modellen, perfecte informatie over de tegenstander, en het gebruik van geen model. Dit leverde een aantal interessante resultaten op. Ten eerste bleek dat het gebruik van een preferentiemodel kan resulteren in een prestatieverbetering, maar dat sommige modellen verminderde prestaties tot gevolg kunnen hebben. Ten tweede leken eenvoudige modellen beter te presteren dan complexere modellen.
Om mijn conclusies te valideren, voerde ik een tweede experiment uit waarin ik de accuraatheid van de modellen bepaalde onafhankelijk van de onderhandelingsstrategie waarin deze wordt toegepast. Net als in het voorgaande experiment bleek dat de eenvoudige leertechnieken beter presteerden. Een opvallend resultaat is echter dat de accuraatheid van het merendeel van de modellen afneemt naarmate een onderhandeling vordert (figuur 3) . Dit is waarschijnlijk te verklaren doordat de tegenstander later in de onderhandeling concessies maakt, en daarbij het beeld over zijn preferenties vertroebelt. Tot slot paste ik beide meetinstrumenten tegelijkertijd toe en onderzocht ik de relatie tussen de uitkomsten. Dit laatste experiment wees uit dat hoewel de meest accurate modellen niet perfect zijn, het verder vergroten van de accuraatheid waarschijnlijk geen significante vergroting in prestatie van een strategie oplevert.
Figuur 3. De accuraatheid van het merendeel van de modellen neemt af naarmate een onderhandeling vordert
 
Toepassingen
Sinds de introductie van de BOA-architectuur is deze meerdere malen toegepast in de ANAC-competitie. In 2012 behaalde de agent van Hendrikx’ team de derde plaats in de finale en een aparte prijs voor de beste prestatie op een van de hoofdonderdelen van de competitie. In 2013 eindigden twee agents ontworpen met behulp van de BOA-architectuur in de finale. Een van deze agents won zelfs de competitie. De BOA-architectuur wordt ook toegepast binnen academische instellingen. Op instellingen waaronder de Bar-Ilan University, Ben-Gurion University of the Negev, Maastricht Universiteit, en de Technische Universiteit Delft wordt de architectuur behandeld in kunstmatige-intelligentievakken. De architectuur helpt studenten bij het ontwikkelen van een strategie doordat ze zich kunnen richten op de individuele componenten. De collectie van bestaande componenten helpt de studenten bij het kritisch evalueren en verbeteren van de componenten.
In samenwerking met mijn begeleiders heb ik meerdere wetenschappelijke publicaties uitgebracht over de BOA-architectuur en preferentiemodellen. De publicatie Predicting the Performance of Opponent Models in Automated Negotiation won de prijs voor beste publicatie tijdens IAT-13: de 2013 IEEE/WIC/ACM International Conference on Intelligent Agent Technology.
Drie bijdragen
Het automatiseren van onderhandelen is een complex probleem dat wordt onderzocht binnen het onderzoeksgebied van kunstmatige intelligentie. Binnen dit vakgebied heb ik drie belangrijke bijdragen geleverd. Ten eerste heb ik bestaande leermodellen in kaart gebracht en gecategoriseerd in een compacte taxonomie. Ten tweede heb ik meegewerkt aan een architectuur waarin onderhandelingsstrategieën worden beschouwd als een verzameling van componenten. Ten derde heb ik deze architectuur toegepast om de kwaliteit te vergelijken van moderne leertechnieken die de preferenties van de tegenstander leren. Uit mijn analyse is gebleken dat een type relatief eenvoudige leertechnieken een bijdrage kan leveren aan het verbeteren van onderhandelingsstrategieën, maar dat bestaande leermodellen nog wel verbeterd kunnen worden wat betreft hun accuraatheid naarmate de onderhandeling vordert.
Momenteel wordt de BOA-architectuur en de verkregen kennis over preferentiemodellen toegepast bij de ontwikkeling van nieuwe onderhandelingsstrategieën. De BOA-architectuur wordt gedoceerd binnen academische instellingen. Tevens zijn er verschillende publicaties verschenen over de BOA-architectuur en preferentiemodellen. Ik heb met mijn werk inzicht gegeven in bestaande leertechnieken voor automatische onderhandelaars en de kwaliteit van deze modellen. Er zijn twee voor de hand liggende richtingen voor toekomstig werk. Ten eerste kan de kwaliteit van andere type leertechnieken, zoals modellen van de strategie van de tegenstander, worden bepaald. Ten tweede kan de analyse van de leertechnieken worden gebruikt om betere modellen te ontwikkelen die niet in accuraatheid afnemen naarmate de tijd vordert.
 
Mark Hendrikx is een van de twee winnaars van een tweede prijs tijdens de Informatie Scriptieprijs 2013. Op dit moment ontwikkelt hij voor Cost Engineering begrotingsprogrammatuur. E-mail: mark.hendrikx@home.nl
 
 
 
Een gedeelde tweede plaats voor Mark Hendrikx (rechts) tijdens de Informatie Scriptieprijs 2013
 
 
 

Tag

Onderwerp



Niet gevonden? Vraag het de redactie!

Heeft u het antwoord op uw vraag niet gevonden, of bent u op zoek naar specifieke informatie? Laat het ons weten! Dan zorgen we ervoor dat deze content zo snel mogelijk wordt toegevoegd, of persoonlijk aan u wordt geleverd!

Stel uw vraag