Archive for July, 2010

GAME 2010 (part 3)

Today is raining. Usual.
In the past days Eva Tardos has presented a lot of interesting stuff.
For instance, she has talked about congestion games. In these games
a meaningful function (e.g., a cost, a response time, a delay) depends
on the load of some structure. We can think about the time necessary
to travel on a road depending on the traffic level, or the delay of running
of a process on a CPU in a load balancing scenario.
These kinds of problems turn out to be equivalent to the problems using
a potential function. Which have the nice property that a Nash equilibrium
exists for the game, if and only if the potential has a minimum. Moreover
Nash equilibria are local minima of the potential. Apart from the equivalences,
since the change in potential can be expressed using the change of
congestion seen by a single user (the change in the traffic of a road seen
by a user, when he changes the road he is travelling on), and since the
potential can be used to approximate the cost of Nash equilibrium,
using a congestion function is a natural choice in order to bound the quality
of the equilibrium.
Moreover, we can consider an infinite amount of infinitesimally small users,
moving the problem in the field of continuous. Besides being able to
analyze the problem with the tools of continuous math, in this framework
are clearly, under a mathematical point of view, identifiable the selfish and
the altruistic contribution to the welfare of the users, when a user moves,
modifying in this way the congestion of the structure. (so when an
infinitesimally part of flow of traffic moves from one road to another one).

In two days I will be at the Βόσπορος again.

GAME 2010 (part 2)

In the past days, Maria Florina Balcan has talked about machine learning in connection
with game theory. So one can imagine iterated games, played in turns, in which every
player learns from the outcome of his moves and the moves of his adversary.
The extension of some machine learning techniques to game theory is quite natural.
Think at the problem of making choices when aided by a group of experts (but we should
call them good chaps instead, since they may know nothing about the topic they are
giving advices…). One is willing to listen to the various advices, but would be happy
to be able to follow only the best possible advisor’s suggestions (the one who makes
the smallest number of errors). Ex ante it is not known who is the most reliable
advisor, so a way of letting the least expert among the experts is needed. This can
be achieved, for example, reducing progressively the weight of those experts who
make errors, so that their advice influences less the decision we will take.

Today Deng Xiaotie has told us about a new, for me, complexity class: PPAD
(guess who has introduced this class?).
Caught as usual by the argument, I harassed the poor Deng with many questions…
The PPAD class contains many problems that are also hard for the class. In
particular it contains the \textsc{Nash Equilibrium} problem, as well as
\textsc{Another End of Lines}, which graciously reduces to \textsc{Sperner}
(and viceversa). The reduction from AEL to \textsc{Sperner} passes through
the planar version of AEL. AEL is defined on a large DAG (|V| =  2^n for a given n),
whose nodes have outdegree and indegree at most 1. A source node 1 is given,
having indegree 0 and outdegree 1. The objective is to find a node such that the
sum of his indegree and outdegree is equal to 1. Other problems in the class and
hard for it are \textsc{Brouwer}, \textsc{Tuck} and \textsc{Fixed Point}. The nifty
thing is that all this reduction rely on parity arguments. From this fact the name
PPAD: P? Parity Argument Directed. I guess in two days we will now what the
first P stands for! By the way, now I should be working on some reductions from
the listed problems, so see you in a while…

GAME 2010

Yesterday we went to the banquet in a very nice restaurant, in the centre
of Shanghai. Nice company and surprising food have made a beautiful evening.
I have launched myself into eating jellyfish; Nina skipped that: wisdom has never
been a quality of mine.

Me and Nina are at GAME2010, International Summer School on Algorithmic
Game Theory. Of course in Shanghai. The weather is somewhat humid, but news
from Rome say that there are cases of self ignition of people there, so I do not
really feel like complaining…

Avrim Blum has introduced some basic concepts in game theory in the first
lecture, such as Nash equilibria, zero-sum games and minimax-optimal
strategies. A good start, just to warm up people already in the field and
give some building blocks to those who are new to the topic.
During the introductory lecture, various interesting, although old, results
have been presented. For instance we discovered that adding highways to a road
network can increase the travel time between two points, even though it would
seem to help. Or that when shooting a penalty, it is way better not to have
a deterministic strategy, but just choose at random where to kick the ball,
left or right. And also the goal keeper should do the same.

Stefano Leonardi has presented approximation techniques for cost sharing and
utilitarian mechanisms. Then he also talked about combinatorial auctions with
For cost sharing mechanisms, where a group of users shares in some way the cost
of a service, the main issue is to ensure, along with other
properties, the so called group strategyproofness; that is, even
though users of some service collaborate, their best strategy is to bid for the
service the true utility they would get in return. In order to achieve this
characteristic of the mechanisms, preserving the others, the cross
property can be exploited. This property consists in the fact
that when a new player joins the game, the cost shares of other players do not


German precognitive cephalopod decides central open question in theoretical computer science. Another great oracle result.

ICALP 2010

I’m at ICALP 2010 in sunny Bordeaux. I have been very busy working on two papers with colleagues who happen to attend ICALP as well, so I have missed a bunch of interesting talks on the first two days already.

I did, however, attend the business meeting, an event that combines various reports from ICALP committees with the general assembly of EATCS, the “European SIGACT.”

I normally enjoy business meetings, but ICALP business meetings are relatively stiff and mind-numbingly boring, with no discussion and no free beers. Still, let me give an incomplete and skewed summary of some of the issues that were mentioned.

ICALP publication

EATCS views ICALP as its flagship conference, and ICALP has published with Springer’s LNCS proceedings series for many years – if DBLP is to be trusted, the proceedings from the 4th ICALP (Turku, Finland, 1977) appear as LNCS volume 52. Since a few years ago, Springer has started an LNCS subline called ARCoSS (Springer page about ARCoSS) “in cooperation with” EATCS and ETAPS. These have a nicer cover.

However, it has been unclear in which sense this publication model coincides with the current preferences of the members of EATCS. Just to mention an alternative, the STACS conference now publishes with the LIPIcs series, which is Open Access in the sense that they are available on line and free of charge.

Very commendably, and to my pleasant surprise, EATCS actually implemented a member poll in the Spring of 2010 to determine our opinions on open source publication models, and in particular the outlet for ICALP’s proceedings. The results are online ([poll results at EACTS website]), but for mysterious reasons only accessible to EATCS members. It’s fair to say that there is a large majority of members that would prefer another publication model. For example, only 10% want EATCS to “Publish the proceedings of ICALP as before in a traditional print publication?” To the question “What is the publication model for scientific papers in theoretical computer science that you would prefer to see gain prominence in the near future?”, 83% respond “Open access publication as for LMCS, LIPIcs and EPTCS”

EATCS chairman Burkhard Monien reported that the EATCS Council has now approached Springer about the ICALP proceedings. According to him, Springer has made substantially better offer “very close to open access. We have discussed this carefully in the council.”

I think this is good news. However, I am less than impressed about the speed with which the process will continue. According to Monien, the result of the May 2010 poll were not sufficiently conclusive, so “We’ll ask your opinion again.” This time, there will be mercilessly concrete choices about either (1) going with LIPIcs, or (2) staying with Springer, under specific (and, I assume, new) terms. Monien explained the EATCS council wants to get this right, ICALP is a big steamer, should not go in zig-zag course, and stick to its decisions. He was unsure if the next poll will be implemented in the Fall, but promised “beginning of next year, at the latest.” I’m not holding my breath.

Still, all in all I think this is splendid news, and I’m particularly happy to the the EATCS council involving its members in an important decision process.

ICALP 2010 Organization

The report from the ICALP 2010 organizers was the usual list of statistics. I have become increasingly interested in these details after arranging ALGO 2009 myself. In total, ICALP 2010 has 292 participants, including 55 locals (the latter strikes me as a high number). 200 of these are registrants for ICALP itself, rather than one of the affiliated workshops, 147 pay the full registration fee. Only 3 Swedes and 1 Dane are registered, I wonder which I am.

This ICALP is held in the conference facilities of a large, soul-less hotel in down-town Bordeaux. I’m not a big fan of this kind of conference, and the contrast in atmosphere to the locally organised SWAT I attended in June is enormous. There’s a small lobby to hang out in, with few chairs or tables (let alone blackboards), interaction between attendees is minimal, except for the cliques one is already in. Furthermore, ICALP provides no lunches, so people scatter into small groups and look for a place to eat. Pretty much like the large US conferences.

Also, the Friday banquet is included only for full participants, meaning that many students will not be able to get the 90 Euro dinner ticket reimbursed, and consequently won’t attend. In my experience, this decision is de rigeur for Southern European ICALPs, but I think it is fundamentally misguided. The food better be spectacular.

On the other hand, the proceedings are included in the registration, which is another mistake. Many people never even remove the shrink wrap anymore, paper proceedings are just ballast. Moreover, proceedings are easy to reimburse, even for those students who honestly prefer to pay for the privilege to read the absurdly formatted 12 page LNCS amputated paper rather than reading the full version on the web.

The budget for the whole event is slightly over 100,000€, and the organizer received 2,500 emails. Apparently, EATCS maintains some for of organizer’s manual for ICALP; I’d like to see that. (I have seen the ESA/ALGO manual.) These things should be on-line, and allow for feed-back.

Programme Committees

The reports from ICALPs various programme committees included the usual absurd statistics, which were useless even by the low standards we are used to. The best paper award (Track A) went to Leslie Goldberg and Mark Jerrum’s result about about Approximating the partition function of the ferromagnetic Potts model. This is, of course, utterly splendid work. In total ICALP Track A received 229 submissions (6 were withdrawn) and accepted 60. Denmark submitted 3.33 papers, 1.17 accepted. Sweden submitted 1.83 and accepted 1.17. Again, I wonder which I am.

The programming for ICALP’s Track A has left me, and many others, completely puzzled, and looks as if it’s the result of a grep script based on paper titles. For example, ICALP had two strongly related results about Cuckoo hashing; but the results appeared in different sessions:

  • Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh and Michael Rink’s Tight Thresholds for Cuckoo Hashing via XORSAT appeared in session 3 on “Sorting & hashing,” inconceivably scheduled in parallel with the session 3 on “Data structures”. These are the only sessions on data structures in a 5-day, 3-track conference! In parallel!
  • Nikolaos Fountoulakis and Konstantinos Panagiotou’s Orientability of Random Hypergaphs and the Power of Multiple Choices appeared in session 5, “Graphs and hypergraphs.”

ICALP 2011

Michael Hoffmann presented the ICALP 2011 organisation in Zürich. . This seems to be an ICALP model closer to my preferences. The conference will be held in in university facilities, at something called CAB from late 19th century, with several large lecture rooms for workshops or parallel tracks, an even larger lecture hall, WLAN, and plenty of working space.

Also, there is no banquet, but rather a number of receptions with plenty of finger food and drinks. As an added benefit, registration fees are expected to be low. Of course, Zürich is “not among the cheapest places”, and prices are even higher than shown last year, because of the exchange rate between Swiss Franc and Euro, which shows high variance.

I will certainly attend, as I am one of the invited speakers. Apparently, I’m speaking on the 5th.

ICALP 2012

Artur Czumaj presented the plans for ICALP 2012, which (somewhat unusually) is already fixed two years in advance. The dates are July 9–13 2012 in Warwick, for the centenary of Alan Turing’s birth. Thus, ICALP is one of many events in the UK for the Alan Turing year, see the list of events. ICALP will be held on Warwick’s campus, including accommodation and lunches. Satellite events were said to include Wimbledon right before ICALP and the London Olympic games somewhat later.

Possibly this is the right time to start thinking about what we in the greater Copenhagen area (e.g., Sweden and Denmark, or all of Scandinavia) should be doing for the Turing year. Computer Science has far from the pop-sci clout that biology enjoys, but shouldn’t we be able to drum up at least one hundredth of the attention that Darwin got? Ideas are welcome.

For example SWAT 2012 is in the Turing year. We should start branding all our CS-related activities in 2012 as Turing-related, and hopefully concoct some more.