*Abstract: *

Imagine a group of people that need each day to make some collective decision (for the entire group), choosing one of two options A and B. Some people prefer A, some prefer B, and others are OK with any of the two options. (The next day the preferences may change arbitrarily, and a new group choice is made.) The group management needs to choose A or B, in both cases making some people unhappy. This cannot be avoided completely (if someone wants A and someone else wants B, one of them will be unhappy), so the goal is more modest: each person should not be unhappy too many times.

Even this modest goal may be hard to achieve: if one person always wants A, and another person always wants B, then one of them will be unhappy at least T/2 times during a T-day period. To ensure that this kind of obstacle does not appear, let us make an additional assumption. We say that two people are in a conflict at some day d if one of them wants A, and the other one wants B. (The people that are OK with both options do not conflict with anyone.) The additional assumption: for every pair of people there is O(1) days where they are in a conflict.

We show that there exists a strategy which makes every person unhappy at most sqrt{T} * polylog(N) times, where N is the size of the group. This bound is optimal, but our proof is very strange and somehow follows from inequalities about Kolmogorov complexity. In particular, it does not give an efficient explicit strategy. Kolmogorov complexity is often used as a tool to prove combinatorial results but, in most cases, one can reformulate the argument in terms of counting, or probabilities, or Shannon entropies, or at least find an alternative purely combinatorial argument. We do not know how to do this in this case. So far, using a combinatorial argument, we only obtained a worse bound T^{2/3} * polylog(N) by analyzing the multiplicative weight algorithm.

Venue: Sala de Seminario John Von Neumann, CMM, Beauchef 851, Torre Norte, Piso 7.

Speaker: Alexander Kozachinskyi

Affiliation: Pontificia Universidad Católica de Chile

Coordinator: José Verschae