Optimal stochastic auctions for constrained sponsored search

A computer-readable medium storing thereon computer-readable instructions, comprising:

• instructions for defining a polyhedron that incorporates a set of one or more restrictions, wherein the polyhedron that incorporates the set of one or more restrictions represents a plurality of allocations, wherein each of the plurality of allocations is a subset of a plurality of ads to be displayed on a particular occurrence of a search query received via a search engine;
• instructions for obtaining a subset of the plurality of allocations via application of an analysis tool to the polyhedron;
• and
• instructions for identifying one of the subset of the plurality of allocations.

An apparatus, comprising:

• a processor;
• and
• a memory, at least one of the processor or the memory being adapted for:
• defining a polyhedron that incorporates a set of one or more restrictions, wherein the polyhedron that incorporates the set of one or more restrictions represents a plurality of allocations, wherein each of the plurality of allocations is a subset of a plurality of ads to be displayed on a particular occurrence of a search query received via a search engine;
• obtaining a subset of the plurality of allocations via application of an analysis tool to the polyhedron;
• and
• identifying one of the subset of the plurality of allocations.