Optimal list order under partial memory constraints

Abstract

Suppose that we are given a set of n elements which are to be arranged in some order. At each unit of time a request is made to retrieve one of these elements — the ith being requested with probability P_i. We show that the rule which always moves the requested element one closer to the front of the line minimizes the average position of the element requested among a wide class of rules for all probability vectors of the form P₁ = p, P₂= · ·· = P_n = (1 – p)/(n − 1). We also consider the above problem when the decision-maker is allowed to utilize such rules as ‘only make a change if the same element has been requested k times in a row', and show that as k approaches infinity we can do as well as if we knew the values of the P_i.