Monte Carlo algorithms for expected utility estimation in dynamic purchasing

This 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 online combinatorial purchasing problem 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 QR-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 QR-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.