You are currently browsing the monthly archive for June 2014.

Yesterday the Israeli Parliament elected the state’s new president. This position is mostly ceremonial, and does not carry any significant duty. Nevertheless, quite a few people, mostly current and past Parliament members, wanted to get this job. The race was fruitful, as a couple of them were forced to withdraw their candidacy after secrets of weird sex stories and bribes were published in the press.

Three main candidates survived until the final stage, Rivlin, Itzik, and Shitrit (in addition to two candidates who did not stand much chance). Election is done by a two-round system: Each of the 120 Parliament members secretly votes for a candidate. If no candidate gets more than 60 votes, then all candidates except the leading two leave the arena, and the Parliament members secretly vote to either one of the two leaders. The candidate who got more than 60 votes is the new proud president of the state.

Politics was ugly. Rivlin, who is a member of the largest party, was the leading candidate, but the Prime Minister, who comes from the very same party, was against him. Many members of the opposition voted for Rivlin. In the first round, Rivlin and Shitrit got the highest number of votes, but none of them had a majority of votes. In the second round, Rivlin won.

What I found interesting in this process is what one of the Parliament members of the second largest party said. He said that in the first round some members of his party voted for Shitrit, but then, in the second round, they voted for Rivlin. Why? “It was a tactical vote.” This way they ensured that the final election will be between Rivlin and Shitrit and not between Rivlin and Itzik. Politics is ugly, but at least as long as the election process does not satisfy Independence of Irrelevant Alternatives, we do not have dictatorship.

 

Abraham Neyman had numerous contributions to game theory. He extended the analysis of the Shapley value in coalitional games with player set which is a measurable space, he proved the existence of the uniform value in stochastic games, and he developed the study of repeated games with boundedly rational players, among others. Abraham Neyman was also one of the founding fathers of the Center for Game Theory at the State University of New York at Stony Brook, which hosts the annual conference of the community for the past 25 years.

The International Journal of Game Theory will honor Abraham Neyman on his 66th birthday, which will take place in 2015, by a special issue, see the announcement here. Everyone is encouraged to submit a paper.

The Nan-Shan, a Siamese steamer under the control of Captain James MacWhirr, on his orders, sails into a typhoon in the South China Sea. Conrad described the captain as

“Having just enough imagination to carry him through each successive day”.

On board, an all-white crew and 200 Chinese laborers, returning home with seven years’ wages stowed in

“a wooden chest with a ringing lock and brass on the corners, containing the savings of his labours: some clothes of ceremony, sticks of incense, a little opium maybe, bits of nameless rubbish of conventional value, and a small hoard of silver dollars, toiled for in coal lighters, won in gambling-houses or in petty trading, grubbed out of earth, sweated out in mines, on railway lines, in deadly jungle, under heavy burdens—amassed patiently, guarded with care, cherished fiercely.”

Ship and souls driven by McWhirr’s will survive the Typhoon. The wooden chest does not. Its contents strewn below deck, the silver dollars are mixed together. It falls to McWhirr to determine how the dollars are to be apportioned between the Chinese laborers to forestall an uprising.

“It seems that after he had done his thinking he made that Bun Hin fellow go down and explain to them the only way they could get their money back. He told me afterwards that, all the coolies having worked in the same place and for the same length of time, he reckoned he would be doing the fair thing by them as near as possible if he shared all the cash we had picked up equally among the lot. You couldn’t tell one man’s dollars from another’s, he said, and if you asked each man how much money he brought on board he was afraid they would lie, and he would find himself a long way short. I think he was right there. As to giving up the money to any Chinese official he could scare up in Fuchau, he said he might just as well put the lot in his own pocket at once for all the good it would be to them. I suppose they thought so, too.”

My former colleague Gene Mumy, writing in the JPE, argued that McWhirr’s solution was arbitrary. We know what McWhirr’s response would have been:

” The old chief says that this was plainly the only thing that could be done. The skipper remarked to me the other day, ‘There are things you find nothing about in books.’ I think that he got out of it very well for such a stupid man.”

Mumy, undeterred, proposed instead a pivotal mechanism (Clark, Groves, Tidemann, Tullock etc). For each agent compute the difference between the total amount of money and the sum of all other claims. If an agent claims at most this amount, they receive their claim. If his claim exceeds this amount, he is penalized. Mumy showed that truth telling was a full information Nash equilibrium of the mechanism.

Saryadar, in a comment in the JPE, criticizes Mumy’s solution on the grounds that it rules out pre-play communication on the part of the agents. Such communication could allow agents to transmit threats (I’m claiming everything) that if credible change the equilibrium outcome. He also hints that the assumption of common knowledge of the contributions is hard to swallow.

Schweinzer and Shimoji revisit the problem with the observation that truth telling is not the only Nash equilibrium of the mechanism proposed by Mumy. Instead, they treat it as problem of implementation under incomplete information. The captain is assumed to know the total amount of money to be divided but not the agents. They propose a mechanism and identify a sufficient condition on beliefs under which truth telling is the unique rationalizable strategy for each agent. The mechanism is in the spirit of a scoring rule, and relies on randomization. I think McWhirr might have objected on the grounds that the money represented the entire savings of the laborers.

Conrad describes the aftermath.

“We finished the distribution before dark. It was rather a sight: the sea running high, the ship a wreck to look at, these Chinamen staggering up on the bridge one by one for their share, and the old man still booted, and in his shirt-sleeves, busy paying out at the chartroom door, perspiring like anything, and now and then coming down sharp on myself or Father Rout about one thing or another not quite to his mind. He took the share of those who were disabled to them on the No. 2 hatch. There were three dollars left over, and these went to the three most damaged coolies, one to each. We turned-to afterwards, and shovelled out on deck heaps of wet rags, all sorts of fragments of things without shape, and that you couldn’t give a name to, and let them settle the ownership themselves.”

This post is dedicated to a new and important result in game theory – the refutation of Mertens’ conjecture by Bruno Zilliotto. Stochastic games were defined by Shapley (1953). Such a game is given by

  • a set Z of states,
  • a set N = {1,2,…,n} of players,
  • for every state z and every player i a set A_i(z) of actions available to player i at state z. Denote by Λ = { (z,(a_i)_{i ∈ N}) : a_i ∈ A_i(z) for every i} the set of all pairs (state, action profile at that state).
  • for every player i, a stage payoff function u_i : Λ → R, and
  • a transition function q : Λ → Δ(Z), where Δ(Z) is the set of probability distributions over Z.

The game starts at an initial state z^1 ∈ Z and is played as follows. At every stage t, each player i chooses an action a_i^t ∈ A_i(z^t), receives a stage payoff u_i(a_1^t,…,a_n^t), and the play moves to a new state, z^{t+1}, that is chosen according to q(z^t;a_1^t,…,a_n^t).

In this post I assume that all sets are finite. The N-stage game is a finite game, and therefore by backwards induction it has an equilibrium. As I mentioned in my previous post, the discounted game has an equilibrium (even a stationary equilibrium) because of continuity-compactness arguments.

 

Read the rest of this entry »

Recent Comments

Join 120 other followers

Follow

Get every new post delivered to your Inbox.

Join 120 other followers

%d bloggers like this: