Generalized online matching and real time risk management
AssigneeMicrosoft Corporation
InventorKamal Jain
Life of this patent
Estimating the term…
Abstract
The claimed subject matter provides an architecture and associated schema for facilitating advantageous solutions the generalized online matching problem. The architecture can employ a blended schema that includes distinct aspects of both primal-dual schema and dual-fitting schema. In accordance therewith, the blended schema can provide algorithms that yield solutions in accordance with a competitive ratio of 1−1/e. In addition, the blended schema can be extended to provide for rich risk management features. Further, an addition of stochastic information can be employed in connection with the blended schema to improve the results beyond the competitive ratio.
Claims15
A computer-implemented system that allocates advertisements to ad-slots, comprising:
- a memory;
- a processing unit coupled to the memory;
- a blended schema that incorporates properties of both a primal-dual schema and a dual-fitting schema, the blended schema simultaneously maintaining feasible duals and bounded duals for individual iterations, wherein:
- a property of the primal-dual schema that is incorporated into the blended schema includes maintaining the feasible duals for individual iterations;
- and
- a property of the dual-fitting schema that is incorporated into the blended schema includes maintaining the bounded duals for individual iterations;
- and
- a matching component configured to be operated on the processing unit to match an ad slot offered by an ad host to an ad from an advertiser based at least in part upon the blended schema under a relaxed assumption that a bid from the advertiser is negligible compared to an advertising budget of the advertiser and is to be ignored.
A method, executed by a processing unit for allocating ads from advertisers to ad slots from ad hosts, the method comprising:
- utilizing a blended schema for satisfying a performance ratio of 1−(1/e), the blended schema incorporating properties of both a dual-fitting schema and a primal-dual schema, wherein:
- a property of the primal-dual schema that is incorporated into the blended schema includes maintaining feasible duals for individual iterations;
- and
- a property of the dual-fitting schema that is incorporated into the blended schema includes maintaining bounded duals for individual iterations;
- evaluating the blended schema iteratively based on a greedy criteria;
- simultaneously maintaining a feasible primal, a feasible dual and a bound dual for individual iterations;
- and
- allocating by the processing unit, the ads from the advertisers that are matched to the ad slots from the ad hosts based at least in part upon the blended schema under a relaxed assumption that a bid from a particular advertiser is negligible compared to an advertising budget of the particular advertiser and is to be ignored.
A computer-implemented system for allocating ads from advertisers to ad slots from ad hosts, comprising:
- one or more processors;
- and
- memory to store computer readable instructions that, when executed, cause the one or more processors to perform acts that:
- utilize a blended schema for meeting a performance ratio metric of 1−(1/e), the blended schema incorporating properties of both a dual-fitting schema and a primal-dual schema, wherein:
- a property of the primal-dual schema that is incorporated into the blended schema includes maintaining feasible duals for individual iterations;
- and
- a property of the dual-fitting schema that is incorporated into the blended schema includes maintaining bounded duals for individual iterations;
- evaluate the blended schema iteratively based on a greedy criteria;
- simultaneously maintain a feasible dual and a bound dual for individual iterations;
- and
- distribute the ads to the ad slots based at least in part upon the blended schema under a relaxed assumption that a bid from a particular advertiser is negligible compared to an advertising budget of the particular advertiser and is to be ignored.
Dependencies are inferred from the claim text.