COMSOC Days 0, 1

NOTE: The entire conference report is available as a guest post on Noam Nisan’s blog.

I am in Dusseldorf for COMSOC 2010. The LOGICC tutorial day was yesterday and the first full day today. It is a good way to meet many people in a short time. The organizers are doing a good job overall. All talks today had a good or very good standard of presentation. The most interesting talks in my opinion:

Nicholas Tideman: after long experience, claims that spatial models are the best for modelling real voter behaviour. Discussed difficulties of obtaining real data and had plenty of computational problems to offer the audience, often involving Gaussian quadrature. Challenged us to generate fake elections that he could not distinguish from real ones.

Gabrielle Demange: has a new ranking method which she has characterized axiomatically. Ranking methods focus attention of the rankers, and there is a dynamic process which converges in some cases.

Tyler Lu: interpolate between social choice and full personalized recommendations. Isomorphic to theory of fully proportional representation. Hardness results, greedy algorithms, approximation algorithms.

Matthew Jackson: in experiments, if you offer people $100 now or $200 in 2 years, most take the $100. But if you offer $100 in 6 years or $200 in 8 years, they take the $200. This is inconsistent with standard rational models. Main idea is that perhaps each person has several “personalities”, some with more patience than others. He showed that in that case, this kind of inconsistency is basically inevitable (impossibility result like Arrow, but easier to prove).

Toby Walsh is giving a ridiculously large number of talks. One good idea he had is a standard library of benchmark election data for testing algorithms.

Plenty of complexity and especially parametrized complexity results.