Article

Pricing for customers with probabilistic valuations as a continuous knapsack problem

Authors:

ICEC '06: Proceedings of the 8th international conference on Electronic commerce: The new e-commerce: innovations for conquering current barriers, obstacles and limitations to conducting successful business on the internet

Pages 38 - 46

https://doi.org/10.1145/1151454.1151475

Published: 13 August 2006 Publication History

Get Access

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, and M. C. Tschantz. Botticelli: A supply chain management agent. In Proceedings of AAMAS '04, pages 1174--1181, New York, July 2004.

Digital Library

Google Scholar

[2]

K. E. Case and R. C. Fair. Principles of Economics (5th ed.). Prentice-Hall, 1999.

Google Scholar

[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.

Google Scholar

[4]

O. Etzioni, R. Tuchinda, C. A. Knoblock, and A. Yates. To buy or not to buy: mining airfare data to minimize ticket purchase price. In Proceedings of KDD'03, pages 119--128, New York, NY, USA, 2003. ACM Press.

Digital Library

Google Scholar

[5]

R. Ghani. Price prediction and insurance for online auctions. In Proceedigns of KDD'05, pages 411--418, New York, NY, USA, 2005. ACM Press.

Digital Library

Google Scholar

[6]

H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. Springer, 2004.

Crossref

Google Scholar

[7]

D. Lawrence. A machine-learning approach to optimal bid pricing. In Proceedings of INFORMS'03, 2003.

Crossref

Google Scholar

[8]

A. Melman and G. Rabinowitz. An efficient method for a class of continuous knapsack problems. Society for Industrial and Applied Mathematics Review, 42(3):440--448, 2000.

Digital Library

Google Scholar

[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.

Google Scholar

[10]

J. R. Quinlan. Learning with Continuous Classes. In 5th Australian Joint Conference on Artificial Intelligence, pages 343--348, 1992.

Google Scholar

[11]

A. G. Robinson, N. Jiang, and C. S. Lerme. On the continuous quadratic knapsack problem. Math. Program., 55(1--6):99--108, 1992.

Digital Library

Google Scholar

[12]

T. Sandholm and S. Suri. Market clearability. In Proceedings of IJCAI'01, pages 1145--1151, 2001.

Digital Library

Google Scholar

Cited By

View all

Fasli MKovalchuk Y(2019)Learning approaches for developing successful seller strategies in dynamic supply chain managementInformation Sciences: an International Journal10.1016/j.ins.2011.04.014181:16(3411-3426)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.1016/j.ins.2011.04.014
Collins JKetter WGini M(2018)Flexible decision control in an autonomous trading agentElectronic Commerce Research and Applications10.1016/j.elerap.2008.09.0048:2(91-105)Online publication date: 21-Dec-2018
https://dl.acm.org/doi/10.1016/j.elerap.2008.09.004
Manistersky ELin RKraus S(2014)The Development of the Strategic Behavior of Peer Designed AgentsLanguage, Culture, Computation. Computing - Theory and Technology10.1007/978-3-642-45321-2_9(180-196)Online publication date: 2014
https://doi.org/10.1007/978-3-642-45321-2_9
Show More Cited By

Index Terms

Pricing for customers with probabilistic valuations as a continuous knapsack problem
1. Computing methodologies
  1. Modeling and simulation
2. Information systems
  1. Information systems applications
    1. Decision support systems
      1. Expert systems

Recommendations

Pricing Equilibria and Graphical Valuations

We study pricing equilibria for graphical valuations, whichare a class of valuations that admit a compact representation. These valuations are associated with a value graph, whose nodes correspond to items, and edges encode (pairwise) complementarities/...
Optimal pricing for submodular valuations with bounded curvature
AAAI'17: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence

The optimal pricing problem is a fundamental problem that arises in combinatorial auctions. Suppose that there is one seller who has indivisible items and multiple buyers who want to purchase a combination of the items. The seller wants to sell his items ...
CMieux: adaptive strategies for competitive supply chain trading
ICEC '06: Proceedings of the 8th international conference on Electronic commerce: The new e-commerce: innovations for conquering current barriers, obstacles and limitations to conducting successful business on the internet

Supply chains are a central element of today's global economy. Existing management practices consist primarily of static interactions between established partners. Global competition, shorter product life cycles and the emergence of Internet-mediated ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

August 2006

624 pages

ISBN:1595933921

DOI:10.1145/1151454

Conference Chairs:
Mark S. Fox
University of Toronto, Canada
,
Bruce Spencer
National Research Council Canada

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 August 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

ICEC '06 Paper Acceptance Rate 53 of 112 submissions, 47%;

Overall Acceptance Rate 150 of 244 submissions, 61%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
291
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Fasli MKovalchuk Y(2019)Learning approaches for developing successful seller strategies in dynamic supply chain managementInformation Sciences: an International Journal10.1016/j.ins.2011.04.014181:16(3411-3426)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.1016/j.ins.2011.04.014
Collins JKetter WGini M(2018)Flexible decision control in an autonomous trading agentElectronic Commerce Research and Applications10.1016/j.elerap.2008.09.0048:2(91-105)Online publication date: 21-Dec-2018
https://dl.acm.org/doi/10.1016/j.elerap.2008.09.004
Manistersky ELin RKraus S(2014)The Development of the Strategic Behavior of Peer Designed AgentsLanguage, Culture, Computation. Computing - Theory and Technology10.1007/978-3-642-45321-2_9(180-196)Online publication date: 2014
https://doi.org/10.1007/978-3-642-45321-2_9
Ketter WCollins JGini MGupta ASchrater P(2012)Real-Time Tactical and Strategic Sales Management for Intelligent Agents Guided by Economic RegimesInformation Systems Research10.1287/isre.1110.041523:4(1263-1283)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1287/isre.1110.0415
Collins JKetter WSadeh N(2010)Pushing the Limits of Rational Agents: The Trading Agent Competition for Supply Chain ManagementAI Magazine10.1609/aimag.v31i2.228731:2(63-80)Online publication date: Jun-2010
https://doi.org/10.1609/aimag.v31i2.2287
Kovalchuk YFasli M(2010)A Demand-Driven Approach for a Multi-Agent System in Supply Chain ManagementAgent-Mediated Electronic Commerce. Designing Trading Strategies and Mechanisms for Electronic Markets10.1007/978-3-642-15117-0_7(88-101)Online publication date: 2010
https://doi.org/10.1007/978-3-642-15117-0_7
Benisch MSardinha AAndrews JRavichandran RSadeh N(2009)CMieuxElectronic Commerce Research and Applications10.1016/j.elerap.2008.09.0058:2(78-90)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1016/j.elerap.2008.09.005
Sardinha ABenisch MSadeh NRavichandran RPodobnik VStan M(2009)The 2007 procurement challengeElectronic Commerce Research and Applications10.1016/j.elerap.2008.09.0028:2(106-114)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1016/j.elerap.2008.09.002
Kovalchuk YFasli MFensel DWerthner H(2008)Adaptive strategies for predicting bidding prices in supply chain managementProceedings of the 10th international conference on Electronic commerce10.1145/1409540.1409548(1-10)Online publication date: 19-Aug-2008
https://dl.acm.org/doi/10.1145/1409540.1409548
Kovalchuk YFasli M(2008)Deploying Neural-Network-Based Models for Dynamic Pricing in Supply Chain ManagementProceedings of the 2008 International Conference on Computational Intelligence for Modelling Control & Automation10.1109/CIMCA.2008.92(680-685)Online publication date: 10-Dec-2008
https://dl.acm.org/doi/10.1109/CIMCA.2008.92
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Pricing Equilibria and Graphical Valuations

Optimal pricing for submodular valuations with bounded curvature

CMieux: adaptive strategies for competitive supply chain trading