线性拍卖 发表评论(0) 编辑词条

　　n个相同物品同时拍卖，称为线性拍卖(n>1)。买方需以暗标的方式分别报出买k个（k=1,2,...,n）个物品出的总价。所有买方报价结束后，卖方通过计算，确定使得自身效用达到最大的分配方案，并以买方的报价将物品卖给买方。例如，两个买方竞买3个物品，甲乙两个买方的出价分别是（$4，$16，$21）（表示第一个买方买1件物品愿意出$4，买2件愿意出$16，买3件愿意出$21）和（$6，$15，$20）。则卖方将2个物品卖给甲，1个物品卖给乙，可使效用最大，为16+6=$22。计算如何分配物品的算法称为胜者决定算法，可以证明线性拍卖的胜者决定算法可在多项式时间内完成。