System and method for matching multi-attribute auction bids

• US 6,952,682 B1
• Filed: 07/02/1999
• Issued: 10/04/2005
• Est. Priority Date: 07/02/1999
• Status: Expired due to Term

• Current Assignee: Ariba Incorporated (SAP SE)
• Original Assignee: Ariba Incorporated (SAP SE)
• Inventors: Wellman, Michael P.
• Primary Examiner(s): Hayes, John W.
• Assistant Examiner(s): Abdi, Kambiz
• Application Number:
  US09/347,110
• Time in Patent Office: 2,286 Days
• Field of Search: 705/1, 705/50, 705/80, 705 35- 45, 705/26, 705/28, 395/140
• US Class Current: 705/37
• 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 99/00 Subject matter not provided for in other groups of this subclass

Abstract

A system and a method for matching multi-attribute auction bids are disclosed. A set of multi-attribute bids or bid values are collected from one or more buyers and one or more sellers. The set of bid values may include variances from nominal bid values. Buyer and seller bids are generated from the set of buyer and seller multi-attribute bid values after predetermined attribute values, if any, are added. A pair of bids between each buyer and each seller having a highest surplus is selected. The method generates a weighted bipartite graph having buyer nodes and seller nodes and an edge between each buyer node and each seller node, each edge having the highest surplus of the pair of bids between the buyer and seller as a weight. The maximal weighted matching bids from the highest surplus pairs of bids are determined using the weighted bipartite graph.

Claims

1. A computerized method of matching at least one multi-attribute bid from one or more buyers and at least one multi-attribute bid from one or more sellers, the computerized method comprising:

electronically selecting a pair of bids between each buyer and each seller from a plurality of compatible bid pair combinations, the selected pair of bids having a highest surplus between each buyer bid and seller bid, each buyer and seller bid being based on at least one variance to a nominal attribute value of at least one attribute and a corresponding variance relative to the nominal bid value, wherein each buyer and seller bid is a price, the price being expressed in terms of a uniform measurement unit;

electronically generating a weighted bipartite graph comprising buyer nodes and seller nodes and an edge between each buyer node and each seller node, each edge having the highest surplus of the pair of bids between the buyer and seller as a weight; and

electronically determining maximal weighted matching bids from the highest surplus pairs of bids using the weighted bipartite graph.

2. The computerized method of claim 1, wherein each buyer is associated with at most one maximal weighted matching bid and each seller is associated with at most one maximal weighted matching bid.

3. The computerized method of claim 1, wherein said selecting the highest surplus pair of bids between each buyer and each seller includes determining a value associated with each bid of a buyer and each bid of a seller.

4. The computerized method of claim 3, wherein said highest surplus of a pair of bids between each buyer and each seller is a highest difference between the value of each bid of the buyer and the value of each bid of the seller.

5. The computerized method of claim 1, further comprising collecting at least one multi-attribute bid from one or more buyers and at least one multi-attribute bid from one or more sellers, each bid having a plurality of attributes specified by a buyer or seller.

6. The computerized method of claim 5, wherein each bid has at least one predetermined attribute.

7. The computerized method of claim 5, wherein said plurality of attributes are specified relative to a uniform measurement unit.

8. The computerized method of claim 7, wherein said uniform measurement unit is a monetary unit.

9. The computerized method of claim 1, wherein said selecting the highest surplus pair of bids between each buyer and each seller includes determining a difference between the price of each buyer bid and the price of each seller bid.

10. The computerized method of claim 1, wherein each bid has a plurality of attributes, at least a portion of the attributes being specified by a buyer or seller and wherein said selecting the highest surplus pair of bids between each buyer and each seller further includes:

electronically generating bids for each buyer from the plurality of attributes;

electronically generating bids for each seller from the plurality of attributes;

electronically comparing attributes of each bid of each buyer with attributes of each bid of each seller.

11. The computerized method of claim 10, wherein said selecting the highest surplus pair of bids between each buyer and each seller further includes generating a list of matching bids between each buyer and each seller, each matching bid having compatible attributes.

12. The computerized method of claim 11, wherein said highest surplus pair of bids between each buyer and each seller is selected from said list of matching bids.

13. The computerized method of claim 10, wherein said compatible attributes includes a buyer price lower than or equal to a seller price.

14. The computerized method of claim 11, wherein said generating the list includes discarding pairs of bids between each buyer and each seller where a buyer price is lower than a seller price.

15. A computer-readable medium having instructions to cause a computer to perform a computerized method of matching at least one multi-attribute bid from one or more buyers and at least one multi-attribute bid from one or more sellers, the computerized method comprising:

Electronically selecting a pair of bids between each buyer and each seller from a plurality of compatible bid pair combinations, the selected pair of bids having a highest surplus between each buyer bid and seller bid, each buyer and seller bid being based on at least one variance to a nominal attribute value of at least one attribute and a corresponding variance relative to the nominal bid value, wherein each buyer and seller bid is a price, the price being expressed in terms of a uniform measurement unit;

Electronically generating a weighted bipartite graph comprising buyer nodes and seller nodes and an edge between each buyer node and each seller node, each edge having the highest surplus of the pair of bids between the buyer and seller as a weight; and

Electronically determining maximal weighted matching bids from the highest surplus pairs of bids using the weighted bipartite graph.

16. The computer-readable medium of claim 15, wherein each buyer is associated with at most one maximal weighted matching bid and each seller is associated with at most one maximal weighted matching bid.

17. The computer-readable medium of claim 15, wherein said selecting the highest surplus pair of bids between each buyer and each seller includes determining a value associated with each bid of a buyer and each bid of a seller.

18. The computer-readable medium of claim 17, wherein said highest surplus of a pair of bids between each buyer and each seller is a highest difference between the value of each bid of the buyer and the value of each bid of the seller.

19. The computer-readable medium of claim 15, further comprising collecting at least one multi-attribute bid from one or more buyers and at least one multi-attribute bid from one or more sellers, each bid having a plurality of attributes specified by a buyer or seller.

20. The computerized method of claim 19, wherein each bid has at least one predetermined attribute.

21. The computer-readable medium of claim 19, wherein said plurality of attributes are specified relative to a uniform measurement unit.

22. The computer-readable medium of claim 21, wherein said uniform measurement unit is a monetary unit.

23. The computer-readable medium of claim 15, wherein said selecting the highest surplus pair of bids between each buyer and each seller includes determining a difference between the price of each buyer bid and the price of each seller bid.

24. The computer-readable medium of claim 15, wherein each bid has a plurality of attributes, at least a portion of the attributes being specified by a buyer or seller and wherein said selecting the highest surplus pair of bids between each buyer and each seller further includes:

generating bids for each buyer from the plurality of attributes;

generating bids for each seller from the plurality of attributes;

comparing attributes of each bid of each buyer with attributes of each bid of each seller.

25. The computer-readable medium of claim 24, wherein said selecting the highest surplus pair of bids between each buyer and each seller further includes generating a list of matching bids between each buyer and each seller, each matching bid having compatible attributes.

26. The computer-readable medium of claim 25, wherein said highest surplus pair of bids between each buyer and each seller is selected from said list of matching bids.

27. The computer-readable medium of claim 24, wherein said compatible attributes includes a buyer price lower than or equal to a seller price.

28. The computer-readable medium of claim 25, wherein said generating the list includes discarding pairs of bids between each buyer and each seller where a buyer price is lower than a seller price.

29. A system comprising:

a processor; and

a means for electronically matching at least one multi-attribute bid from one or more buyers and at least one multi-attribute bid from one or more sellers, wherein the means for matching includes;

means for electronically selecting a pair of bids between each buyer and each seller from a plurality of compatible bid pair combinations, the selected pair of bids having a highest surplus between each buyer bid and seller bid, each buyer and seller bid being based on at least one variance to a nominal attribute value of at least one attribute and a corresponding variance relative to the nominal bid value, wherein each buyer and seller bid is a price, the price being expressed in terms of a uniform measurement unit;

means for electronically generating a weighted bipartite graph comprising buyer nodes and seller nodes and an edge between each buyer node and each seller node, each edge having the highest surplus of the pair of bids between the buyer and seller as a weight; and

means for electronically determining maximal weighted matching bids from the highest surplus pairs of bids using the weighted bipartite graph.

30. A system comprising:

a processor; and

a computer-readable medium coupled to the processor, the computer-readable medium having instructions to cause the processor to match at least one multi-attribute bid from one or more buyers and at least one multi-attribute bid from one or more sellers, the instructions further to cause the processor to;

select a pair of bids between each buyer and each seller from a plurality of compatible bid pair combinations, the selected pair of bids having a highest surplus between each buyer bid and seller bid, each buyer and seller bid being based on at least one variance to a nominal attribute value of at least one attribute and a corresponding variance relative to the nominal bid value, wherein each buyer and seller bid is a price, the price being expressed in terms of a uniform measurement unit;

generate a weighted bipartite graph comprising buyer nodes and seller nodes and an edge between each buyer node and each seller node, each edge having the highest surplus of the pair of bids between the buyer and seller as a weight; and

determine maximal weighted matching bids from the highest surplus pairs of bids using the weighted bipartite graph.