Let f(n) be a non-decreasing function from naturals to naturals. Consider the following game:
Let n be a large natural number. Mark and Betty alternate (Mark goes first) putting M's and B's on an n by n checkerboard. No square can have two markers on it. They play until all squares are covered; hence the game will end after n2 moves. If at the end there is some row or column A where the number of M's in A is at least n/2 + f(n) then Mark wins! If not then Betty wins! (NOTE- the M's in A do not have to be adjacent.)I asked for your intuitions on when Mark or Betty have a winning strategy. Here are the answers and a pointer to my writeup of it. NONE of this is my work- it is all the work of J.Beck (the reference is in the writeup). Here are the results:
- If f(n) ≤ O(\sqrt(n)) then Mark has a winning strategy.
- If f(n) ≥ Ω(\sqrt(n log n)) then Betty has a winning strategy.
- My writeup is here. If I fill in more details it may change.
My writeup of the first result is complete. I included more detail then you usually get in a math paper. I do not know if this is good or bad; however, I really wanted to check it all for myself. My writeup of the second result is much sketchier; however, it is essentially Beck's proof.
Beck has a book on games of this nature entitled Combinatorial Games: Tic Tac Toe Theory. Will children buy it thinking it is about tic-tac-toe? Maybe Bill Gates' kids: the book costs $146.00 new and $107.00 used.
Would it have any interesting consequences to close the gap?
ReplyDeleteIn the write-up I am confused on one point: Once there is a good row or column you write that Mark always plays there but you also say that the game runs for n^2/2 rounds. Won't the row be filled up long before that?
ReplyDeleteOk, I am looking at Beck's work now, it seems that these questions are "interesting for their own sake", going back to Erdos...
ReplyDeleteBut besides Jozef Beck himself, would anybody else care about closing the \sqrt(log n) gap?
If there is an expert here, please let me know whether/why this is (not) interesting. Thanks!
Apparently, I didn't follow up with the further intuition that I had. I am surprised by the fact that Betty's position is asymptotically defensible at all. My sense was that at some [finite] board size, regardless of f(n), Betty's position would be become hopelessly indefensible.
ReplyDeleteAnon 2- Oh, good point, once row or col is filled up and Ben has
ReplyDeletethe required surplus the game ends,
so it need NOT go n^2/2 turns.
Thanks for the correction.
Others- as for who cares about this game or closing the gap,
INSERT USUAL ARGUMENTS WHY IT IS GOOD TO STUDY QUESTIONS WITH NO
IMMEDIATE APPLICATION.
It was Reinhard Selten who memorably remarked that "Game theory is for proving theorems, not for playing games."
ReplyDeleteSelten was articulating a Great Truth, in the sense that its converse is a Great Truth too. The point being, it is *not* necessary that everyone do mathematics with the same motives (whether pure or applied) ... such uniformity would not even be desirable.
Similarly, von Neumann advocated a mixed strategy (1947): "When (mathematical style) becomes baroque, then the danger signal is up ... the only remedy seems to me to be the rejuvinating return to the source: the reinjection of more or less directly empirical ideas. I am convinced that this is a necessary condition to preserve the freshness and vitality of the subject, and that this will remain equally true in the future.''
Ooh, I have a question!
ReplyDeleteLet f(n) be some nondecreasing function again.
Suppose the players now alternate playing on an *infinite* board. Mark wins if at any point there is some row/column A, and some n, such that Mark's additive surplus in the first n entries of A exceeds f(n).
When does Mark win?
Of course, Mark can pick any target n and borrow a strategy from the finite game; so he wins for some f(n) = Omega(sqrt(n)) by the known result.
The question is whether Betty can win for some f(n) not too much larger than sqrt(n). It might be possible to adapt the known Betty-strategy to work for all n simultaneously; I just don't have time to study the question. (Nice posts by the way.)
OK, it looks like you can easily take any family of Betty-strategies successful against f(n) in the finite game, and combine them into one successful against O(f(n)) in the infinite game.
ReplyDeleteAny news about this new claim of P!=NP?
ReplyDeleteit seems the whole umd website is down for a while, so i can't access the writeup. really like to take a look though.
ReplyDeletehttp://www.hpl.hp.com/personal/Vinay_Deolalikar/ .... did he really prove P != NP??
ReplyDeleteHere is a 100-page writeup of the proof:
ReplyDeletehttp://www.scribd.com/doc/35539144/pnp12pt
It uses the FO(LFP) characterization of P and claims that any P algorithm must miss some fraction of some kind of SAT instances. The background sections on complexity are sensible. He's a mathematician with a respectable record but no published prior work in complexity. Which either means that he's made some naive mistake coming from the outside, or that his being outside our community gives him some special insight. Or both...
I don't see any obvious reason this couldn't be right, though of course the way to bet is that it's wrong...
Dick Lipton has now posted something on the proof:
ReplyDeletehttp://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/
bill + lance, can you make sure to have an updated blog post at the end of the day (okok I aint pushy, maybe in a few days then) with something on that paper everyone is talking about.
ReplyDeleteIt has generated enough hype to warrant a post at the prestigious weblog.fortnow.com site.
xxx
x
Anon who wants a copy of my manuscript on the game- email me your email address and
ReplyDeleteI'll email it to you (unless you already
have it).