Bundle pricing with comparable items

Alexander Grigoriev, Joyce van Loon, Maxim Sviridenko, Marc Jochen Uetz, Tjark Vredeveld

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)
15 Downloads (Pure)

Abstract

We consider a revenue maximization problem where we are selling a set of items, each available in a certain quantity, to a set of bidders. Each bidder is interested in one or several bundles of items. We assume the bidders’ valuations for each of these bundles to be known. Whenever bundle prices are determined by the sum of single item prices, this algorithmic problem was recently shown to be inapproximable to within a semi-logarithmic factor. We consider two scenarios for determining bundle prices that allow to break this inapproximability barrier. Both scenarios are motivated by problems where items are different, yet comparable. First, we consider classical single item prices with an additional monotonicity constraint, enforcing that larger bundles are at least as expensive as smaller ones. We show that the problem remains strongly NP-hard, and we derive a PTAS. Second, motivated by real-life cases, we introduce the notion of affine price functions, and derive fixed-parameter polynomial time algorithms.
Original languageUndefined
Title of host publicationAlgorithms - ESA 2007, 15th Annual European Symposium
EditorsL. Arge, M. Hoffmann, E. Welzl
Place of PublicationBerlin
PublisherSpringer
Pages475-486
Number of pages12
ISBN (Print)978-3-540-75519-7
DOIs
Publication statusPublished - 2007
Event15th Annual European Symposium, ESA - Eilat, Israel
Duration: 8 Oct 200710 Oct 2007

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
NumberSupplement
Volume4698
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th Annual European Symposium, ESA
Period8/10/0710/10/07
Other8-10 Oct 2007

Keywords

  • IR-62053
  • METIS-245857
  • EWI-11569

Cite this