A monopolist is auctioning off m items in m consecutive stages to n interested buyers. A buyer learns her value for the k-th item at the beginning of stage k. For the future items only a prior distribution is known. The prior of buyer i depends on the values of that buyer for the items so far. How should this monopolist behave in order to maximize her expected revenue?
In the first part of the talk we study the computational complexity of finding the optimal auction. This part is based on joint work with Christos Papadimitriou, George Pierrakos and Aviad Rubinstein.
In the second part of the talk we study the competition complexity of this problem. The competition complexity of an auction measures how much competition is needed for the revenue of a simple auction to surpass the optimal revenue. This part is based on joint work with Siqi Liu.