单调值神经网络：机器学习在组合分配问题中的新应用
50 浏览量
更新于2024-06-16
收藏 2.37MB PDF 举报
"这篇论文介绍了单调值神经网络（Monotone Value Neural Networks, MVNN），这是一种新型的机器学习方法，特别适用于处理组合分配问题。在组合分配问题中，如拍卖或课程分配，物品通常以捆绑包的形式分配，而代理人的偏好可能对这些组合具有单调性。传统的机器学习算法往往无法有效地捕捉这种特性，导致代理人的偏好诱导成本增加。
MVNN的设计目的是捕捉组合值，同时强制执行单调性和归一化。通过证明MVNN在单调和归一化的价值函数类中是通用的，作者们为基于MVNN的获胜者确定问题（Winner Determination Problem, WDP）提供了一个混合整数线性规划（Mixed Integer Linear Programming, MILP）的公式，使得实际应用中的解决方案变得可行。在技术层面，这一创新降低了代理的偏好诱导成本，提高了机制的效率。
论文以频谱拍卖为例进行了实验，结果显示MVNN在预测性能上表现优秀，能产生最先进的分配效率，并且减少了求解WDP的时间。此外，MVNN也适用于其他没有固定预算的组合分配问题，如商学院课程分配。研究者使用了结构化的偏好生成器来创建代理人的偏好，以模拟实际环境。
论文中提到的应用案例包括重新分配渔获量份额和商学院的课程分配问题，这两个场景都涉及到代理对多个项目组合的价值评估。通过MVNN，代理人可以更准确地表达复杂偏好，而不会因为组合空间的指数级增长而导致偏好诱导困难。
代码实现已公开在GitHub上，供进一步研究和应用。这项工作强调了结合机器学习与先验知识（如单调性）在解决组合分配问题中的潜力，为未来的相关研究提供了新的思路和工具。"
+v：mala2277获取更多论
文
11
∈
一
∈
⊆
`
`
A
i
[
R
i
]
（
a
i
）
d
优化步骤
2
求解
q
∈argmax
延迟
VCG
支付
p
（
R
）
=
（
p
（
R
）
1
.. .
，
p
（
R
）
n
）
∈
Rn
为
5
定义F
=
{
a
∈
F
：
ai
/
=
x
，
<
$
（
x
，
v
<$
i
（
x
））
∈
R
i
}
J
R
−
i
J
R
J
j∈N\{i}
：
次：对于每个投标人i∈N，Q
轮
-1次，不包括
a
R
∈argmax
V
（
a
|
R
）
=
argmax
不同的投标人
j
/
=
i
（行
5
a
∈F
a
∈
Fi
∈
N
：
（
ai
，
v
<
$
i
（
ai
））
∈
Ri
附录
A
一种机器学习驱动的ICA
算法2：MLCA（Q
init
，
Q
max
，
Q
round
）（Brero等人，2021）
参数：Q
init
、
Q
max
、
Q
round
initial
、
max
和
#queries/round
在本节中，我们详细介绍了Brero等人的
机器学习驱动的
组合拍卖（
MLCA
）。
1
foreach
i N
do
2
接收报告
R
i
for
Q
init
随机抽取丛
[
2021
年]
。
MLCA的核心是一个
查询模块
（算法1），
3
端
4
对于k
=
1
，
...
，
[
（
Q
max
−
Q
init
）
/Q
round
n =
d
Round iterator
5
对i∈N做 d
次
边际经济查询
对于每个投标人
i
，
N
，其确定新的值
6
查询
q
i
.
首先，在
估计步骤
（第
1
行）中，使用
ML
算法
i
从报
告
Ri
学习投标人
i
的估价
.
7
接下来，在
优化步骤
（行2）中，
基于
ML
的
WDP为
8
求解以找到值查询的候选q原则上，
9
ML
算法
A
i
，其允许求解对应的
10
端
从
N
\
{
i
}
中均匀地抽取无替换（Q
轮
-1）
投标
人，并将其
存储
在
N
中
，对于每个
j
∈
N
do
q
new
=
q
new
Next
（
N\{j}
，
R
−
j
）
可以快速使用基于ML的WDP最后，如果q
i
11
q
new
=
下一个
（
N
，
R
）
d
主要经济查询
已经被查询之前（行4），另一个，更多的re-
12
foreachi
∈
Ndo
新
新
新
求解严格的基于NN的WDP（行6），并且相应地更新
q
i
。这确保了所有最终查询q都是新的。
13
14
15末端
端
接收
q
i
的
报告
R
i
，设
R
i
=R
i
<$
R
i
算法
1
：
NEXT Q UERIES
（
I
，
R
）
（Brero et al. 2021年）
输入：投标人
I
和报告值
R
的索引集
1
对于每个
i
∈
I
，
Fi
∈
A
i
在
R
i
上
：
A
i
[
R
i
] d
估计步骤
16
Given
引出的报告
R
如等式（
1
）中那样
计算
Δ
R
17
给定引出的报告
R
计算
VCG-
支付
p
（
R
）
18
最终分配额
a
和付款额
p
（
R
）
R
−
i
：
=（
R
1
，
. . .
，
R
i
−
1
，
R
i
+1
，
. . .
，
Rn
）
。 然后我
们计算
-
a
∈F
3
foreach
i∈I
do
i
∈
I
+
如下所示：
4
如果
（
q
i
，
v
<$
i
（
q
i
））
′
∈
R
i
则
d
丛已被查询
p
（
R
）
：
=
v
.
.
一
个
Σ
Σ
−
Σ
v
.
（
a
）（
b
）
（i）（a）
（i）（ii）（
i
6
重新求解
q
′
∈
argmax
<$
A
[
R
]
（
a
）
j
∈
N
\{
i
}
J
j∈N\{i}
7
8
9 端
端
更新
q
i
=
q
i
′
a
∈F
'
l
∈
I
l l l
whe re
a
R
−
i
（十九）
最大化报告的社会福利时，
10
return
新查询的
Profile
q
=
（
q
1
，
. . .
，
q
n
）
包括投标人
I
，即，
a
<$
R
−
i
∈
argmax
V
^
（
a
|
R
−
i
）
=
argmax
v
在算法2中，我们提出了MLCA。 在下文中，让
R
−i
=
（
R
1
，
. . .
，
R
i−
1
，
R
i
+1
，
. . .
，
Rn
）。
M
LCA
收益
还有
一
个
（
a
j
，
v
<$
j
（
a
j
））
∈
R
j
是一种社会福利最大化的分配
循环，直到每个投标人的最大查询数量Q
max
为
（包括所有投标人），即，
达到了在每一轮中，它调用算法1（Q
轮
-1
）n
+
1
<$
^
<$
经济体
）和一次包括所有投标人（第11行，
主要
经济
）。 每个投标人总共被询问Q
轮
捆绑，
因此，当使用VCG时，投标人i
u
=
v（（a））
−
p（R）
在MLCA的一轮。在每一轮结束时，
i i
ri
i
从所有投标人接收新生成的报告R
new
查询q
new
，并更新整个引出的报告R（行
=
v
i
（（
a
<$
R
）
i
）
+
<$
v
<$
j
（（
a
<$
R
）
j
）
−
<$
v
<
$
j
（（
a
<$
R
−
i
）
j
）
。
j
∈
N
\{
i
}
j
∈
N
\{
i
}
12-14
）。在第
16
使
报告
的社会福利最大化（见公式（1）），并根据报
告值R（见附录定义B.1）确定VCG支付p（R）
B
MLCA的激励措施
在 本 节 中， 我 们 简 要回 顾 了Brero等人的 主 要 论 点
。
[
2021
]
为什么MLCA在实践中有很好的激励措施。首先，我
们定义VCG支付投标人
定义 B.1. （VCG 项目 从 R E-
港口
）
让
R
=
（
R
1
，
. . .
，
R
n
）
表示 从
M L C A
获
得 的 来自每 个 投标者的 报 告 的加 权 值 对 的引 出集 合
（算法
2
），让
端
我
a
∈F
a
∈F
v
i
（
a
i
）
.
（
二十一）
剩余65页未读，继续阅读
2021-08-18 上传
2021-05-20 上传
论文
论文
论文
2023-05-05 上传
2023-05-28 上传
2024-05-12 上传
cpongm
- 粉丝: 5
- 资源: 2万+
我的内容管理
展开
最新资源
- 多模态联合稀疏表示在视频目标跟踪中的应用
- Kubernetes资源管控与Gardener开源软件实践解析
- MPI集群监控与负载平衡策略
- 自动化PHP安全漏洞检测：静态代码分析与数据流方法
- 青苔数据CEO程永：技术生态与阿里云开放创新
- 制造业转型： HyperX引领企业上云策略
- 赵维五分享：航空工业电子采购上云实战与运维策略
- 单片机控制的LED点阵显示屏设计及其实现
- 驻云科技李俊涛：AI驱动的云上服务新趋势与挑战
- 6LoWPAN物联网边界路由器：设计与实现
- 猩便利工程师仲小玉：Terraform云资源管理最佳实践与团队协作
- 类差分度改进的互信息特征选择提升文本分类性能
- VERITAS与阿里云合作的混合云转型与数据保护方案
- 云制造中的生产线仿真模型设计与虚拟化研究
- 汪洋在PostgresChina2018分享：高可用 PostgreSQL 工具与架构设计
- 2018 PostgresChina大会：阿里云时空引擎Ganos在PostgreSQL中的创新应用与多模型存储
