Search-Based Advertising Auctions with Choice-Based Budget Constraint

Tsan Ming Choi, Xun Li, Cheng Ma

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)


In this paper, we model and formulate the search-based advertising auction problem with multiple slots, choice behaviors of advertisers, and the popular generalized second-price mechanism. A Lagrangian-based method is then proposed for tackling this problem. We present an extension to the subgradient algorithm based on Lagrangian relaxation coupled with the column generation method in order to improve the dual multipliers and accelerate its convergence. Simulation results show that the proposed algorithm is efficient and it shows significant improvement compared to the greedy algorithm.
Original languageEnglish
Article number7039204
Pages (from-to)1178-1186
Number of pages9
JournalIEEE Transactions on Systems, Man, and Cybernetics: Systems
Issue number8
Publication statusPublished - 1 Aug 2015


  • Generalized second-price (GSP) mechanism
  • online auction
  • search-based advertising (SA)

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Software
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Search-Based Advertising Auctions with Choice-Based Budget Constraint'. Together they form a unique fingerprint.

Cite this