Wolf Ketter's Publications

• Sorted by Date • Classified by Publication Type • Classified by Research Category •

Improving the Winner Determination Process in Multi-Agent Contracting

Alexander Babanov and Wolfgang Ketter. Improving the Winner Determination Process in Multi-Agent Contracting. www.cs.umn.edu/~ketter, December 2001.

Download

[PDF]386.6kB  [gzipped postscript]385.5kB  [postscript]1.5MB  

Abstract

We propose a methodology to improve the performance of the winner determination process in the MAGNET (Multi-AGent NEgotiation Testbed) research project. MAGNET agents participate in a first-price sealed-bid combinatorial auction over compound plans with precedence relations and time constraints. After the auction ends, agents solve a winner determination problem for the feasible combinations of bids submitted to the auction and award bids from the best combination. Currently there are two known implementations of the winner determination process: one is based on a Simulated Annealing (SA) and the other employs modified Integer Programming (IP) formulation. However, both SA and IP methods do not scale satisfactory with the number of bids and have solution quality issues that are common for ``brute-force'' solution concepts not designed atop the market information analysis. As the scalability problem effectively prevents the current system from exploring realistically large and sophisticated markets, we face a need to either find a better algorithm for the winner determination or improve the performance of the existing ones.

@Misc{Bab01,
  title =        "Improving the Winner Determination Process in Multi-Agent Contracting",
  author =       "Alexander Babanov and Wolfgang Ketter",
  year =         "2001",
  month =        dec,
  abstract = "We propose a methodology to improve the performance of
  the winner determination process in the MAGNET (Multi-AGent
  NEgotiation Testbed) research project. MAGNET agents participate in
  a first-price sealed-bid combinatorial auction over compound plans
  with precedence relations and time constraints. After the auction
  ends, agents solve a winner determination problem for the feasible
  combinations of bids submitted to the auction and award bids from
  the best combination. Currently there are two known implementations
  of the winner determination process: one is based on a Simulated
  Annealing (SA) and the other employs modified Integer Programming
  (IP) formulation. However, both SA and IP methods do not scale
  satisfactory with the number of bids and have solution quality
  issues that are common for ``brute-force'' solution concepts not
  designed atop the market information analysis. As the scalability
  problem effectively prevents the current system from exploring
  realistically large and sophisticated markets, we face a need to
  either find a better algorithm for the winner determination or
  improve the performance of the existing ones."
  howpublished = {www.cs.umn.edu/~ketter},
  annote =       "Unrefereed",
  bib2html_pubtype = {Unrefereed},
  bib2html_rescat = {Trading Agents: Combinatorial Auctions},
}

Generated by bib2html.pl (written by Patrick Riley ) on Thu Nov 12, 2009 06:42:01