Lowest price auctions PUZZLE

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
Drostie
Posts: 262
Joined: Fri Nov 03, 2006 6:17 am UTC

Postby Drostie » Wed Apr 04, 2007 3:38 am UTC

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 1-q, and you do the same with probabilities p and 1-p, then this suggests that your win rate with two players, W(2), is equal to:

W(2) = p * (1-q) + (1-p)(1-q) 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 * (1-q) / [1 - (1-p)(1-q) ]

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 = ( (1-q)(1 - (1-p)(1-q)) - p * (1-q) * (1-q) )/ [1 - (1-p)(1-q) ]^2

dW(2)/dp = q (1-q) / [1 - (1-p)(1-q) ]²

*Now* you may set p = q, and set this whole thing to 0, to get:

p (1-p) / [1 - (1-p)² ]² = 0

p (1-p) / [1 - (1-2p+p²) ]² = 0

p (1-p) / [2p-p²]² = 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 1-q, and p does the same for me.

Building up my win rate, I get:

W(3) = p*(1-q)^2 + (1-p)*q^2 + (1-p)(1-q)^2 W(3)

W(3) = [p*(1-q)^2 + (1-p)*q^2] / [1 - (1-p)(1-q)^2]

Taking a derivative with respect to p gives:

dW(3)/dp =

{ [(1-q)² - q²] [1 - (1-p)(1-q)²] - [p*(1-q)² + (1-p)*q²] [(1-q)²]}/[1 - (1-p)(1-q)²]²

Settin q=p gives:

{ (1-2p)[1 - (1-p)³] - [p*(1-p)^4 + (1-p)³ p²] }/[1 - (1-p)³]² = 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 root-finding 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*(1-P)
3 with probability P*(1-P)²

Et cetera.

You can confirm that, indeed, when everyone plays this strategy, nobody can "game the system," as it were. Go ahead. Play always-1. It won't help.

A general-case solution for n is much harder to get at, because you may have W(i) dependent on W(i-2N) 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(i-2N)).

cjr
Posts: 15
Joined: Wed Jan 10, 2007 6:29 pm UTC

Postby cjr » Fri Apr 06, 2007 10:39 am UTC

*bows down*

User avatar
genewitch
Posts: 298
Joined: Sun Feb 25, 2007 2:28 am UTC

Postby genewitch » Mon Apr 09, 2007 10:57 am UTC

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 non-academic 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 13-17 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!

User avatar
LE4dGOLEM
is unique......wait, no!!!!
Posts: 5972
Joined: Thu Oct 12, 2006 7:10 pm UTC
Location: :uoıʇɐɔol

Postby LE4dGOLEM » Mon Apr 09, 2007 11:31 am UTC

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.
Image Une See Fights - crayon super-ish hero webcomic!
doogly wrote:It would just be much better if it were not shitty.

User avatar
Macbi
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

Postby Macbi » Mon Apr 09, 2007 11:45 am UTC

My strategy for games like this is that since everyone has the same optimum strategy you should go for that and then lie like crazy to confuse everyone else.

User avatar
genewitch
Posts: 298
Joined: Sun Feb 25, 2007 2:28 am UTC

Postby genewitch » Mon Apr 09, 2007 12:27 pm UTC

LE4dGOLEM wrote:
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.

right. I totally forgot to convert for people. Thanks golemguy

User avatar
Vaniver
Posts: 9422
Joined: Fri Oct 13, 2006 2:12 am UTC

Postby Vaniver » Mon Apr 09, 2007 7:32 pm UTC

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.
I mostly post over at LessWrong now.

Avatar from My Little Pony: Friendship is Magic, owned by Hasbro.

oblivimous
Posts: 139
Joined: Tue Nov 07, 2006 6:36 pm UTC
Location: Fremont, CA

Postby oblivimous » Tue Apr 24, 2007 6:32 pm UTC

Puzzle appeared here, with an interesting solution

http://www.greylabyrinth.com/puzzles/pu ... zle_id=206

Alan
Posts: 39
Joined: Thu Feb 08, 2007 9:09 pm UTC

Postby Alan » Tue May 01, 2007 10:56 pm UTC

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.

wizeman
Posts: 3
Joined: Fri May 11, 2007 8:11 pm UTC
Location: Portugal

Postby wizeman » Fri May 11, 2007 8:50 pm UTC

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 real-time 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.

wizeman
Posts: 3
Joined: Fri May 11, 2007 8:11 pm UTC
Location: Portugal

Postby wizeman » Fri May 11, 2007 8:56 pm UTC

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/luig-result1.png.

Also, 2 ExpoPlayers win against 2 RandomPlayers, but 3 ExpoPlayers lose to 1 RandomPlayer.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Postby jestingrabbit » Fri May 11, 2007 9:58 pm UTC

wizeman, have a look at what happens if you just pick a number and play that against a pair of expoplayers. Its a feature not a bug.

wizeman
Posts: 3
Joined: Fri May 11, 2007 8:11 pm UTC
Location: Portugal

Postby wizeman » Fri May 11, 2007 10:09 pm UTC

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?

User avatar
HiEv
Posts: 37
Joined: Wed Apr 11, 2007 7:45 am UTC

Postby HiEv » Mon May 14, 2007 5:50 am UTC

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 non-negative 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. :twisted:
The difference between intelligence and stupidity is that intelligence has its limits.

northern_bear
Posts: 10
Joined: Tue May 29, 2007 1:47 pm UTC

Postby northern_bear » Tue May 29, 2007 5:44 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 Paper-Rock-Scisors 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.

User avatar
silverhammermba
Posts: 178
Joined: Fri Oct 13, 2006 1:16 am UTC

Postby silverhammermba » Thu May 31, 2007 4:46 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 n-1. 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.

User avatar
arbivark
Posts: 531
Joined: Wed May 23, 2007 5:29 am UTC

Postby arbivark » Wed Jun 06, 2007 11:18 pm UTC

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?

User avatar
Cuton
Posts: 168
Joined: Tue Jun 19, 2007 5:11 pm UTC
Location: Waterloo, Ontario

Re: Lowest price auctions PUZZLE

Postby Cuton » Wed Oct 24, 2007 6:58 pm UTC

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 write-up: (don't worry, I waited to post this here until the relevant work was handed in) Write-up
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

Gyvulys624
Posts: 35
Joined: Tue Oct 16, 2007 9:49 pm UTC

Re: Lowest price auctions PUZZLE

Postby Gyvulys624 » Wed Oct 24, 2007 10:27 pm UTC

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.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 10 guests