Abstract
We consider a setting known as combinatorial auctions in which self-interested agents have preferences over items or sets of items, and interact with an auction or allocation mechanism that determines what items are given to which agents. We consider the perspective of an outside observer who each day can only see which agents show up and what they get, or perhaps just which agents are satisfied and which are not. Our goal will be from observing a series of such interactions to try to learn the agent preferences and perhaps also the rules of the allocation mechanism.
As an example, consider observing web pages where the agents are advertisers and the winners are those whose ads show up on the given page. Or consider observing the input-output behavior of a server, where the input consists of a set of agents requesting service, and the output is a partition of them into some whose requests are
actually fulfilled and the rest that are not---due to overlap of their resource needs with higher-priority requests. We give learning algorithms for scenarios of this form, for fairly simple but interesting classes of preferences and mechanisms. We also consider a classic Myerson single-item auction setting, where from observing who wins and also being able to participate ourselves we would like to learn agents' valuation distributions.
In examining these problems we will see connections to decision-list learning and to Kaplan-Meier estimators from medical statistics.
This is based on joint work with Yishay Mansour and Jamie Morgenstern.