saforrest

12:31 pm: Strip iterated prisoner's dilemma
Today's xkcd leads inevitably to the shockingly unexamined question: what would a strip version of iterated prisoner's dilemma look like?

The key requirement for prisoner's dilemma (stealing shamelessly from the Wikipedia article) is the relation T > R > P > S, where T is the temptation to defect, R is the reward for mutual cooperation, P is the punishment for mutual defection, and S is the sucker's payoff.  Obviously if the outcome is mutual cooperation or defection both players share either R or P respectively; otherwise, the defector gets T while the sucker gets S.

Now, competitive strip-based games usually have three outcomes: opponent strips, player strips, nobody strips.  The first two outcomes are nicely one-sided thus fit with T and S.  But what outcome should mutual cooperation and mutual defection map to?

At first I was thinking that in the case of mutual defection both players should both take clothing off and that would be a fitting punishment for their shared treachery.   But it's not clear to me that this is a worse outcome than both keeping clothing on.  I guess the question is really whether a player's personal sense of shame matches or exceeds his or her interest in seeing the other player less clothed.  If "yes", then "mutual cooperation" should correspond to keeping clothing on and "mutual defection" should correspond to mutual stripping.  If "no", then the situation should be reversed.  It goes without saying that the players should both have the same answer to this question and if they don't, the game will be unbalanced.

Tags: prisoner's dilemma

10:55 am: A graph-theoretic question
Given my friends list this is as good a place as any to post math questions, so here goes:

I have a undirected graph G=(V,E) and I also have a natural total order ≤ on the set V. With this I can immediately produce a directed acyclic graph G₂=(V,E₂) where, for x,y ∈ V, there is a directed edge from x to y in E₂ (written x→y ∈ E₂) whenever there is an edge from x to y in E and x ≤ y (in the total order).

I am looking for cliques in the original graph. I know the maximum clique problem is NP-complete, but I'm hoping I can exploit the total order to solve the problem with way less work. Specifically, I'm looking for the largest set S ⊆ V such that for every x,y ∈ S, x ≤ y implies x → y ∈ E₂ and y ≤ x implies y → x ∈ E₂. That is to say, every node in S is incident with every other node in S in a way respecting the total order. S will form a clique in the original undirected graph G.

Does this sound like a familiar problem? I'm no expert on graph theory would have expected there to be a fair amount of literature on directed analogues of the clique problem, but can't find any description of it.

I'm also wondering if my expectation that this is a simpler problem than the undirected clique problem is naive. It seems simpler, and the total order suggests that I should be able to break up the graph into subpieces and solve the clique problem on this smaller set, then hook the cliques together.

However, I don't see how it involves any loss of generality and that concerns me. Even though my total order is a natural one which the problem itself imposes, if there's truly no loss of generality then it would be possible to solve the clique problem on any graph simply by choosing an arbitrary total order and employing this newly-created 'special structure' which seems very fishy. It may be that there's something further specific to my problem which imposes special structure that I haven't captured in this description.

Tags: clique, graph theory, math

11:08 pm: Thunderstruck
“Tory MPs seemed thunderstruck late Thursday by the possibility that their second term might come to a sudden end. As some of them piled onto a parliamentary shuttle bus, they were heard incredulously asking opposition MPs if they're serious about a coalition.”

I wonder if this choice of words might be a subversive reference to our Right Honourable leader's favourite song?

Tags: politics

01:16 pm: Your mom is a supermassive object
After reading this XKCD comic, I was very surprised to see that a Google query for "your mom" and "supermassive object" turned up only three hits.
( Read more... )

12:00 am: Quote from Clemenceau
"Une dictature est un pays dans lequel on n'a pas besoin de passer toute une nuit devant son poste pour apprendre le résultat des élections."

It's midnight; think I'll go to bed now.

Tags: federal election

09:58 am: Putting the Mean back in Mean Value Theorem
Hmm, I can't think of another recent case of such a direct instance of the Mean Value Theorem being applied so visibly.

I know photo radar really does the same thing. However, because the time points in photo radar are so much closer, in the popular mind it's measuring instantaneous velocity rather than computing an average. It's all the same, really, but I expect with the "average speed" cameras people will feel the victims of oppressive mathematics rather than believe they were fairly caught out.

I wonder what the response would be if a believer in constructivist mathematics responded to an automated speeding ticket with a demand for a witness?

Tags: law, mean value theorem

05:35 pm: Too-fast indexing from Google?
At 17:15 EST, I created a Wikipedia article about a Rwandan government minister. In the interests of adding more content, I happened to be googling the subject of the article. My Wikipedia article, then less than 15 minutes old, came up as the second hit.

I suppose Google's indexing bot might have hit the page and updated its search cache in those 15 minutes, but that seems a little implausible, no? I find this search result to be rather creepy. My first ill-conceived paranoid thought was that my being logged in to Gmail had somehow enabled Google to monitor my Wikipedia edits, but I suppose the more natural and innocent explanation is that Google is using the Recent Changes RSS feed from Wikipedia to update its own search results.

Still, I wasn't aware that Google employed site-specific change tracking like this. And wouldn't such an indexing strategy generate an awful lot of false hits owing to constant vandalism of Wikipedia? Perhaps they have a more refined strategy, such as updating based on all edits from 15 minutes ago that have not since been reverted.

Tags: google, wikipedia

12:12 am: Adoption law followup
In my last adoption-related post, I said that I hoped the Liberals would resolve the present legal morass with an amendment including a disclosure veto. Seems I got my wish there.
( Read more... )

Tags: adoption disclosure

12:05 pm: On being adopted
It feels strange to be part of a small minority which is directly and uniquely affected by provincial legislation, but this is the case.

Being adopted (and yes, for me it is a question of being rather than having been) is a strange sort of "optional minority" status: a truth which I can selectively reveal but of which I am always aware, even if I don't always think of it. Both my sister and I were adopted, so there were no blood relatives in my immediate family: even now I still find watching two relatives to be a novelty. Of course, a large part of this interest comes from speculating about my unknown birth relatives. I know a little about them, thanks to the Non-Identifying Infomation which was released to my parents when they adopted me; the idea is to paint a picture of the birth family, short of giving enough to find them.

Which is of course exactly what I want to do. ( Read more... )

Tags: adoption disclosure

02:33 am: Modus ponens
I was going to say something about the allegations of undercover police at Montebello; while I'm sure that more than enough virtual ink has already been spilled on that, I thought after watching the video, I had a couple more complex arguments about why those three “protesters” were indeed police that I hadn't seen expressed elsewhere.

But while looking in Google News for the original story, all my arguments crumbled away like old cobwebs as their existence was now quite unnecessary.
( Read more... )