№ | Слайд | Текст |
1 |
 |
Multi-Attribute Exchange Market: Search for Optimal MatchesEugene Fink Jianli Gong John Hershberger |
2 |
 |
MotivationBuild an automated exchange for trading goods and services |
3 |
 |
Previous workCombinatorial auctions Standardized exchanges - Simple goods - Symmetry between buyers and sellers - Liquid |
4 |
 |
Research goalsBuild an automated exchange for non-standardized goods. Support fast-paced trading for markets with millions of orders Include optimization techniques to maximize traders’ satisfaction |
5 |
 |
OutlineMulti-attribute orders Best-price matches Quality functions Experimental results |
6 |
 |
MarketA market is a set of items that can be traded, defined by a list of attributes. Example A used-car market is a set of all conceivable vehicles, defined by model, year, and mileage. |
7 |
 |
OrdersA trader specifies a buy or sell order by attribute values and a price limit. A value specification may include lists of values and numeric ranges. Buy order Model: Mustang or Corvette Year: 2002..2004 Mileage: 0..10K Price: ? $32,000 |
8 |
 |
MatchingPrice Year Model Sell order Mustang, made in 2004, $30,000 $32,000 Buy order Mustang, made after 2001, $32,000 04 $30,000 03 02 01 Camaro Mustang Corvette |
9 |
 |
OutlineMulti-attribute orders Best-price matches Quality functions Experimental results |
10 |
 |
Main structuresTree of fully specified orders Unordered list of the other orders |
11 |
 |
Depth-first searchBuy Order: Any car made after 1990 |
12 |
 |
Depth-first searchDrawback: If there are many matching leaves, the search takes a long time. Solution: Apply best-first search : Store the best price for each subtree Use these prices to guide the search |
13 |
 |
Best prices for subtrees$4,000 |
14 |
 |
Search for the best priceBuy Order: Any car made after 1990 |
15 |
 |
OutlineMulti-attribute orders Best-price matches Quality functions Experimental results |
16 |
 |
Quality functionsA trader can specify a quality function that ranks the acceptable transactions. The transaction quality may depend on an item and its price. |
17 |
 |
Quality functionsA trader can specify a quality function that ranks the acceptable transactions. The transaction quality may depend on an item and its price. The system searches for the matches with the highest quality. |
18 |
 |
Depth-first searchBuy Order: Any car made after 1990 |
19 |
 |
Monotonic attributesThe quality monotonically changes with the price Usually, it is also monotonic on several other attributes Example: Car quality Increases with the year Decreases with the mileage |
20 |
 |
Best-first searchFor every subtree, store the best value of each monotonic attribute Use these values to estimate the quality of the best match in every subtree |
21 |
 |
Best values for subtrees2000, 10K, $4,000 |
22 |
 |
Search for the best matchBuy Order: Any car made after 1990 50K, $7,000 |
23 |
 |
OutlineMulti-attribute orders Search for matches Quality functions Experimental results |
24 |
 |
PerformanceExperiments using a Pentium computer : 2 GHz CPU 1 Gbyte memory 166 MHz bus |
25 |
 |
Cars and bondsCar market with eight attributes Bond market with two attributes : 500 to 50,000 orders per second bonds cars |
26 |
 |
Artificial marketsSynthetic market data: 1 to 100 attributes 300,000 orders Best-First Depth-First |
27 |
 |
SummaryGeneral model for trading of multi-attribute goods Fast identification of matches between buy and sell orders |
«Multi-Attribute Exchange Market: Search for Optimal Matches» |
http://900igr.net/prezentacija/ekonomika/multi-attribute-exchange-market-search-for-optimal-matches-229703.html