Fast payment schemes for truthful mechanisms with verification

Inthispaperwestudyoptimizationproblemswithverifiableone-parameterselfishagentsintroduced by Auletta et al. [V. Auletta, R. De Prisco, P. Penna, P. Persiano, The power ofverificationforone-parameteragents,in:Proceedingsofthe31stInternationalColloquiumonAutomata,LanguagesandProgramming,ICALP,in:LNCS,vol.3142,2004,pp.171–182].Ourgoalistoallocateloadamongtheagents,providedthatthesecretdataofeachagentis a single positive real number: the cost they incur per unit load. In such a setting thepayment is given after the load completion, therefore if a positive load is assigned to anagent, we are able to verify if the agent declared to be faster than she actually is. Wedesign truthful mechanisms when the agents’ type sets are upper-bounded by a finitevalue.Weprovideatruthfulmechanismthatisc·(1+)-approximateiftheunderlyingalgorithmisc-approximateandweakly-monotone.Moreover,iftypesetsarealsodiscrete,we provide a truthful mechanism preserving the approximation ratio of its algorithmicpart. Our results improve the existing ones which provide truthful mechanisms dealingonly with finite type sets and do not preserve the approximation ratio of the underlyingalgorithm. Finally, we give applications for our payment schemes. Firstly, we give a fullcharacterization of theQ‖Cmaxproblem by using our techniques. Even if our paymentschemesneedupper-boundedtypesets,everyinstanceofQ‖Cmaxcanbe‘‘mapped’’intoaninstancewithupper-boundedtypesetspreservingtheapproximationratio.Inconclusion,weturnourattentiontobinarydemandgames.Inparticular,weshowthattheMinimumRadiusSpanningTreeadmitsanexacttruthfulmechanismwithverificationachievingtime(and space) complexity of the fastest centralized algorithm for it. This contrasts with arecent truthful mechanism for the same problem [G. Proietti, P. Widmayer, A truthfulmechanismforthenon-utilitarianminimumradiusspanningtreeproblem,in:Proceedingsof the 17th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, ACMPress,2005,pp.195–202]whichpaysalinearfactorwithrespecttothecomplexityofthefastest centralized algorithm. Such a result is extended to several binary demand gamesstudiedinliterature.