Lowest price auctions PUZZLE
Moderators: jestingrabbit, Moderators General, Prelates
Yeah, so this problem is kind of hard to solve in the general case. But, unlike skeptical scientist believed, it *does* have symmetric equilibria.
I'll do the n=2 and n=3 situations for you. They will suggest the solution methods for higher n, but those require more work than I presently wish to invest.
n=2.
First off, break the problem into situations where people either play 1 or ~1. Then iterate over the entire state space. Here, I'm writing it as (Me, other player 1, other player 2, ...) and since there's only two players, life is easy.
(1, 1)  I lose
(1, ~1)  I win
(~1, 1)  I lose
(~1, ~1)  I might win, depending.
Your total win rate is W. If your opponents all choose 1 with probability q and ~1 with probability 1q, and you do the same with probabilities p and 1p, then this suggests that your win rate with two players, W(2), is equal to:
W(2) = p * (1q) + (1p)(1q) W(2)
Notice how W(2) appears on the right hand side, as the win rate which you'll have if both you and your opponent choose ~1. This is an odd but useful little symmetry of the system; that if we're sure that folks didn't choose 1, then we can just do the exact same thing starting with 2. Works fantastically. So, we get that:
W(2) = p * (1q) / [1  (1p)(1q) ]
Take a derivative with respect to p. Do *not* set p=q before you take the derivative. (Remember, the *first* thing you want to do is maximize your own personal profits, and only *then* do you want to make everyone else follow the same strategy as you.)
dW(2)/dp = ( (1q)(1  (1p)(1q))  p * (1q) * (1q) )/ [1  (1p)(1q) ]^2
dW(2)/dp = q (1q) / [1  (1p)(1q) ]Â²
*Now* you may set p = q, and set this whole thing to 0, to get:
p (1p) / [1  (1p)Â² ]Â² = 0
p (1p) / [1  (12p+pÂ²) ]Â² = 0
p (1p) / [2ppÂ²]Â² = 0
As p goes to 0, the left hand side goes to infinity, so p ≠ 0. With that established, we must have p=1; there are no other values that could work. So the equilibrium value is p=1.
Fine, but how do you know that this is the right answer? Well, I'll tell you: go back to the original four options:
(1, 1)  I lose
(1, ~1)  I win
(~1, 1)  I lose
(~1, ~1)  I might win, depending.
Now, notice that if the other person chooses ~1, then I can only gain by choosing 1 over ~1. I might win some extra games. And if the other person chooses 1, then I cannot win in any event, so it doesn't matter which one I choose. So, to maximize my win rate, I should indeed always choose 1.
For n=3.
Same deal:
(1,1,1)  I lose.
(1,1,~1)  I lose.
(1,~1,1)  I lose.
(1,~1,~1)  I win.
(~1,1,1)  I win.
(~1,1,~1)  I lose.
(~1,~1,1)  I lose.
(~1,~1,~1)  I might win.
Again, all of the opponents have a probability of choosing 1 of q, and a probability of choosing ~1 of 1q, and p does the same for me.
Building up my win rate, I get:
W(3) = p*(1q)^2 + (1p)*q^2 + (1p)(1q)^2 W(3)
W(3) = [p*(1q)^2 + (1p)*q^2] / [1  (1p)(1q)^2]
Taking a derivative with respect to p gives:
dW(3)/dp =
{ [(1q)Â²  qÂ²] [1  (1p)(1q)Â²]  [p*(1q)Â² + (1p)*qÂ²] [(1q)Â²]}/[1  (1p)(1q)Â²]Â²
Settin q=p gives:
{ (12p)[1  (1p)Â³]  [p*(1p)^4 + (1p)Â³ pÂ²] }/[1  (1p)Â³]Â² = 0
Which can be simplified to:
(2p + 4pÂ³  p^4  6pÂ²) / (3p  3pÂ² + pÂ³)Â² = 0
Now, at p=0, the numerator goes like 2p while the denominator goes like (3p)Â², so in total, the thing goes like 2/(9p)  which is to say, it goes to infinity. So, again, p ≠ 0. With that said, we can multiply both sides by the denominator and then divide by p to get:
pÂ³  4pÂ² + 6p  2 = 0
Simple rootfinding algorithms will give you this polynomial's root on [0,1], which is:
P = 0.45631098730792363
Now, notice that this defines a full geometric PMF for your solutions. You choose:
1 with probability P
2 with probability P*(1P)
3 with probability P*(1P)Â²
Et cetera.
You can confirm that, indeed, when everyone plays this strategy, nobody can "game the system," as it were. Go ahead. Play always1. It won't help.
A generalcase solution for n is much harder to get at, because you may have W(i) dependent on W(i2N) for integer N, which was why I was using those funky numbers as if W was a function. And it's not clear whether afterwards, you'd still do a geometric PMF (probably, it gets more complicated when W(i) depends on W(i2N)).
I'll do the n=2 and n=3 situations for you. They will suggest the solution methods for higher n, but those require more work than I presently wish to invest.
n=2.
First off, break the problem into situations where people either play 1 or ~1. Then iterate over the entire state space. Here, I'm writing it as (Me, other player 1, other player 2, ...) and since there's only two players, life is easy.
(1, 1)  I lose
(1, ~1)  I win
(~1, 1)  I lose
(~1, ~1)  I might win, depending.
Your total win rate is W. If your opponents all choose 1 with probability q and ~1 with probability 1q, and you do the same with probabilities p and 1p, then this suggests that your win rate with two players, W(2), is equal to:
W(2) = p * (1q) + (1p)(1q) W(2)
Notice how W(2) appears on the right hand side, as the win rate which you'll have if both you and your opponent choose ~1. This is an odd but useful little symmetry of the system; that if we're sure that folks didn't choose 1, then we can just do the exact same thing starting with 2. Works fantastically. So, we get that:
W(2) = p * (1q) / [1  (1p)(1q) ]
Take a derivative with respect to p. Do *not* set p=q before you take the derivative. (Remember, the *first* thing you want to do is maximize your own personal profits, and only *then* do you want to make everyone else follow the same strategy as you.)
dW(2)/dp = ( (1q)(1  (1p)(1q))  p * (1q) * (1q) )/ [1  (1p)(1q) ]^2
dW(2)/dp = q (1q) / [1  (1p)(1q) ]Â²
*Now* you may set p = q, and set this whole thing to 0, to get:
p (1p) / [1  (1p)Â² ]Â² = 0
p (1p) / [1  (12p+pÂ²) ]Â² = 0
p (1p) / [2ppÂ²]Â² = 0
As p goes to 0, the left hand side goes to infinity, so p ≠ 0. With that established, we must have p=1; there are no other values that could work. So the equilibrium value is p=1.
Fine, but how do you know that this is the right answer? Well, I'll tell you: go back to the original four options:
(1, 1)  I lose
(1, ~1)  I win
(~1, 1)  I lose
(~1, ~1)  I might win, depending.
Now, notice that if the other person chooses ~1, then I can only gain by choosing 1 over ~1. I might win some extra games. And if the other person chooses 1, then I cannot win in any event, so it doesn't matter which one I choose. So, to maximize my win rate, I should indeed always choose 1.
For n=3.
Same deal:
(1,1,1)  I lose.
(1,1,~1)  I lose.
(1,~1,1)  I lose.
(1,~1,~1)  I win.
(~1,1,1)  I win.
(~1,1,~1)  I lose.
(~1,~1,1)  I lose.
(~1,~1,~1)  I might win.
Again, all of the opponents have a probability of choosing 1 of q, and a probability of choosing ~1 of 1q, and p does the same for me.
Building up my win rate, I get:
W(3) = p*(1q)^2 + (1p)*q^2 + (1p)(1q)^2 W(3)
W(3) = [p*(1q)^2 + (1p)*q^2] / [1  (1p)(1q)^2]
Taking a derivative with respect to p gives:
dW(3)/dp =
{ [(1q)Â²  qÂ²] [1  (1p)(1q)Â²]  [p*(1q)Â² + (1p)*qÂ²] [(1q)Â²]}/[1  (1p)(1q)Â²]Â²
Settin q=p gives:
{ (12p)[1  (1p)Â³]  [p*(1p)^4 + (1p)Â³ pÂ²] }/[1  (1p)Â³]Â² = 0
Which can be simplified to:
(2p + 4pÂ³  p^4  6pÂ²) / (3p  3pÂ² + pÂ³)Â² = 0
Now, at p=0, the numerator goes like 2p while the denominator goes like (3p)Â², so in total, the thing goes like 2/(9p)  which is to say, it goes to infinity. So, again, p ≠ 0. With that said, we can multiply both sides by the denominator and then divide by p to get:
pÂ³  4pÂ² + 6p  2 = 0
Simple rootfinding algorithms will give you this polynomial's root on [0,1], which is:
P = 0.45631098730792363
Now, notice that this defines a full geometric PMF for your solutions. You choose:
1 with probability P
2 with probability P*(1P)
3 with probability P*(1P)Â²
Et cetera.
You can confirm that, indeed, when everyone plays this strategy, nobody can "game the system," as it were. Go ahead. Play always1. It won't help.
A generalcase solution for n is much harder to get at, because you may have W(i) dependent on W(i2N) for integer N, which was why I was using those funky numbers as if W was a function. And it's not clear whether afterwards, you'd still do a geometric PMF (probably, it gets more complicated when W(i) depends on W(i2N)).
i've seen this puzzle twice in my life...
To be honest i always picked 15, with 30 people playing (or so)
I don't remember why, but we got into a huge discussion about why. this isn't just game theory, this is economics as well...
allow me to explain. On world of warcraft there is an auction house. your goal is to get your items sold in 24 hours. Your goal is to actually make money. Two subgoals (that may not be, and certainly aren't important to everyone) are: ensure that the market remains stable so you can continue to make money; or: destabilize the market so you can buy everything cheaper and relist the stuff in a few weeks when everything has restabilized.
this may seem trivial, but my friend and i have broken the economies on several realms with as little as 10 gold and as much as 100 gold before.
Basically, you have to figure out what is the lowest you can list an item, such that no one else would list lower than you while yours is still listed. you don't mind if they list the same as you (unless it's an obscure item. let's pretend that it is "oxygen tank" and everyone can use those at one point or another); or higher. As a matter of fact, you'd rather they list higher than you in the hopes that your low valued item gets sold first and then theirs is the next highest. Do you see how this can get very complex? If you price way lower than the market, you will get everyone listing around your price or slightly higher (or lower, if they don't know how much the item is worth just trading to a vendor), and if you list say, 200 of the same item at the same price, you've just broken the market. Now the next time you go to list your oxygen tank (because you found 4 more) they're worthless as an item to trade to players, and now you have to sell it to a vendor.
My current strategy is to get 3 or 4 of an 'item' by collecting one item myself and buying the other 2 or three from the auction house, and relisting them all so the profits are gleaned from my added stack, while still being cheaper than what i paid for the 2 or 3 i bought. For those of you who know what i am talking about, 45 silver is now around 65 gold in the span of a week, and i only play the AH for about 15 minutes at a time, two to three times a day on average. And 10 of those minutes is me going downstairs to have a cigarette, while the scanner gets me the latest prices.
The other time i saw this puzzle in a nonacademic setting was 44110.com or something similar, where they would give you an item SKU (like 65764 for instance) and you would text 44110 via SMS(cellphone) the SKU and your bid. the lowest unique bid would win. they had stuff like cars and TVs and dvd players and stuff like that.
If i recall correctly they did show you how many people had currently bid on it on the website. I remember discussing this with my friends and determining that waiting until the last possible moment to bid was the best... and for some reason i kept coming up with 1317 dollars being the best bet.
It's very sneaky that you are using our fantastic minds of math and psychology to get that TV for yourself, though. share the love!
To be honest i always picked 15, with 30 people playing (or so)
I don't remember why, but we got into a huge discussion about why. this isn't just game theory, this is economics as well...
allow me to explain. On world of warcraft there is an auction house. your goal is to get your items sold in 24 hours. Your goal is to actually make money. Two subgoals (that may not be, and certainly aren't important to everyone) are: ensure that the market remains stable so you can continue to make money; or: destabilize the market so you can buy everything cheaper and relist the stuff in a few weeks when everything has restabilized.
this may seem trivial, but my friend and i have broken the economies on several realms with as little as 10 gold and as much as 100 gold before.
Basically, you have to figure out what is the lowest you can list an item, such that no one else would list lower than you while yours is still listed. you don't mind if they list the same as you (unless it's an obscure item. let's pretend that it is "oxygen tank" and everyone can use those at one point or another); or higher. As a matter of fact, you'd rather they list higher than you in the hopes that your low valued item gets sold first and then theirs is the next highest. Do you see how this can get very complex? If you price way lower than the market, you will get everyone listing around your price or slightly higher (or lower, if they don't know how much the item is worth just trading to a vendor), and if you list say, 200 of the same item at the same price, you've just broken the market. Now the next time you go to list your oxygen tank (because you found 4 more) they're worthless as an item to trade to players, and now you have to sell it to a vendor.
My current strategy is to get 3 or 4 of an 'item' by collecting one item myself and buying the other 2 or three from the auction house, and relisting them all so the profits are gleaned from my added stack, while still being cheaper than what i paid for the 2 or 3 i bought. For those of you who know what i am talking about, 45 silver is now around 65 gold in the span of a week, and i only play the AH for about 15 minutes at a time, two to three times a day on average. And 10 of those minutes is me going downstairs to have a cigarette, while the scanner gets me the latest prices.
The other time i saw this puzzle in a nonacademic setting was 44110.com or something similar, where they would give you an item SKU (like 65764 for instance) and you would text 44110 via SMS(cellphone) the SKU and your bid. the lowest unique bid would win. they had stuff like cars and TVs and dvd players and stuff like that.
If i recall correctly they did show you how many people had currently bid on it on the website. I remember discussing this with my friends and determining that waiting until the last possible moment to bid was the best... and for some reason i kept coming up with 1317 dollars being the best bet.
It's very sneaky that you are using our fantastic minds of math and psychology to get that TV for yourself, though. share the love!
 LE4dGOLEM
 is unique......wait, no!!!!
 Posts: 5972
 Joined: Thu Oct 12, 2006 7:10 pm UTC
 Location: :uoıʇɐɔol
genewitch wrote:45 silver is now around 65 gold in the span of a week
And for those who don't it's basically 4,500 units becomes 650,000 units.
Une See Fights  crayon superish hero webcomic!
doogly wrote:It would just be much better if it were not shitty.
The optimal strategy depends on how many times you'll play the game, and the degree of collusion allowed between players.
Assuming you'll only play it once (with the group in question), and collusion is severely limited or nonexistent, I believe Drostie has the right approach.
Assuming you'll only play it once (with the group in question), and collusion is severely limited or nonexistent, I believe Drostie has the right approach.
I mostly post over at LessWrong now.
Avatar from My Little Pony: Friendship is Magic, owned by Hasbro.
Avatar from My Little Pony: Friendship is Magic, owned by Hasbro.

 Posts: 139
 Joined: Tue Nov 07, 2006 6:36 pm UTC
 Location: Fremont, CA
Puzzle appeared here, with an interesting solution
http://www.greylabyrinth.com/puzzles/pu ... zle_id=206
http://www.greylabyrinth.com/puzzles/pu ... zle_id=206
Restrict the problem so that with N players each player chooses a number on [1..N].
With two players, you have the following payoffs for P1.
(P1,P2) > (P1 Payoff)
1,1>0
1,2>1
2,1>1
2,2>0
P1 has a dominated strategy to choose 1. No matter what P2 does, P1 always does better by choose 1 over 2. While dominated strategies are Nash Equilibriums, they are not particularly interesting ones.
I'm working on a solution for the three person game. I suspect it will be a mixed strategy where you choose 1, 2 or 3 with some decreasing probability.
With two players, you have the following payoffs for P1.
(P1,P2) > (P1 Payoff)
1,1>0
1,2>1
2,1>1
2,2>0
P1 has a dominated strategy to choose 1. No matter what P2 does, P1 always does better by choose 1 over 2. While dominated strategies are Nash Equilibriums, they are not particularly interesting ones.
I'm working on a solution for the three person game. I suspect it will be a mixed strategy where you choose 1, 2 or 3 with some decreasing probability.
I liked this puzzle so much that I felt compelled to write a simulator for this game.
I was wondering which strategy was better  Drostie's or the solution linked by oblivimious.
So here are some results.. How to interpret the chart:
The y axis represents the player's money (every player starts with 100,000).
The x axis represents the number of rounds (in millions).
The ExpoPlayer uses the exponencially smaller probability strategy.
The Drostie playeruses Drostie's strategy.
Draws return the money to the players.
So unless I'm misunderstanding Drostie's post, I think there must be something wrong with his calculations.
Feel free to play with the simulator, it displays the chart in realtime and it can calculate millions of rounds in a matter of seconds (on my laptop).
The source code can be downloaded from http://www.wizy.org/files/luig/.
I was wondering which strategy was better  Drostie's or the solution linked by oblivimious.
So here are some results.. How to interpret the chart:
The y axis represents the player's money (every player starts with 100,000).
The x axis represents the number of rounds (in millions).
The ExpoPlayer uses the exponencially smaller probability strategy.
The Drostie playeruses Drostie's strategy.
Draws return the money to the players.
So unless I'm misunderstanding Drostie's post, I think there must be something wrong with his calculations.
Feel free to play with the simulator, it displays the chart in realtime and it can calculate millions of rounds in a matter of seconds (on my laptop).
The source code can be downloaded from http://www.wizy.org/files/luig/.
Last edited by wizeman on Sat May 12, 2007 12:45 am UTC, edited 2 times in total.
Interestingly, 1 ExpoPlayer wins easily against 2 RandomPlayers (who simply choose 1..3 randomly), but 2 ExpoPlayers don't seem to have any advantage whatsoever against 1 RandomPlayer  see http://www.wizy.org/files/luig/luigresult1.png.
Also, 2 ExpoPlayers win against 2 RandomPlayers, but 3 ExpoPlayers lose to 1 RandomPlayer.
Also, 2 ExpoPlayers win against 2 RandomPlayers, but 3 ExpoPlayers lose to 1 RandomPlayer.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
You are right, I added a ConstantPlayer that always chooses the same number. It doesn't matter which number it chooses, it never wins nor loses against 2 ExpoPlayers.
In fact, the page even says this (I should've read it better).
So I'm wondering why this strategy doesn't work with 4 players. For those of you who are more mathematically inclined than me  what must the probabilities of choosing a number be in this case?
In fact, the page even says this (I should've read it better).
So I'm wondering why this strategy doesn't work with 4 players. For those of you who are more mathematically inclined than me  what must the probabilities of choosing a number be in this case?
Wow. If I played against you guys I would either win the first round or win every round, depending on whether I had to reveal my numbers to everyone else or not, respectively.
That being said, I will now reveal my strategy. He said you had to pick the lowest unique nonnegative integer. So far not one of you has realized that the lowest possible number you can pick is not one, but zero. While you guys were busy trying to pick 1 or 2, I'd be picking 0 and winning every time.
That being said, I will now reveal my strategy. He said you had to pick the lowest unique nonnegative integer. So far not one of you has realized that the lowest possible number you can pick is not one, but zero. While you guys were busy trying to pick 1 or 2, I'd be picking 0 and winning every time.
The difference between intelligence and stupidity is that intelligence has its limits.

 Posts: 10
 Joined: Tue May 29, 2007 1:47 pm UTC
Yakk wrote:(The idea (well, the proof that one exists in all finite games) was worth a Nobel prize, IIRC, so don't feel bad if you missed it.)
You should be clear that this only applies for mixed strategies.
Without mixed strategies, there are plenty of games with no nash equilbrium.
For example, in PaperRockScisors games, there is a Nash equilibrium that is based on each player playing paper, rock, or scissors, exactly one third of the time.
There is no unique (non mixed) strategy for always doing the same thing.
"Good old rock, nothing beats it"  Bart.
"Poor, predictable Bart. Always goes with rock."  Lisa
skeptical scientist wrote:Note that there's no reason to expect that a Nash equilibrium strategy is symmetric.
In general, Nash equilibriums need not be symetric. But in this situation I would hope the sollution would be symetric.
I think it highly unlikely that there could exist a situation in whcih competitors use different strategies, but neither has any motive to switch.
 silverhammermba
 Posts: 178
 Joined: Fri Oct 13, 2006 1:16 am UTC
I don't think there's really too much to gain by having a specific strategy for such a game. Finding a strategy that wins most of the time would have to take into account all the possible numbers of opponents as well as their possible strategies! After all, each strategy has multiple counter strategies that would foil it.
Frankly, I think that with n players your best bet would be to randomly pick numbers between 1 and n1. Then again, this is entirely dependent on the people who you play against and I'm pretty sure there's no mathematical model for predicting other people's actions (psychohistory, anyone?). You could be playing against some crazies who always pick numbers in the triple digits or you could be playing against three people who always stick to 1.
If you were to tell a person to randomly pick integers and plotted them, you'd definitely see patterns emerge. But I'm pretty sure that these patterns would be different from person to person and thus difficult to counter.
There may be a mathematical model that gives an optimal strategy but simply judging by the chaotic nature of the game, I wouldn't think it would have all that much of an advantage.
Frankly, I think that with n players your best bet would be to randomly pick numbers between 1 and n1. Then again, this is entirely dependent on the people who you play against and I'm pretty sure there's no mathematical model for predicting other people's actions (psychohistory, anyone?). You could be playing against some crazies who always pick numbers in the triple digits or you could be playing against three people who always stick to 1.
If you were to tell a person to randomly pick integers and plotted them, you'd definitely see patterns emerge. But I'm pretty sure that these patterns would be different from person to person and thus difficult to counter.
There may be a mathematical model that gives an optimal strategy but simply judging by the chaotic nature of the game, I wouldn't think it would have all that much of an advantage.
The game Uno is basicly the public domain game crazy 8's, branded and packaged.
Similar backstory with Battleship and Monopoly.
Can we brand and package this game?
At what point does one take shots or remove clothing?
Anybody want to get it ready to demo at GenCon?
Is it already trademarked?
Some questions about the rules: do you know how many are bidding?
Do you know if there will be multiple iterations of the game, how many?
Some questions about the simulation:
did it come up with optimum strategies?
Similar backstory with Battleship and Monopoly.
Can we brand and package this game?
At what point does one take shots or remove clothing?
Anybody want to get it ready to demo at GenCon?
Is it already trademarked?
Some questions about the rules: do you know how many are bidding?
Do you know if there will be multiple iterations of the game, how many?
Some questions about the simulation:
did it come up with optimum strategies?
Re: Lowest price auctions PUZZLE
Hey, sorry to necro this topic but I've just had this "problem" come up during one of my classes and thought you guys may find that sort of interesting.
Here's the writeup: (don't worry, I waited to post this here until the relevant work was handed in) Writeup
and the code that goes with: JavaCode
The results aren't out yet but I'll be sure to follow up here and give you guys an idea of what's happened. Have fun with the code.
Cuton
Here's the writeup: (don't worry, I waited to post this here until the relevant work was handed in) Writeup
and the code that goes with: JavaCode
The results aren't out yet but I'll be sure to follow up here and give you guys an idea of what's happened. Have fun with the code.
Cuton

 Posts: 35
 Joined: Tue Oct 16, 2007 9:49 pm UTC
Re: Lowest price auctions PUZZLE
I'm having a problem looking at this as a solely a problem of probability or arithmetics. I see it more of a game of Texas Hold 'Em  an issue of gambling. There is no one perfect solution. To succeed you must know how to react to every situation possible. You must be able to read people and anticipate their movements. All of this comes solely from experience. We all understand the math related to this, but I truly fail to see how this "riddle" can be answered by math. It's like asking which strategy in Chess will help you win  there is no one strategy, you must adapt to all situation (again, this comes with experience).
There are also lurking variables  say, someone playing with an accomplice. One of them just says the number you announce to knock you out, and their buddy goes lower.
It's a psychological and philosophical question, not a mathematical one.
There are also lurking variables  say, someone playing with an accomplice. One of them just says the number you announce to knock you out, and their buddy goes lower.
It's a psychological and philosophical question, not a mathematical one.
Who is online
Users browsing this forum: No registered users and 6 guests