Pricing for customers with probabilistic valuations as a continuous knapsack problem

ABSTRACT

In this paper, we examine the problem of choosing discriminatory prices for customers with probabilistic valuations and a seller with indistinguishable copies of a good. We show that under certain assumptions this problem can be reduced to the continuous knapsack problem (CKP). We present a new fast ε-optimal algorithm for solving CKP instances with asymmetric concave reward functions. We also show that our algorithm can be extended beyond the CKP setting to handle pricing problems with overlapping goods (e.g.goods with common components or common resource requirements), rather than indistinguishable goods.We provide a framework for learning distributions over customer valuations from historical data that are accurate and compatible with our CKP algorithm, and we validate our techniques with experiments on pricing instances derived from the Trading Agent Competition in Supply Chain Management (TAC SCM). Our results confirm that our algorithm converges to an ε-optimal solution more quickly in practice than an adaptation of a previously proposed greedy heuristic.

REFERENCES

• 1: M. Benisch , A. Greenwald , I. Grypari , R. Lederman , V. Naroditskiy , M. Tschantz, Botticelli: A Supply Chain Management Agent, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1174-1181, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.77]
• 2: K. E. Case and R. C. Fair. Principles of Economics (5th ed.). Prentice-Hall, 1999.
• 3: J. Collins, R. Arunachalam, N. Sadeh, J. Eriksson, N. Finne, and S. Janson. The supply chain management game for the 2005 trading agent competition. Technical Report CMU-ISRI-04-139, Carnegie Mellon University, 2005.
• 4: Oren Etzioni , Rattapoom Tuchinda , Craig A. Knoblock , Alexander Yates, To buy or not to buy: mining airfare data to minimize ticket purchase price, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956767]
• 5: Rayid Ghani, Price prediction and insurance for online auctions, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081918]
• 6: H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. Springer, 2004.
• 7: D. Lawrence. A machine-learning approach to optimal bid pricing. In Proceedings of INFORMS'03, 2003.
• 8: A. Melman , G. Rabinowitz, An Efficient Method for a Class of Continuous Nonlinear Knapsack Problems, SIAM Review, v.42 n.3, p.440-448, Sept. 2000 [doi>10.1137/S0036144598330177]
• 9: D. Pardoe and P. Stone. Bidding for customer orders in TAC SCM. In Proceedings of AAMAS-04 Workshop on Agent-Mediated Electronic Commerce, 2004.
• 10: J. R. Quinlan. Learning with Continuous Classes. In 5th Australian Joint Conference on Artificial Intelligence, pages 343--348, 1992.
• 11: A. G. Robinson , N. Jiang , C. S. Lerme, On the continuous quadratic knapsack problem, Mathematical Programming: Series A and B, v.55 n.1-6, p.99-108, April 1992 [doi>10.1007/BF01581193]
• 12: T. Sandholm and S. Suri. Market clearability. In Proceedings of IJCAI'01, pages 1145--1151, 2001.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.0 General

Keywords:
TAC SCM, multi-agent systems, supply chain management, trading agents