Werepoker bidding

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.

About these ads

4 thoughts on “Werepoker bidding

  1. So, I was looking at the perl module implementation and in the first normalization step, it subtracts the minimum value in each row by the rest of the elements in that row. Now, this is only important if you set up your array a particular way (as I did). If your players were the rows (and roles the columns) then this normalization procedure treats someone who bid 8 on everything the same as someone who bid zero on everything (which is very much not what you want!). That being said – you might check, it may very well explain the anomalies we saw last night.

    Have Fun

  2. Why is that very much not what I want? Yes, we would like to give the guy who bid 8 on everything his first choice in role, but he bid 8 on everything so he obviously has no first choice. Indeed, since each player must be assigned a role, it is always a stupid move if you don’t bid 0 at least once!

    I am still debating whether to use the Hungarian algorithm for bidding or whether to use my heuristic (or a similar heuristic). Both seem “right” in a sense. An auctioneer wishes to maximize his revenue, and that the highest bidder in an auction always gets what he wants is an consequence of the fact that there is no necessity for everyone at the auction to get an item; it is not, I believe, an essential property of an auction system.

    However, if a simpler heuristic is used (because, let’s face it, the Hungarian algorithm is not simple), you can extract more information from the bidding procedure, which may be construed as positive or negative. For example, say you bid 10 on werewolf, and you don’t get werewolf. You have limited the set of possible werewolves to coincide with the set of people who paid at least 10 for their role.

    It could be argued that although the Hungarian algorithm is complex, it is not beyond human comprehension, and so we are restricting that type of reasoning to those who can understand the algorithm rather than eliminating the reasoning altogether (which I would say is a point against the Hungarian algorithm).

  3. I think this is sort of getting at a potential issue with Werepoker. Werewolf is a game of hidden information. Werepoker is a game of eonomics and hidden information. Given that it is better to focus on the essential mechanic driving gameplay, and refine that as much as possible in order to achieve a pure and elegant game, I think the economics need to be emphasized and the hidden information de-emphasized. To this end, it makes sense to use the Heuristic bidding system, because it reduces the amount of hidden information while matching the player’s expectations. If my highest bid was the highest bid for that role, I should get that role. However, I think that the game needs some substantial evolution in order to work currency into more of the gameplay and roles. I think that adherence to what makes werewolf a good game (hidden information that is slowly revealed) will hinder werepoker from developing into the best game it can be. I don’t have any more concrete suggestions on how to change it yet. We should play it some more at next gamedev though, I think it has potential and is worth iterating on.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s