All week I have been trying to program Werepoker and giving up after the first 20 minutes or so. I think that’s partially because it’s needlessly tough networking and threading, and partially because I know there is a high probability that the program would never be used. Well, I want to play werepoker tonight at GameDev, so I want to implement something. I think I will implement the minimal computer assistant necessary for the game to function: the bidding.
The situation: a silent auction. Everyone puts in bids for the roles they want; i.e. how much they are willing to pay for a particular role. Then we assign roles according to the bids. But there are lots of little edge cases to worry about: what to do in case of a tie, what about when someone wins two roles, etc.? The metric we will use to decide these edge cases is fairly obvious, namely to maximize the total amount everyone pays (that’s what you want to do when you’re holding an auction).
Let’s formalize this. For each player p ε P, there is a bid function bp: R -> $, where R is the set of roles, and $ is the set of nonnegative amounts of money. We’re trying to find an assignment function a: P -> R that maximizes Σpbp(a(p)).
Thanks to Daniel Crumly for pointing me at the Hungarian algorithm to solve this problem.
Hmm, the Hungarian algorithm won’t work for this problem, because it needs to be predictable by players. If you bid higher than anyone else on something, it’s still possible that you won’t get your choice depending on other bids. I’m thinking I’ll use a simple heuristic greedy algorithm.
It goes like this. Sort all bids, highest first. Give the highest bidder his wish, and remove him from the candidates. If there is a tie for the highest bidder, choose the one with the lowest secondary bid (because he is likely to pay more for a different role), or tertiary in case of a tie for that, and so on. Of course, if the bids are identical then just choose randomly.