The Fractal Prince [Hannu Rajaniemi] — the sequel to The Quantum Thief is a bit of an arabesque (fans of Grimwood or Effinger may like that aspect). There are some interesting ideas about stories/code/viruses in there but some of it felt more like poetic gesture. I rather liked the Oubliette as a setting, but Sirr has some interesting bits too. I found the sequel a bit thinner than the original. Recommended for those who have read the first book and who are fans of the Culture novels of Iain M. Banks.

One Red Bastard [Ed Lin] — Third in the series of police/detective novels about Robert Chow, NYC Chinatown cop. This one focuses on the murder of a mainland representative who was going to smooth the way for Li Na to defect to the US. A fun read, although you probably want to read the first two novels in the series first.

Kingdom’s End and Other Stories [Saadat Hasan Manto] — A collection of short stories by a Pakistani writer who lived through Partition (and hated it, more or less). The stories are often dark, and depict a sordid underlife of violence, sex, and drugs in post-Independence worlds of Bombay and Punjab. I had never encountered Manto before — his sour cynicism is a counterpoint to the kind of knowing parody typical of R.K. Narayan, for example. I also checked out a new book about Manto from the Chicago Public Library.

Railsea [China Miéville] — A young adult book set in a world in which the sea is made up of traintracks and instead of hunting whales people hunt giant moles (moldywarpes). Captains have philosophies — everyone is out to hunt for their Moby Dick. The narrator, Sham ap Soorap, is a well-intentioned but somewhat immature fellow, and the world is just-enough-imagined to make you want to go along with it. A fun read.

No One Makes You Shop at Wal-Mart: The Surprising Deceptions of Individual Choice [Tom Slee] — A popular non-fiction book about how the rhetoric of “individual choice” is woefully misleading. Slee uses simple game-theoretic models to show how information asymmetries, power relationships, externalities, free-riding, herding, and other factors can make rational (and reasonable) individual choices result in (very) poor social outcomes. It’s a nice and accessible description of these results and a useful reminder of how dangerous it is to accept as an axiom that more individual choice is preferable. Collective action is also a choice. Recommended!


Truth in surveying

A few weeks ago I attended Scott Kominers‘s class on Market Design. They were talking about mechanism design and differential privacy so I felt like it would be fun to attend that session. In the class Scott mentioned some interesting work by Nicholas Lambert and Yoav Shoham on Truthful Surveys that appeared at WINE 2008. There’s also some recent work by Aaron Roth and Grant Schoenebeck up on ArXiV.

In Lambert and Shoham’s set up, the opinion distribution of a population is given by some CDF F(x) (with a density) on the unit interval [0,1]. We can think of x as a level of approval (say of a politician) and F(x) as the proportion of the population which has approval less than x. A surveyor selects n agents \{x_i\} i.i.d. from F and asks them to report their opinion. They can report anything they like, however, so they will report \{r_i\}. In order to incentivize them, the surveyor will issue a payment \Pi_i( r_1, \ldots, r_n ) to each agent i. How should we structure the payments to incentivize truthful reporting? In particular, can we make a mechanism in which being truthful is a Nash equilibrium (“accurate”) or the only Nash equilibrium (“strongly accurate”)?

Let A_i = |\{j : r_i  r_j \}|. They propose partitioning the agents into k groups with \mathcal{G}(i) denoting the group of agent $i$, and \tilde{F}_i(x) as an unbiased estimator of F(x) that uses the points \{r_j : \mathcal{G}_j \ne \mathcal{G}_i \}. The payments are:

\Pi_i(\{r_j\}) = \frac{1}{|\mathcal{G}_i| - 1} \left[ A_i - B_i \right] + 2 \tilde{F}_i(r_i) - \frac{2}{|\mathcal{G}_i| - 1} \sum_{j \in \mathcal{G}_i \setminus \{i\} } \tilde{F}_j(r_j)

This mechanism is accurate and also permutation-invariant with respect to the agents (“anonymous”) and the sum of the payments is 0 (“budget-balanced”).

This is an instance of a more general mechanism for truthfully inducing samples from a collection of distributions that are known — each agent has a distribution F_i and you want to get their sample of that distribution. Here what they do is replace the known distributions with empirical estimates, in a sense. Why is this only accurate and not strongly accurate? It is possible that the agents could collude and pick a different common distribution G and report values from that. Essentially, each group has an incentive to report from the same distribution and then globally the optimal thing is for all the groups to report from the same distribution, but that distribution need not be F if there is global collusion. How do we get around this issue? If there is a set of “trusted” agents \mathcal{T}, then the estimators in the payment model can be built using the trusted data and the remaining untrusted agents can be put in a single group whose optimal strategy is now to follow the trusted agents. That mechanism is strongly accurate. In a sense the trusted agents cause the population to “gel” under this payment strategy.

It seems that Roth and Schoenbeck are not aware of Lambert and Shoham’s work, or it is sufficiently unrelated (they certainly don’t cite it). They also look at truth in surveying from a mechanism design perspective. Their model is somewhat more involved (an has Bayesian bits), but may be of interest to readers who like auction design.