wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Game theory problem
        
(Message started by: BenVitale on Jun 19^th, 2008, 6:24pm)

Title: Game theory problem
Post by BenVitale on Jun 19^th, 2008, 6:24pm

This is an optimization problem common to game theory. You want to get the most out of your situation, so it's not enough just to say I'd make the call or I'd take the buck. You have to explain why you would want to do so.

You are alone in a room which contains a one dollar coin, a pay-phone and a scrap of paper with a phone number on it. There are one million identical rooms in the building, each containing a single person. Every person can choose to do one of the following:

A. Use the coin to call the number, if somebody older than them also calls then they win one million dollars (the younger caller wins the million). If nobody older than them calls, then they leave with nothing.

B. You can take the $1 and leave, never to return.

What do you do?
-------------------------------------------
My answer:

I would make the call. I do this based on the following assumptions.

1. At least some people will choose to make the call as well.

2. Out of everyone that does call, it is likely that I will not be the oldest. In particular, I assume that the probability 'k' (say) that I am not the oldest out of all the caller is greater than 1/1000000.

Assumption 2 implies that the expected amount that I am to win if I make the call is
E($) = k*1,000,000 + 0*(1-k) = k*1,000,000 which is greater than 1, since by 2, k is greater than 1/1000000.

It follows that because E($) is greater than one that I should decide to make the call.

Is this correct?

Title: Re: Game theory problem
Post by Obob on Jun 19^th, 2008, 8:10pm

Since you have absolutely no information about the ages of the other people, there is no best strategy for this scenario. But since $1 matters to almost nobody, whereas $1,000,000 matters to almost everybody, virtually anybody in this situation would make the call.
And only one person doesn't get the $1,000,000, so the probability that you win the $1,000,000 would be 99.9999% (maybe the wrong number of 9's) given that the ages are somewhat random, including your own age.

The question would probably be more interesting if only the youngest person to call gets the $1,000,000. As is, far too much money is being paid out, to the point that anybody making the call expects to get the $1,000,000.

Title: Re: Game theory problem
Post by Frumious Bandersnatch on Jun 19^th, 2008, 8:12pm

Just to make sure I understand the rules:
Each person who calls the number gets a million dollars, except for the oldest person who calls, who wins nothing. If everybody calls, then whoever set this up is out nearly a trillion dollars: a million dollars to 999,999 callers. That's assuming they get to keep the million that went into the pay phones. If they have to turn that over to the phone company, they're out exactly a trillion dollars. Plus however much it cost them to set up the million-room building and install all those phones. But I digress.

This being a game theory question, you've got to make a bunch of estimations. First, what are the odds that you're the oldest person in the building? If you're, say 100 years old, you probably don't want to call. If you're 15, you're in better shape there.

Next, what's the relatively utility (or value, or whatever the proper game theory term is), of a.) winning nothing; b.) winning a dollar; and c.) winning a million dollars? For most people, the difference between c and b makes the difference between a and b negligible. Unless you're in particularly dire straits and really need that dollar for something right now, you're really not risking that much by making the call.

Ultimately, it's almost always in your best interest to call the number.

Title: Re: Game theory problem
Post by towr on Jun 20^th, 2008, 12:15am

Suppose everyone knows everyone's age.
Then the oldest person won't call, because he knows he won't win.
But then the second oldest person, knowing this, won't call because he wouldn't win.
Etc.
So with perfect knowledge, no one will call, if they value a dollar over nothing.

With imperfect knowledge, it's harder to say. What's the probability of the oldest person calling? Given a million people, it's usually a safe bet you're not the oldest.

Title: Re: Game theory problem
Post by rmsgrey on Jun 20^th, 2008, 9:54am

on 06/20/08 at 00:15:14, towr wrote:

Assuming everyone else is rational.

With as few as a thousand people older than me, I'd be inclined to gamble on one or more of them having just picked up the phone and dialled the number before thinking through the rules...

Title: Re: Game theory problem
Post by towr on Jun 20^th, 2008, 2:02pm

on 06/20/08 at 09:54:28, rmsgrey wrote:

Assuming everyone else is rational.

Well, yes; it is game-theory after all. Reality doesn't factor into it ;)

Title: Re: Game theory problem
Post by Grimbal on Jun 21^st, 2008, 9:56am

As I know old people, even if they know for certain they are the oldest, many would just make the call to make someone happy.

Anyway, when leaving the building along with the million-1 other people he could just mention around that he is the unlucky one, he lost one dollar, but that he is happy that everybody else won a million. Not asking for anything, of course.

Title: Re: Game theory problem
Post by rmsgrey on Jun 22^nd, 2008, 6:50am

on 06/21/08 at 09:56:33, Grimbal wrote:

Anyway, when leaving the building along with the million-1 other people he could just mention around that he is the unlucky one, he lost one dollar, but that he is happy that everybody else won a million. Not asking for anything, of course.

Yeah, I'd be happy to chip in a dollar from my winnings...

Title: Re: Game theory problem
Post by BenVitale on Jun 24^th, 2008, 4:05pm

a flaw in game theory

http://www.sciencenews.org/view/generic/id/33381/title/Math_Trek__The_tell-tale_anecdote

What do you think?

Title: Re: Game theory problem
Post by towr on Jun 25^th, 2008, 12:59am

on 06/24/08 at 16:05:04, BenVitale wrote:

a flaw in game theory

http://www.sciencenews.org/view/generic/id/33381/title/Math_Trek__The_tell-tale_anecdote

What do you think?

I think it's a flaw of my microwave that it doesn't vacuum clean my room.

Title: Re: Game theory problem
Post by BenVitale on Jun 26^th, 2008, 11:40pm

An economic stability problem:

Suppose we have 3 farmers who depend on each other for growing their crop in the following way.

1) Famer A grows crop 'a' seeds, but needs the crop 'b' seeds which are grown by farmer B in order to grow his crop 'a' seeds.

2) Similarily farmer B needs the crop 'c' seeds in order for him to grow his crop 'b' seeds.

3) Farmer C needs the crop 'a' seeds in order for him to grow his crop 'c' seeds.

Furthermore suppose that every time a farmer grows his seeds, he immediately sells all of his seeds to the other farmer who is in need of them. Each seed sells for exactly 1 dollar, and each farmer shall start out with exactly 50 dollars each. Also, with one seed of one kind, that seed can be used to grow 2 seeds of another kind.

For example, if farmer C buys 50 crop 'a' seeds, then he will grow 100 crop 'c' seeds.

Finally, all seeds are grown/sold once a year and are all sold at the same time.

If in the first year the three farmers A,B and C produce (a,b,c) = (13,8,26) number of seeds, then will these three farmers be able to continue this business indefinitely?

Under what initial year conditions (a,b,c) will three farmers with 50 dollars be able to indefinitely continue this kind of business?

Title: Re: Game theory problem
Post by towr on Jun 27^th, 2008, 12:08am

I wonder what strange universe this takes place in, where one type of seed yield another type of seed.

One question, can they sell to anyone other than eachother?

Title: Re: Game theory problem
Post by Grimbal on Jun 27^th, 2008, 7:10am

Can they sell on credit? Or just exchange seeds?

If A, B and C have a million seeds, A could buy B's seeds on credit, B could buy C's seeds trading in A's debt and C could buy A's seeds canceling A's debt in exchange.

If they need to pay cash, the money will become a problem. If there are fixed periods where you grow seeds, at the end of which all sales are made simultaneously, then the maximum sale is 150 seeds, and the maximum production is 300 seeds per period.

But yes, they can go on growing a few seeds.

Title: Re: Game theory problem
Post by BenVitale on Jun 27^th, 2008, 10:17am

Quote:

I wonder what strange universe this takes place in, where one type of seed yield another type of seed.

Can they sell to anyone other than each other?

Can they sell on credit? Or just exchange seeds?

For this question no, they cannot. I'm keeping the restrictions high so as to easily determine when they can or cannot indefinitely continue to do business with each other (eg for what initial values (a,b,c) is this possible).

After we get through this, we can loosen up some of the variables to see what may happen otherwise.

Another interesting question is that when is it possible for one or two of the farmers to end with a net profit when such a proposed business cannot be continued?

Title: Re: Game theory problem
Post by BenVitale on Jun 28^th, 2008, 4:01pm

Nash equilibrium is a solution concept of a game involving two or more players, in which no player has anything to gain by changing only his or her own strategy unilaterally. If each player has chosen a strategy and no player can benefit by changing his or her strategy while the other players keep theirs unchanged, then the current set of strategy choices and the corresponding payoffs constitute a Nash equilibrium.

For example, if A and B are two people involved in a personal relationship, A and B are in Nash equilibrium if A is making the best decision she can, taking into account B’s decision, and B is making the best decision he can, taking into account A’s decision.

Title: Re: Game theory problem
Post by Grimbal on Jun 29^th, 2008, 9:53am

on 06/26/08 at 23:40:47, BenVitale wrote:

Furthermore suppose that every time a farmer grows his seeds, he immediately sells all of his seeds to the other farmer who is in need of them.

It seems sales are limited by the money the potential buyer has.
Does a farmer have the choice to sell or not? Does a farmer have the choice to buy or not?

And since the total money present is 150 dollars, is the object of the game to stop trading at the best moment to get out with the most money? It seems to me that nobody would buy a seed if he still has some to sell. So nobody would buy the first seed.

Title: Re: Game theory problem
Post by BenVitale on Jul 11^th, 2008, 2:42pm

Here's an article -- a tribute to 2 things I love : Mathematics and playing video/board (chess) games:

Game theory could save the world

http://www.telegraph.co.uk/earth/main.jhtml?view=DETAILS&grid=&xml=/earth/2008/07/09/scigame109.xml

Title: Re: Game theory problem
Post by towr on Jul 11^th, 2008, 3:13pm

on 07/11/08 at 14:42:43, BenVitale wrote:

Here's an article -- a tribute to 2 things I love : Mathematics and playing video/board (chess) games:

I don't really see where video/board games come in in that article.

Quote:

Game theory could save the world

The tendencies in populations that might help to safe the world don't seem to depend much on game theory either; it just predicts they're there.
It's like saying nature programs make lions hunt antelopes. Well maybe they do, I've never seen lions do it outside of those programs.

Title: Re: Game theory problem
Post by BenVitale on Jul 12^th, 2008, 3:04pm

Towr wrote:

Quote:

I don't really see where video/board games come in in that article.

Perhaps not directly, I play chess online, and I play Blackjack and Poker. I started these games long before I knew of Game Theory. These games motivated me to study game theory.

I have 2 new questions/observations in game theory:

(1) Jesus Christ's turn the other cheek vs. Tit for tat strategy :

Jesus proposed turning the other cheek. That doesn't work. It has been shown experimentally that his rule is a weak rule for any society since the beginning of civilization. Cheating and lying is part of human behavior. Tit for tat is a more sensible strategy. Our system of law attempts to apply “tit for tat” combined with elements of rehabilitation.

(2) Decision making and Nash equilibrium:

According to classical game theory, decision makers invariably act in their individual self-interest, leading to "Nash equilibrium".

But psychologists have shown that, in some circumstances, people seem to act not in their individual self-interest but in the interest of their families, companies, departments, or the religious, ethnic, or national groups with which they identify themselves.

Title: Re: Game theory problem
Post by towr on Jul 13^th, 2008, 7:38am

on 07/12/08 at 15:04:41, BenVitale wrote:

I have 2 new questions/observations in game theory:

(1) Jesus Christ's turn the other cheek vs. Tit for tat strategy :

Jesus proposed turning the other cheek. That doesn't work.

One theory goes he meant it quite literally, and for the reason that it's awkward to strike the other cheek. So really, it's an act of defiance, rather than meekness.

Quote:

It has been shown experimentally that his rule is a weak rule for any society since the beginning of civilization. Cheating and lying is part of human behavior. Tit for tat is a more sensible strategy. Our system of law attempts to apply “tit for tat” combined with elements of rehabilitation.

Law is not based on tit for tat. If someone robs my house or murders my family, it is not condoned I do the same to him.
Tit-for-Tat is maladapted for a civilized society. Society's solution is police, rather than indulge in (personal) revenge.
Also consider the way the west looks at the Sharia laws, like cutting off the hands of thieves. That is in a sense a very tit-for-tat kind of solution, and prevents them from ever laying their hands on your goods again. But it isn't a very good solution for a modern society.
The applicability of "rules" depends on their context. Now, personally, I don't know in what experiment they "showed" that "turning the other cheek" is a weak rule. It certainly wouldn't work when, say, a lion is mauling you, no. But it beats perpetuating an infinite cycle of hitting eachother. Moving on is sometimes better that getting stuck in a cycle of revenge and obstinacy (because it has also been shown some people (http://research.nottingham.ac.uk/NewsReviews/newsDisplay.aspx?id=453) do not take just punishment lying down).

Quote:

But psychologists have shown that, in some circumstances, people seem to act not in their individual self-interest but in the interest of their families, companies, departments, or the religious, ethnic, or national groups with which they identify themselves.

Yes, humans are not abstract purely rational (in terms of game theory) agents. You could try reading "Artificial morality" (Peter Danielson) for a different approach to rational decision making.
The thing is, game theory is short sighted. A game theoretic agent cannot make unconditional commitments. You cannot trust them, they flipflop when it suits their immediate interest. And for that reason you can only cooperate with them in a very limited fashion. If I help a GT agent bring in the harvest, I can not expect him to return the favour. But if I had a friend, one I could trust, then we could benefit from doing the harvest together, on both our fields.
Heck, we can band together and beat the sh*t out of GT agents, because they won't be able to organize themselves; each one would be better of doing a step backwards when the fight starts.

GT completely ignores the reality of our genetic heritage. Evolution doesn't particularly care about the individuals interests, what matter is that genes (and proteins) reach the next generation. If bees as a species do better when workers kill themselves stinging invaders of the hive, then that's what they do. Now, you can't argue that it's in the individual bee's best interest to die; dead organisms no longer have interests. But her genes have a better chance of being exhibited in the next generation, because she protected her sisters that share her genes.

And aside from this type of kin selection you also have group selection (overall nice groups may outcompete egoistic groups); sexual selection (affording kindness, dedication, etc shows fitness and gets you laid); (communal) reciprocal altruism (build your reputation by helping the community so it will help you in return); etc.

Title: Re: Game theory problem
Post by ThudanBlunder on Jul 13^th, 2008, 8:06am

on 07/12/08 at 15:04:41, BenVitale wrote:

Towr wrote:
Tit for tat is a more sensible strategy. Our system of law attempts to apply “tit for tat” combined with elements of rehabilitation.

You may find this (http://en.wikipedia.org/wiki/Tit_for_tat) interesting.

Title: Re: Game theory problem
Post by BenVitale on Jul 13^th, 2008, 12:12pm

Towr and ThudanBlunder,

Thanks for your insights. Speaking of the Prisoners' dilemma, I have a linked document that puzzles me:

http://relationary.wordpress.com/2008/02/16/abandoning-the-prisoners-dilemma/

Does it make sense to you ?

I have trouble understanding the Transaction Triangle game which has 3 roles.

Title: Re: Game theory problem
Post by BenVitale on Jul 17^th, 2008, 3:10pm

Why Things Cost $19.95
What are the psychological "rules" of bartering? Is life an auction?

http://www.sciam.com/article.cfm?id=why-things-cost-1995

Quote:

... if we see a $20 toaster, we might wonder whether it is worth $19 or $18 or $21; we are thinking in round numbers. But if the starting point is $19.95, the mental measuring stick would look different. We might still think it is wrongly priced, but in our minds we are thinking about nickels and dimes instead of dollars, so a fair comeback might be $19.75 or $19.50.

I found interesting comments at the bottom of the document,

Quote:

Why are things marked as $19.95 in the US, but as £19.99 in the UK? Does that 4 cents/pence really make a difference?

Quote:

I've heard two alternative explanations for the $19.95 phenomenon. One is that sales taxes were based on whole dollar amounts (for ease of calculating percentiles), so the merchants were getting most of that extra dollar ; the other is that $9.95 looks smaller (fewer digits) than $10.00, and because we read from left to right, we see $19.95 as less than $20.00. I've also read that we've become so ingrained to see 9s as indicating a mark-down in price that sales of a product actually increased when the price was changed from 96c to 99c. I can't explain the 95c vs. 99p dichotomy, but in Australia, 1c and 2c pieces were abolished and 5c is the smallest coin available - yet many book distributors here have just increased prices from (for example) $32.95 to $32.99. This is rounded up by cash registers to $33, saving the need to give change, but it still has the psychological impact of the 9s. (In Australia and the UK, sales taxes are already factored into retail prices.)

Title: Re: Game theory problem
Post by BenVitale on Jul 21^st, 2008, 11:14pm

Topic: Game Theory with applications in warfare.

I watched in the films, countless times, how European and even American rival armies used to engage in battle one to three centuries ago.

They used to form a long and compact wall of aligned soldiers facing also a long wall of aligned enemy soldiers from a given distance in an open and almost flat field and then without any physical protection to their bodies they aimed their muskets or rifles against the soldiers of the enemy’s line and after a signal of their commanders they started to shoot each other !

With such compact line of people there was almost no way that bullets could miss.

In ancient times, the greek phalanx formation was used.

The British used the line formation against Napoleon to defeat his forces. Napoleon used the same tactic for too long, he used the tactic of attacking in columns.

But why they used a strategy that excessively exposed their soldiers to bullets ( even from cannons ) and nothing to shield or protect them ?

Title: Re: Game theory problem
Post by Grimbal on Jul 22^nd, 2008, 1:58am

That would make sense if the range of your guns is longer than the range of your enemy's guns.

Title: Re: Game theory problem
Post by towr on Jul 22^nd, 2008, 2:01am

on 07/21/08 at 23:14:47, BenVitale wrote:

Topic: Game Theory with applications in warfare.

Really? That's the topic? Are you quite sure?

Quote:

But why they used a strategy that excessively exposed their soldiers to bullets ( even from cannons ) and nothing to shield or protect them ?

It's not like they wouldn't hide behind a wall when there was one. But if both sides dig in, then neither will win. If they both want to win (rather than keep the other tied up), then they will have to engage each other and get it over with.

Did you have an alternative strategy in mind?

Title: Re: Game theory problem
Post by ThudanBlunder on Jul 22^nd, 2008, 2:10am

on 07/21/08 at 23:14:47, BenVitale wrote:

But why they used a strategy that excessively exposed their soldiers to bullets ( even from cannons ) and nothing to shield or protect them ?

Because in those days lives were cheaper than bullets.

Title: Re: Game theory problem
Post by BenVitale on Jul 22^nd, 2008, 7:39pm

I went Online to read about military history and military campaigns. There's just too much to read. I got tired and bored with it.

I came across the following:

The musket (and to some extent the early rifles) were in no way accurate at all.

Most shots would hit the ground or go over the line of enemy. What these kinds of battles really came down to was the rate of fire that a well trained unit could put down. They also did not just stand and shoot. The front ranks would shoot prone, the middle kneeling and the rear standing so that they could fire over the ranks in front of them.

We also need to question the authenticity of those movies. Movies are tools for propaganda, for making people feel good about themselves, feeling superior, about their country.

One author wrote, "In wars, it is always the same people who die."

These movies are designed to create a patriotic mindset, to have people rally behind the flag, and convince the public that sacrifices were needed to defeat the enemy.

I need to read on to find applications of Game Theory. Perhaps I need to learn more about "coalition theory".

Title: Re: Game theory problem
Post by towr on Jul 23^rd, 2008, 12:53am

on 07/22/08 at 19:39:38, BenVitale wrote:

We also need to question the authenticity of those movies. Movies are tools for propaganda, for making people feel good about themselves, feeling superior, about their country.
[...]
These movies are designed to create a patriotic mindset, to have people rally behind the flag, and convince the public that sacrifices were needed to defeat the enemy.

You only watch movies about your own country's wars?!

Movies, these days, are tools for profit. They're entertainment. They suit propaganda only in so far as that serves to bring people in to watch them. And more than a few depict the horrors of war rather than aggrandizing them.