Moshe Babaioff, Ron Lavi, and Elan Pavlov
In this paper we present a general scheme to create mechanisms that approximate the social welfare in the presence of selfish (but rational) behavior of agents. The usual approach is to design truthful mechanisms in which an agent can only lose by impersonating as another agent. In contrast, our approach is to allow an agent to impersonate several different agents. We design the mechanisms such that only a limited set of impersonations are reasonable to rational agents. Our mechanisms make sure that for any choice of such impersonations by the agents, an approximation to the social welfare is achieved. We demonstrate our results on the well studied domain of Combinatorial Auctions (CA). Our mechanisms are algorithmic implementations, a notion recently suggested in (Babaioff, Lavi, & Pavlov 2006).