For every constant \epsilon>0, a randomized mechanism is called truthful with probability 1-\epsilon if for every agent and for every vector of bids, the probability that the agent benefits by bidding non-truthfully is at most \epsilon, where the probability is taken over the randomness of the mechanism [REF].
If the constant \epsilon goes to 0 when the number of bidders grows, then the mechanism is called truthful with high probability.