Selecting and pricing content items including multiple bid amounts

A computer program product comprising a non-transitory computer-readable storage medium having instructions encoded thereon that, when executed by a processor, cause the processor to:

• maintain a plurality of advertisement requests (“ad requests”) at an online system, each ad request associated with a user and including a plurality of bid amounts, where each bid amount identifying an alternative user and specifying an amount of compensation from the user associated with the ad request to the online system;
• for each of the plurality of ad requests, determine connections between the ad requests and additional ad requests associated with alternative users, a connection between the ad request and an additional ad request associated with the alternative user including a bid amount included in the ad request identifying the alternative user;
• select an amount of compensation to the online system;
• remove connections between ad requests having bid amounts less than the selected amount of compensation;
• determine one or more groups of ad requests based on the connections, each ad request in a group having one or more connections to each other ad request in the group;
• in response to determining a single group of ad requests:
• increase the selected amount of compensation, removing connections between ad requests in the single group including bid amounts equaling the increased selected amount of compensation, and removing ad requests without a connection to at least one other ad request in the group until the single group includes a single ad request;
• select the single ad request;
• and
• determine a price to charge a user associated with the selected single ad request based on bid amounts included in connections from the selected single ad request to one or more other ad requests in the group most recently removed before selecting the single ad request;
• and
• in response to identifying more than a single group of ad requests:
• remove a group in which at least one ad request does not have a connection to another ad request that is not included in the group;
• determine connections between the groups, a connection between a group and an additional group including a bid amount based on bid amounts of ad requests in the group identifying users associated with ad requests in the additional group;
• and
• remove connections between groups based on the bid amounts included in the connections between groups and removing groups that are no longer connected to at least one other group after removing the connections between groups until the single group remains.