We describe a general technique for converting an online algorithm B to a truthtelling mechanism. We require that the original online competitive algorithm has certain "niceness" properties in that actions on future requests are independent of the actual value of requests which were accepted (though these actions will of course depend upon the set of accepted requests). Under these conditions, we are able to give an online truthtelling mechanism (where the values of requests are given by bids which may not accurately represent the valuation of the requesters) such that our total profit is within O(ρ + log µ) of the optimum offline profit obtained by an omniscient algorithm (one which knows the true valuations of the users). Here ρ is the competitive ratio of B for the optimization version of the problem, and µ is the ratio of the maximum to minimum valuation for a request. In general there is an Ω(log µ) lower bound on the ratio of worst-case profit for a truthtelling mechanism when compared to the profit obtained by an omniscient algorithm, so this result is in some sense best possible. In addition, we prove that our construction is resilient against many forms of "cheating" attempts, such as forming coalitions. We demonstrate applications of this result to several problems. We develop online truthtelling mechanisms for online routing and admission control of path or multicast requests, assuming large network capacities. Assuming the existance of an algorithm B for the optimization version of the problem, our techniques provide truthtelling mechanisms for general combinatorial auctions. However, designing optimization algorithms may be difficult in general because of online or approximation lower bounds. For the cases described above, we are able to design optimization algorithms *
Awerbuch, Azar, and Myerson REF give a general scheme that produces posted prices for general combinatorial auctions, with a competitive ratio equal to the logarithm of the ratio between highest and lowest prices, times the underlying competitive ratio for the combinatorial auction (which is terrible, in general).
Reducing truth-telling online mechanisms to online optimization
STOC '03
Computer Science