System and method for conducting combinatorial exchanges

• US 20070011080A1
• Filed: 03/23/2006
• Published: 01/11/2007
• Est. Priority Date: 03/23/2005
• Status: Active Grant

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Jain, Rahul, Varaiya, Pravin, Rajagopal, Ram, Shu, Jun, Pillai, Nisha, Kaskiris, Charis
• Granted Patent: US 7,627,510 B2
• Time in Patent Office: Days
• US Class Current: 705/37
• CPC Class Codes: G06Q 30/06 Buying, selling or leasing transactions
• CPC Class Codes: G06Q 30/08 Auctions
• CPC Class Codes: G06Q 40/00 Finance; Insurance; Tax strategies; Processing of corporate or income taxes
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange
• CPC Class Codes: G06Q 40/06 Asset management; Financial planning or analysis

Abstract

A system and method for implementing a double-sided exchange. In an illustrative embodiment, the double-sided exchange may be an exchange wherein both buyers and sellers provide bids for matching via the exchange. A first interface receives one or more buy bids from one or more buyers and a second interface receives one or more sell bids from one or more sellers. A controller matches the one or more sell bids with the one or more buy bids, yielding one or more matched buy bids and one or more matched sell bids in response thereto so that allocations of the matched one or more buy bids and the one or more matched sell bids maximize a surplus of the exchange. Certain embodiments of the present invention may provide an allocation that substantially maximizes an auctioneer'"'"'s profit and/or announces payments based on one or more sell bids. The announced allocations and prices can be shown to be a substantially competitive equilibrium in some applications.

Claims

1. A double-sided exchange, the exchange comprising:

a first interface for receiving one or more buy bids from one or more buyers;

a second interface for receiving one or more sell bids from one or more sellers; and

a controller for matching the one or more sell bids with the one or more buy bids, yielding one or more matched buy bids and one or more matched sell bids in response thereto so that allocations of the one or more matched buy bids and the one or more matched sell bids maximize a surplus of the exchange.

2. The exchange of claim 1, wherein the controller further includes first means for determining a settlement price for a thing to be exchanged via the exchange, wherein the settlement price includes a highest ask price among one or more matched sell bids.

3. The exchange of claim 2, wherein the settlement price is uniform for similar things being exchanged.

4. The exchange of claim 2, wherein the double-sided exchange is a combinatorial double-sided exchange.

5. The exchange of claim 4, wherein the one or more buy bids include one or more bid prices for one or more bundles of things, wherein the one or more bundles of things must be matched in their entirety for an exchange pertaining to the one or more buy bids to occur.

6. The exchange of claim 5, wherein the one or more sell bids include one or more ask prices for individual things.

7. The exchange of claim 2, wherein the surplus is defined according to the following expression:

$\underset{i}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>b_i<br><br>x_i-\underset{j}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>a_j<br><br>y_j,$

where x_i may be an integer 0≦

x_i≦

δ

_i representing a number of bundles of type R_i that are to be allocated to an i^th buyer;

i may be an integer index where 0≦

i≦

M where M may be a number of buyers participating in the exchange;

δ

_i represents a maximum number of units of the bundle R_i demanded by the i^th buyer;

b_i may represent a buy bid price or finction thereof per unit of the bundle R_i;

y_j may be an integer number of units such that 0≦

y_j≦

σ

_j, where σ

_j may be a number of units of an item l_j sold by a j^th seller, where j may be an integer index, where 0≦

j≦

N, where N may be a number of sellers participating in the exchange; and

a_j may be an ask price or function thereof for an item l_j offered by the j^th seller.

8. The exchange of claim 7, wherein the exchange is constrained so that one or more of the buyers bid on bundles and require that full demand is met for a given bid, otherwise a corresponding transaction is not made, while a seller may offer individual things and may sell any integral part of a capacity of the seller.

9. The exchange of claim 8, wherein total supply of a given thing being traded via the exchange is greater than or equal to total demand for the given thing.

10. The exchange of claim 7, wherein the settlement price ({circumflex over (p)}_l) for an item (l) is defined according to the following equation:

{circumflex over (p)}_l=max{a_j;

y_j*>

0,l∈

L_j},

where L_j may be a set of items of which item l is an element;

y_j^* may be a number of items l allocated for sale or exchange and associated with a matched seller ask price.

11. The exchange of claim 10, wherein each of the one or more buy bids include an offered buy price for a bundle of things to be exchanged.

12. The exchange of claim 11, wherein each of the one or more sell bids include an offered sell price for one or more of the things.

13. The exchange of claim 12, wherein the controller further includes second means for determining payments for buyers based on a sum of prices of things in the bundle.

14. The exchange of claim 13, wherein the second means further includes third means for determining payments to sellers based on a number of certain things sold via the exchange multiplied by the settlement price for the certain things.

15. A combinatorial double exchange, the exchange comprising:

one or more buy bids for bundles of things;

one or more sell bids pertaining to things in the bundles of things;

a first exchange mechanism for matching one or more of the buy bids with the one or more sell bids to maximize a social surplus for the exchange, yielding one or more matched buy bids and one or more matched sell bids in response thereto; and

second exchange mechanism for determining a settlement price for a the one or more matched buy bids and the one or matched sell bids based on an ask price offered by one or more sellers associated with the one or more matched sell bids.

16. The exchange of claim 15, wherein the ask price includes a highest ask price (max (a_j)) among numbers (y*) of matched sell bids.

17. The exchange of claim 16, wherein each buyer associated with the one or more buy bids is associated with a first quasi-linear utility function.

18. The exchange of claim 17, wherein the first quasi-linear utility function (u_i^b(x;

w, R_i)) is defined in accordance with the following equations;

$u_i^b<br><br>\left(x;<br><br>w,R_i\right)={\stackrel{\_}{v}}_i<br><br>\left(x\right)+w;<br><br>$ ${\stackrel{\_}{v}}_i<br><br>\left(x\right)=\{\begin{array}{cc}x·<br><br>v_i,& \mathrm{for}<br><br>\text{\hspace{1em}<br><br>}<br><br>x\le <br><br>{\mathrm{\delta <br><br>}}_i,\\ {\mathrm{\delta <br><br>}}_i·<br><br>v_i,& \mathrm{for}<br><br>\text{\hspace{1em}<br><br>}<br><br>x><br><br>{\mathrm{\delta <br><br>}}_i\end{array}$

where x may be an integer 0≦

x≦

δ

_i representing a number of bundles of type R_i that are to be allocated to an i^th buyer;

w may represent money;

v_i may represent a reservation value corresponding to a maximum amount an i^th buyer is willing to pay for x bundles of things.

19. The exchange of claim 17, wherein each seller associated with the one or more sell bids is associated with a second quasi-linear utility function.

20. The exchange of claim 19, wherein the second quasi-linear utility function is defined in accordance with the following equations:

$u_j^s<br><br>\left(x;<br><br>w,L_j\right)=-{\stackrel{\_}{c}}_j<br><br>\left(y\right)+w;<br><br>$ ${\stackrel{\_}{c}}_j<br><br>\left(y\right)=\{\begin{array}{cc}y·<br><br>c_j,& \mathrm{for}<br><br>\text{\hspace{1em}<br><br>}<br><br>y\le <br><br>{\mathrm{\sigma <br><br>}}_j,\\ \mathrm{\infty <br><br>},& \mathrm{for}<br><br>\text{\hspace{1em}<br><br>}<br><br>y><br><br>{\mathrm{\sigma <br><br>}}_j\end{array}$

where y may be an integer number of units such that 0≦

y≦

σ

_j, where σ

_j may be a number of units of an item l_j sold by a j^th seller;

w may represent money;

c_j may represent true cost per thing for a the j^th seller for y amount of things; and

L_j may be a set of all items l_j being sold by the j^th seller.

21. The exchange of claim 15, wherein the first exchange mechanism further includes a first module adapted to determine the matched buy bids and the matched sell bids in accordance with a Mixed Integer Program (MIP).

22. The exchange of claim 21, wherein the MIP is subject to a constraint requiring that supply be greater than or equal to demand.

23. The exchange of claim 22, wherein the MIP is adapted to maximize social surplus for the exchange.

24. The exchange of claim 21, wherein the MIP is implemented in accordance with the following equations:

$\underset{x,y}{\max }<br><br>\left[\underset{i}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>b_i<br><br>x_i-\underset{j}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>a_j<br><br>y_j\right]$ $\mathrm{where}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{j;<br><br>l\in <br><br>L_j}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>y_j\ge <br><br>\underset{i;<br><br>l\in <br><br>R_i}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>x_i,\text{\hspace{1em}<br><br>}<br><br>\forall <br><br>l\in <br><br>\left[1;<br><br>L\right],<br><br>x_i\in <br><br>\left\{0,1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},{\mathrm{\delta <br><br>}}_i\right\},\text{\hspace{1em}<br><br>}<br><br>\forall <br><br>i,\text{\hspace{1em}<br><br>}<br><br>y_j\in <br><br>\left[0,{\mathrm{\sigma <br><br>}}_j\right].\text{\hspace{1em}<br><br>}<br><br>\forall <br><br>j$

where x_i may be an integer 0≦

x_i≦

δ

_i representing a number of bundles of type R_i that are to be allocated to an i^th buyer;

i may be an integer index where 0≦

i≦

M where M may be a number of buyers participating in the exchange;

δ

_i represents a maximum number of units of the bundle R_i demanded by the i^th buyer;

b_i may represent a buy bid price or function thereof per unit of the bundle R_i;

y_j may be an integer number of units such that 0≦

y_j≦

σ

_j, where σ

_j may be a number of units of an item l_j sold by a j^th seller, where j may be an integer index, where 0≦

j≦

N, where N may be a number of sellers participating in the exchange; and

a_j may be an ask price or function thereof for an item l_j offered by the j^th seller;

L may be a total number of items or things l being allocated for exchange; and

L_j may be a set of all items or things l_j being sold by the j^th seller.

25. A combinatorial double exchange, the exchange comprising:

first means for receiving one or more buy bids and one or more sell bids, wherein the one or more buy bids and/or the one or more sell bids are combinatorial;

second means for matching a buy bid with a sell bid in accordance with an exchange rule that maximizes exchange surplus, and providing a matched buy bid and a matched sell bid in response thereto; and

third means for determining a settlement price for the combinatorial double exchange based on an ask price associated with the matched sell bid.

26. The exchange of claim 25, wherein the ask price includes a highest ask price among one or more matched sellers participating in the combinatorial double exchange.

27. The exchange of claim 26, wherein each of the one or more buy bids include a bid price for one or more bundles of a thing;

a maximum number of bundles needed;

a maximum number of bundles demanded during a current exchange session.

28. The exchange of claim 27, wherein each of the one or more sell bids include an ask price for one or more things associated with a bundle;

a maximum supply of the things; and

a maximum number of things offered.

29. An exchange, the exchange comprising:

first means for implementing an efficient, budget-balanced, individually rational market mechanism that is approximately dominant strategy incentive compatible, when participants in the exchange have knowledge of strategies available to other participants in the exchange and

second means for implementing a budget-balanced, individual rational, incentive compatible, and asymptotically efficient market mechanism when participants in the exchange lack information pertaining to strategies available to other participants in the exchange.

30. The exchange of claim 29, further including third means for implementing the first means for incomplete-information applications and implementing the second means for complete-information applications.

31. The exchange of claim 29, wherein the first means and the second means are implemented so that any Nash equilibrium allocation associated with the exchange is efficient.

32. The exchange of claim 31, wherein the first means and the second means are implemented so that any semi-symmetric Bayesian-Nash equilibrium allocation is asymptotically efficient.

33. A method for implementing a double exchange , the method comprising:

accepting a first set of buy bids from buy bids from buyers;

receive a first set of sell bids from sellers;

employing an optimization engine to match one or more sell bids with one or more buy bids, yielding one or more matched buy bids and one or more matched sell bids in response thereto;

using the optimization engine to determine a uniform settlement price based on a highest ask price among one or more matched sell bids; and

scheduling payments so that matched buyers pay a sum of the settlement prices of things in a matched bid for a bundle of the things, and so that matched sellers receive a payment equal to the number of things sold multiplied by the settlement price for the item.

34. The method of claim 33, wherein the one or more buy bids each include a buy price per bundle, wherein each bundle includes up to (δ

_i) items or things.

35. The method of claim 34, wherein the one or more buy bids further specify maximum bundles needed and maximum bundles demanded for a given buy bid.

36. The method of claim 33, wherein the one or more sell bids each include a sell price per item or thing, a maximum number of items or things offered;

and maximum supply.

37. The method of claim 36, wherein the optimization engine further determines allocations for units sold and allocations of units bought so as to maximize auction surplus.

38. The method of claim 37, wherein the optimization engine operates with a constraint specifying that supply is greater than demand.

39. The method of claim 38, wherein the optimization engine implements a Mixed Integer Program (MIP).

40. A method for implementing a combinatorial double exchange, the method comprising:

receiving one or more buy bids and one or more sell bids, wherein the one or more buy bids and/or the one or more sell bids are combinatorial;

matching a buy bid with a sell bid in accordance with an exchange rule that maximizes exchange surplus, and providing a matched buy bid and a matched sell bid in response thereto; and

determining a settlement price for the combinatorial double exchange based on an ask price associated with the matched sell bid.

41. A method for determining a winning bid in a combinatorial exchange, comprising:

(a) receiving first bids from one or more buyers, wherein each of the first bids includes one or more items and a first bid price associated with each of the one or more items;

(b) receiving second bids from one or more sellers, wherein each of the second bids includes one or more items and a second bid price associated with each of the one or more items;

(c) choosing a subset of the first and second bids as matched based substantially on a maximization technique;

(d) determining a price for each of the one or more items as a highest bid among one or more matched sellers offering the one or more items;

(e) determining a payment by one or more matched buyers as a sum of prices of the one or more items in the matched bid;

(f) excluding the matched buyers from payment that have bids lower than determined payments; and

(g) determining payments to sellers based on the prices and a demand for the one or more items after exclusion of at least one buyer.

42. A computer readable medium having stored thereon instructions adapted to perform the method of claim 41.

43. A method for determining a winning allocation of bids in an auction, the method comprising:

(a) receiving a plurality of bids, wherein each of the plurality of bids includes one or more items and an associated bid price for the one or more items;

(b) utilizing a maximization technique to create from the received bids a plurality of disjoint candidate allocations of bids;

(c) determining a price for each of the one or more items as a bid of a highest matched seller;

(d) determining a payment for each buyer as a sum of the prices of the one or more items in a matched bid;

(e) determining a final matched one or more buyers as those with a bid lower than an announced payment; and

(f) determining a final matched one or more sellers.

44. An apparatus for facilitating the exchange of resources over a digital network, the apparatus comprising:

a processor;

a display device coupled to the processor;

a user input device coupled to the processor;

a machine-readable medium including instructions executable by processor for;

displaying information on the display device to prompt the human user to specify resource demand and supply;

accepting signals from the user input device to specify resource demand and supply; and

transferring the specified resource demand and supply to a process for identifying specified bids that substantially match.

45. A system configured to support auction mechanisms, the system including the apparatus of claim 44.

46. The invention as substantially described herein.