# US 2012/0253922 A1 · Optimizing placement and delivery of advertisements

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0253922 A1
- Document ID: US20120253922A1
- Status: Published application
- Kind: A1
- Application number: 13/494,214
- Filed: 2012-06-12
- Published: 2012-10-04
- Earliest claimed: 2004-11-10
- Assignees: Google Inc.
- Inventors: Shumeet Baluja
- Web page: https://patentgrep.com/patent/US20120253922A1

## CPC

- G06Q 30/0275: {Auctions}
- G06Q 30/0238: at point-of-sale [POS]
- G06Q 30/0244: {Optimization}
- H04N 21/812: {involving advertisement data (advertising per se G06Q30/02)}
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

The efficient allocation of advertisements, also known as creatives, on one or more web sites is provided for while ensuring that guarantees to advertisers are honored. In one embodiment, a linear program solver allocates creatives to advertising slots according to an optimizing function designed to maximize revenue for the site. The linear program solver takes as input a set of creatives, creative performance data, constraints, and slot identifiers. The output of the linear program solver is an optimized schedule not violative of any of the input constraints.

## Claims

### Claim 1

A method, comprising:
obtaining proposed offer data that request distribution of a first set of advertisements according to first allocation constraints, the first allocation constraints specifying a maximum price that a first advertiser will pay for distribution of the first set of advertisements;
obtaining allocation data for a second set of advertisements to which slot inventory are currently allocated, the allocation data specifying:
second allocation constraints for the second set of advertisements, the second allocation constraints being indicative of a minimum amount of the slot inventory that must be allocated to the second set of advertisements; and
current allocations of the slot inventory to the second set of advertisements, the current allocations indicating that more than the minimum amount of the slot inventory is currently allocated to the second set of advertisements;
determining, based on the proposed offer data and the allocation data, that:
re-allocation of a portion of the slot inventory from the second set of advertisements to the first set of advertisements will increase total revenue generated by allocation of the slot inventory; and
after the re-allocation, at least the minimum amount of the slot inventory will remain allocated to the second set of advertisements; and
in response to the determination, re-allocating, in accordance with the first allocation constraints, the portion of the slot inventory from the second set of advertisements to the first set of advertisements, the re-allocation being performed without violating the second allocation constraints.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
obtaining an estimated amount of slot inventory that will be available with a publisher property;
determining, based on the proposed offer data, the estimated amount of slot inventory, and the current allocations, that at least a portion of the current allocations must be re-allocated in order to satisfy requirements of the first allocation constraints; and
distributing, according to the re-allocation, the first set of advertisements and the second set of advertisements for presentation with the publisher property.

### Claim 3 (depends on 2)

The method of claim 2, wherein determining that at least a portion of the current allocations must be re-allocated comprises determining that the first allocation constraints require allocation, to the first set of advertisements, of an amount of slot inventory that exceeds a remaining portion of the estimated amount of slot inventory that is not included in the current allocations.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
receiving the second allocation constraints, wherein the second allocation constraints include a maximum budget for the second set of advertisements;
determining, based on the second allocation constraints, that a portion of the budget required to provide the minimum amount of the slot inventory to the second set of advertisements is less than the maximum budget; and
in response to determining that the portion of the budget is less than the maximum budget, allocating more than the minimum amount of the slot inventory to the second set of advertisements.

### Claim 5 (depends on 4)

The method of claim 4, wherein the second allocation constraints specify that less than a particular portion of the maximum budget is to be spent on allocations of demographically targeted slot inventory, the demographically targeted slot inventory being a portion of the slot inventory that is presented to users that are part of a specified demographic group.

### Claim 6 (depends on 1)

The method of claim 1, wherein re-allocating the portion of the slot inventory comprises:
determining, based on the second allocation constraints, a minimum portion of the current allocations that must remain allocated to the second set of advertisements in order to satisfy the second allocation constraints;
identifying, based on the current allocations and the minimum portion, available slot inventory that is not included in the minimum portion of the current allocations; and
re-allocating, to the first set of advertisements, at least a portion of the available slot inventory.

### Claim 7 (depends on 6)

The method of claim 6, further comprising determining that at least a portion of the available slot inventory satisfies the first allocation constraints, wherein the re-allocating is further performed in response to determining that at least a portion of the available slot inventory satisfies the first allocation constraints.

### Claim 8 (depends on 6)

The method of claim 6, wherein the first allocation constraints require that one or more advertisements in the first set of advertisements be allocated demographically targeted slot inventory, the demographically targeted slot inventory being a portion of the slot inventory that is presented to users that are part of a specified demographic group.

### Claim 9 (depends on 6)

The method of claim 6, wherein determining that re-allocation of a portion of the slot inventory from the second set of advertisements to the first set of advertisements will increase the total revenue comprises determining that current revenue generated by the available slot inventory is less than proposed revenue that will be generated by re-allocating, to the first set of advertisements, at least a portion of the available slot inventory.

### Claim 10 (depends on 1)

The method of claim 1, wherein determining that after the re-allocation, at least the minimum amount of the slot inventory will remain allocated to the second set of advertisements comprises:
determining, based on the first allocation constraints, a first portion of the slot inventory that is required to be allocated to the first set of advertisements;
determining, based on the second allocation constraints, a second portion of the slot inventory that is required to be allocated to the second set of advertisements; and
determining that there is sufficient slot inventory to allocate both the first portion of slot inventory to the first set of advertisements and the second portion of the slot inventory to the second set of advertisements.

### Claim 11 (depends on 10)

The method of claim 10, wherein determining that the re-allocation of a portion of the slot inventory from the second set of advertisements to the first set of advertisements will increase total revenue generated by allocation of the slot inventory further comprises determining that proposed revenue generated by allocation of both the first portion of slot inventory and the second portion of the slot inventory is greater than current revenue generated by the current allocations.

### Claim 12 (depends on 1)

The method of claim 1, further comprising determining a portion of the slot inventory to be re-allocated from the second set of advertisements to the first set of advertisements, the determination being constrained by the second allocation constraints.

### Claim 13 (depends on 12)

The method of claim 12, wherein determining a portion of the slot inventory to be re-allocated comprises:
determining, based on the first allocation constraints, a first portion of the slot inventory that is required to be allocated to the first set of advertisements;
determining, based on the second allocation constraints, a second portion of the slot inventory that is required to be allocated to the second set of advertisements;
determining, based on the first portion, the second portion, and the slot inventory, that a portion of the current allocations of the slot inventory must be re-allocated to the first set of advertisements to satisfy the first allocation constraints; and
selecting the portion of the current allocations as the portion of the slot inventory to be re-allocated.

### Claim 14 (depends on 13)

The method of claim 13, wherein determining a portion of the slot inventory to be re-allocated further comprises:
determining that re-allocation of an additional portion of the current allocations to the first set of advertisements increases proposed revenue without violating the second allocation constraints; and
including the additional portion of the current allocations in the portion of the slot inventory to be re-allocated.

### Claim 15 (depends on 13)

The method of claim 13, wherein:
the first allocation constraints require that one or more advertisements in the first set of advertisements be allocated demographically targeted slot inventory, the demographically targeted slot inventory being a portion of the slot inventory that is presented to users that are part of a specified demographic group; and
the portion of the slot inventory that is re-allocated to the first set of advertisements includes the demographically targeted slot inventory.

### Claim 16

A method, comprising:
obtaining allocation data for a set of advertisements to which slot inventory are allocated, the allocation data specifying:
allocation constraints for the set of advertisements;
current allocations of the slot inventory to the set of advertisements;
determining, based on the allocation constraints, that the current allocations include allocation, to the set of advertisements, of additional slot inventory beyond a minimum portion of the slot inventory that is required to be allocated to satisfy the allocation constraints;
for each of one or more current allocations of the additional slot inventory:
determining, based on current revenue generated by allocating the additional slot inventory, a minimum price at which the additional slot inventory will be allocated through an auction; and
re-allocating at least one of the current allocations of the additional slot inventory through an auction, the re-allocation being based on the minimum price.

### Claim 17 (depends on 16)

The method of claim 16, further comprising:
determining, based on the minimum portion of the slot inventory that is required to be allocated for the set of advertisements, a remaining amount of slot inventory that remains after allocation of the minimum portion for the set of advertisements; and
allocating up to the remaining amount of the slot inventory through the auction.

### Claim 18 (depends on 17)

The method of claim 17, wherein allocating up to the remaining amount of the slot inventory comprises allocating a portion of the remaining amount of slot inventory for which an auction price for slot inventory is greater than the minimum price.

### Claim 19

A system comprising:
one or more computers; and
a storage device communicatively coupled to the one or more computers, the storage device storing instructions, that upon execution by the one or more computers, cause the one or more computers to perform operations including:
obtaining proposed offer data that request distribution of a first set of advertisements according to first allocation constraints, the first allocation constraints specifying a maximum price that a first advertiser will pay for distribution of the first set of advertisements;
obtaining allocation data for a second set of advertisements to which slot inventory are currently allocated, the allocation data specifying:
second allocation constraints for the second set of advertisements, the second allocation constraints being indicative of a minimum amount of the slot inventory that must be allocated to the second set of advertisements; and
current allocations of the slot inventory to the second set of advertisements, the current allocations indicating that more than the minimum amount of the slot inventory is currently allocated to the second set of advertisements;
determining, based on the proposed offer data and the allocation data, that:
re-allocation of a portion of the slot inventory from the second set of advertisements to the first set of advertisements will increase total revenue generated by allocation of the slot inventory; and
after the re-allocation, at least the minimum amount of the slot inventory will remain allocated to the second set of advertisements; and
in response to the determination, re-allocating, in accordance with the first allocation constraints, the portion of the slot inventory from the second set of advertisements to the first set of advertisements, the re-allocation being performed without violating the second allocation constraints.

### Claim 20 (depends on 19)

The system of claim 19, wherein the instructions further cause the one or more computers to perform operations including:
obtaining an estimated amount of slot inventory that will be available with a publisher property;
determining, based on the proposed offer data, the estimated amount of slot inventory, and the current allocations, that at least a portion of the current allocations must be re-allocated in order to satisfy requirements of the first allocation constraints; and
distributing, according to the re-allocation, the first set of advertisements and the second set of advertisements for presentation with the publisher property.

### Claim 21 (depends on 20)

The system of claim 20, wherein determining that at least a portion of the current allocations must be re-allocated comprises determining that the first allocation constraints require allocation, to the first set of advertisements, of an amount of slot inventory that exceeds a remaining portion of the estimated amount of slot inventory that is not included in the current allocations.

### Claim 22 (depends on 19)

The system of claim 19, wherein the instructions further cause the one or more computers to perform operations including:
receiving the second allocation constraints, wherein the second allocation constraints include a maximum budget for the second set of advertisements;
determining, based on the second allocation constraints, that a portion of the budget required to provide the minimum amount of the slot inventory to the second set of advertisements is less than the maximum budget; and
in response to determining that the portion of the budget is less than the maximum budget, allocating more than the minimum amount of the slot inventory to the second set of advertisements.

### Claim 23 (depends on 22)

The system of claim 22, wherein the second allocation constraints specify that less than a particular portion of the maximum budget is to be spent on allocations of demographically targeted slot inventory, the demographically targeted slot inventory being a portion of the slot inventory that is presented to users that are part of a specified demographic group.

### Claim 24 (depends on 19)

The system of claim 19, wherein re-allocating the portion of the slot inventory comprises:
determining, based on the second allocation constraints, a minimum portion of the current allocations that must remain allocated to the second set of advertisements in order to satisfy the second allocation constraints;
identifying, based on the current allocations and the minimum portion, available slot inventory that is not included in the minimum portion of the current allocations; and
re-allocating, to the first set of advertisements, at least a portion of the available slot inventory.

### Claim 25 (depends on 19)

The system of claim 19, wherein determining that after the re-allocation, at least the minimum amount of the slot inventory will remain allocated to the second set of advertisements comprises:
determining, based on the first allocation constraints, a first portion of the slot inventory that is required to be allocated to the first set of advertisements;
determining, based on the second allocation constraints, a second portion of the slot inventory that is required to be allocated to the second set of advertisements; and
determining that there is sufficient slot inventory to allocate both the first portion of slot inventory to the first set of advertisements and the second portion of the slot inventory to the second set of advertisements.

### Claim 26 (depends on 25)

The system of claim 25, wherein determining that the re-allocation of a portion of the slot inventory from the second set of advertisements to the first set of advertisements will increase total revenue generated by allocation of the slot inventory further comprises determining that proposed revenue generated by allocation of both the first portion of slot inventory and the second portion of the slot inventory is greater than current revenue generated by the current allocations.

### Claim 27 (depends on 19)

The system of claim 19, wherein the instructions further cause the one or more computers to perform operations including determining a portion of the slot inventory to be re-allocated from the second set of advertisements to the first set of advertisements, the determination being constrained by the second allocation constraints.

### Claim 28 (depends on 27)

The system of claim 27, wherein determining a portion of the slot inventory to be re-allocated comprises:
determining, based on the first allocation constraints, a first portion of the slot inventory that is required to be allocated to the first set of advertisements;
determining, based on the second allocation constraints, a second portion of the slot inventory that is required to be allocated to the second set of advertisements;
determining, based on the first portion, the second portion, and the slot inventory, that a portion of the current allocations of the slot inventory must be re-allocated to the first set of advertisements to satisfy the first allocation constraints; and
selecting the portion of the current allocations as the portion of the slot inventory to be re-allocated.

### Claim 29 (depends on 28)

The system of claim 28, wherein determining a portion of the slot inventory to be re-allocated further comprises:
determining that re-allocation of an additional portion of the current allocations to the first set of advertisements increases proposed revenue without violating the second allocation constraints; and
including the additional portion of the current allocations in the portion of the slot inventory to be re-allocated.

### Claim 30 (depends on 28)

The system of claim 28, wherein:
the first allocation constraints require that one or more advertisements in the first set of advertisements be allocated demographically targeted slot inventory, the demographically targeted slot inventory being a portion of the slot inventory that is presented to users that are part of a specified demographic group; and
the portion of the slot inventory that is re-allocated to the first set of advertisements includes the demographically targeted slot inventory.
