We study mechanism design in non-Bayesian settings of incomplete information, when the designer has no information about the players, and the players have arbitrary, heterogeneous, first-order, and possibilistic beliefs about their opponents' payoff types.

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...