US 2003/0225628 A1 · Market clearability in combinatorial auctions and exchanges

Abstract

A method of determining a winning allocation in an auction or exchange includes receiving at least one buy bid that includes a price-quantity demand curve and/or receiving at least one sell bid that includes a price-quantity supply curve. The received curves are utilized to determine clearing prices therefor that maximize a clearing surplus. A winning allocation is determined based on the clearing prices.

Claims32

Dependent claims

A computer-implemented method of determining a winning allocation in an auction or exchange comprising:

receiving at least one buy bid that includes a price-quantity demand curve;
receiving at least one sell bid that includes a price-quantity supply curve;
utilizing the demand and supply curves to determine clearing prices for the buy and sell bids that maximize a clearing surplus;
and
determining a winning allocation based on the clearing prices.

2 more elements

A computer-implemented method of determining a winning allocation in a forward auction comprising:

(a) receiving from each of a plurality of bidders for an item a bid for said item that includes a price-quantity demand curve;
(b) referencing each demand curve to a Cartesian coordinate system that has an origin where axes representing price and quantity meet;
(c) determining the position of a point on each demand curve that maximizes an area of a rectangle that is bounded by said demand curve and said origin;
(d) summing the quantities associated with the points on the demand curves;
and
(e) if the sum determined in step (d) is no more than the total quantity of the item available, including in the winning allocation the price-quantity pairs associated with the points on the demand curves.

3 more elements

A computer-implemented method of determining a winning allocation in a reverse auction comprising:

(a) receiving from each of a plurality of sellers of an item a bid for said item that includes a price-quantity supply curve of the form
q=ap+b,
where
q=quantity,
p=price,
a=slope of the supply curve, and
b=offset of the quantity of the supply curve from a quantity of zero;
(b) sorting the supply curves in increasing order of the ratio b/a for each supply curve;
(c) determining for each supply curve in a list S of adjacent supply curves in the sorted order a clearing price pi and a clearing quantity qi utilizing the equations:
8 c ⁢ learing ⁢ ⁢ quantity :
⁢ q i = ( - b i / 2 ) + ( a i / 2 ) ⁢ ( ( 2 ⁢ Q + ∑ j ⁢ ⁢ in ⁢ ⁢ S ⁢ ⁢ b j ) / ( ∑ j ⁢ ⁢ in ⁢ ⁢ S ⁢ ⁢ a j ) ) ⁢ c ⁢ learing ⁢ ⁢ price :
⁢ p i = ( - b i / 2 ⁢ a i ) + ( 1 / 2 ) ⁢ ( ( 2 ⁢ Q + ∑ j ⁢ ⁢ in ⁢ ⁢ S ⁢ ⁢ b j ) / ( ∑ j ⁢ ⁢ in ⁢ ⁢ S ⁢ ⁢ a j ) )
clearing price:
9 p i = ( - b i / 2 ⁢ a i ) + ( 1 / 2 ) ⁢ ( ( 2 ⁢ Q + ∑ j ⁢ ⁢ in ⁢ ⁢ S ⁢ ⁢ ⁢ b j ) / ( ∑ j ⁢ ⁢ in ⁢ ⁢ S ⁢ ⁢ ⁢ a j ) )
where
i=the supply curve under consideration,
j in S=each supply curve j in S,
Q=total number of units of the item available,
ai and bi=coefficients of the supply curve under consideration, i.e., qi=(ai)(pi)+bi, and
aj and bj=coefficients of each supply curve in S, i.e., qj=(aj)(pj)+bj;
(d) identifying from the clearing prices determined thus far the clearing price having the largest value;
and
(e) if the value of the clearing price having the largest value is less than the ratio b/a of the next supply curve in the sorted order that is not already in list S or if list S includes all of the supply curves, including in the winning allocation the clearing prices and the clearing quantities determined thus far.

20 more elements

A computer-implemented method of determining a winning allocation in an exchange comprising:

(a) receiving from each of a plurality of buyers for an item a bid for said item that includes a price-quantity demand curve;
(b) receiving from each of a plurality of sellers of the item a bid for said item that includes a price-quantity supply curve;
(c) forming an aggregate demand curve that includes the sum of the quantities of the demand curves;
(d) forming an aggregate supply curve that includes the sum of the quantities of supply curves;
(e) referencing the aggregate demand curve and the aggregate supply curve to a Cartesian coordinate system that has an origin where axes representing price and quantity meet;
(f) determining the position of a point on each of the aggregate demand curve and the aggregate supply curve that maximize an area of a rectangle that is bounded by the aggregate demand curve, the aggregate supply curve and the price axis, wherein each said point has the same quantity associated therewith and the price associated with the point on the aggregate demand curve is greater than the price associated with the point on the aggregate supply curve;
(g) determining the position of a point on each demand curve where the price associated therewith is the same as the price associated with the point on the aggregate demand curve;
(h) determining the position of a point on each supply curve where the price associated therewith is the same as the price associated with the point on the aggregate supply curve;
and
(i) including in the winning allocation in connection with the item, the price-quantity pairs associated with the points on the demand curves and the points on the supply curves.

7 more elements

A computer-implemented method of determining a winning allocation in an exchange comprising:

(a) receiving a plurality of price-quantity demand curves and a plurality of price-quantity supply curves, wherein each demand curve and each supply curve is of the form:
q=ap+b,
where
q=quantity,
p=price,
a=slope of the supply curve, and
b=offset of the quantity of the supply curve from a quantity of zero;
(b) determining for each price-quantity demand curve the point thereon where the product of the price-quantity pair represented by said point is maximized;
(c) forming an aggregate revenue-quantity demand curve as a function of the demand curves and the points determined thereon in step (b);
(d) forming an aggregate cost-quantity supply curve as a function of the supply curves;
(e) comparing the aggregate demand curve and the aggregate supply curve to determine the location of points thereon where a difference in price therebetween for a specific quantity is maximized;
and
(f) including in the winning allocation the price-quantity pairs associated with said points on the aggregate demand curve and the aggregate supply curve.

10 more elements

Dependencies are inferred from the claim text.

Facts

Application

10/410,876Filed 10 Apr 2003

Priority

10 Apr 2002

Published

4 Dec 2003

Term ends

Not estimatedThe source records don’t support an estimate.

Classification3 codes

G06Q 30/08
Buying, selling or leasing transactions: auctions
G06Q 10/087
Logistics, e.g. warehousing, loading or distribution; Inventory or stock management: inventory or stock management, e.g. order filling,…
G06Q
Information and communication technology [ict] specially adapted for administrative, commercial, financial, managerial

Abstract

Claims32

Dependent claims

A computer-implemented method of determining a winning allocation in an auction or exchange comprising:

receiving at least one buy bid that includes a price-quantity demand curve;
receiving at least one sell bid that includes a price-quantity supply curve;
utilizing the demand and supply curves to determine clearing prices for the buy and sell bids that maximize a clearing surplus;
and
determining a winning allocation based on the clearing prices.

2 more elements

A computer-implemented method of determining a winning allocation in a forward auction comprising:

(a) receiving from each of a plurality of bidders for an item a bid for said item that includes a price-quantity demand curve;
(b) referencing each demand curve to a Cartesian coordinate system that has an origin where axes representing price and quantity meet;
(c) determining the position of a point on each demand curve that maximizes an area of a rectangle that is bounded by said demand curve and said origin;
(d) summing the quantities associated with the points on the demand curves;
and
(e) if the sum determined in step (d) is no more than the total quantity of the item available, including in the winning allocation the price-quantity pairs associated with the points on the demand curves.

3 more elements

A computer-implemented method of determining a winning allocation in a reverse auction comprising:

(a) receiving from each of a plurality of sellers of an item a bid for said item that includes a price-quantity supply curve of the form
q=ap+b,
where
q=quantity,
p=price,
a=slope of the supply curve, and
b=offset of the quantity of the supply curve from a quantity of zero;
(b) sorting the supply curves in increasing order of the ratio b/a for each supply curve;
(c) determining for each supply curve in a list S of adjacent supply curves in the sorted order a clearing price pi and a clearing quantity qi utilizing the equations:
8 c ⁢ learing ⁢ ⁢ quantity :
⁢ q i = ( - b i / 2 ) + ( a i / 2 ) ⁢ ( ( 2 ⁢ Q + ∑ j ⁢ ⁢ in ⁢ ⁢ S ⁢ ⁢ b j ) / ( ∑ j ⁢ ⁢ in ⁢ ⁢ S ⁢ ⁢ a j ) ) ⁢ c ⁢ learing ⁢ ⁢ price :
⁢ p i = ( - b i / 2 ⁢ a i ) + ( 1 / 2 ) ⁢ ( ( 2 ⁢ Q + ∑ j ⁢ ⁢ in ⁢ ⁢ S ⁢ ⁢ b j ) / ( ∑ j ⁢ ⁢ in ⁢ ⁢ S ⁢ ⁢ a j ) )
clearing price:
9 p i = ( - b i / 2 ⁢ a i ) + ( 1 / 2 ) ⁢ ( ( 2 ⁢ Q + ∑ j ⁢ ⁢ in ⁢ ⁢ S ⁢ ⁢ ⁢ b j ) / ( ∑ j ⁢ ⁢ in ⁢ ⁢ S ⁢ ⁢ ⁢ a j ) )
where
i=the supply curve under consideration,
j in S=each supply curve j in S,
Q=total number of units of the item available,
ai and bi=coefficients of the supply curve under consideration, i.e., qi=(ai)(pi)+bi, and
aj and bj=coefficients of each supply curve in S, i.e., qj=(aj)(pj)+bj;
(d) identifying from the clearing prices determined thus far the clearing price having the largest value;
and
(e) if the value of the clearing price having the largest value is less than the ratio b/a of the next supply curve in the sorted order that is not already in list S or if list S includes all of the supply curves, including in the winning allocation the clearing prices and the clearing quantities determined thus far.

20 more elements

A computer-implemented method of determining a winning allocation in an exchange comprising:

(a) receiving from each of a plurality of buyers for an item a bid for said item that includes a price-quantity demand curve;
(b) receiving from each of a plurality of sellers of the item a bid for said item that includes a price-quantity supply curve;
(c) forming an aggregate demand curve that includes the sum of the quantities of the demand curves;
(d) forming an aggregate supply curve that includes the sum of the quantities of supply curves;
(e) referencing the aggregate demand curve and the aggregate supply curve to a Cartesian coordinate system that has an origin where axes representing price and quantity meet;
(f) determining the position of a point on each of the aggregate demand curve and the aggregate supply curve that maximize an area of a rectangle that is bounded by the aggregate demand curve, the aggregate supply curve and the price axis, wherein each said point has the same quantity associated therewith and the price associated with the point on the aggregate demand curve is greater than the price associated with the point on the aggregate supply curve;
(g) determining the position of a point on each demand curve where the price associated therewith is the same as the price associated with the point on the aggregate demand curve;
(h) determining the position of a point on each supply curve where the price associated therewith is the same as the price associated with the point on the aggregate supply curve;
and
(i) including in the winning allocation in connection with the item, the price-quantity pairs associated with the points on the demand curves and the points on the supply curves.

7 more elements

A computer-implemented method of determining a winning allocation in an exchange comprising:

(a) receiving a plurality of price-quantity demand curves and a plurality of price-quantity supply curves, wherein each demand curve and each supply curve is of the form:
q=ap+b,
where
q=quantity,
p=price,
a=slope of the supply curve, and
b=offset of the quantity of the supply curve from a quantity of zero;
(b) determining for each price-quantity demand curve the point thereon where the product of the price-quantity pair represented by said point is maximized;
(c) forming an aggregate revenue-quantity demand curve as a function of the demand curves and the points determined thereon in step (b);
(d) forming an aggregate cost-quantity supply curve as a function of the supply curves;
(e) comparing the aggregate demand curve and the aggregate supply curve to determine the location of points thereon where a difference in price therebetween for a specific quantity is maximized;
and
(f) including in the winning allocation the price-quantity pairs associated with said points on the aggregate demand curve and the aggregate supply curve.

10 more elements

Dependencies are inferred from the claim text.

Market clearability in combinatorial auctions and exchanges

Life of this patent

Abstract

Claims32

Market clearability in combinatorial auctions and exchanges

Life of this patent

Abstract

Claims32