DIMACS Theoretical Computer Science Seminar

Title: Leveraging Higher-Order Beliefs in Mechanism Design

Speaker: Jing Chen, IAS

Date: Wednesday, March 27, 2013 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


In a setting of incomplete information, we model the hierarchy of the players' beliefs about each other's payoff types in a set-theoretic way. A player's beliefs can be totally arbitrary, and the beliefs of different players can be inconsistent with each other. In single-good auctions, for k=0, 1, ... , we define a revenue benchmark $G^k$ on the players' belief hierarchy. Intuitively, $G^k$ is greater than or equal to v if and only if there exist at least two players "believing that there exists a player ..." (k times) valuing the good at least v. We construct an interim individually rational mechanism M that, without any clue about the players' beliefs and their rationality level, virtually guarantees revenue $G^k$ whenever the players happen to be level-(k+1) rational. We also separate the revenue achievable with level-k and level-(k+1) rational players. For every non-negative k, we show that no interim individually rational mechanism can virtually guarantee revenue $G^k$ when the players' rationality level is k instead of k+1.

See: http://paul.rutgers.edu/~yixinxu/theory-spring13.html