|
Abstract : |
Abstract We describe a general technique for converting an online algorithm B to a truthtelling mechanism. We require that theoriginal 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 acceptedrequests). Under these conditions, we are able to give an online truth telling 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(ae + log _) of the optimum offline profit obtained by an omniscient algorithm (one which knows the true valuationsof the users). Here ae is the competitive ratio of B for the optimization version of the problem, and _ is the ratio of themaximum to minimum valuation for a request. In general there is an \Omega (log _) lower bound on the ratio of worst-case profitfor a truth telling mechanism when compared to the profit obtained by an omniscient algorithm, so this result is in some, |
