Linda Cai will present her MSE talk "Novel Behaviors in Combinatorial Auctions" on Friday, May 8, 2020 at 4pm via Zoom. Link to Zoom: [ https://us04web.zoom.us/j/5668379247 | https://us04web.zoom.us/j/5668379247 ] The members of her committee are as follows: Matt Weinberg (adviser) and Mark Braverman (reader) Understanding the power and limitations of efficient combinatorial auctions in various settings is a problem at the heart of modern day algorithmic game theory. There are two main notions of efficiency, computational efficiency (running the auction requires low computational power) and communication efficiency (a small number of bits need to be exchanged during the auction). For truthful combinatorial auctions with submodular valuation functions, these two notions of efficiency differ doubly exponentially in the approximation guarantees they can provide, and this distinction stems from the fact that demand queries are communication efficient but hard to even approximate in a computationally efficient way. We suggest a mild and natural relaxation of truthfulness under which this distinction disappears. Under our relaxation, we define a notion of demand queries, called bicriterion approximate demand queries, that can be computed in polynomial time. We use these demand queries to design computationally efficient combinatorial auctions satisfying our relaxed notion of truthfulness with approximation guarantees matching those known for communication efficient auctions. We also briefly discuss the problem of revenue maximization in repeated auctions when bidders are using mean-based no regret learning algorithms.