Evaluating multiple attribute items using queries

ABSTRACT

The task of evaluating and ranking items with multiple-attributes appears in many guises in commerce. Examples include evaluating responses to a request for quotes (RFQ) for some item and comparison shopping for an item within one or more catalogs. This task is straightforward if the value of the item can be explicitly specified by the evaluator as a function of the attribute values. However, a typical evaluator may not be able to provide the value function in explicit form. In contrast, it is intuitive for them to compare, say, two items and pick the preferable one based on all of the relevant attributes. In this paper we present a method, Q-Eval, that queries the evaluator with selected pairs of items and uses the responses to build a preference model for the evaluator. This model is then used to rank the items in order of the inferred preference. The evaluator can then pick the winning item or items by considering only the top few items in this ranked list. This should result in significant productivity improvement for the evaluator when the number of items to choose from is large. Our algorithm is novel in the way it attempts to derive a stable preference model with only a small number of user queries. This paper describes the algorithm and presents experimental results with real-life data to validate the approach.

REFERENCES

• 1: S.Arnborg.Learning n prevision space.In Proceedings of 1st International Symposium on Imprecise Probabilities and their Applications ,1999.
• 2: B.Bueler,A.Enge,and K.Fukuda.Exact volume computation for convex polytopes:A practical study. In Polytopes -Combinatorics and Computation . DMV-Seminars,Birkhauser Verlag,1998.FTP site=ftp://ftp.ifor.math.ethz.ch/pub/fukuda/reports.
• 3: R. J. Caron , H. J. Greenberg , A. G. Holder, Analytic Centers and Repelling Inequalities, University of Colorado at Denver, Denver, CO, 1999
• 4: R.Clemen.Making Hard Decisions .Duxbury Press, 1996.
• 5: M.Dyer.The complexity of vertex enumeration methods.Mathematics of Operations Research , 8(3):381 -402,1983.
• 6: M. E. Dyer , A. M. Frieze, On the complexity of computing the volume of a polyhedron, SIAM Journal on Computing, v.17 n.5, p.967-974, October 1988 [doi>10.1137/0217060]
• 7: Martin Dyer , Alan Frieze , Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM (JACM), v.38 n.1, p.1-17, Jan. 1991 [doi>10.1145/102782.102783]
• 8: K .Fukuda.Cdd -an mplementation of the double description method.Technical Report Technical Report,DMA-EPFL,Institute for Operations Research,ETH Zentrum,Zurich,1993. URL=http://www.ifor.math.ethz.ch/ ~fukuda/ cdd home/cdd.html.
• 9: Komei Fukuda , Alain Prodon, Double Description Method Revisited, Selected papers from the 8th Franco-Japanese and 4th Franco-Chinese Conference on Combinatorics and Computer Science, p.91-111, July 03-05, 1995
• 10: P.Green and A.Krieger.Recent contributions to optimal product positioning and buyer segmentation. European Journal of Operational Research , 41:127 -141,1989.
• 11: P.Green and V.Srinivasan.Conjoint analysis in marketing research:New developments and directions. Journal of Marketing ,54(4):3 -19,October 1990.
• 12: R.Johnson.Adaptive conjoint analysis.In Sawtooth Software Conference on Perceptual Mapping,Conjoint Analysis and Computer Interviewing ,pages 253 -265. Sawtooth Software,1987.
• 13: R.Johnson.Comment on 'adaptive conjoint analysis: Some caveats and suggestions '.Journal of Marketing Research ,28(2):223 -225,May 1991.
• 14: Ravi Kannan , László Lovász , Miklós Simonovits, Random walks and an O*(n5) volume algorithm for convex bodies, Random Structures & Algorithms, v.11 n.1, p.1-50, Aug. 1997 [doi>10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X]
• 15: R.Keeney and H.Rai .a.Decisions with Multiple Objectives:Preferences and Value Tradeo .s .Wiley, 1976.
• 16: G.Lilien,P.Kotler,and K.Moorthy.Marketing Models .Prentice Hall,1992.
• 17: S.Nash and A.Sofer.Linear and Nonlinear Programming .McGraw-Hill,1996.
• 18: R.Pindyck and D.Rubinfeld.Microeconomics . Prentice Hall,1997.
• 19: T.Saaty.How to make a decision:The analytic hierarchy process.Interfaces ,24(6):19 -43,1994.
• 20: G.Sonnevend.An "analytical centre" for polyhedrons and newlasses of global algorithms for linear (smooth, convex)programming.In System modelling and optimization (Budapest,1985),pages 866 -875. Springer,Berlin,1986.
• 21: Gaurav Tewari , Pattie Maes, Design and implementation of an agent-based intermediary infrastructure for electronic markets, Proceedings of the 2nd ACM conference on Electronic commerce, p.86-94, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352881]
• 22: L.Valiant.The complexity of computing the permanent.Theoretical Computer Science , 8(2):189 -201,1979.
• 23: Y.Zhang.Computational experience with the maximum-volume ellipsoid problem.In Informs National Meeting ,October 1998.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

  J. Computer Applications
  J.1 ADMINISTRATIVE DATA PROCESSING
      Subjects: Business

General Terms:
Design, Experimentation, Performance