Optimization Online


A pricing problem under Monge property

Oktay Gunluk (oktay***at***watson.ibm.com)

Abstract: We study a pricing problem where buyers with non-uniform demand purchase one of many items. Each buyer has a known benefit for each item and purchases the item that gives the largest utility, which is defined to be the difference between the benefit and the price of the item. The optimization problem is to decide on the prices that maximize total revenue of the seller. This problem is also called the optimal product line design problem in the absence of competition. Even though the general problem is known to be NP-hard, it can be solved efficiently under some natural assumptions on customer benefits. In this paper we study properties of optimal solutions and present a dynamic programming algorithm when customer benefits satisfy the Monge property. The same algorithm can also be used to solve the problem under the additional requirement that all buyers should be served.

Keywords: pricing, optimization, product line design

Category 1: Combinatorial Optimization

Category 2: Other Topics (Dynamic Programming )


Download: [Postscript][PDF]

Entry Submitted: 01/30/2006
Entry Accepted: 01/30/2006
Entry Last Modified: 06/12/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society