---
_id: '23744'
abstract:
- lang: eng
  text: "In a Stackelberg pricing game a leader aims to set prices on a subset of
    a given collection of items, such as to maximize her revenue from a follower purchasing
    a feasible subset of the items. We focus on the case of computationally bounded
    followers who cannot optimize exactly over the range of all feasible subsets,
    but apply some publicly known algorithm to determine the set of items to purchase.
    This corresponds to general multi-dimensional pricing assuming that consumers
    cannot optimize over the full domain of their valuation functions but still aim
    to act rationally to the best of their ability.\r\n\r\nWe consider two versions
    of this novel type of Stackelberg pricing games. Assuming that items are weighted
    objects and the follower seeks to purchase a min-cost selection of objects of
    some minimum weight (the Min-Knapsack problem) and uses a simple greedy 2-approximate
    algorithm, we show how an extension of the known single-price algorithm can be
    used to derive a polynomial-time (2 + ε)-approximation algorithm for the leader’s
    revenue maximization problem based on so-called near-uniform price assignments.
    We also prove the problem to be strongly NP-hard.\r\n\r\nConsidering the case
    that items are subsets of some ground set which the follower seeks to cover (the
    Set-Cover problem) via a standard primal-dual approach, we prove that near-uniform
    price assignments fail to yield a good approximation guarantee. However, in the
    special case of elements with frequency 2 (the Vertex-Cover problem) it turns
    out that exact revenue maximization can be done in polynomial-time. This stands
    in sharp contrast to the fact that revenue maximization becomes APX-hard already
    for elements with frequency 3."
author:
- first_name: Patrick
  full_name: Briest, Patrick
  last_name: Briest
- first_name: Martin
  full_name: Hoefer, Martin
  last_name: Hoefer
- first_name: Luciano
  full_name: Gualà, Luciano
  last_name: Gualà
- first_name: Carmine
  full_name: Ventre, Carmine
  last_name: Ventre
citation:
  ama: 'Briest P, Hoefer M, Gualà L, Ventre C. On Stackelberg Pricing with Computationally
    Bounded Consumers. In: <i>Lecture Notes in Computer Science</i>. Berlin, Heidelberg;
    2009. doi:<a href="https://doi.org/10.1007/978-3-642-10841-9_6">10.1007/978-3-642-10841-9_6</a>'
  apa: Briest, P., Hoefer, M., Gualà, L., &#38; Ventre, C. (2009). On Stackelberg
    Pricing with Computationally Bounded Consumers. In <i>Lecture Notes in Computer
    Science</i>. Berlin, Heidelberg. <a href="https://doi.org/10.1007/978-3-642-10841-9_6">https://doi.org/10.1007/978-3-642-10841-9_6</a>
  bibtex: '@inbook{Briest_Hoefer_Gualà_Ventre_2009, place={Berlin, Heidelberg}, title={On
    Stackelberg Pricing with Computationally Bounded Consumers}, DOI={<a href="https://doi.org/10.1007/978-3-642-10841-9_6">10.1007/978-3-642-10841-9_6</a>},
    booktitle={Lecture Notes in Computer Science}, author={Briest, Patrick and Hoefer,
    Martin and Gualà, Luciano and Ventre, Carmine}, year={2009} }'
  chicago: Briest, Patrick, Martin Hoefer, Luciano Gualà, and Carmine Ventre. “On
    Stackelberg Pricing with Computationally Bounded Consumers.” In <i>Lecture Notes
    in Computer Science</i>. Berlin, Heidelberg, 2009. <a href="https://doi.org/10.1007/978-3-642-10841-9_6">https://doi.org/10.1007/978-3-642-10841-9_6</a>.
  ieee: P. Briest, M. Hoefer, L. Gualà, and C. Ventre, “On Stackelberg Pricing with
    Computationally Bounded Consumers,” in <i>Lecture Notes in Computer Science</i>,
    Berlin, Heidelberg, 2009.
  mla: Briest, Patrick, et al. “On Stackelberg Pricing with Computationally Bounded
    Consumers.” <i>Lecture Notes in Computer Science</i>, 2009, doi:<a href="https://doi.org/10.1007/978-3-642-10841-9_6">10.1007/978-3-642-10841-9_6</a>.
  short: 'P. Briest, M. Hoefer, L. Gualà, C. Ventre, in: Lecture Notes in Computer
    Science, Berlin, Heidelberg, 2009.'
date_created: 2021-09-03T10:55:38Z
date_updated: 2022-01-06T06:55:59Z
department:
- _id: '63'
doi: 10.1007/978-3-642-10841-9_6
language:
- iso: eng
place: Berlin, Heidelberg
publication: Lecture Notes in Computer Science
publication_identifier:
  issn:
  - 0302-9743
  - 1611-3349
publication_status: published
status: public
title: On Stackelberg Pricing with Computationally Bounded Consumers
type: book_chapter
user_id: '15415'
year: '2009'
...