US2010312663A1PendingUtilityA1
Market Clearability in Combinatorial Auctions and Exchanges
Est. expiryApr 10, 2022(expired)· nominal 20-yr term from priority
G06Q 10/087G06Q 30/08
55
PatentIndex Score
0
Cited by
0
References
0
Claims
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.
Claims
exact text as granted — not AI-modified1 . A computer-implemented method of determining a winning allocation in an auction comprising:
(a) a processor of the computer receiving from each of a plurality of bidders for an item a bid for said item that includes a price-quantity curve; (b) the processor forming an aggregate curve that includes the sum of the quantities of the price-quantity curves; (c) the processor referencing the aggregate curve to a Cartesian coordinate system that has an origin where axes representing price and quantity meet; (d) the processor determining the position of a point on the aggregate curve that, for a forward auction, maximizes an area of a rectangle that is bounded by the origin and the aggregate curve and, for a reverse auction, minimizes the area of said rectangle; (e) the processor determining the position of a point on each price-quantity curve where the price associated therewith is the same as the price associated with the point on the aggregate curve; and (f) the processor including in the winning allocation in connection with the item, the price-quantity pairs associated with the points on the price-quantity curves.
2 . The method of claim 1 , wherein each price-quantity curve is either a linear curve, a piecewise linear curve, a non-linear curve, a piecewise non-linear curve, or one or more price-quantity pairs.
3 . The method of claim 1 , wherein, when the price-quantity curves are aggregated to form in the aggregate curve, each instance where a quantity on the aggregate curve has two or more prices associated therewith, the price having the greatest value is associated with said quantity.
4 . The method of claim 1 , wherein:
in a forward auction, the quantity associated with the point on the aggregate curve is no more than the total quantity of the item available; and in a reverse auction, the quantity associated with the point on the aggregate curve is no less than the total quantity of the item required.
5 . A computer-implemented method of determining a winning allocation in a forward auction comprising:
(a) a processor of the computer receiving from each of a plurality of bidders for an item a bid for said item that includes a price-quantity demand curve; (b) the processor referencing each demand curve to a Cartesian coordinate system that has an origin where axes representing price and quantity meet; (c) the processor determining a 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) the processor 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, the processor including in the winning allocation the price-quantity pairs associated with the points on the demand curves.
6 . The method of claim 5 , wherein each demand curve is either a linear curve, a piecewise linear curve, a non-linear curve, piecewise non-linear curve, or one or more price-quantity pairs.
7 . The method of claim 5 , further including:
(f) if the sum determined in step (d) is greater than the total quantity of the item available, the processor forming a list S of all the demand curves; (g) the processor identifying the demand curve in list S with the point having the lowest price associated therewith; (h) the processor adjusting the position of the points on the demand curves in list S whereupon the price associated with each adjusted point is increased by said lowest price; (i) the processor summing the quantities associated with the adjusted points on the demand curves in list S; and (j) if the sum determined in step (i) is no more than the total quantity of the item available, the processor including in the winning allocation for each demand curve in list S the quantity associated with the adjusted point on the demand curve and a price p i determined utilizing the equation
p
i
=
[
-
b
i
/
(
2
a
i
)
]
-
[
(
∑
j
in
S
b
j
-
2
Q
)
/
(
2
∑
j
in
S
a
j
)
]
where
S=list of demand curves;
i=the demand curve under consideration;
j in S=each demand curve j in S;
Q=total number of units of the item available;
a i and b i =coefficients of the demand curve under consideration,
i.e., q i =(a i )(p i )+b i ; and
a j and b j =coefficients of each demand curve in S, i.e., q j =(a j )(p j )+b j .
8 . The method of claim 7 , further including:
(k) if the sum determined in step (i) is greater than the total quantity of the item available, the processor deleting from list S the demand curve with the point having the lowest price associated therewith; and (l) the processor repeating steps (g)-(k) as necessary until the condition in step (j) is satisfied.
9 . A computer-implemented method of determining a winning allocation in a reverse auction comprising:
(a) a processor of the computer 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= a p+ 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) the processor sorting the supply curves in increasing order of the ratio b/a for each supply curve; (c) the processor determining for each supply curve in a list S of adjacent supply curves in the sorted order a clearing price p i and a clearing quantity q i utilizing the equations:
Clearing
quantity
:
q
i
=
(
-
b
i
/
2
)
+
(
a
i
/
2
)
(
(
2
Q
+
∑
j
in
S
b
j
)
/
(
∑
j
in
S
a
j
)
)
Clearing
price
:
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,
a i and b i =coefficients of the supply curve under consideration,
i.e., q i =(a i )(p i )+b i , and
a j and b j =coefficients of each supply curve in S, i.e., q j =(a j )(p j )+b j ;
(d) the processor 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, the processor including in the winning allocation the clearing prices and the clearing quantities determined thus far.
10 . The method of claim 9 , further including:
(f) if the clearing price having the largest value is greater than or equal to the ratio b/a of the next supply curve in the sorted order not already in list S, the processor including in list S the next supply curve in the sorted order that is not already in list S; and (g) the processor repeating steps (c)-(f) as necessary until the clearing prices and the clearing quantities determined thus far are included in the winning allocation in step (e).
11 . The method of claim 10 , further including the processor terminating the method if the clearing quantity q i of any seller in step (c) is determined to have a value less than zero.
12 . The method of claim 9 , wherein list S initially includes only the supply curve having the smallest ratio of b/a.
13 . A computer-implemented method of determining a winning allocation in an exchange comprising:
(a) a processor of the computer receiving from a buyer a price-quantity demand curve for an item; (b) the processor receiving from a seller a price-quantity supply curve for the item; (c) the processor referencing the demand and supply curves to a Cartesian coordinate system that has an origin where axes representing price and quantity meet; (d) the processor determining the positions of points on the demand and supply curves that maximize an area of a rectangle that is bounded by the demand and supply curves and the price axis, wherein each said point has the same quantity associated therewith and the price associated with the point on the demand curve is greater than the price associated with the point on the supply curve; and (e) the processor including in the winning allocation the price-quantity pairs associated with the points on the demand and supply curves.
14 . The method of claim 13 , wherein each of the demand and supply curves is either a linear curve, a piecewise linear curve, a non-linear curve, a piecewise non-linear curve, or one or more price-quantity pairs.
15 . A computer-implemented method of determining a winning allocation in an exchange comprising:
(a) a processor of the computer receiving from each of a plurality of buyers for an item a bid for said item that includes a price-quantity demand curve; (b) the processor receiving from each of a plurality of sellers of the item a bid for said item that includes a price-quantity supply curve; (c) the processor forming an aggregate demand curve that includes the sum of the quantities of the demand curves; (d) the processor forming an aggregate supply curve that includes the sum of the quantities of supply curves; (e) the processor 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) the processor 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) the processor 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) the processor 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) the processor 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.
16 . The method of claim 15 , wherein each demand curve and each supply curve is either a linear curve, a piecewise linear curve, a non-linear curve, a piecewise non-linear curve, or one or more price-quantity pairs.
17 . The method of claim 15 , wherein:
when demand curves are aggregated to form the aggregate demand curve, each instance where a quantity on the aggregate demand curve has two or more prices associated therewith, the price having the greatest value is associated with said quantity; and when supply curves are aggregated to form the aggregate supply curve, each instance where a quantity on the aggregate supply curve has two or more prices associated therewith, the price having the least value is associated with said quantity.
18 . A computer-implemented method of determining a winning allocation in an exchange comprising:
(a) a processor of the computer 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= a p+ 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) the processor 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) the processor forming an aggregate revenue-quantity demand curve as a function of the demand curves and the points determined thereon in step (b); (d) the processor forming an aggregate cost-quantity supply curve as a function of the supply curves; (e) the processor 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) the processor including in the winning allocation the price-quantity pairs associated with said points on the aggregate demand curve and the aggregate supply curve.
19 . The method of claim 18 , wherein step (c) includes:
the processor determining a value Q d equal to the sums of the quantities associated with the points determined in step (b) for the demand curves; and
20 . The method of claim 19 , wherein step (c) further includes:
(c)(1) the processor forming a list S d of the demand curves. (c)(2) the processor determining for each curve in the list S d a demand clearing price p i utilizing the equation:
p
i
=
(
b
i
/
2
a
i
)
+
(
1
/
2
)
(
(
∑
j
in
S
b
j
-
2
Q
d
)
/
(
∑
j
in
S
a
j
)
)
(c)(3) the processor determining for each curve in the list S d a demand clearing quantity q i utilizing the equation:
q
i
=
(
b
i
/
2
)
-
(
a
i
/
2
)
(
(
∑
j
in
S
b
j
-
2
Q
d
)
/
(
∑
j
in
S
a
j
)
)
where
i=the curve under consideration,
j in S d =each curve j in S d ,
a i and b i =coefficients of the curve under consideration,
i.e., q i =(a i )(p i )+b i , and
a j and b j =coefficients of each curve in S d ,
i.e., q j =(a j )(p j )+b j ;
(c)(4) for the curves in the list S d , the processor summing the thus determined demand clearing prices p i and summing the thus determined demand clearing quantities q i , wherein the sum of the demand clearing prices and the sum of the demand clearing quantities define a point on the aggregate demand curve;
(c)(5) the processor decreasing the value of Q d ; and
(c)(6) the processor repeating steps (c)(2)-(c)(5) until Q d equals zero.
21 . The method of claim 20 , wherein step (c)(5) includes:
the processor selecting one curve from the list S d ; the processor substituting the ratio b/a for said selected one curve for the value of p i in the equation of step (c)(1); the processor determining a new value for Q d by solving the equation of step (c)(1) with the substituted value of p i ; and the processor removing said selected one curve from the list S d .
22 . The method of claim 21 , wherein said selected one curve has the smallest ratio of b/a in the list S d .
23 . The method of claim 18 , wherein step (d) includes:
the processor setting a supply quantity value Q s equal to zero (0); the processor setting a supply clearing price value p i equal to zero (0), wherein the value of Q s and the value of p i define a point on the aggregate supply curve; and the processor including in a list S s the supply curve having the smallest ratio of b/a.
24 . The method of claim 23 , wherein step (d) further includes:
(d)(1) the processor including in the list S s the supply curve not already included therein having the next largest ratio b/a; (d)(2) the processor substituting the ratio b/a of the supply curve included in the list S s in step (d)(1) for the value of p i ; (d)(3) the processor solving the following equation for a new value Q s with the substituted value of p i , wherein the new value of Q s and the substituted value of p i define a point on the aggregate supply curve,
p
i
=
(
b
i
/
2
a
i
)
+
(
1
/
2
)
(
(
2
Q
s
+
∑
j
in
S
b
j
)
/
(
∑
j
in
S
a
j
)
)
;
where
i=the selected one supply curve,
j in S s =each curve j in S s ,
a i and b i =coefficients of the selected one supply curve,
i.e., q i =(a i )(p i )+b i , and
a j and b j =coefficients of each curve in S s ,
i.e., q j =(a j )(p j )+b j ;
and
(d)(4) the processor repeating steps (d)(1)-(d)(3) until Q s equals Q d or until all of the plurality of supply curves are included in the list S s .Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.