线性拍卖

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。计算如何分配物品的算法称为胜者决定算法，可以证明线性拍卖的胜者决定算法可在多项式时间内完成。