In unrestricted combinatorial auctions, we put forward a mechanism that guarantees a meaningful revenue benchmark based on the possibilistic beliefs that the players have about each other's valuations. In essence, the mechanism guarantees, within a factor of two, the maximum revenue that the 'best informed player' would be sure to obtain if he/she were to sell the goods to his/her opponents via take-it-or-leave-it offers. Our mechanism is probabilistic and of an extensive form. It relies on a new solution concept, for analyzing extensive-form games of incomplete information, which assumes only mutual belief of rationality. Moreover, our mechanism enjoys several novel properties with respect to privacy, computation and collusion.
possibilistic beliefs unrestricted combinatorial auctions mutual belief of rationality incomplete information extensive-form games distinguishable dominance