Auction optimization using regression trees and linear models as integer programs

S. Verwer, Y. Zhang, Q.C. Ye

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)
13 Downloads (Pure)

Abstract

In a sequential auction with multiple bidding agents, the problem of determining the ordering of the items to sell in order to maximize the expected revenue is highly challenging. The challenge is largely due to the fact that the autonomy and private information of the agents heavily influence the outcome of the auction.

The main contribution of this paper is two-fold. First, we demonstrate how to apply machine learning techniques to solve the optimal ordering problem in sequential auctions. We learn regression models from historical auctions, which are subsequently used to predict the expected value of orderings for new auctions. Given the learned models, we propose two types of optimization methods: a black-box best-first search approach, and a novel white-box approach that maps learned regression models to integer linear programs (ILP), which can then be solved by any ILP-solver. Although the studied auction design problem is hard, our proposed optimization methods obtain good orderings with high revenues.

Our second main contribution is the insight that the internal structure of regression models can be efficiently evaluated inside an ILP solver for optimization purposes. To this end, we provide efficient encodings of regression trees and linear regression models as ILP constraints. This new way of using learned models for optimization is promising. As the experimental results show, it significantly outperforms the black-box best-first search in nearly all settings.
Original languageEnglish
Pages (from-to)368-395
Number of pages28
JournalArtificial Intelligence
Volume244
Early online date29 May 2015
DOIs
Publication statusPublished - Mar 2017

Fingerprint

auction
linear model
regression
revenue
Linear regression
Learning systems
Auctions
autonomy
learning

Cite this

@article{153536eb00e44eb28d64258f4366c818,
title = "Auction optimization using regression trees and linear models as integer programs",
abstract = "In a sequential auction with multiple bidding agents, the problem of determining the ordering of the items to sell in order to maximize the expected revenue is highly challenging. The challenge is largely due to the fact that the autonomy and private information of the agents heavily influence the outcome of the auction.The main contribution of this paper is two-fold. First, we demonstrate how to apply machine learning techniques to solve the optimal ordering problem in sequential auctions. We learn regression models from historical auctions, which are subsequently used to predict the expected value of orderings for new auctions. Given the learned models, we propose two types of optimization methods: a black-box best-first search approach, and a novel white-box approach that maps learned regression models to integer linear programs (ILP), which can then be solved by any ILP-solver. Although the studied auction design problem is hard, our proposed optimization methods obtain good orderings with high revenues.Our second main contribution is the insight that the internal structure of regression models can be efficiently evaluated inside an ILP solver for optimization purposes. To this end, we provide efficient encodings of regression trees and linear regression models as ILP constraints. This new way of using learned models for optimization is promising. As the experimental results show, it significantly outperforms the black-box best-first search in nearly all settings.",
author = "S. Verwer and Y. Zhang and Q.C. Ye",
year = "2017",
month = "3",
doi = "10.1016/j.artint.2015.05.004",
language = "English",
volume = "244",
pages = "368--395",
journal = "Artificial Intelligence",
issn = "0004-3702",
publisher = "Agon Elsevier",

}

Auction optimization using regression trees and linear models as integer programs. / Verwer, S.; Zhang, Y.; Ye, Q.C.

In: Artificial Intelligence, Vol. 244, 03.2017, p. 368-395.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Auction optimization using regression trees and linear models as integer programs

AU - Verwer, S.

AU - Zhang, Y.

AU - Ye, Q.C.

PY - 2017/3

Y1 - 2017/3

N2 - In a sequential auction with multiple bidding agents, the problem of determining the ordering of the items to sell in order to maximize the expected revenue is highly challenging. The challenge is largely due to the fact that the autonomy and private information of the agents heavily influence the outcome of the auction.The main contribution of this paper is two-fold. First, we demonstrate how to apply machine learning techniques to solve the optimal ordering problem in sequential auctions. We learn regression models from historical auctions, which are subsequently used to predict the expected value of orderings for new auctions. Given the learned models, we propose two types of optimization methods: a black-box best-first search approach, and a novel white-box approach that maps learned regression models to integer linear programs (ILP), which can then be solved by any ILP-solver. Although the studied auction design problem is hard, our proposed optimization methods obtain good orderings with high revenues.Our second main contribution is the insight that the internal structure of regression models can be efficiently evaluated inside an ILP solver for optimization purposes. To this end, we provide efficient encodings of regression trees and linear regression models as ILP constraints. This new way of using learned models for optimization is promising. As the experimental results show, it significantly outperforms the black-box best-first search in nearly all settings.

AB - In a sequential auction with multiple bidding agents, the problem of determining the ordering of the items to sell in order to maximize the expected revenue is highly challenging. The challenge is largely due to the fact that the autonomy and private information of the agents heavily influence the outcome of the auction.The main contribution of this paper is two-fold. First, we demonstrate how to apply machine learning techniques to solve the optimal ordering problem in sequential auctions. We learn regression models from historical auctions, which are subsequently used to predict the expected value of orderings for new auctions. Given the learned models, we propose two types of optimization methods: a black-box best-first search approach, and a novel white-box approach that maps learned regression models to integer linear programs (ILP), which can then be solved by any ILP-solver. Although the studied auction design problem is hard, our proposed optimization methods obtain good orderings with high revenues.Our second main contribution is the insight that the internal structure of regression models can be efficiently evaluated inside an ILP solver for optimization purposes. To this end, we provide efficient encodings of regression trees and linear regression models as ILP constraints. This new way of using learned models for optimization is promising. As the experimental results show, it significantly outperforms the black-box best-first search in nearly all settings.

U2 - 10.1016/j.artint.2015.05.004

DO - 10.1016/j.artint.2015.05.004

M3 - Article

VL - 244

SP - 368

EP - 395

JO - Artificial Intelligence

JF - Artificial Intelligence

SN - 0004-3702

ER -