Monte Carlo Algorithms for Expected Utility Estimation in Dynamic Purchasing

  1. (PDF, 1 MB)
AuthorSearch for:
AbstractThis thesis describes a theory for decision-making in a dynamic purchasing environment where one of possibly many bundles of items must be purchased from possibly many suppliers. The <em>online combinatorial purchasing problem</em> is defined as the problem with which a purchase agent in such an environment is faced when deciding which combination of items, from whom and at what time to buy in order to maximize overall satisfaction. Expected utility maximization is used as the criterion on which decision-making is based. To facilitate the exchange of probabilistic and temporal information between suppliers and purchasers, the PQR protocol is defined. The theory considers two distinct purchasing models, one in which only complete bundle purchases can be made at any time, and one in which partial bundle purchases are allowed. In the first model, a decision procedure that exploits future time intervals where several options will be available is developed that provably yields higher expected utility than simply pursuing the bundle with highest expected utility. For the second model, the <em>QR</em>-tree is defined as a decision tree that can be exponentially smaller than conventional decision trees when used to model the same system of decisions. Efficient Monte Carlo methods are developed that solve the <em>QR</em>-tree in linear time on the number of nodes in the tree. Results show that these methods estimate expected utility as much as 25 times more accurately than a greedy method that always pursues the bundle with the current highest expected utility.
Publication date
PublisherUniversity of New Brunswick
PlaceFredericton, N.B., Canada
Peer reviewedNo
NRC number46557
NPARC number8913717
Export citationExport as RIS
Report a correctionReport a correction
Record identifier7c11798f-1714-4d30-90c0-ffcb55b95cbd
Record created2009-04-22
Record modified2016-05-09
Bookmark and share
  • Share this page with Facebook (Opens in a new window)
  • Share this page with Twitter (Opens in a new window)
  • Share this page with Google+ (Opens in a new window)
  • Share this page with Delicious (Opens in a new window)
Date modified: