AdONE Seminar: Eleni Batziou (AdONE)

In this paper, we deal with preference elicitation mechanisms in combinatorial domains, focusing on combinatorial auctions, whereby an auctioneer offers multiple items and the agents purchase mutually disjoint subsets (bundles) of them. The exponential growth of the number of available bundles in large combinatorial markets poses a challenge to agents, who need to report their valuations for every possible bundle, so as to reach an optimal item allocation for a predefined auction objective. Fortunately, approximations are possible by using only partial information on agent valuations, thus significantly reducing time and effort. To achieve this, one needs to design a mechanism to elicit maximally informative data from agents, which traditionally is implemented in the form of value queries, (i.e., asking bidders their values for specific bundles). However, the determination of every new query involves solving a computationally expensive Mixed Integer Program (MIP), which poses a significant computational burden. To overcome this, we propose to incorporate reinforcement learning techniques for combinatorial optimization in the design of preference elicitation mechanisms. In particular, we introduce a parametric randomized algorithm to predict value queries given an estimation of the agents' preferences. We optimize the parameters of the algorithm using gradient descent, where the gradients w.r.t. the auction objective are estimated with policy gradient. We experimentally validate our method on an established real-world combinatorial auction scenario, i.e., spectrum auction benchmarks, and argue that our approach achieves a significant reduction in the auction runtime while maintaining comparable allocation efficiency to the state-of-the-art mechanisms.