Title: Locally Monotone Payment Rules in Combinatorial Auctions
Abstract: Combinatorial Auctions (CAs) are used to sell multiple goods to multiple bidders, when bidders have complex preferences over goods. The behavior of bidder under different payment rules is not well understood, and there has been limited success in finding Bayesian-Nash equilibria of such auctions due to the computational difficulties involved. In this thesis, I define a property of CAs called local monotonicity. Under a mechanism with this property, a participating bidder cannot cause his payment to decrease by increasing his bid. The well-known VCG-nearest (or quadratic) payment rule fails to satisfy this property, and can thus be manipulated in surprising ways. Furthermore, local monotonicity imposes a structure on the auction game which enables us to search for an approximate BNE much more efficiently than in the general case. I present an algorithm exploiting this structure and show experimentally that it outperforms a state of the art algorithm by orders of magnitude. I also study the over-bidding strategy in combinatorial auctions and prove that it does not happen in single-minded auction with local monotonicity.
