In our sirocco05 paper we erroneously reported an upper bound of 1+1/(r+1) on the competitive ratio of the greedy algorithm for two machines whose speeds ratio is r < φ (where φ is the golden ratio, that is, φ =1+1/φ).

The correct upper bound is 1+r/(r+1) [Cho and Sahni 1980], and we cannot claim that, for some values of r, this algorithm achieves a competitive ratio smaller than our lower bound for truthful mechanisms without verification. For the same reason, we cannot claim that no mechanism without verification can attain the same competitive ratio of a mechanism with verification (namely, the one running the greedy algorithm).

Therefore, the following two questions remain open:

1. Is the "selfish" version of the online task scheduling problem "more difficult" than its "unselfish" version?
2. Does verification really help?

In the full version of the paper, we show that the lower bound holds also for mechanisms with verification (i.e., for roughly monotone algorithms). It thus seems plausible that a stronger lover bound might hold for mechanisms without verification ( i.e., for monotone algorithms).

A possible direction for answering both questions above is to show that, for two machines whose speeds ratio is r, one of the following holds:

1. No monotone algorithm can be less than (1+r/(r+1))-competitive for 1 < r < φ;
2. No monotone algorithm can be less than (1+1/r)-competitive for φ > r.

This would imply that, for the corresponding range of values of r, no truthful mechanism without verification can be as good as an online algorithm (in particular, the greedy one). Moreover, verification does help since the greedy can be turned into a truthful mechanism with verification having the same competitive ratio. So, the answer to both questions would be "yes" if restricting to the case in which r is in some interval of values.