To demonstrate the difficulty, let us start looking at the easiest-to-analyze auction: a second-price
auction of
a single item among two users. It is well known [1]}, [2]} that such an auction is
(dominant-strategy)
incentive-compatible, i.e., that no bidder
ever has any motivation for mis-reporting his value to the auctioneer. Such truthful bidding will
result in an efficient allocation where the player with the higher value wins and pays a price equal to the value of the lower player.
