Eindrapport. 5 November 2007

Virtual Markets Ivo Hunink (3176932, [email protected]) Erik Gerrits(0458341, [email protected]) Institute of Information and Computer Science, University of Utrecht

0 Virtual Markets Eindrapport Ivo Hunink (3176932, [email protected]) Erik Gerrits(0458341, [email protected]) 5 November 2007

1. Introductie In dit document wordt de strategie beschreven die gebruikt wordt door de door ons ontwikkelde agent genaamd SlimAgent. Deze agent moet op een winstgevende manier klanten tevreden stellen met reispakketten die bestaan uit heenreizen, terugreizen, overnachtingen en tickets voor activiteiten. Al deze onderdelen hebben hun eigen prijs die kan stijgen of fluctueren naar verloop van tijd en de klanten hebben bepaalde voorkeuren waarvoor ze meer willen betalen. Er zijn in totaal acht agents die allemaal hun winst proberen te maximaliseren en er is een beperkte hoeveelheid hotels en entertainment beschikbaar, waardoor er concurrentie ontstaat. Wij beschrijven in dit document hoe onze agent met deze concurrentie omgaat.

2. Optimizer 2.1. Werking Om een goede allocatie te berekenen maakt onze agent gebruik van iterative improvement. Het iteratieve proces wordt iedere minuut uitgevoerd en bestaat uit de volgende stappen: 1. De eerste stap van het algoritme bestaat uit het randomizen van iedere client. Dit houdt in dat de allocatie van iedere client volledig willekeurig wordt ingesteld 2. Per willekeurig ingestelde client wordt een groot aantal keren een kleine wijziging aangebracht in de allocatie. Dit kan in vier verschillende gebieden gebeuren: de vluchtdagen, het type hotel, de verschillende typen entertainment en of de client al dan niet mee doet.

Page 1 of 7


3. Als deze gewijzigde client niet resulteert in een hogere profit, dan wordt de wijziging terug gedraaid. 4. Nadat de bovenstaande stappen een groot aantal keren zijn uitgevoerd, wordt het resultaat die de allerhoogste score oplevert als uiteindelijke allocatie gebruikt. Bij het berekenen van de profit per client houden wij rekening met reeds ingekochte goederen en dat er goederen kunnen zijn die niet meer beschikbaar zijn. 2.2. Voordelen van iterative improvement In plaats van gebruik te maken van iterative improvement zijn er andere mogelijkheden om een intelligente agent te bouwen. Hieronder staan twee andere manieren die wij in overweging hebben genomen: • •

Brute force algoritme. Dit heeft als groot voordeel dat alle mogelijkheden in beschouwing worden genomen, maar het grootste nadeel is dat dit niet mogelijk is binnen de gegeven tijd van één minuut. Ieder gedrag handmatig programmeren en hiermee proberen alle mogelijkheden te dekken. Hierbij is er een grote kans dat er mogelijkheden over het hoofd worden gezien en het is maar de vraag of dit beter tot betere resultaten zal leiden dan iterative improvement.

Onze client berekent binnen de gegeven tijd een semi-optimale allocatie. Dit heeft als voordeel dat nagenoeg alle mogelijkheden worden beschouwd terwijl de agent tegelijkertijd snel is. Ook kan de agent hierdoor bij onverwachte situaties flexibel reageren.

3. Bieding strategie 3.1. Vluchten 3.1.1. Manier van veilen Volgens de regels van de competitie zijn er een ongelimiteerde hoeveelheid vluchten voor iedere dag beschikbaar. Gemiddeld stijgen de prijzen van de vluchten licht. Volgens de documentatie van de competitie ligt de prijs altijd tussen de €150 en €800 en verandert deze iedere 10 seconden. De prijzen beginnen ergens tussen de €250 en €400.

Page 2 of 7


3.1.2. Onze strategie Zoals eerder beschreven strijgt de prijs gemiddeld. Om te bepalen hoe veel deze prijs stijgt hebben wij een klein onderzoek gedaan naar deze prijsstijging. In grafiek 1 wordt deze stijging voor één simulatie weergegeven.

Grafiek 1. Prijsverloop van verschillende in- en uitvluchten. In totaal hebben we 20 simulaties gedraaid en daaruit bleek dat de gemiddelde prijsstijging per vlucht €22,50 was. Dit betekent dat het verschil tussen het direct inkopen en het aan het eind inkopen van 16 tickets een verschil oplevert van ongeveer €360. Aan de hand van deze gegevens hebben wij ervoor gekozen, de vluchten helemaal aan het eind in te kopen. Dit omdat het inkopen van twee overbodige tickets al tot slechtere prestaties zal leiden en onze optimizer aan het begin te weinig informatie heeft om nauwkeurig te kunnen voorspellen welke vluchten nodig zijn, zonder maximaal één overbodige vlucht te kopen. In de laatste minuut wordt dus door onze optimizer bepaald welke vluchten er gekocht worden.

Page 3 of 7


3.2. Hotels 3.2.1. Manier van veilen Er zijn in totaal acht hotelveilingen: dure hotels voor vier dagen en goedkope hotels voor vier dagen. Op elke veiling worden zestien overnachtingen aangeboden met een startprijs van €0. De hotelkamers gaan naar de 16 hoogste bieders voor de prijs van de laagste van die 16 boden. Elke minuut sluit er één willekeurige hotelveiling precies op de minuut. Op dat tijdstip wordt ook de nieuwe vraagprijs van de hotelkamers bekend. De vraagprijs wordt dus maar één maal per minuut geüpdate. 3.2.2. Onze strategie In het begin hebben wij de startboden voor de hotels ingesteld op €75 voor goedkope hotels en op €125 voor dure hotels die we wilden hebben. Op het moment dat de vraagprijs veranderde, gingen wij meer bieden. Namelijk het verschil in de vorige en huidige vraagprijs maal 1,m. Hierbij is m het aantal verstreken minuten van het huidige het spel, zodat aan het eind van het spel, wanneer de mogelijkheden om ons flexibel op te stellen minder worden, harder wordt geprobeerd de hotels ook daadwerkelijk te krijgen. Bij het bieden op het allerlaatste hotel bieden we er nog eens €150 overheen aangezien we daarna geen enkel alternatief meer kunnen zoeken en aangezien dit geen effect meer heeft op toekomstige biedingen. Aan de hand van deze biedprijzen berekent de optimizer op welke hotels daadwerkelijk geboden wordt. Bij het selecteren van hotels houdt de optimizer ook in de eerste minuten rekening met de allocatie van vluchten en entertainment. Later hebben we nog een aantal zaken toegevoegd. Allereerst, dat de agent ook een klein bedrag biedt op een aantal niet gealloceerde hotels als backup. En als tweede hebben wij de startprijzen aangepast op basis van experimenten. Uit deze experimenten kwam logischerwijs naar voren dat hotels op de dagen 2 en 3 hoger gewaardeerd dienen te worden. Dit resulteerde in de prijzen getoond in tabel 1. Uit de experimenten blijkt dat wij met deze prijzen meer winst maken.

Dag Dag Dag Dag

1 2 3 4

Goedkoop hotel €50 €100 €100 €70

Duur hotel €85 €140 €135 €100

Tabel 1. Startprijzen van hotels

Page 4 of 7


3.3. Entertainment 3.3.1. Manier van veilen Er zijn in totaal twaalf entertainmentveilingen. Voor elke drie soorten entertainment worden er voor dag één tot vier tickets verkocht. Iedereen krijgt aan het begin twee maal vier tickets van twee verschillende veilingen en nog twee maal twee tickets van twee verschillende veilingen. Spelers kunnen tickets kopen van andere spelers en ze kunnen hun eigen tickets aanbieden. 3.3.2. Onze strategie Normaal gesproken kopen we de entertainment die de optimizer voor ons selecteert pas in de laatste minuut in, omdat we op die manier aan zo goedkoop mogelijke tickets komen voor onze clienten. Er is op die manier echter één probleem. Het kan namelijk zo zijn, dat we op die manier tickets mislopen die ons anders winst zouden opleveren. Dit probleem ontstaat wanneer andere spelers deze tickets eerder opkopen. Om dit probleem te vermijden kopen wij, ondanks dat dit niet moreel verantwoord is, de entertainment net voor de neuzen van onze geduchte tegenstanders weg. Dit gebeurt wanneer de tegenstanders bijna de vraagprijs bieden en het kopen van de entertainment ons winst oplevert. Nadat deze beslissing is gemaakt was er echter nog een dilemma: zou dit ons wel echt meer winst opleveren? Wat als er alsnog tickets over zouden zijn na het inkopen daarvan door onze tegenstander, zodat we ze uiteindelijk nog steeds goedkoop kunnen inkopen in de laatste minuut? Om te testen of dit probleem zich voordoet, hebben wij dit getest. We hebben twee agents, één met laatstgenoemde eigenschap en de andere zonder deze eigenschap, twintig games laten spelen tegen onze tegenstanders. Gemiddeld hadden we met het snel wegkopen van entertainment €50 per potje meer winst, dus hebben we besloten deze eigenschap te behouden. Het verkopen van de entertainment is eenvoudig. We beginnen met een startprijs van €135 en laten deze lineair afnemen totdat €50 bereikt is. Dit om om onze tegenstanders niet teveel winst te laten maken. Het startbedrag was eerst €200, maar we hebben deze verlaagd, omdat we op die manier veel meer tickets konden verkopen en daar ook in totaal meer winst mee konden maken.

4. Resultaten Onze agent deed het in de competitie vrij goed. In de eerste competitie maakten we net iets minder winst dan kokhoorn en hoornkok waardoor we op de tweede plek terecht kwamen. De tweede competitie draaide na de presentaties toen zijn

Page 5 of 7


wij eerste geworden. Dit kwam waarschijnlijk doordat de agents kokhoorn en hoornkok een aantal kleine wijzigingen hebben uitgevoerd. Verder was de standaarddeviatie van de winst die we per ronde hadden het laagst. Dit was een goede geplande eigenschap aangezien we zo weinig rondes draaiden in de competitie.

Grafiek 2. Uitslagen simulatie

5. Reflectie De reden dat onze standaarddeviatie zo laag was, was omdat we iterative improvement gebruiken. Dit algoritme is zeer flexibel en bedenkt de juiste oplossingen wanneer alles niet zo gaat als eerder gepland. Een andere reden is dat wij meeste zaken pas aan het eind kopen, zodat we weinig risico lopen eerst verkeerd inkopen te doen en zo flink verlies te maken. Dit alles in tegenstelling tot bijvoorbeeld onze tegenstanders smith en bond. Het door hen gekozen algoritme biedt zelfs zo hoog waardoor er voor bepaalde clienten wel een totaal pakket ontstaat maar geen winst. Hierdoor hebben deze agents ook een zeer hoge standaard deviatie. Onze score was goed omdat iterative improvement op zichzelf al zeer intelligente beslissingen neemt en omdat we de waarden, zoals beginwaarden van hotels en verkoop van tickets, goed ingesteld hebben door experimenten. Ook het moment

Page 6 of 7


van entertainment inkopen was juist: De kokhoorn, hoornkok, kampkant en kantman agents (voor de bond en smith agents is het onbekend) boden hun entertainment op het eind zeer goedkoop aan. Bovendien zorgde onze truc, om entertainment voor de neus van onze tegenstanders weg te kopen, ons extra winst op en voor hen wat minder. Door commentaar na de presentatie kwamen we erachter dat het niet zo slim was dat we zomaar álle vliegtickets in de laatste minuut inkochten en dat het beter zou zijn geweest onderzoek te doen naar hoeveel tickets voor bepaalde dagen onze optimizer sowieso vrijwel altijd inkoopt. Op die manier konden we een aantal tickets, waarvan we vrijwel zeker waren dat ze nodig waren, alvast in de eerste minuut inkopen om onze winst nog iets te laten stijgen. Tevens hadden we beter de lage prijs, waarmee we overnachtingen proberen te krijgen die we initieel niet nodig hebben, een randomwaarde tussen twee lage waarden kunnen laten aannemen. Dit omdat kokhoorn en hoornkok wel erg geniepig van onze waarde gebruik maakten en hier net heel iets overheen bieden, om zo eerder te hotels te krijgen dan onze agent. Ondanks dat we het niet helemaal perfect hebben gedaan, was onze agent toch zeer goed opgewassen tegen de agents van onze tegenstanders, wat te zien aan de resultaten van de competitie.

Page 7 of 7

Eindrapport. 5 November 2007

Recommend Documents