A facility for selecting an advertising message to present to a user via a selected device in connection with a selected instance of electronic content presented via the device is described. For the selected instance of electronic content, as well as any other instances of electronic content that were previously presented via the selected device during an immediately preceding period of time of preselected length, the facility distinguishes any subjects identified as corresponding to the instance of electronic content. Among a number of advertising messages, the facility distinguishes advertising messages identified as corresponding to any of the distinguished subjects. The facility weights each of the distinguished advertising messages based upon its expected level of performance, and randomly selects one of the distinguished advertising messages in accordance with their weights for presentation in connection with the selected instance of electronic content via the selected device.