Trading Agent Competition Botfather
Auteurs:
Marinko Brands Costyn van Dongen Tebbo Herrewijnen Flip Mulder
Inleiding Tijdens het practicum voor het vak Virtuele Markten was het de bedoeling om een agent te maken die kon meedoen aan de Trading Agent Competition die wordt gehouden door de University of Michigan. In elk spel zijn er 8 agents, of bots, die elk 8 klanten hebben met verschillende wensen wat betreft een reis die zij willen maken binnen een periode van 5 dagen. De agents moeten zo goed mogelijk de wensen van de klanten proberen te vervullen door middel van veilingen de goederen aan te schaffen. De reis is naar Tampa, en dat gebeurt per vliegtuig. Er moet dus voor elke klant een heen en terugreis gekocht worden. Deze vluchten worden gekocht van de TAC_seller, een agent die vluchten en hotels verkoopt. Eenmaal in Tampa, moeten de klanten in een hotel verblijven. Er zijn 2 hotels, met elk 16 kamers. Het ene hotel, Tampa Towers, is beter dan het andere, Shoreline Shanties. Een klant verblijft dan ook liever in de Tampa Towers. De hotelkamers worden op de veiling gezet door de TAC_seller. Tijdens zijn of haar verblijf zal de klant ook hun tijd willen vullen met “alligator wrestling”, een bezoek aan het museum, of vermaak in het pretpark. Een klant kan maar één ding per dag doen. Op de dag dat de klant terug gaat, kan hij of zij geen amusement meer bijwonen. Een pakket amusements kaartjes worden in het begin van het spel aan iedere agent verschaft, die er voor kan kiezen om deze aan eigen klanten uit te delen of te veilen. De agent kan dan dus ook kaartjes van andere agents kopen. Voor volledige uitleg en regels van het spel, zie: http://auction2.eecs.umich.edu/game.html
Strategie LoserAgent Omdat het om meerdere artikelen gaat per klant, en dat de klant alleen utiliteit heeft aan bepaalde combinaties van artikelen, is het uiterst lastig om een duidelijke veiling strategie te bedenken. Een klant heeft alleen wat aan de vluchten als hij voor die periode ook een hotel kamer heeft. En andersom. We hebben zowel de Java client als de C++ client uitgeprobeerd. Uiteindelijk hebben we toch gekozen voor de Java versie, omdat deze consistentere uitkomsten had. Maar voor de volledigheid hier nog even over de C++ versie. Na wat uitproberen bleek het een goede strategie te zijn om heel hoog, dus agressief, op hotels en vluchten te bieden. $400 boven de huidige vlucht prijzen of $650 in de eerste 4 minuten, $750 in de volgende 4, en $900 in de laatste 4 minuten. Dan waren we er in ieder geval zeker van dat we de vluchten zouden krijgen en dat geen probleem zou zijn. Het zou misschien beter zijn om steeds te wachten op goedkope prijzen, maar dan is er weer kans dat je de vluchten misloopt. $200 boven de huidige hotel prijzen en alleen bieden op de Shoreline Shanties (door de sourcecode aan te passen). Dit omdat de extra utiliteit die een klant zou hebben vanwege de Tampa Towers maar weinig was in contrast met het verschil in prijzen. De Shoreline Shanties werden toch meestal voor $0 of $1 verkocht. Door hoog boven de vraagprijs te bieden waren we verzekerd van een kamer. Maar, deze strategie zou alleen werken als wij de enigen waren die deze strategie gebruikte. Als iedereen hoge prijzen zou gaan bieden, zou je al gauw ‘price wars’ krijgen met als gevolg dat de prijzen van de hotelkamers omhoog schieten. Voor de entertainment tickets was het lastig om een duidelijke strategie te bedenken. Hier was de C++ agent dan ook niet zo goed in, en hebben we door de parameters aan te passen geen verbetering in kunnen maken. Omdat de wensen van de klanten vaak wisselen en de uitkomsten bijna willekeurig waren, hebben we dus gekozen voor een agressieve strategie. Die bleek uiteindelijk toch betere uitkomsten te leveren. Deze wordt dan ook in het volgende stuk besproken.
Java Agent Er wordt in principe een vrij simpele strategie gehanteerd door onze agent, The_Botfather. Na het uitbrengen van de initiële boden wordt met bepaalde in te stellen intervals bekeken hoe de zaken ervoor staan. Indien nodig en mogelijk worden de boden aangepast, dan wel verhoogt. Het bieden zelf, maar vooral de strategie ervan, is onderverdeeld in drie delen en wel de volgende: 1. Flighthandler Zoals de naam al zegt zorgt de flighthandler voor het inkopen van de in- en uitvluchten voor de klanten. Door middel van aanpassing van het properties-bestand is te specificeren op welk ogenblik er begonnen moet worden met het bieden op de vluchten en wat de maximale prijs is die de agent er voor over heeft. Het is in deze agent zo dat alle vluchten op een enkel moment worden gekocht, wij hebben er voor gekozen om dat meteen in het begin te doen op het moment dat het spel begint. We hebben het zo ingesteld dat de agent vrij veel overheeft voor de vluchten, dit vanwege het feit dat de vluchten toch verkocht worden voor de door TAC-air gevraagde prijs. Oorspronkelijk was het zo dat er eerst gekeken werd of er voor de klant een complete overnachting verwacht werd en indien daar aan voldaan werd zou er pas op de betreffende vluchten geboden worden. Aangezien echter in het begin wat moeilijk te voorspellen is in hoeverre de hotels verdeeld worden is er hier voor gekozen om gewoon voor alle klanten vluchten te kopen, er van uit gaande dat de hotels ook wel binnen komen. Dit is op zich wel een wat riskante aanpak aangezien het zou kunnen dat je vluchten koopt voor klanten waar je geen hotel voor kunt krijgen. Maar het is wat ons betreft beter wat risico te nemen en zo te zorgen dat je in ieder geval de vluchten krijgt zodat je daar niet achteraf mee achter het net vist. 2. Hotelhandler De hotelhandler zorgt voor de aankoop van de hotels voor de klanten. Opnieuw wordt de strategie voor een groot deel mede bepaald door de instellingen zoals die zijn gedaan in het properties-bestand. Er zijn twee soorten hotels te krijgen, namelijk de Shoreline Shanties en de Tampa Towers. De klant heeft in principe een voorkeur voor de Tampa Towers die wordt uitgedrukt door een bepaalde utiliteit variërend tussen de 0 en 150. Het zou dus mooi zijn om kamers in de Tampa Towers te krijgen aangezien dit een bonus oplevert. Het is echter de vraag hoe ver je daar voor wilt gaan. Het is natuurlijk zinloos om honderden punten voor de Tampa Towers te betalen indien je daar maar 50 punten voor terugkrijgt. Het bieden op de hotels gebeurt enigszins verschillend, voor de Shoreline Shanties geldt een hard gecodeerd basisbod die in te stellen is in het propertiesbestand. Het basisbod voor de Tampa Towers ligt iets gevoeliger, namelijk als volgt. In de properties is in te stellen in hoeverre je de Tampa Towers boven de Shoreline Shanties verkiest. Ook kun je instellen hoeveel boven de verwachte utiliteit je bereid bent op de Tampa Towers te bieden. Dat zijn twee zaken die mede bepalen wat het bod zal zijn dat wordt gedaan. Verder heeft ook het aantal dagen dat de klant wil blijven invloed op het bod. Het uiteindelijke initiële bod wordt als volgt geconstrueerd: Initieel bod = HP / ndays + TowersPremium. Hier is HP de utiliteit van de klant voor het hotel. ndays is het aantal dagen dat de klant blijft. Towerspremium is de waarde hoeveel je boven je verwachte
utiliteit biedt op de Tampa Towers. Vervolgens bekijkt de agent bij iedere iteratie, hier dus om de zoveel seconden, hoe de situatie is. Zo worden de huidige prijzen opgevraagd, gekeken of de gedane boden voldoende zijn en indien dat niet het geval is worden de boden verhoogd. Tenminste, indien de prijzen nog niet boven de maximale in de properties toegestane prijzen zijn uitgekomen. We hebben ook hier gekozen om vrij stevig op hotels te bieden en daarbij ook de Shoreline Shanties absoluut niet te negeren. Onder het motto “Beter te veel hotels dan te weinig” denken we dat het beter is voor de zekerheid ook een aantal Shoreline Shanties kamers te kopen aangezien deze vaak toch niet veel kosten en het risico om vooral op de Tampa Towers te gokken toch wat hoog is. Daar komt dan ook bij dat de opgebrachte utiliteit niet dermate hoog is, namelijk maximaal 150, dat we alles op alles willen spelen om die kamers te bemachtigen. Vandaar dat we ook al van het begin af aan hoog op de Shoreline Shanties bieden. De boden kunnen dus ook verhoogd worden. Hiertoe wordt eerst bekeken welke verhoging, die voor de Tampa Towers of die voor de Shoreline Shanties, het laagst is. Dit wordt berekend aan de hand van huidige vraagprijzen, de utiliteit van de klant en de voorkeur die wij hebben voor de Tampa Towers. Voor de Shoreline Shanties is het bedrag een constante gespecificeerd in het properties bestand. Vervolgens wordt voor de goedkoopste oplossing gekozen. Door toch mee te bieden op de Tampa Towers kunnen de prijzen wel opgevoerd worden en dat kan dus een nadelig effect hebben voor de tegenstander. Verder is het wel de moeite waard om een Tampa Towers kamer te bemachtigen voor een klant die slechts een of twee nachten blijft. Om die reden bieden we ook zeker enigszins serieus mee op de Tampa Towers maar deze hebben in ieder geval geen enorme prioriteit. 3. Entertainmenthandler De entertainmenthandler moet zorgen dat de entertainment tickets van de klanten goed verdeeld worden. De klanten willen namelijk graag een aantal dingen doen tijdens hun verblijf. Zo is er de keuze tussen het zogenaamde: “Alligator Wrestling”, “Amusement Park” en “Museum”. De klanten kunnen maar een ding per dag doen en verder hebben ze voorkeuren, uitgedrukt in een utiliteit, voor bepaalde evenementen. Iedere agent krijgt in het begin een aantal tickets en in tegenstelling tot vluchten en hotels mogen agents ook zelf in tickets handelen. Opnieuw zijn er een aantal variabelen in te stellen in het al eerder genoemde properties bestand. Op deze manier is in te stellen op welk moment begonnen moet worden met het handelen in tickets. Wij hebber er voor gekozen om dit vanaf het begin te doen, er vanuit gaande dat we alle klanten tevreden kunnen stellen geeft dit ons dan ook meer tijd om dat daadwerkelijk te doen. Verder is ook de te vragen prijs voor overbodige tickets in te stellen. Aan de ene kant wil je deze natuurlijk verkopen om er zo in ieder geval aan te verdienen, er moet echter rekening mee gehouden worden dat de andere agents door het aankopen van een dergelijk ticket meer kunnen verdienen dan jij met de verkoop. Het is dus de bedoeling de tickets niet te goedkoop weg te doen, om zo te veel winst bij de tegenstander te voorkomen, maar ook niet te duur aangezien je ze dan niet kwijtraakt. We hebben er voor gekozen toch een redelijk gemiddelde prijs te hanteren, op deze manier kan het niet beide kanten opslaan. Een ander iets is de prijs waarvoor gebruikte tickets weg worden gedaan. Deze tickets leveren iets op in de vorm van de utiliteit die de klant er aan toekent maar indien je ze voor meer kunt verkopen is
dat natuurlijk eerder aan te raden. Op zich kunnen hier dezelfde nadelen aan zitten als bij het verkopen van de ongebruikte tickets met als enige verschil dat de prijzen hier automatisch wat hoger liggen. Er kan namelijk gezegd worden hoeveel boven de verwachte utiliteit ze op moeten brengen. Het laatste punt is de prijs die geboden wordt voor gewenste tickets. In ons geval is er voor gekozen om iets (ongeveer 20) onder de verwachte utiliteit te bieden voor het ticket. Dit omdat de tegenstander waarschijnlijk ook niet zo gek zal zijn om de tickets te goedkoop weg te doen en wij op deze manier toch wat extra puntjes kunnen halen. Dit alles gebeurt op een moment in het spel, bij ons dus meteen in het begin. Op deze manier worden alle boden in elkaar gezet en getracht alle benodigde goederen te verkrijgen.
Implementatie We hebben uiteindelijk gekozen om de Java code gebruikt van TAClib: http://ludde.net/taclib om onze agent te maken. We hebben de sourcecode en parameters aangepast om wat wij dachten dat een goede agent zou zijn. Aangezien wij ons aardig in de strategie konden vinden hebben we geen al te grote veranderingen doorgevoerd. Hier en daar zijn er toch wat zaken veranderd. Ten eerste is de agent aangepast om meerdere games te kunnen spelen, het aantal te spelen games en de game_id’s moeten worden gespecificeerd in de code waarna de bot een voor een alle games afloopt. Verder hebben we ook de code zo aangepast dat we altijd alle 8 de in- en uitvluchten proberen te krijgen. Oorspronkelijk was het zo dat alleen voor de klanten waarvan gedacht werd de hotels ook te kunnen krijgen de vluchten gekocht werden. Uit de informatie op de tac pagina blijkt dat er een oneindig aantal vluchten zou zijn en in dat geval zou het niet uit moeten maken wanneer een vlucht gekocht wordt. In de praktijk bleek echter dat wanneer er later op de vluchten geboden werd dit tot resultaat had dat niet alle vluchten verkregen werden. Om die reden hebben we de code dus aangepast. We hebben ook nog met de C++ agent gewerkt. Deze agent hadden we eerst aan de praat, na wat geklooi met libxml libraries, api’s en bidderclasses. Deze agent hebben we in eerste instantie met meerdere kopieën laten draaien, om zo snel iets te kunnen vinden.
Analyse Tijdens oefen spelletjes op de TAC server hebben wij onze agent getest en tegen andere agents laten spelen. In het begin was het een beetje natte vinger werk, alleen de parameters veranderen en kijken wat er tijdens een spel gebeurde. Omdat de klanten steeds andere wensen hadden, was het noodzakelijk om meerdere spellen met dezelfde parameters te doen, om niet helemaal te vertrouwen op het resultaat van één spel. We draaiden soms meerdere agents tegelijk, om zo parallel te kunnen zoeken in de parameter ruimte. Zoals gezegd kon de LoserAgent zeer goed uit de hoek komen, maar de resultaten waren wel erg wisselvallig. De Java agent deed het in dat opzicht toch beter, deze had een redelijk constant prestatieniveau. Het was wel opvallend te zien dat, vooral in het begin, de door de tacserver ingezette dummy_buyers regelmatig boven onze agents uitkwamen en ook wonnen. Naarmate de spelen vorderden en alle in te stellen variabelen duidelijker werden kon toch opgemerkt worden dat deze dummy_buyers meer en meer het onderspit moesten delven.
Conclusie Uiteindelijk was het allemaal lastiger dan we hadden verwacht, in plaats van echt een duidelijke strategie te bedenken en veel zelf te programmeren kwam het vooral neer op het veranderen van parameters en doorvoeren van veelal kleine veranderingen in de code zelf. Wat ook niet hielp was het feit dat er steeds 20 minuten tussen de games zat, hierdoor zat je toch een hoop tijd te wachten en te niksen voordat de resultaten van de veranderingen bekend waren. Hierbij kwam dan ook nog eens dat een spel natuurlijk niet voldoende is om conclusies aan te verbinden, daar zijn al snel twee of drie spellen nodig en dan is er dus alweer een uur voorbij. Op die manier duurde het dus vrij lang om echt door te krijgen wat slimme tactieken waren, en wat het precieze effect van een verandering zou zijn. Verder was de gebruikte tactiek al vrij goed in overeenstemming met wat wij zelf hadden bedacht. Al met al is de gebruikte tactiek vrij eenvoudig doch effectief.
