Dominion Strategy Forum
Miscellaneous => Forum Games => Topic started by: QuickSync on July 27, 2015, 11:52:16 pm
-
@UmbrageOfSnow had mentioned the Nash Equilibrium when talking about predicting how people would behave regarding his off-shoot of @mail-mi's Greater idea game. My question is it possible to use zero sum games as a vehicle to use in a game of mafia and the implications that that would have. I believe this is totally a topic worth talking about since mafia is largely a game that requires knowing what, how and why people do. I don't actually understand the theory myself since I am not learned enough in math to understand the concepts that Nash talked about in how people decide what do do, but it is definitely a curiosity to me and know if/how it can be used in mafia is something I have tried having a conversation with people about before.
Thoughts?
-
It depends how formal and mathy you want to get, but "solving" any reasonable game of mafia is extremely difficult. If you let players take turns voting, with a fixed endpoint (I'm not really sure how else to simulate voting, since forum mafia is time-based), you can solve 2 VT's vs. 1 Goon pretty easily. Anything bigger than that gets nuts really fast. I tried to solve 3 VT's vs. 2 Goons but there's just way too much going on.
Anyway, that doesn't mean it can't be helpful to think about game theory in mafia. In fact, to me it's the main thing that I like about mafia (except for those rare times that I get a really strong read on someone, which is fun until they flip and I find out how wrong I was). Knowing that there is a Nash equilibrium is cool, because it means there has to be some optimal strategy like "Bus x% of the time" (which, by the way, I think is way less than what people do). But it would be very difficult to actually calculate it, which means you just have to rely on your gut, which is what makes it a hard (and good) game. When you throw in roles, everything gets even messier very quickly.
I actually tried to use game theory to help me design the Yoshi's Island set-up. I knew I couldn't solve it, but I thought maybe I could assign rough values to things and use that to help determine town's best strategy. It didn't end up being very helpful though, because I still couldn't solve anything.
-
Ah, Ok. Yeah I had one person tell me it couldn't be done and another who took a whole course on game theory say they don't use it when they play mafia, but it can be done. They were both actually BF and GF as weird as that is.
But if you could tell me the basic principle behind game theory and its applications, maybe just knowing more what its about could help me think a little bit differently on how to approach the game.
I take it there are some very bright people on this site if the theory was mentioned when coming up with a game to test run a setup. I'm starting to feel like my play wouldn't be too good around here. Oh, well. Still would like to play a few games here though.
-
Ah, Ok. Yeah I had one person tell me it couldn't be done and another who took a whole course on game theory say they don't use it when they play mafia, but it can be done. They were both actually BF and GF as weird as that is.
But if you could tell me the basic principle behind game theory and its applications, maybe just knowing more what its about could help me think a little bit differently on how to approach the game.
I take it there are some very bright people on this site if the theory was mentioned when coming up with a game to test run a setup. I'm starting to feel like my play wouldn't be too good around here. Oh, well. Still would like to play a few games here though.
there are some really smart people here i think. but don't worry there are also people like me who just kinda do things on a whim.
-
But if you could tell me the basic principle behind game theory and its applications, maybe just knowing more what its about could help me think a little bit differently on how to approach the game.
Here's the thing: Let's assume a game of Rock/Paper/Scissors. If I win, I get a value of 1. If I lose, I get -1, and in case of a draw 0. Since it's a zero-sum game, my opponent has the same values. We can write a table with all possible outcomes as follows:
R P S
R 0 -1 1
P 1 0 -1
S -1 1 0
Each player has three "strategies": Rock, Paper or Scissors. They can choose any of these strategies. But they might also do some randomization, say with 60% probability I choose Rock, with 10% I choose Paper, and otherwise I choose Scissors. This can be represented by a vector x=(x1,x2,x3) where the entries are the probabilities for each strategy. They have to add up to one. Player 2 can do the same thing, choosing a strategy y=(y1,y2,y3). We can then determine the expected outcome of the game as follows (now some knowledge about vector/matrix calculation is needed):
Let A be the matrix above, i.e. A=(0,-1,1; 1,0,-1; -1,1,0). Then the outcome is determined by the formula xAy^T.
As Player 1, I try to find a vector x such that the outcome xAy^T is as big as possible, i.e. no matter what strategy y my opponent chooses, I want the best thing possible for me. A always assume my opponent will play the perfect strategy against me, i.e. the strategy that minimizes the expected outcome. For a given strategy x, my expected outcome will then be the minimum over all y of xAy^T. This is what I want to get a big as possible. So the formula that maximizes my chances of winning is something likes this:
max(over all x) (min(over all y) (xAy^T))
Doing the calculations, it's relatively easy to see that for Rock/Paper/Scissors, all strategies are equally good.
-
Doing the calculations, it's relatively easy to see that for Rock/Paper/Scissors, all strategies are equally good.
Huh? Clearly throwing rock all the time is worse than throwing each with equal probability, because it is countered perfectly by throwing paper all the time. Unless there is something I am not understanding?
-
Doing the calculations, it's relatively easy to see that for Rock/Paper/Scissors, all strategies are equally good.
Huh? Clearly throwing rock all the time is worse than throwing each with equal probability, because it is countered perfectly by throwing paper all the time. Unless there is something I am not understanding?
There are different types of equilibria. I don't know too much about it, but both players playing randomly is the 'strongest' equilibrium. However, if you know that your opponent will play randomly, it doesn't matter how you play, so all those are equilibria too, even though your opponent could improve his play by deviating.
I've been trying to use game theory in mafia ever since D7 of DS9. I don't have any staggering results, and applying it to large initial setups is computationally not-fun. I did do some stuff a while back to determine who I should kill in a multiball game (fire and ice), since there were a few funky rules there but only one town role, who was known.
Here's a nice puzzle:
3 players are alive during the day: A vanilla townsperson, a Mafia goon, and a Serial Killer. All three know the alignments of the others. Voting is as normal; players can place votes at any time, and two votes is sufficient for a lynch. Let's say all the players are online, all the time. Better yet, IRL. If an hour goes by without a lynch, the day ends and night starts. In the night, the mafia goon and the serial killer have the opportunity to kill somebody.
If the Mafia and the Serial Killer die, the townsperson wins. If one of the mafia/serial killer die, the other wins. If just the townsperson dies, the mafia and serial killer tie, which is halfway between winning and losing. If the mafia or SK must lose, they would very slightly rather the town win.
What happens? Note that this is not a zero-sum game, but that doesn't really matter. Assume a win is worth 1, a loss 0, and a tie 1/2. Say that the Mafia/SK get .01 from the town winning. Here's a variant that I haven't solved yet. Say that instead the Mafia/SK get x from the other bad guy winning, where 0 < x < 1/2. Now what happens, in terms of x? This came from D7 of DS9, where I was the townsperson in this scenario. However, I thought just one of them was a bad guy, so that didn't work out so well.
Here's a different puzzle, more commonly applicable to mafia games.
3 players are alive during the day; two townspeople, and a mafia. Neither townsperson has any clue who the mafia is. Town wins if they lynch the mafia, mafia wins if they lynch a townsperson or no lynch happens. Say that the game is IRL again, and that if nobody votes for an entire hour, no lynch happens. It takes two votes for a lynch. What are the optimal strategies and expected payoffs for each player? Note that this is a zero-sum game, if we assume that the town is one player.
And here's a puzzle I posted in the maths thread, already solved there but you can try it too! Not related to mafia, but rock-paper-scissors!
We're playing a game of Rock, Paper, Scissors, with a twist; I am never allowed to throw paper. If we both throw the same thing, we throw again. If we throw different things, the winner gets +1, the loser -1, and the game ends. If we both throw the same thing n times, for some whole number n which is fixed ahead of time, the game ends and I get +1, you -1. Only the last throw of the game matters.
What is the optimal strategy for each player and what is your expected payoff for this game, in terms of n?
-
I'd like to point out that I was talking about the power-voting sub-game for "Charge Me Up" rather than the actual game of mafia. As has already been pointed out, mafia is just too complicated, and I'm not sure how much it would get you even if you were a super computer. Sometimes there is a breaking strategy, but those are usually found through chess-like calculation. EDIT: Okay, Lio has some nice examples.
One concept that comes from Game Theory that does apply in Mafia is that often the best strategy involves some amount of randomness: rather than picking X each time, often the best strategy is to pick X 60% of the time and Y 40% of the time or whatever based on what you think your opponent's best strategy, and best strategy to counter your best strategy, etc. are. That's just for Night Kill or Power Role targets though, like who to kill at night if there's a doctor, or who to protect if you're a doctor or whether or not to use your bulletproof shot tonight. It's especially good if you want to claim what you are doing. I don't think I've ever actually done math to something like that, but I've pulled good-looking numbers out of my ass before. Approximating a game theory answer by random guessing is still pretty good, and much easier I think.
--------
Lengthy Ramble about Charge Me Up
With the voting in Charge Me Up, I also wasn't doing any real math, as I said there. I just mentioned Nash Equilibrium hoping to clarify why I had the scumteams picking evenly among the top 2/3s of the fictional players, rather than limiting themselves to the top few as people seem to think is intuitive (i.e. town then counters this by never voting for the top few players.) So my guess (again I haven't done any math, nor do I intend to do so) was that something like an even distribution among the top 2/3s was where the equilibrium (the strategy that emerges when both players have considered the best strategy of the other player and changing strategies to account for the other player's current best strategy no longer brings any improvement, which is Nash's idea) would be around there for the simplified model I was using.
Keep in mind that we don't really know how much impact making Faust or Ash the best PRs has vs. making Lurky McLurkerson or Sir Quixote, Lord of the Village Idiots the best Prs. I think we can all safely assume there is an impact, but good luck putting a number on it. So we can't really tell how much Town should care.
I don't actually think that distribution is correct even for that simplification, but I think it's close enough to get an idea of balance. And as I said in that thread, an ordering of the player list from best to worst would probably be better, but that's also a lot more work for me to come up with a reasonable way for "players" to vote. That whole thing really comes down to the fact that I'm just looking for an approximation to look at balance, not actually playing the game. And the game there (the power voting) is a lot simpler than Mafia, and someone could probably try to find the optimal solution using game theory. I don't care to.
(Another reason why it's pointless to try for any more precision in the examples I was running: Playerlists will vary, including how the players will be distributed. And good luck trying to get the entire list to agree on the ranking, I'm not sure who I think is stronger among e and Silverspawn, for example. And even if I decided, good luck getting 15 random people to agree. And it's not like all players will vote rationally either, someone would probably take the worst strategy just to be contrary. The point is just to get reasonable setups, not accurately predict everything. But I've wandered way too far off topic. Shutting up now.)
-
If just the townsperson dies, the mafia and serial killer tie,
how can this happen, wouldn't the game just continue?
-
If just the townsperson dies, the mafia and serial killer tie,
how can this happen, wouldn't the game just continue?
They then both kill each other and town wins!!
-
If just the townsperson dies, the mafia and serial killer tie,
how can this happen, wouldn't the game just continue?
They then both kill each other and town wins!!
If the townsperson dies, then the only people left alive are the serial killer and mafia goon. If you like, we can let the game continue and then they kill each other at night and nobody wins, and it doesn't really change the problem.
-
If just the townsperson dies, the mafia and serial killer tie,
how can this happen, wouldn't the game just continue?
They then both kill each other and town wins!!
If the townsperson dies, then the only people left alive are the serial killer and mafia goon. If you like, we can let the game continue and then they kill each other at night and nobody wins, and it doesn't really change the problem.
that is what I would like, thank you
-
If just the townsperson dies, the mafia and serial killer tie,
how can this happen, wouldn't the game just continue?
They then both kill each other and town wins!!
If the townsperson dies, then the only people left alive are the serial killer and mafia goon. If you like, we can let the game continue and then they kill each other at night and nobody wins, and it doesn't really change the problem.
that is what I would like, thank you
so to be clear there is no possibility of a tie?
-
Sure! If town is lynched or only town is killed at night, we will say that everyone loses. This makes the problem easier to solve, but does not actually change the answer. The result is exactly the same if we say that it's a tie, it's just harder to show.
-
Sure! If town is lynched or only town is killed at night, we will say that everyone loses. This makes the problem easier to solve, but does not actually change the answer. The result is exactly the same if we say that it's a tie, it's just harder to show.
I would say the result is quite different. if town dying results in a loss, then scum will just no lynch and shoot each other at night, giving town the win, which for some reason they each prefer to nobody winning.
If town dying results in a tie, then scum will lynch town for the tie.I'm not an expert on any of this, so it's entirely possible I'm misunderstanding all this and making it much simpler than it really is.
-
If town dying results in a tie, then scum will lynch town for the tie.I'm not an expert on any of this, so it's entirely possible I'm misunderstanding all this and making it much simpler than it really is.
Your first part is correct. However, the scum won't be able to lynch the town for the tie. Say you're the townie. How do you prevent that?
-
If town dying results in a tie, then scum will lynch town for the tie.I'm not an expert on any of this, so it's entirely possible I'm misunderstanding all this and making it much simpler than it really is.
Your first part is correct. However, the scum won't be able to lynch the town for the tie. Say you're the townie. How do you prevent that?
well my only power is my vote. I could vote for one of them, but the other one would shoot me at night, so I don't come out ahead. so I don't know.
-
Well you just say that you will vote for the first person who votes for you. If someone votes for you, you will lose anyway, so why not vote for them? Then the other bad guy will take a win over a tie and will lynch the other bad guy. Then neither bad guy will be the first to vote for you because they would lose, so they don't.
Maybe we need to add a clause that the townsperson would slightly prefer one of the factions to win (doesn't matter which) than a tie.
-
Well you just say that you will vote for the first person who votes for you. If someone votes for you, you will lose anyway, so why not vote for them? Then the other bad guy will take a win over a tie and will lynch the other bad guy. Then neither bad guy will be the first to vote for you because they would lose, so they don't.
Maybe we need to add a clause that the townsperson would slightly prefer one of the factions to win (doesn't matter which) than a tie.
ah. Should've seen that
-
Well you just say that you will vote for the first person who votes for you. If someone votes for you, you will lose anyway, so why not vote for them? Then the other bad guy will take a win over a tie and will lynch the other bad guy. Then neither bad guy will be the first to vote for you because they would lose, so they don't.
Maybe we need to add a clause that the townsperson would slightly prefer one of the factions to win (doesn't matter which) than a tie.
This is why I think you need to define a turn order if you want to analyze voting situations with game theory. What if the second bad guy can vote faster than town? Then the townie's threat doesn't matter.
-
Well you just say that you will vote for the first person who votes for you. If someone votes for you, you will lose anyway, so why not vote for them? Then the other bad guy will take a win over a tie and will lynch the other bad guy. Then neither bad guy will be the first to vote for you because they would lose, so they don't.
Maybe we need to add a clause that the townsperson would slightly prefer one of the factions to win (doesn't matter which) than a tie.
This is why I think you need to define a turn order if you want to analyze voting situations with game theory. What if the second bad guy can vote faster than town? Then the townie's threat doesn't matter.
Well if I were the second guy, I'd rather vote for the other bad guy, so I'll wait for the town to vote.
-
Well you just say that you will vote for the first person who votes for you. If someone votes for you, you will lose anyway, so why not vote for them? Then the other bad guy will take a win over a tie and will lynch the other bad guy. Then neither bad guy will be the first to vote for you because they would lose, so they don't.
Maybe we need to add a clause that the townsperson would slightly prefer one of the factions to win (doesn't matter which) than a tie.
This is why I think you need to define a turn order if you want to analyze voting situations with game theory. What if the second bad guy can vote faster than town? Then the townie's threat doesn't matter.
Well if I were the second guy, I'd rather vote for the other bad guy, so I'll wait for the town to vote.
what if the day will end b4 town can vote?
-
I'd like to point out that I was talking about the power-voting sub-game for "Charge Me Up" rather than the actual game of mafia. As has already been pointed out, mafia is just too complicated, and I'm not sure how much it would get you even if you were a super computer. Sometimes there is a breaking strategy, but those are usually found through chess-like calculation. EDIT: Okay, Lio has some nice examples.
One concept that comes from Game Theory that does apply in Mafia is that often the best strategy involves some amount of randomness: rather than picking X each time, often the best strategy is to pick X 60% of the time and Y 40% of the time or whatever based on what you think your opponent's best strategy, and best strategy to counter your best strategy, etc. are. That's just for Night Kill or Power Role targets though, like who to kill at night if there's a doctor, or who to protect if you're a doctor or whether or not to use your bulletproof shot tonight. It's especially good if you want to claim what you are doing. I don't think I've ever actually done math to something like that, but I've pulled good-looking numbers out of my ass before. Approximating a game theory answer by random guessing is still pretty good, and much easier I think.
--------
Lengthy Ramble about Charge Me Up
With the voting in Charge Me Up, I also wasn't doing any real math, as I said there. I just mentioned Nash Equilibrium hoping to clarify why I had the scumteams picking evenly among the top 2/3s of the fictional players, rather than limiting themselves to the top few as people seem to think is intuitive (i.e. town then counters this by never voting for the top few players.) So my guess (again I haven't done any math, nor do I intend to do so) was that something like an even distribution among the top 2/3s was where the equilibrium (the strategy that emerges when both players have considered the best strategy of the other player and changing strategies to account for the other player's current best strategy no longer brings any improvement, which is Nash's idea) would be around there for the simplified model I was using.
Keep in mind that we don't really know how much impact making Faust or Ash the best PRs has vs. making Lurky McLurkerson or Sir Quixote, Lord of the Village Idiots the best Prs. I think we can all safely assume there is an impact, but good luck putting a number on it. So we can't really tell how much Town should care.
I don't actually think that distribution is correct even for that simplification, but I think it's close enough to get an idea of balance. And as I said in that thread, an ordering of the player list from best to worst would probably be better, but that's also a lot more work for me to come up with a reasonable way for "players" to vote. That whole thing really comes down to the fact that I'm just looking for an approximation to look at balance, not actually playing the game. And the game there (the power voting) is a lot simpler than Mafia, and someone could probably try to find the optimal solution using game theory. I don't care to.
(Another reason why it's pointless to try for any more precision in the examples I was running: Playerlists will vary, including how the players will be distributed. And good luck trying to get the entire list to agree on the ranking, I'm not sure who I think is stronger among e and Silverspawn, for example. And even if I decided, good luck getting 15 random people to agree. And it's not like all players will vote rationally either, someone would probably take the worst strategy just to be contrary. The point is just to get reasonable setups, not accurately predict everything. But I've wandered way too far off topic. Shutting up now.)
I am sorry if I made it seem like I implied that you were saying you could use game theory to solve a game, that was not my intention. I simply noticed that you had mentioned the theory and I got curious what the practical application of that theory might be in a game of mafia.
-
Well you just say that you will vote for the first person who votes for you. If someone votes for you, you will lose anyway, so why not vote for them? Then the other bad guy will take a win over a tie and will lynch the other bad guy. Then neither bad guy will be the first to vote for you because they would lose, so they don't.
Maybe we need to add a clause that the townsperson would slightly prefer one of the factions to win (doesn't matter which) than a tie.
This is why I think you need to define a turn order if you want to analyze voting situations with game theory. What if the second bad guy can vote faster than town? Then the townie's threat doesn't matter.
Well if I were the second guy, I'd rather vote for the other bad guy, so I'll wait for the town to vote.
what if the day will end b4 town can vote?
I assumed that all players are online or IRL, and that they have an hour to lynch. But sure, there are scenarios where that would be a factor.
The interesting part is at night. Why do they always shoot each other instead of the townsperson or nobody?
-
Well you just say that you will vote for the first person who votes for you. If someone votes for you, you will lose anyway, so why not vote for them? Then the other bad guy will take a win over a tie and will lynch the other bad guy. Then neither bad guy will be the first to vote for you because they would lose, so they don't.
Maybe we need to add a clause that the townsperson would slightly prefer one of the factions to win (doesn't matter which) than a tie.
This is why I think you need to define a turn order if you want to analyze voting situations with game theory. What if the second bad guy can vote faster than town? Then the townie's threat doesn't matter.
Well if I were the second guy, I'd rather vote for the other bad guy, so I'll wait for the town to vote.
what if the day will end b4 town can vote?
I assumed that all players are online or IRL, and that they have an hour to lynch. But sure, there are scenarios where that would be a factor.
The interesting part is at night. Why do they always shoot each other instead of the townsperson or nobody?
well because each one thinks: "whatever the other guy does, I won't be worse off if I shoot him
-
IDK about you guys, but if I was SK I'd be looking to kill Mafia.
-
Also No-Lynch is the only thing that makes sense for all three parties. Town will say "I will vote for the first person to vote me" which then no one would vote. So then the question becomes who does SK NK and who does Mafia NK? That would be when the real fun starts I think. The Townie just might win through the Mafia and SK targeting each other for the NK.
-
Well that's the more trivial part
I'm reminded vaguely of prisoner's dilemma here
Let's say you're the SK and you don't know who the Mafia will kill
Well there are two options:
Mafia kills town, in which case it's clearly better that you should kill the Mafia for the win
Mafia kills you, in which case you could argue it's null, you lose either way
If there's even a slight chance Mafia kills town, it's better to kill Mafia every time. Specifically, killing town will only hurt you
Mafia goes through the same options, therefore they always kill each other at night, as lio nicely led on
The No Lynch only makes sense for town, as it's the only way for them to win, and unfortunately for the Mafia and SK, I can't see anyway they can beat town here
-
The nightkill is exactly the prisoner dilemma for the SK and Mafia. Killing town is considered "cooperating", killing each other is considered "betraying". The only question is how do the players value a draw, compared to a win or a loss.
It is important to note that town loses if there is a lynch, so he is not ever going to vote, unless he values the different losses differently (ex: SK winning instead of Mafia winning, etc.). Which means that the only possible lynch is town. So SK and Mafia can safely choose if they want to cooperate or not during the day, by voting town. If they don't lynch town, they are sending a very clear message that they don't want to cooperate, which means that both will betray during the night, and then town wins.
So the sensible choice is for the SK and the last Mafia to lynch town. However, if a mutual nightkill is ruled as a loss for both factions, then there is no way for anyone to win the stalemate.
This assumes that all players are perfectly rational... which they most often are not. In this situation, I fully expect that considerations about who "deserves to win" will tip the scales one way or another (probably in favour of the SK, since it's usually the hardest role to play).
EDIT: I am assuming that an endgame with only a SK and a Mafia player is considered as a draw for the SK and Mafia, but as a loss for town.
EDIT2: And of course liopoil has already gone over all this quite nicely.
-
This is exactly why I prefer VT over any other role.