In tackling the problem of truthful budget, arrival and departure times, it turns out that it is not possible to achieve truthfulness in the classical sense (which we show in a companion paper). As such, we define a new concept called \emph{$\delta$-gain}. $\delta$-gain bounds the utility a player can gain by lying as opposed to his utility when telling the truth. Building on the $\delta$-gain concept we define another new concept called \emph{relative $\epsilon$-gain}, which bounds the relative ratio of the gain a player can achieve by lying with respect to his true utility. We argue that for many practical applications if the $\delta$-gain and or the relative $\epsilon$-gain are small, then players will not invest time and effort in making strategic choices but will truthtell as a default strategy. These concepts capture the essence of dominant strategy mechanisms as they lead the advertiser to choose truthtelling over other strategies.

In order to achieve $\delta$-gain truthful mechanism this paper also presents a new payment scheme, Time series Truthful Payment Scheme (TTPS), for an online budget-constrained auction mechanism. The payment scheme is a generalization of the VCG principles for an online scheduling environment with budgeted players.

Using the concepts of $\delta$-gain truthful we present the only known budget-constrained sponsored search auction with truthful guarantees on budget, arrivals, departures, and valuations. Previous works that deal with advertiser budgets only deal with the non-strategic case.