Agent-based Systems
Paolo Turrini
www.dcs.warwick.ac.uk/~pturrini R p.turrini@warwick.ac.uk
CW Strategy Design: a few points
Paolo Turrini Coursework Agent-based Systems 2 / 12
The plan
This lecture is meant to give you some high-level advice and a few concrete examples.
I’m going to describe the coursework problem structure in such a way that it can be used in relation to what you have learnt so far.
I will then present two scenarios in which this is very clear. I will talk about how to improve the strategy you submit.
Paolo Turrini Coursework Agent-based Systems 3 / 12
Basic principles
Each of the auction games is a finite extensive game with simultaneous moves.
At each round, the game you play is a one-shot game, against the other participants.
At each round, each game you play DEPENDS on the games played before.
Who has won which items
How much money everyone has Etc.
Paolo Turrini Coursework Agent-based Systems 4 / 12
Knowledge
You know: auction type
the items sold and to whom and for how much the budget left to everyone
the amount of items available
the order in which the items will appear next.
You know a lot more in fact, and you can estimate the rest.
Paolo Turrini Coursework Agent-based Systems 5 / 12
Theory
Lots and lots of useful results in game theory Use them!
We haven’t covered everything Do your own research!
Theory is the key, but you need to work on adapting it to your specific problem.
How important is item for a certain player, at a certain round?
The bids you make are not independent from the budget you have, obviously. Neither are they independent from what others have.
R.P. McAfee and J. McMillan.
Auctions and Bidding.
Journal of Economic Literature, 25(2):699–738, 1987.
Paolo Turrini Coursework Agent-based Systems 6 / 12
The key principle
You want to submit a strategy that maximises your expected utility
You know what utility means: in win-lose games
in games with fixed points per item
you know money does not matter in the end
You know what maximises means.
The coursework is about the word ”expected”
USE WHAT YOU KNOW, ESTIMATE WHAT YOU DO NOT
Paolo Turrini Coursework Agent-based Systems 7 / 12
Solving the game
You can in theory solve the game by brute force. Except there are kn possible choices at the first round, where k is the set of possible bids and n the number of bidders, and the game can go on for 200 rounds.
However, there are important considerations:
In certain situations it is very clear what to do.
In certain situations it is very clear what to do given that at the next stage it is very clear what to do.
etc…
Paolo Turrini Coursework Agent-based Systems 8 / 12
Engames (i)
Suppose you are playing the [3,2,1] game and everyone has: {2vG,2P,1R,1DV}. Your budget is 200, all your opponents have 199.
A van Gogh is auctioned.
You have 199 bad moves, no matter the auction type.
Paolo Turrini Coursework Agent-based Systems 9 / 12
Engames (ii)
Ann has 2vG and 2P, 1R and her budget is 10.
You are one of Ann’s opponents. None of you has anything, but the budget is 50 each. A van Gogh is auctioned.
This is one of the most interesting scenarios in the game.
Do you top Ann’s potential all-in? Or do you hope others will?
If everybody free rides and Ann is in the right mind, then she wins.
It’s important to recall that ties are broken randomly. Depending on your situation you might want to take the risk to free ride, or not. You need to estimate that. It goes without saying that the attitude to risk needs to take into account the other participants, if any.
Paolo Turrini Coursework Agent-based Systems 10 / 12
Waiting moves
Waiting will make you gain lots of precious knowledge, for instance the fact that someone else is going to win next.
Different games warrant different levels of patience.
It seems to me (but I might be wrong) that the [3,2,1] game rewards aggressive play, the other game patience. Find out.
Paolo Turrini Coursework Agent-based Systems 11 / 12
Testing
Test your strategy against other strategies.
But do not make the mistake of optimising against one strategy, cause you want to play well against ALL strategies thrown at you.
Please do read the spec carefully and adhere to plagiarism related regulations. I will be very strict. The coursework is your own work, full stop.
Paolo Turrini Coursework Agent-based Systems 12 / 12