计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2006年
7期
1142-1148
,共7页
多Agent系统%资源分配%组合拍卖
多Agent繫統%資源分配%組閤拍賣
다Agent계통%자원분배%조합박매
作为一种协商手段,拍卖方法是多Agent系统(MAS)的重要问题之一,组合拍卖是其中的研究热点.提出了物品分配方案的k-UNT条件,并给出了一种基于1-UNT检查的求边际效用递减组合拍卖的近似算法,证明了1-UNT算法的解的效用率不低于0.5.实验表明,将1-UNT算法和贪心算法结合可在较短的时间内求得较优解.还给出了基于k-UNT检查的胜者决定算法,证明了即使在2人组合拍卖的简单情况下,基于k-UNT检查的胜者决定算法都不可能保证解的效用率大于0.5.1-UNT算法部分改进了Lehmann等人的工作.
作為一種協商手段,拍賣方法是多Agent繫統(MAS)的重要問題之一,組閤拍賣是其中的研究熱點.提齣瞭物品分配方案的k-UNT條件,併給齣瞭一種基于1-UNT檢查的求邊際效用遞減組閤拍賣的近似算法,證明瞭1-UNT算法的解的效用率不低于0.5.實驗錶明,將1-UNT算法和貪心算法結閤可在較短的時間內求得較優解.還給齣瞭基于k-UNT檢查的勝者決定算法,證明瞭即使在2人組閤拍賣的簡單情況下,基于k-UNT檢查的勝者決定算法都不可能保證解的效用率大于0.5.1-UNT算法部分改進瞭Lehmann等人的工作.
작위일충협상수단,박매방법시다Agent계통(MAS)적중요문제지일,조합박매시기중적연구열점.제출료물품분배방안적k-UNT조건,병급출료일충기우1-UNT검사적구변제효용체감조합박매적근사산법,증명료1-UNT산법적해적효용솔불저우0.5.실험표명,장1-UNT산법화탐심산법결합가재교단적시간내구득교우해.환급출료기우k-UNT검사적성자결정산법,증명료즉사재2인조합박매적간단정황하,기우k-UNT검사적성자결정산법도불가능보증해적효용솔대우0.5.1-UNT산법부분개진료Lehmann등인적공작.