Automated Channel Abstraction for Advertising Auctions

Abstract

In a computer-implemented method of determining an abstraction of a plurality of differentiated goods available for exchange, data regarding each differentiated good is stored in a computer storage, wherein the data regarding each differentiated good includes an attribute value assigned to at least one attribute of the differentiated good. A processor of a computer determines a first abstraction of the plurality of differentiated goods based on the stored data. The first abstraction includes at least one abstract good. Each abstract good includes one or more differentiated goods. At least one abstract good of the first abstraction includes at least two distinct differentiated goods. The processor determines for each abstract good a specification for the abstract good based on the data regarding one or more differentiated goods forming the abstract good. The processor stores in the computer storage the specification determined for each abstract good.

The invention claimed is: 
     
         1 . A computer-implemented method for determining an allocation of an abstraction of a plurality of differentiated goods to a set of offers comprising:
 (a) storing in a computer storage accessible to a processor of a computer an abstraction of a supply of differentiated goods, said abstraction comprising a set of one or more abstract goods, each abstract good an aggregation comprising at least one differentiated good, and at least one abstract good in the abstraction comprises at least two differentiated goods;   (b) storing in the computer storage data about at least one offer to purchase, where each offer to purchase includes at least one set of at least one of the plurality of differentiated goods and a price associated with said set of differentiated goods;   (c) storing in the computer storage a current allocation of none or a portion of each abstract good to each offer to purchase;   (d) the processor determining for each abstract good whether the current allocation is feasible or infeasible, wherein the current allocation is feasible when there is an allocation of differentiated goods to each offer to purchase assigned a portion of the abstract good in the current allocation such that: (i) the allocated differentiated goods are contained in the allocated abstract good; (ii) the allocated differentiated goods lie within the one or more sets of goods associated with said offer to purchase; and (iii) the quantity of allocated differentiated goods meets or exceeds the portion of the allocation of the abstract good allocated to the offer to purchase, and wherein the current allocation is infeasible when there is no such allocation of differentiated goods to each offer to purchase assigned a portion of the abstract good;   (e) when at least one abstract good is determined to be infeasible in step (d), the processor determining a new allocation of none or a portion of each abstract good to each offer to purchase that satisfies the constraint that, for any abstract good determined to be infeasible in step (d) and for all offers that are allocated a portion of said abstract good in the current allocation, the new allocation of said abstract good to each offer to purchase is feasible in that an allocation of differentiated goods exists that does not exceed the supply of any differentiated good, and designating the new allocation to be the current allocation; and   (f) repeating steps (d) and (e) until a termination condition is met.   
     
     
         2 . The computer-implemented method of  claim 1 , wherein the allocation of abstract goods to the set of at least one offer to purchase in steps (c) and (e) achieves one of the following objectives:
 maximizes total payments for a known supply of differentiated goods;   maximizes total estimated payments for an estimated supply of differentiated goods;   maximizes worst-case payments over a plurality of possible realizations of the estimated supply of differentiated goods,   maximizes risk-adjusted revenue or expected utility given a distribution on possible realizations of estimated supply of differentiated goods; or   maximizes total social welfare given estimated utility of buyers associated with offers to purchase and an estimated supply of differentiated goods.   
     
     
         3 . The computer-implemented method of  claim 1 , wherein the termination condition is one of the following:
 each abstract good is determined in step (d) to be feasible in the current allocation;   a number of repetitions of steps (d)-(e) meets or exceeds a threshold number of repetitions;   a computation time of steps (d)-(e) meets or exceeds a threshold computation time;   a number of abstract goods that are infeasible in the current allocation in step (d) falls below a threshold number of infeasible abstract goods;   a maximum amount of infeasibility for every abstract good in the current allocation in step (d) falls below a threshold amount of infeasibility, where the degree of feasibility for an abstract good given an allocation is based on the amount by which the quantity of supply required of goods to meet an assigned portion of abstract goods exceeds the available supply;   a value of the objective criteria achieved in determining the new allocation meets or exceeds a threshold value;   a value of the objective criteria achieved in determining the new allocation meets or falls below a threshold value; and   an absolute difference in the value of the objective criteria of the new allocation and the current allocation meets or falls below a threshold value.   
     
     
         4 . The computer-implemented method of  claim 1 , wherein:
 the allocation of abstract goods to offers in steps (c) and (e) is determined by the processor solving a linear or mixed integer program;   the processor determines the feasibility of the current allocation of the supply of an abstract good by checking the feasibility of a linear program that assigns to each offer assigned a portion of an abstract good, a quantity of each differentiated good that comprises the abstract good and lies within the one or more sets of goods associated with said offer, subject to a set of at least one constraint of a type (i) that requires respecting the available supply of each differentiate good and constraints of a type (ii) that require meeting or exceeding the portion of the abstract good allocated to said offer to purchase in the current allocation; and   for each abstract good that is determined to be infeasible in step (d), the processor determines a second set of constraints that is jointly infeasible and is comprised of at least one constraint from the set of constraints of type (i) and at least one constraint from the set of constraints of type (ii), and then introducing a new constraint based on this second set of jointly infeasible constraints to the determination of the new allocation in step (e).   
     
     
         5 . The computer-implemented method of  claim 4 , wherein the second set of constraints that are jointly infeasible is computed as a minimal infeasible set. 
     
     
         6 . The computer-implemented method of  claim 4 , wherein, in determining whether the allocation of an abstract good in the current allocation is feasible, the processor constructs a sub-abstraction of said abstract good, said sub-abstraction comprising a set of sub-abstract goods, each sub-abstract good comprising an aggregation of at least one differentiated good from the abstract good, and at least one sub-abstract good in the sub-abstraction comprising at least two differentiated goods from the abstract good. 
     
     
         7 . The computer-implemented method of  claim 1 , wherein:
 the differentiated goods available for exchange are advertising slots on television, internet or other media; and   the properties by which advertising slots are differentiable are of interest to a set of at least one potential advertiser.