Frustration, and more about the jolly game

My bastard computer ate 6 hours of work. Then I tried to backup my stuff to CD and whenever I unplug the supposedly hotpluggable CD burner, my computer crashed.

I'm on Linux, as if you didn't know. Bah. I'm sick of having an operating system built by volunteers. I want a professional product that just works. My idealism has run out.

Now, on to more amusing things. That cheap-talk game. (You don't find abstract game theory interesting? Shame on you.)

Although it is true that there is no equilibrium in which types within different intervals along the circle play different messages, there may be an equilibrium with an infinity of messages. For example, suppose that c = 1/3 (recall that c is the difference between Sender's and Receiver's ideal points on the circle). Then, there is an equilibrium in which the message space M is [0, 1/3) and Senders send a message equal to their type, modulo 1/3. For example, senders with types 1/6, 1/2 and 5/6 would all send m = 1/6.

Receiver's best response is then any mixed strategy having as its support only actions with the possible values of Sender's type t. For example, if m = 1/6, Receiver can play any combination of 1/6, 1/2 and 5/6. The expected distance from sender's type of any one of these actions is (1/3 * 0 + 1/3*1/3 + 1/3*1/3) = 2/9. The expected distance from sender's type of any other action a is greater than this. The simplest way to see this is to imagine the three possible values of t. By moving Receiver's action a away from one of these values, two of the values get farther away, while one of them gets closer:

Now we consider Sender's best response to Receiver's strategy. First note that if Receiver plays, say "2/3" with probability 1 on receiving m = 0, but randomizes over all 3 possible types for e.g. m = 1/10, then when t = 1/3+1/10 it will be more sensible to send m = 0 (guaranteeing a response close to her bliss point) than the assumed strategy of m = 1/10. So we focus on the case when Receiver randomizes with equal probability over all 3 types, for all messages m in [0,1/3).

In this case, the logic above also holds true for Sender's utility. By sending a message reflecting her true type, she elicits a best response of one of her three possible types. The logic for Sender is just as for Receiver: this has a one in three chance of being at her bliss point (at t+c, where t+c is one of the three possible types) and a 2/3 chance of being 1/3 away; any alternative message would generate a greater expected distance from t+c. Thus, honesty is a best response to Receiver's strategy, and we have our Bayesian Nash equilibrium.

The same logic holds whenever c = 1/n, and n is odd. Then, any message m in [0,1/n) where m corresponds to t modulo 1/n will generate a best response of choosing one of the possible types: any move away from a possible type moves (n+1)/2 of the possible types away from you, and (n-1) towards you, all by the same distance.

On the other hand, when n is even, the equilibrium remains technically but is much less plausible. Now all Receiver's strategies are equally good, because moving action a away from a possible type brings n/2 possible types closer while n/2 move farther away by the same distance. The case with n=4 is shown below:



The equilibrium remains, technically, because choosing a equal to some possible value of t is still a best response. But there would be no incentive, in the long term, for Receiver to play this equilibrium. When n is odd, there are plenty of best responses that don't lead to equilibrium (such as mixed strategies where Receiver doesn't always randomize equally between points) but in the long term one might expect Receiver to play "nicely" in order to keep the flow of useful information going. (I don't know if anyone has toyed with repeated cheap-talk games.)

Before moving on to the general case, where c does not "fit neatly" into the circle, it is worth pointing out that here, as c decreases, the potential equilibria are getting less informative rather than more, in the following two senses:

1. The message space for e.g. c = 1/5 is [0,1/5), which is a proper subset of the message space for c = 1/3, [0,1/3).
2. The expected distance from Receiver's (and Sender's) ideal point, when c=1/n, is (n^2-1)/4(n^2). This increases as n increases, with a limit of 1/4. For example, expected distance when c = 1/3 is just 2/9, when c = 1/5 it is 6/25.

Of course, the fact that, in this family of games, one particular kind of equilibrium gets less informative as conflict of interest decreases doesn't prove that the most informative equilibrium gets less informative. Perhaps there is a wholly different sort of equilibrium I haven't yet thought about, which improves on this one. Intuitively, I doubt it because it seems to me that strategies with an infinite message set are unlikely to improve on the "message sending modulo c" equilibrium without generating potential cheating. It would be nice to prove that this is, indeed, the most informative equilibrium possible. Then we would have a counterexample to the idea that talk always gets more informative as conflict of interest decreases.

That's all for now. Next post, I'll have a shot at the general case. I suspect this will also have an equilibrium of some kind.

A jolly little cheap-talk game

This is just to show off my newly-acquired skills from ICPSR summer school. If you aren't into game theory it will mean nothing to you - you have been warned!

The standard cheap-talk game, found e.g. in Morrow, has Sender's type t drawn from a uniform distribution on a unit interval: t ~ U[0,1]. Sender sends a message m from some set of possible messages M; then Receiver chooses an action a from that same unit interval. Receiver's utility declines monotonically, continuously and symmetrically with the distance of a from t, e.g. UR(a) = - (t-a)^2. In effect Receiver is trying to guess Sender's type. Sender's utility declines monotonically, continuously and symmetrically with distance of a from some point t+c, where c>0 and measures some conflict of interest. For example, Sender's utiliy might be US(a) = - (t+c-a)^2. So Sender wants Receiver to guess Sender's type, but be a little bit off.

It then turns out that if c is small enough, there are informative equilibria where different ranges of types send different messages (so that Receiver can infer something about Sender's type); and as c shrinks the maximum number of messages in a potential equilibrium increases. It's a nice prediction - communication gets easier when there are common interests to rely on.

But now consider this jolly little variation. (I should warn you at once that I can think of no substantive applications, but it's food for thought in any case.)

Suppose that Sender's type is still drawn from U[0,1], but now we think of it as being defined on a unit circle, with distance defined as the shortest possible way round the circle. So now, for example, choosing a = 1 when t=0 would be a very good action for Receiver, as this would give a-t=0.

Now there is no equilibrium in which Senders with t in different sub-intervals send different messages, no matter how small c is. (I am not sure I can prove that there is no informative equilibrium at all. Perhaps there's one in which a continuum of possible messages are sent, informing R about the value of t modulo c, or something similar.)

Proof

Suppose that there are n different sub-intervals around the circle; Senders with t in any of these sub-intervals send different messages. Let's take an arbitrary pair of adjacent sub-intervals (x,y) and (y,z), sending messages m1 and m2. As usual, since t is uniformly distributed, Receiver's best responses are a1 = (x+y)/2 and a2=(y+z)/2. And, as usual, because Sender's utility function is continuous w.r.t. a, Senders at the boundary where t = y must be indifferent between a1 and a2.

Therefore, it must be the case that the distance from a1 to y+c (Sender's ideal point when t=y) is equal to the distance from a2 to y+c. And so the boundary point y must be closer to the midpoint of (x,y) than to the midpoint of (y,z); and so the interval (y,z) must be larger than (x,y).


But this must be true for all intervals round the circle, which is clearly impossible. (If there is a finite number of intervals, n, then the nth interval must be bigger than the n-1th interval, which itself is bigger than the n-2th interval and so on down to the first; but it must also be smaller than the first interval which is adjacent to it. If there are an infinite number of intervals, then choose an arbitrary selection of 2 or more points on the circle and consider that the size of the intervals containing these points must continue to increase as you move clockwise around the circle. I think this works. Hey, it's a blog, and I'm only writing this to avoid real work.) QED.

Note that nothing here depends on the exact geometry of the "circle". The proof works for any interval with distance defined in an appropriately circular fashion. (But, as I said, what the hell are the substantive applications? A hunter is chasing an elephant, which itself is chasing a bear around a big lake; he wants his friend to slay both elephant and bear, but his friend only wants to tackle the elephant. Oh Lord. Answers on a postcard?)

and on the other hand

7.50 this morning we get dear old Rabbi Blue on Thought for the Day, an exemplar of kindness, humour and good sense.

2am eternal

It's 2 am. On the world service: "Reporting Religion".

First up, two rabbis discuss the meaning of Zionism. One of them believes that compromise over the status of Jerusalem is impossible, because the Jewish people have a contract with God.

Next: Delhi is being overrun by monkeys, who have been e.g. attacking children. The monkeys cannot be harmed because they are sacred, in fact divine.

And finally, does the Koran contain truths only recently discovered by Western science? A columnist in an Egyptian newspaper thinks so, and has a page of scriptural reinterpretation every week.

The traditional response to idiocies of this kind has been something like "religion and science deal with different, incommensurable kinds of truth". Here's an alternative way to look at it. All the three ideas above involve empirical claims, which are more or less testable... and completely preposterous. Monkey Gods, contracts between God and his "chosen people", quantum physics hidden in the Koran code: what serious person can regard these ideas with anything but contempt?

There are some complex explanations of the "revenge of God", the resurgence of religion over the past fifty years. Here's a simple one, which I'm sure cannot be the whole truth: enlightened, thoughtful people took their eye off the ball. The others got so angry when we disputed their stories, that it became easier just to go along and to pretend that there was no fact of the matter in these areas. So the nutters grew louder, more confident and madder than ever. Now we should learn our lesson. When someone talks nonsense, we should stand up and call it nonsense to its face.

In NY again

So I'm back in New York. This time I haven't managed to fall on my feet like the last two times: instead I rented a flat off craigslist.com and am in a nice area of Brooklyn, but still not as nice as downtown Manhattan. It has a pretty little courtyard and I'm sitting out there in the dark, leeching someone's wifi as usual. I would take a photo of it... but when I picked up my baggage from the Northwest Airlines flight, my camera was not in it. I'm not happy at all. That was the most valuable thing I owned, and a gift from my brother. NWA had a strike the day I went out, and I guess they had hired temporary baggage handlers. Draw your own conclusions.

Quote

There have been abundance of people, in all ages of Christianity, who tried ... to convert us into a sort of Christian Mussulmans, with the bible for a Koran, prohibiting all improvement: and great has been there power, and many have had to sacrifice their lives in resisting them. But they have been resisted, and the resistance has made us what we are, and will yet make us what we are to be.

-- John Stuart Mill, The Subjection of Women (1869)

A Room of One's Own

I've just read Virginia Woolf's A Room of One's Own for the first time. What an astonishing book. It's only about a hundred pages long, but like one of those pop-up birthday cards, it unfolds to reveal a very intricate architecture, containing in miniature almost the whole programme of feminism from that day to this: anger at inequalities of power, wealth and privilege, and examination of their roots; a call for a women's history; a sceptical focus on men's “knowledge” of women; mistrust of simple ideas about the sexes; interest in relations among women where men stop being the focus. As if she just knew! The book – it was originally meant for a lecture to undergraduate's at the women's colleges of Girton and Newnham – is full of casual asides as to how a student might profitably look at, say, the domestic history of the Elizabethan household, or the psychology of women's art.

The idea that culture has material foundations, that you need a room of your own and five hundred pounds a year to be a poet, is a Bloomsbury theme, it comes out in Howards' End too. The Bloomsbury people's intellectual elitism and passionate love for higher things combined with this intense awareness to make them more egalitarian, funnily enough. If you think pushpin is just as good as poetry then the fact that some people are poor and others rich doesn't really matter much, especially as everybody is getting richer together. But if you think Art and Beauty and above all good Conversation are the most important things in the world, then it matters terribly. (So I suppose that the Blair government's artistic policy of “access” is another way in which the powerless little clique has conquered the world.)

Did they conquer the world? If you could trace back the lineage of the spiky-haired gothic brats in Camden Town, and the elegant loft-dwellers of Manhattan or Hoxton, and the pot-smoking first-homers in small towns everywhere – of everything alternative or bohemian or unconventional, which by now includes almost everything in contemporary culture, would you find the little Cambridge gang of lesbians and nutters? I would like to think so.

Here are two quotes which make me very happy.

Meanwhile the wineglasses had flushed yellow and flushed crimson; had been emptied; had been filled. And thus by degrees was lit, halfway down the spine, which is the seat of the soul, not that hard little electric light which we call brilliance, as it pops in and out upon our lips, but the more profound, subtle and subterranean glow which is the rich yellow flame of rational intercourse. No need to hurry. No need to sparkle. No need to be anyone but oneself.

So long as you write what you wish to write, that is all that matters; and whether it matters for ages or only for hours, nobody can say. But to sacrifice a hair of the head of your vision, a shade of its colour, in deference to some Headmaster with a silver pot in his hand or to some professor with a measuring-rod up his sleeve, is the most abject treachery, and the sacrifice of wealth and chastity which used to be said the greatest of human disasters, a mere flea-bite in comparison.

Reading books like this could be a very bad idea. After spending a few hours with Virginia Woolf, you may not want to spend time with anyone else, and you may not care about anyone else's good opinion. Then you will be cursed with the worm that dyeth not, of permanent dissatisfaction, because there aren't many people like that in the world.

But she's wrong about the silver pot. The trick is to want praise and commendation from the right people.

addictive?

Planarity

and on a similar note...

The semicolon: half-assed by definition.

Style tips #1:

Never use a punctuation mark named after part of your ass.

You know you're at ICPSR when...

... you've been working till 11 and you get out of Helen Newberry building and head home... but at midnight, your flatmate says, "hey, let's go to Rendezvous and work", and you find yourself sitting in the Rendezvous cafe doing equations until 2.30.

Good night!