Backward Reasoning Over Decision Trees

Very nice that you're doing this!

The line item example is a bit too complicated for my taste. Here's a simpler one: let's say Alice has the option of cooking a pie, but must share half of it with Bob. So Alice cooks the pie and everyone is happy. Now let's give Bob the option of stealing the whole pie and frustrating Alice. Then Alice won't cook the pie because she will anticipate that Bob's optimal decision would leave her without pie and frustrate her, so everyone is worse off.

Suggestion: Republicans should use a wider paper, and write "high domestic spending" and "high military spending" on the same line. This gives them their 5 utility points back. :D

#!/usr/python3
title1 = open("Title_01.txt").read()
target = "That which can be destroyed by the truth, should be."
target = list(target)
target.reverse()
keep_chars = []
for i, c in enumerate(title1):
....try:
........if c == target[-1]:
............keep_chars.append(i)
............target.pop()
....except:
........break
print(keep_chars)
revised = ""
for i in keep_chars:
....revised += title1[i]
print(revised)

Good introduction, nothing new (but the "line-item veto" example is a nice one), but still good to have around.

One thing that made me "wail and gnash" a little :

that everyone is purely self-interested

That's not really the case. Game theory usually consider that everyone is an utility maximizer, but nothing says that the utility function has to be selfish. Utility function can factor well-being and happiness of others in it.

You can apply game theory in cases like a parent-child relation, in which the parent and the child disagree, but the parent still is motivated with the interest of the child. Even in more classical cases, nothing forces the utility function to be selfish and not value the other well-being. Game theory only apply when the agents have different goals, but it can just be "I value my own well-being twice as much as the well-being of the other", which is not "purely self-interested".

It makes me "wail and gnash" because it's a very frequent cliché that rationalists and utility maximizer are necessarily selfish and don't care about others, and it's a cliché we should fight. That say, I understand the a whole part of game theory is about showing how even pure selfishness can, in some cases, lead to cooperation being the best solution. Your "line-item veto" is a good example of it, Clinton and Congress can still cooperate to get the previous 5-5 equilibrium, if they trust each others, and this is an IPD at the end.

This method of alternating moves in a branching tree matches both our intuitive thought processes during a chess game (“Okay, if I do this, then Black's going to do this, and then I'd do this, and then...”) and the foundation of the algorithms chess computers like Deep Blue use.

Could you include a reference to alpha-beta pruning, since that is precisely what you're describing? Some readers may be more familiar with that subject domain and appreciate explicitly linking game theory to an established search algorithm.

game theorists call this a gnash equilibrium

Did you mean "Nash equilibrium"? If it was a deliberate pun, you might want to indicate it for those who are looking up new concepts, this being an introductory series.

Pretty good so far. I personally felt like the line-item example was pretty illuminative, but using real political examples instead of sticking with the national game theory month approach is a bit iffy. In particular the line

If Republicans are perfectly rational agents (a sentiment, I admit, open to doubt)

Can easily be interpreted as an attack on republicans.

It starts with the same questionable premises as economics: that everyone behaves rationally, that everyone is purely self-interested, and that desires can be easily and exactly quantified

I agree that it assumes that everyone behaves rationally and that desires can be exactly quantified, but I don't see how it assumes that everyone is purely self-interested or that desires can be easily quantified.

game theorists call this a gnash equilibrium

Well played, sir.

I suggest adding a link at the bottom to the next post in the sequence.

This is a well-written, light, fun intro. I'll look forward to linking my friends here. You should add an attractive image to that post somewhere, so e.g. it shows up with a cool image thumbnail when people link it from Facebook. That's why I added the image here.

Hopefully stuffy LWers won't fail to upvote this merely because it's stuff they (mostly) know already.

Go to the beach? (Utility +5) Hit yourself on the head with a hammer? (Utility -20)

Actually, I wouldn't be willing to hit my head with a hammer with probability 25% in order to go to the beach with probability 100% - epsilon, so the magnitude of the second utility ought to be much larger. YMMV.

ETA: Well, if you don't specify how hard I am supposed to hit myself, maybe I would. :-)

Art of Strategy describes a debate from 1990s US politics revolving around so-called “line-item veto” power, the ability to veto only one part of a bill....During the '90s, President Clinton fought pretty hard for this power, which seems reasonable as it expands his options when dealing with the hostile Republican Congress.

Just for the benefit of those who don't know the history (and won't bother to click on the Wikipedia link), it should be noted that the Republican Congress happily gave Clinton this power (perhaps not so surprising after reading this post!), but it was struck down by the Supreme Court (which functions as America's House of Lords -- kind of a mirror image of how the actual House of Lords used to function as Britain's Supreme Court).

The line item veto is probably a bad choice to use as an example. In the current US political climate, there is a significant life to the meme of paralyzing washington on purpose to get spending down "at any expense." So the problem with your current example is the current American may look at it and think you are presenting lower over all spending as some kind of win, when int his example it is intended to show a loss to both sides.

And indeed, it seems a president who wanted lower overall spending would support the line item veto. She could then get the credit for vetoing the things her constituents don't want and lay the blame for under funding the things her constituents do want on the opposite party. And of course take the credit for a lower overall budget irrespective of what she would have done running open loop. Is this an example of some more complex game theory, or do results like this come about relatively straightforwardly in simple game theory?

Fascinating, thanks. I already knew a lot of this in a vague manner, but it was nice to see it made concrete and clear.

This seems to have obvious evpsych implications regarding emotions such as love and friendship - if you love somebody enough that you can't take serious actions against them, even if it would otherwise be rational (for a purely selfish agent), then it's also more profitable for your partner to keep interacting with you. Of course, handicapping yourself is only a good idea if the other person isn't out to ruthlessly exploit you anyway, so love often demands a lot of reciprocity - unless, perhaps (getting into strong armchair evpsych territory here), the status difference is so large that you have potentially more to gain than lose anyway. I expect somebody here can give a pointer to the standard papers about this?

This is a bit off-topic/already guarded against by your disclaimer, but if black takes the pawn after white takes the knight (the single move from that node of the given tree), black will lose the bishop and the rook immediately, and the game very soon.

Nice discussion of game theory in politics. Is there any theoretical basis for expecting the line-item veto generally to be more harmful than beneficial to the president?

(Not an attempt to belittle the above fascinating example, but genuine interest in any related, more general results of the theory.)

Is that Chess for Kindle?

I doubt that the line-item veto is a good example, because there are so many complications in any kind of real politics. For example, C&C might agree in advance that a certain line item will be included only if some other item is not vetoed. This improves everyone's utility without going all the way back to the "all-or-nothing" setup, in essence prioritizing the line items.

An example where workarounds are impossible or unlikely would illustrate the standard idea of working backwards better.