[TOC]
反向拍卖：
组合式拍卖
买方有一个预算
众包
买家希望用固定的预算 购买照片标签的服务。
目标是最大限度地增加有标签的照片的数量。
一个卖家出售标签服务。
卖家愿意标注的照片数量是不同的。
卖家的投标价格是不同的。
联邦学习
买方希望用固定的预算购买培训服务
其目的是使训练样本的数量最大化
卖方出售培训数据和培训服务
对于卖家来说数据量和投标成本都是不同的。
在预算限制下，优化有标签的照片数量或总数据量。这是一个NP-hard的问题!
m a x ∑ i ∈ S x i v i s . t . ∑ i ∈ S x i c i ≤ B max \sum_{i \in S} x_i v_i \\ s.t.\sum_{i \in S} x_i c_i \le B m a x i ∈ S ∑ x i v i s . t . i ∈ S ∑ x i c i ≤ B
这个问题与背包问题很类似。
个人理性（Individual rationality）：任何诚实的投标人的效用总是非负的，p i ≥ c i , ∀ i ∈ S p_i \ge c_i, \forall i \in S p i ≥ c i , ∀ i ∈ S
真实性（Truthfulness）：没有卖家可以通过虚报成本来提高效用，U i ( ( v i , c i ^ ) , b − i ) ≥ U i ( ( v i , c i ) , b − i ) , ∀ i ∈ S , c i ≠ c i ^ 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} U i ( ( v i , c i ^ ) , b − i ) ≥ U i ( ( v i , c i ) , b − i ) , ∀ i ∈ S , c i = c i ^
问题公式化
max ∑ i ∈ S x i v i s.t. ∑ i ∈ S x i p i ≤ B -预算约束 p i ≥ c i , ∀ i ∈ S -个人理性 U i ( ( v i , c l ^ ) , b − i ) ≥ U i ( ( v i , c i ) , b − i ) , ∀ i ∈ S , c i ≠ c l ^ -真实性 \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} max ∑ i ∈ S x i v i s.t. ∑ i ∈ S x i p i ≤ B - 预算约束 p i ≥ c i , ∀ i ∈ S - 个人理性 U i ( ( v i , c l ) , b − i ) ≥ U i ( ( v i , c i ) , b − i ) , ∀ i ∈ S , c i = c l - 真实性
从直觉上讲，类似于LOS机制（原本用于解决无限可分物体拍卖）的想法是可以实现的。
买方根据r i = c i / v i r_i=c_i/v_i r i = c i / v i r 1 < = r 2 < = ⋯ < = r s r_1<=r_2<= \cdots <=r_s r 1 < = r 2 < = ⋯ < = r s
根据上述顺序，检查从2到N的买方i，进行以下操作：
如果：r i ∗ ( v 1 + v 2 + v i − 1 ) > B r_i * (v_1+v_2+v_{i-1})>B r i ∗ ( v 1 + v 2 + v i − 1 ) > B 否则，请检查下一个投标人。 投标者1至投标者i-2获胜。每个赢家k的支付费用为v k ∗ r i − 1 v_k*r_{i-1} v k ∗ r i − 1
有多个任务，其中每个任务都需要多个传感数据。
对于任务j，需要的数据片断的上限是w j w_j w j
m i n ( n j , w j ) min(n_j,w_j) m i n ( n j , w j )
目标是在预算约束B下最大限度地提高有效数据片的数量。
∑ j ∈ T m i n ( n j , w j ) \sum_{j \in T} min(n_j, w_j) j ∈ T ∑ m i n ( n j , w j )
max V = ∑ j ∈ T m i n ( n j , w j ) -有效数据数量 s.t. ∑ i ∈ S x i p i ≤ B -预算约束 n j = ∑ i ∈ S & j ∈ T i x i p i ≥ c i , ∀ i ∈ S -个人理性 U i ( ( v i , c l ^ ) , b − i ) ≥ U i ( ( v i , c i ) , b − i ) , ∀ i ∈ S , c i ≠ c l ^ -真实性 \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} max V = ∑ j ∈ T m i n ( n j , w j ) - 有效数据数量 s.t. ∑ i ∈ S x i p i ≤ B - 预算约束 n j = ∑ i ∈ S & j ∈ T i x i p i ≥ c i , ∀ i ∈ S - 个人理性 U i ( ( v i , c l ) , b − i ) ≥ U i ( ( v i , c i ) , b − i ) , ∀ i ∈ S , c i = c l - 真实性
在当前获胜的卖家集合U下，卖家i的边际贡献为
V i ( U ) = V ( U ∪ { i } ) − V ( U ) V_i(U)=V(U \cup \{i\})-V(U) V i ( U ) = V ( U ∪ { i } ) − V ( U )
边际效率e i e_i e i
e i ( U ) = V i ( U ) / c i e_i(U) = V_i(U)/c_i e i ( U ) = V i ( U ) / c i
这是贪婪 的！
伪代码表示
B’=0.5B; U={}e i e_i e i V f ( U ) / c f ≥ V ( U ∪ f ) / B ′ V_f(U)/c_f ≥V(U \cup {f})/B′ V f ( U ) / c f ≥ V ( U ∪ f ) / B ′ U = U ∪ f U= U \cup {f} U = U ∪ f
比例份额规则
单位成本的边际贡献>=单位预算购买的平均贡献
对于每一个中标者i，我们首先移除中标者i，重新计算中标者的集合。
对于新计算出的中标集合中的每个投标人f,为投标人i计算出一个侯选付款p i f p_{if} p i f p i f p_{if} p i f
在所有的侯选付款p i f p_{if} p i f
因此，现在最重要的问题是如何计算出投标人i为击败投标人f而申报的费用 ？
1.要想代替f占据第一的位置，他们的边际效率应该是相同的
V i ( U ) / a i > = V f ( U ) / c f V_i(U)/a_i >= V_f(U)/c_f V i ( U ) / a i > = V f ( U ) / c f
2.为了满足循环条件
V i ( U ) / b i > = V ( U ∪ { i } ) / B ′ V_i(U)/b_i>=V(U \cup \{ i \})/B^{\prime} V i ( U ) / b i > = V ( U ∪ { i } ) / B ′
3.在a i a_i a i b i b_i b i
m i n { a i , b i } min\{a_i ,b_i\} m i n { a i , b i }
伪代码表示
S’=S{i}; U={}; p i p_{i} p i
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 ′ V_f (U)/c_f ≥V(U∪{f})/B′ V f ( U ) / c f ≥ V ( U ∪ f ) / B ′
$a_{if}=V_i(U) * c_{f}/V_f(U) $
b i f = V i ( U ) ∗ B ’ / V ( U ∪ { i } ) b_{if}=V_i(U) * B’/V(U∪\{ i \}) b i f = V i ( U ) ∗ B ’ / V ( U ∪ { i } )
p i = m a x { p i , m i n { a i f , b i f } } p_{i}=max \{p_{i},min \{ a_{if},b_{if} \} \} p i = m a x { p i , m i n { a i f , b i f } }
U=U∪{f};
Sort bidders in S’\U according to e i e_i e i
end while
a i f = V i ( U ) ∗ c f / V f ( U ) a_{if}=V_i(U) * c_{f}/Vf(U) a i f = V i ( U ) ∗ c f / V f ( U )
b i f = V i ( U ) ∗ B ’ / V ( U ∪ { i } ) b_{if}=V_i(U) * B’/V(U∪\{ i \}) b i f = V i ( U ) ∗ B ’ / V ( U ∪ { i } )
p i = m a x { p i , m i n { a i f , b i f } } p_{i}=max \{p_{i},min \{ a_{if},b_{if} \} \} p i = m a x { p i , m i n { a i f , b i f } }
真实性
个人理性
预算可行性
逼近率*
t是所有竞标者中最大的边际贡献与该机制实现的总数据效用的比率。 (e-1)/[3e(1+t)] 竞标者按顺序到达。
投标人可以在开始时间和结束时间之间的任何时间前来投标。
当出价人到达时，拍卖商必须立即返回决策结果，包括赢或不赢和付款，而不知道未来的信息。
相同的问题，只不过是在线拍卖，公式如下：
max V = ∑ j ∈ T m i n ( n j , w j ) -有效数据数量 s.t. ∑ i ∈ S x i p i ≤ B -预算约束 n j = ∑ i ∈ S & j ∈ T i x i p i ≥ c i , ∀ i ∈ S -个人理性 U i ( ( v i , c l ^ ) , b − i ) ≥ U i ( ( v i , c i ) , b − i ) , ∀ i ∈ S , c i ≠ c l ^ -真实性 \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} max V = ∑ j ∈ T m i n ( n j , w j ) - 有效数据数量 s.t. ∑ i ∈ S x i p i ≤ B - 预算约束 n j = ∑ i ∈ S & j ∈ T i x i p i ≥ c i , ∀ i ∈ S - 个人理性 U i ( ( v i , c l ) , b − i ) ≥ U i ( ( v i , c i ) , b − i ) , ∀ i ∈ S , c i = c l - 真实性
预算只能负担一个secretary。
申请人按随机顺序逐一到达。
当申请人到达时，要在面试后立即做出决定。一旦被拒绝，申请人就不能再被召回。
这个问题是于最佳策略，以最大限度地提高选择最佳申请人的概率。
拒绝先来的n/e个申请人，并记录其中的最高分s。在接下来的申请者中，招聘第一个得分高于s的人。这个操作可以理解为我们进行招聘，先拿到几份简历找到其中的最好的，接下来以这个为标准，只招聘比这个更好的员工。既然存在这个值，那么也很有可能存在更高的值。
这一策略实现了最佳概率1/e。
这个的思路就是利用历史来预测未来 。
https://en.wikipedia.org/wiki/Secretary_problem
把整个时间长度T在T/e处切断. 拒绝所有在T/e之前的投标人，并记录他们的信息。假设这些投标人构成集合S。 通过S和B ′ = B / e B^{\prime}=B/e B ′ = B / e V ′ V^{\prime} V ′ r = V ′ / B ′ r = V^{\prime} / B^{\prime} r = V ′ / B ′ 对于在T/e之后到来的投标人，如果V i ( U ) / c i ≥ r V_i(U)/c_i \ge r V i ( U ) / c i ≥ r V i ( U ) / r V_i(U)/r V i ( U ) / r 实现了真实性和个人理性。但这对先到的竞标者是不公平的！
