Polyhedral sampling for multiattribute preference elicitation

ABSTRACT

A basic requirement for running multiattribute auctions is knowledge of the utility function of the buyer that trades off nonprice attributes against price. We present and study an approach that elicits this preference structure based on a markovian polyhedral sampling scheme called the "Hit-and-Run" algorithm. An advantage of this technique is its relative simplicity - it relies only on matrix algebra as opposed to the use of nonlinear optimization techniques by other methods in the literature. Computational results suggest that this method is fast and accurate.

REFERENCES

• 1: Boneh, A., and A. Golan, "Constraints' Redudancy and Feasible Region Boundedness by Random Feasible Point Generator (RFPG)", In Third European Congress on Operations Research, EURO III, Amsterdam (April 9-11).
• 2: Vijay S. Iyengar , Jon Lee , Murray Campbell, Evaluating multiple attribute items using queries, Proceedings of the 3rd ACM conference on Electronic Commerce, p.144-153, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501174]
• 3: Lovasz, L, "Hit-and-run mizes fast", Working paper, Microsoft Research, 2001.
• 4: R.L. Smith, "Efficient Monte Carlo Procedures for Generating Random Feasible Solutions over Bounded Regions", Operations Research Vol 32, 1984.
• 5: Toubia, O., D. Simester, and J.R. Hauser, "Fast Polyhedral Adaptive Conjoint Estimation", Working Paper, MIT Sloan School, May 2001.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms

Keywords:
markov chains, multiattribute utility, pairwise comparisons, polytopes, preference elicitation, sampling