目录
4 预算可行的拍卖机制
4.1 特征
反向拍卖：
- 一位拍卖师：买方
- 许多竞标者：卖家
组合式拍卖
买方有一个预算
4.2 使用案例
众包
买家希望用固定的预算购买照片标签的服务。
目标是最大限度地增加有标签的照片的数量。
一个卖家出售标签服务。
卖家愿意标注的照片数量是不同的。
卖家的投标价格是不同的。
联邦学习
买方希望用固定的预算购买培训服务
其目的是使训练样本的数量最大化
卖方出售培训数据和培训服务
对于卖家来说数据量和投标成本都是不同的。
4.3 拍卖设计问题
在预算限制下，优化有标签的照片数量或总数据量。这是一个NP-hard的问题!
\[max \sum_{i \in S} x_i v_i \\ s.t.\sum_{i \in S} x_i c_i \le B \]这个问题与背包问题很类似。
个人理性（Individual rationality）：任何诚实的投标人的效用总是非负的，\(p_i \ge c_i, \forall i \in S\)
真实性（Truthfulness）：没有卖家可以通过虚报成本来提高效用，\(U_i((v_i,\hat{c_i}),b_{-i}) \ge U_i((v_i,c_i),b_{-i}), \forall i \in S, c_i \neq \hat{c_i}\)
问题公式化
\[\begin{array}{l} \max \sum_{i \in S} x_{i} v_{i} \\ \text { s.t. } \sum_{i \in S} x_{i} p_{i} \leq B \quad \text { -预算约束 } \\ p_{i} \geq c_{i}, \forall i \in S \quad \text {-个人理性 } \\ U_{i}\left(\left(v_{i}, \widehat{c_{l}}\right), b_{-i}\right) \geq U_{i}\left(\left(v_{i}, c_{i}\right), b_{-i}\right), \forall i \in S, c_{i} \neq \widehat{c_{l}} \quad \text {-真实性} \end{array} \]从直觉上讲，类似于LOS机制（原本用于解决无限可分物体拍卖）的想法是可以实现的。
买方根据\(r_i=c_i/v_i\)对收到的出价进行重新排序，\(r_1<=r_2<= \cdots <=r_s\)
根据上述顺序，检查从2到N的买方i，进行以下操作：
- 如果：\(r_i * (v_1+v_2+v_{i-1})>B\)，终止检查过程。
- 否则，请检查下一个投标人。
投标者1至投标者i-2获胜。每个赢家k的支付费用为\(v_k*r_{i-1}\)
4.4 单调次模函数（Monotone Submodular Function）
有多个任务，其中每个任务都需要多个传感数据。
对于任务j，需要的数据片断的上限是\(w_j\)
\[min(n_j,w_j) \]目标是在预算约束B下最大限度地提高有效数据片的数量。
\[\sum_{j \in T} min(n_j, w_j) \]
4.4.1 分配算法
在当前获胜的卖家集合U下，卖家i的边际贡献为
\[V_i(U)=V(U \cup \{i\})-V(U) \]边际效率\(e_i\)为
\[e_i(U) = V_i(U)/c_i \]这是贪婪的！
伪代码表示
B’=0.5B; U={}
Sort all bidders in S according to \(e_i\) in the non-increasing order.
Bidder f is the head of the list
while \(V_f(U)/c_f ≥V(U \cup {f})/B′\)
\(U= U \cup {f}\)
Sort bidders in S\U according to ei in the non-increasing order.
Bidder f is the head of the list
end while
比例份额规则
单位成本的边际贡献>=单位预算购买的平均贡献
4.4.2 关键支付计划
对于每一个中标者i，我们首先移除中标者i，重新计算中标者的集合。
对于新计算出的中标集合中的每个投标人f,为投标人i计算出一个侯选付款\(p_{if}\)。\(p_{if}\)等于投标人i为击败投标人f的费用。
在所有的侯选付款\(p_{if}\)中选取最大的付款。
因此，现在最重要的问题是如何计算出投标人i为击败投标人f而申报的费用？
1.要想代替f占据第一的位置，他们的边际效率应该是相同的
\[V_i(U)/a_i >= V_f(U)/c_f \]2.为了满足循环条件
\[V_i(U)/b_i>=V(U \cup \{ i \})/B^{\prime} \]3.在\(a_i\)和\(b_i\)之间取最小值。
\[min\{a_i ,b_i\} \]伪代码表示
S’=S{i}; U={}; \(p_{i}\)=0
Sort all bidders in S’ according to ei in the non-increasing order. Bidder f is the head of the list
while \(V_f (U)/c_f ≥V(U∪{f})/B′\)
$a_{if}=V_i(U) * c_{f}/V_f(U) $
\(b_{if}=V_i(U) * B’/V(U∪\{ i \})\)
\(p_{i}=max \{p_{i},min \{ a_{if},b_{if} \} \}\)
U=U∪{f};
Sort bidders in S’\U according to \(e_i\) in the non-increasing order. Bidder f is the head of the list.
end while
\(a_{if}=V_i(U) * c_{f}/Vf(U)\)
\(b_{if}=V_i(U) * B’/V(U∪\{ i \})\)
\(p_{i}=max \{p_{i},min \{ a_{if},b_{if} \} \}\)
4.4.3 特性
真实性
个人理性
预算可行性
逼近率*
- t是所有竞标者中最大的边际贡献与该机制实现的总数据效用的比率。
- (e-1)/[3e(1+t)]
4.5 在线预算可行的拍卖机制
竞标者按顺序到达。
投标人可以在开始时间和结束时间之间的任何时间前来投标。
当出价人到达时，拍卖商必须立即返回决策结果，包括赢或不赢和付款，而不知道未来的信息。
相同的问题，只不过是在线拍卖，公式如下：
\[\begin{array}{l} \max V = \sum_{j \in T} min(n_{j},w_{j}) \text { -有效数据数量 } \\ \text { s.t. } \sum_{i \in S} x_{i} p_{i} \leq B \quad \text { -预算约束 } \\ n_j = \sum_{i \in S \& j \in T_i} x_i \\ p_{i} \geq c_{i}, \forall i \in S \quad \text {-个人理性 } \\ U_{i}\left(\left(v_{i}, \widehat{c_{l}}\right), b_{-i}\right) \geq U_{i}\left(\left(v_{i}, c_{i}\right), b_{-i}\right), \forall i \in S, c_{i} \neq \widehat{c_{l}} \quad \text {-真实性} \end{array} \]4.5.1 Secretary Problem(A Optimal Stopping Problem)
预算只能负担一个secretary。
申请人按随机顺序逐一到达。
当申请人到达时，要在面试后立即做出决定。一旦被拒绝，申请人就不能再被召回。
这个问题是于最佳策略，以最大限度地提高选择最佳申请人的概率。
拒绝先来的n/e个申请人，并记录其中的最高分s。在接下来的申请者中，招聘第一个得分高于s的人。这个操作可以理解为我们进行招聘，先拿到几份简历找到其中的最好的，接下来以这个为标准，只招聘比这个更好的员工。既然存在这个值，那么也很有可能存在更高的值。
这一策略实现了最佳概率1/e。
这个的思路就是利用历史来预测未来。
4.5.2 在线预算可行的拍卖机制
- 把整个时间长度T在T/e处切断.
- 拒绝所有在T/e之前的投标人，并记录他们的信息。假设这些投标人构成集合S。
- 通过S和\(B^{\prime}=B/e\)来计算目标\(V^{\prime}\)
- \(r = V^{\prime} / B^{\prime}\)是平均效率，即单位预算实现的目标值。
- 对于在T/e之后到来的投标人，如果\(V_i(U)/c_i \ge r\)并且剩余的预算足以支付\(V_i(U)/r\)，就招募他/她。U是当前的获胜者集合。
实现了真实性和个人理性。但这对先到的竞标者是不公平的！
标签：可行,text,sum,投标人,拍卖,right,预算,机制,left From： https://www.cnblogs.com/zuiyixin/p/17065524.html