Optimal stochastic auctions for constrained sponsored search

摘要

Disclosed are methods and apparatus for processing an auction for sponsored search according to a set of constraints. In accordance with one embodiment, a polyhedron that incorporates a set of one or more restrictions is defined, 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. A subset of the plurality of allocations is obtained via application of an analysis tool to the polyhedron. One of the subset of the plurality of allocations is then identified, enabling the ads in the allocation to be displayed.