Well… This article is tagged decision_theory, not game_theory. The goal is not merely to explore solutions to this game, the goal is to explore solution-finding strategies to this game, or at least lay the foundations for that.
Isn’t that exactly the topic of game theory?
I think your CliqueBots need the insight behind Emile’s hashMe proposal—they each need a unique ID. Otherwise, when CliqueBot_0 plays a copy, “X xor Y xor ID” is 0, so both play B, so they both lose.
Yes, I assumed that the execution environment provides the bots with a binary role ID as an additional (implicit) parameter. If that’s a problem you can use a more sophisticated symmetry-breaking scheme, on the lines of Emile’s proposal, but I think it is better to maintain cliquing, which is missing from Emile’s proposal.
Well, you seem to be more expert than I am, so I can just ask you :D Given a small, two-player payoff matrix, what general process outputs the correct move for player 1?
I’m not really that expert, but I can try to answer the question anyway.
The short answer is to implement game theory.
Of course, this is easier said than done. Under the assumption that the other player is at least as rational as you are, you generally want a decision procedure that chooses a strategy which is part of a Nash equilibrium (under mild assumptions, at least one Nash equilibrium always exists). If there are multiple Nash equilibria, as it is often the case, you want your decision procedure to seek for a refinement and hope that the other player does the same. Ultimately, for some games there is no single satisfactory solution. It could be that this happens because game theory is incomplete or that these games are intrinsically unsolvable dilemmas. In these cases, you might want to fall back to an heuristic (such as randomization or trying to guess the other player decision)
Hm. So I think I reinvented the wheel to moderate success, then. In the blind, no-communication case, you play the bargaining equilibrium. With communication via source code, though, I didn’t make my wheel—following the bargaining equilibrium among strategies—very round. This is because you can use your source codes to send two random numbers, which lets you cooperate with the other player. But there are many different possible ways of doing this, each corresponding to a different equilibrium.
To have any chance of cooperating, and thus beating my slightly non-round wheel, you need a prior over opponents to let you narrow down the search for cooperation schemes (probably “pick the simplest”), and you need to randomize over the multiple remaining equilibria. And no cliqueishness here, since we’re trying to play blind.
Isn’t that exactly the topic of game theory?
Yes, I assumed that the execution environment provides the bots with a binary role ID as an additional (implicit) parameter. If that’s a problem you can use a more sophisticated symmetry-breaking scheme, on the lines of Emile’s proposal, but I think it is better to maintain cliquing, which is missing from Emile’s proposal.
Well, you seem to be more expert than I am, so I can just ask you :D Given a small, two-player payoff matrix, what general process outputs the correct move for player 1?
I’m not really that expert, but I can try to answer the question anyway.
The short answer is to implement game theory.
Of course, this is easier said than done.
Under the assumption that the other player is at least as rational as you are, you generally want a decision procedure that chooses a strategy which is part of a Nash equilibrium (under mild assumptions, at least one Nash equilibrium always exists). If there are multiple Nash equilibria, as it is often the case, you want your decision procedure to seek for a refinement and hope that the other player does the same.
Ultimately, for some games there is no single satisfactory solution. It could be that this happens because game theory is incomplete or that these games are intrinsically unsolvable dilemmas. In these cases, you might want to fall back to an heuristic (such as randomization or trying to guess the other player decision)
Hm. So I think I reinvented the wheel to moderate success, then. In the blind, no-communication case, you play the bargaining equilibrium. With communication via source code, though, I didn’t make my wheel—following the bargaining equilibrium among strategies—very round. This is because you can use your source codes to send two random numbers, which lets you cooperate with the other player. But there are many different possible ways of doing this, each corresponding to a different equilibrium.
To have any chance of cooperating, and thus beating my slightly non-round wheel, you need a prior over opponents to let you narrow down the search for cooperation schemes (probably “pick the simplest”), and you need to randomize over the multiple remaining equilibria. And no cliqueishness here, since we’re trying to play blind.