应用数学学报
應用數學學報
응용수학학보
ACTA MATHEMATICAE APPLICATAE SINICA
2009年
5期
779-786
,共8页
装箱%纳什均衡%最坏均衡比
裝箱%納什均衡%最壞均衡比
장상%납십균형%최배균형비
bin packing%Nash equilibrium%price of anarchy
带参量的非合作装箱博弈是指:每个物品的尺寸都介于0和参量x(0<x≤1)之间,并且它们是由自私的用户所控制的,每个物品(或用户)的目标是最小化他个人的分担费用.物品的分担费用是由它的尺寸在它所在箱子中所有物品的总尺寸中所占的比重所决定的.我们考虑了最坏均衡比,即最差均衡装箱和最优装箱所用箱子数的比,并且给出了它的一个下界和渐近上界.
帶參量的非閤作裝箱博弈是指:每箇物品的呎吋都介于0和參量x(0<x≤1)之間,併且它們是由自私的用戶所控製的,每箇物品(或用戶)的目標是最小化他箇人的分擔費用.物品的分擔費用是由它的呎吋在它所在箱子中所有物品的總呎吋中所佔的比重所決定的.我們攷慮瞭最壞均衡比,即最差均衡裝箱和最優裝箱所用箱子數的比,併且給齣瞭它的一箇下界和漸近上界.
대삼량적비합작장상박혁시지:매개물품적척촌도개우0화삼량x(0<x≤1)지간,병차타문시유자사적용호소공제적,매개물품(혹용호)적목표시최소화타개인적분담비용.물품적분담비용시유타적척촌재타소재상자중소유물품적총척촌중소점적비중소결정적.아문고필료최배균형비,즉최차균형장상화최우장상소용상자수적비,병차급출료타적일개하계화점근상계.
We study a bin packing game in which any item to be packed is handled by a selfish agent, where the size of any item is between 0 and the parameter x(0 < x ≤ 1).Each agent aims at minimizing his cost and the cost of a bin is shared among all the items it contains according to the normalized fraction of the bin they use. We consider the ratio of the worst cost of equilibrium packing to the optimal social cost and give a lower bound and an asymptotic upper bound on the ratio.
