B1427
Title: Probability forecasts for serving competing renewal processes for resource allocation
Authors: Samira Sadeghi - University of Alberta (Canada) [presenting]
Abstract: A probabilistic algorithm is constructed for resource allocation: several clients, with arrivals following processes of renewal type specific to each client, are competing for a resource; a reward for serving depends on the client. The motivation comes from television advertising: several networks (channels) broadcasting simultaneously insert commercial breaks, which are filled by a user-tailored content-resource. There is a limited number of resources: if more networks are to be served, some are rejected. The reward for serving the network depends on factors like the number of viewers. The current method is a first-come-first-serve algorithm serving requests in their incoming order. It is in general sub-optimal: if a lucrative network has a big probability of a commercial break in the near future, it may be more profitable to reserve the resource for it rather than serving the less rewarding ones. This raises a question of prediction: it turns out that in this situation, it is more appropriate to predict the probabilities rather than events themselves. The constructed algorithm is shown to yield better results for known probabilities; for estimated ones, experiments indicate that it outperforms the first-come-first-serve algorithm. We discuss several methods for predicting probability distributions relevant in this setting.
Journal