A facility for presenting advertising messages on behalf of multiple advertisers is described. The facility determines allocations that each specify a share for an advertiser, the specified shares all being different. The facility causes advertising messages to be presented on behalf of the advertisers in accordance with the shares specified by their allocations.