We study combinatorial optimization problems involving one-parameter selfish agents considered by Archer and Tardos [FOCS 2001]. In particular, we show that, if agents can lie in one direction (that is they either overbid or underbid) then any (polynomial-time) c-approximation algorithm, for the optimization problem without selfish agents, can be turned into a (polynomial-time) c(1 + epsilon)-approximation truthful mechanism, for any epsilon > 0. We then look at the Q||Cmax problem in the case of agents owning machines of different speeds. We consider the model in which payments are given to the agents only after the machines have completed the jobs assigned. This means that for each machine that receives at least one job, the mechanism can verify if the corresponding agent declared a greater speed. For this setting, we characterize the allocation algorithms A that admit a payment function P such that M = (A, P) is a truthful mechanism. In addition, we give a (1+epsilon)-approximation truthful mechanism for Q||Cmax when machine speeds are bounded by a constant. Finally, we consider the classical scheduling problem Q||wjCj which does not admit an exact mechanism if verification is not allowed. By contrast, we show that an exact mechanism for Q||wjCj exists when verification is allowed.

The Power of Verification for One-Parameter Agents

AULETTA, Vincenzo;DE PRISCO, Roberto;PENNA, Paolo;PERSIANO, Giuseppe
2004

Abstract

We study combinatorial optimization problems involving one-parameter selfish agents considered by Archer and Tardos [FOCS 2001]. In particular, we show that, if agents can lie in one direction (that is they either overbid or underbid) then any (polynomial-time) c-approximation algorithm, for the optimization problem without selfish agents, can be turned into a (polynomial-time) c(1 + epsilon)-approximation truthful mechanism, for any epsilon > 0. We then look at the Q||Cmax problem in the case of agents owning machines of different speeds. We consider the model in which payments are given to the agents only after the machines have completed the jobs assigned. This means that for each machine that receives at least one job, the mechanism can verify if the corresponding agent declared a greater speed. For this setting, we characterize the allocation algorithms A that admit a payment function P such that M = (A, P) is a truthful mechanism. In addition, we give a (1+epsilon)-approximation truthful mechanism for Q||Cmax when machine speeds are bounded by a constant. Finally, we consider the classical scheduling problem Q||wjCj which does not admit an exact mechanism if verification is not allowed. By contrast, we show that an exact mechanism for Q||wjCj exists when verification is allowed.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/1067389
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 12
social impact