It has been a while since I looked at Aumann’s Handbook, and I don’t have access to a copy now, but I seem to recall discussion of an NTU analog of the Shapley value. Ah, I also find it in Section 9.9 of Myerson’s textbook. Perhaps the problem is they don’t collectively voluntarily punish defectors quite as well you would like them to. I’m also puzzled by your apparent restriction of correlated equilibria to symmetric games. You realize, of course, that symmetry is not a requirement for a correlated equilibrium in a two-person game?
It wasn’t my intention, at least in this posting, to advocate standard Game Theory as the solution to the FAI decision theory question. I am not at all sure I understand what that question really is. All I am doing here is pointing out the analogy between the “best play” problem and the “best decision theory” metaproblem.
I’m also puzzled by your apparent restriction of correlated equilibria to symmetric games. You realize, of course, that symmetry is not a requirement for a correlated equilibrium in a two-person game?
Yes, I realize that. The problem lies elsewhere. When you pit two agents using the same “good” decision theory against each other in a non-symmetric game, some correlated play must result. But which one? Do you have a convention for selecting the “best” correlated equilibrium in an arbitrary non-symmetric game? Because your “good” algorithm (assuming it exists) will necessarily give rise to just such a convention.
About values for NTU games: according to my last impressions, the topic was a complete mess and there was no universally agreed-upon value. Unlike the TU case, there seems to be a whole zoo of competing NTU values with different axiomatic justifications. Maybe our attempts to codify “good” algorithms will someday cut through this mess, but I don’t yet see how.
Do you have a convention for selecting the “best” correlated equilibrium in an arbitrary non-symmetric game?
What is wrong with the Nash bargaining solution (with threats)? Negotiating an acceptable joint equilibrium is a cooperative game. It is non-cooperatively enforceable because you limit yourself to only correlated equilibria rather than the full Pareto set of joint possibilities.
I must be missing something. You are allowing communication and (non-binding) arbitration, aren’t you? And a jointly trusted source of random numbers.
Um, maybe it’s me who’s missing something. Does the Nash bargaining solution uniquely solve all games? How do you choose the “disagreement point” used for defining the solution, if the game has multiple noncooperative equilibria? Sorry if I’m asking a stupid question.
Nash’s 1953 paper covers that, I think. Just about any game theory text should explain. Look in the index for “threat game”. In fact, Googling on the string “Nash bargaining threat game” returns a host of promising-looking links.
Of course, when you go to extend this 2-person result to coalition games, it gets even more complicated. In effect, the Shapley value is a weighted average of values for each possible coalition structure, with the division of spoils and responsibilities within each coalition also being decided by bargaining. The thing is, I don’t see any real justification for the usual convention of giving equal weights to each possible coalition. Some coalitions seem more natural to me than others—one most naturally joins the coalitions with which one communicates best, over which one has the most power to reward and punish, and which has the most power over oneself. But I’m not sure exactly how this fits into the math. Probably a Rubinstein-style answer could be worked out within the general framework of Nash’s program.
Well, sorry. You were right all along and I’m a complete idiot. For some reason my textbook failed to cover that, and I never stumbled on that anywhere else.
Does this paper have what you’re looking for? I’m not in the office, so can’t read it at the moment—and might not be able to anyway, as my university’s subscriptions tend not to include lots of Science Direct journals—it does at least seem to provide one plausible answer to your question.
(no idea if that link will work—the paper is Bargained-Correlated Equilibria by Tedeschi Piero)
Thanks a lot. RobinZ sent me the paper and I read it. The key part is indeed the definition of the disagreement point, and the reasoning used to justify it is plausible. The only sticky issue is that the disagreement point defined in the paper is unattainable; I’m not sure what to think about that, and not sure whether the disagreement point must be “fair” with respect to the players.
The “common priors” property used in the paper gave me the idea that optimal play can arise via Aumann agreement, which in turn can emerge from individually rational behavior! This is really interesting and I’ll have to think about it.
The abstract looks interesting, but I can’t access the paper because I’m a regular schmuck in Russia, not a student at a US university or something :-)
It has been a while since I looked at Aumann’s Handbook, and I don’t have access to a copy now, but I seem to recall discussion of an NTU analog of the Shapley value. Ah, I also find it in Section 9.9 of Myerson’s textbook. Perhaps the problem is they don’t collectively voluntarily punish defectors quite as well you would like them to. I’m also puzzled by your apparent restriction of correlated equilibria to symmetric games. You realize, of course, that symmetry is not a requirement for a correlated equilibrium in a two-person game?
It wasn’t my intention, at least in this posting, to advocate standard Game Theory as the solution to the FAI decision theory question. I am not at all sure I understand what that question really is. All I am doing here is pointing out the analogy between the “best play” problem and the “best decision theory” metaproblem.
Yes, I realize that. The problem lies elsewhere. When you pit two agents using the same “good” decision theory against each other in a non-symmetric game, some correlated play must result. But which one? Do you have a convention for selecting the “best” correlated equilibrium in an arbitrary non-symmetric game? Because your “good” algorithm (assuming it exists) will necessarily give rise to just such a convention.
About values for NTU games: according to my last impressions, the topic was a complete mess and there was no universally agreed-upon value. Unlike the TU case, there seems to be a whole zoo of competing NTU values with different axiomatic justifications. Maybe our attempts to codify “good” algorithms will someday cut through this mess, but I don’t yet see how.
What is wrong with the Nash bargaining solution (with threats)? Negotiating an acceptable joint equilibrium is a cooperative game. It is non-cooperatively enforceable because you limit yourself to only correlated equilibria rather than the full Pareto set of joint possibilities.
I must be missing something. You are allowing communication and (non-binding) arbitration, aren’t you? And a jointly trusted source of random numbers.
Um, maybe it’s me who’s missing something. Does the Nash bargaining solution uniquely solve all games? How do you choose the “disagreement point” used for defining the solution, if the game has multiple noncooperative equilibria? Sorry if I’m asking a stupid question.
Nash’s 1953 paper covers that, I think. Just about any game theory text should explain. Look in the index for “threat game”. In fact, Googling on the string “Nash bargaining threat game” returns a host of promising-looking links.
Of course, when you go to extend this 2-person result to coalition games, it gets even more complicated. In effect, the Shapley value is a weighted average of values for each possible coalition structure, with the division of spoils and responsibilities within each coalition also being decided by bargaining. The thing is, I don’t see any real justification for the usual convention of giving equal weights to each possible coalition. Some coalitions seem more natural to me than others—one most naturally joins the coalitions with which one communicates best, over which one has the most power to reward and punish, and which has the most power over oneself. But I’m not sure exactly how this fits into the math. Probably a Rubinstein-style answer could be worked out within the general framework of Nash’s program.
Well, sorry. You were right all along and I’m a complete idiot. For some reason my textbook failed to cover that, and I never stumbled on that anywhere else.
(reads paper, goes into a corner to think)
Does this paper have what you’re looking for? I’m not in the office, so can’t read it at the moment—and might not be able to anyway, as my university’s subscriptions tend not to include lots of Science Direct journals—it does at least seem to provide one plausible answer to your question.
(no idea if that link will work—the paper is Bargained-Correlated Equilibria by Tedeschi Piero)
Thanks a lot. RobinZ sent me the paper and I read it. The key part is indeed the definition of the disagreement point, and the reasoning used to justify it is plausible. The only sticky issue is that the disagreement point defined in the paper is unattainable; I’m not sure what to think about that, and not sure whether the disagreement point must be “fair” with respect to the players.
The “common priors” property used in the paper gave me the idea that optimal play can arise via Aumann agreement, which in turn can emerge from individually rational behavior! This is really interesting and I’ll have to think about it.
The abstract looks interesting, but I can’t access the paper because I’m a regular schmuck in Russia, not a student at a US university or something :-)
I have it. PM me with email address for PDF.
Done!
ETA: and received. Thanks!