We study a dynamic non-bipartite matching problem. There is a fixed set of agent types, and agents of a given type arrive and depart according to type-specific Poisson processes. Agent departures are not announced in advance. The value of a match is determined by the types of the matched agents. We present an online algorithm that is (1/8)-competitive with respect to the value of the optimal-in-hindsight policy, for arbitrary weighted graphs. Our algorithm treats agents heterogeneously, interpolating between immediate and delayed matching in order to thicken the market while still matching valuable agents opportunistically.


翻译:我们研究的是动态的非双向匹配问题。 有一套固定的代理类型, 特定类型的代理按照特定类型的 Poisson 程序到达和离开。 代理离开不会提前宣布。 匹配的价值由匹配的代理类型决定。 我们提出了一个在线算法, 相对于最佳内向政策的价值来说, 具有1/8的竞争性, 用于任意的加权图表。 我们的算法以多种方式处理代理, 将即时匹配和延迟匹配相互交错, 以便扩大市场, 同时仍然以机会方式匹配有价值的代理商 。

0
下载
关闭预览

相关内容

【KDD2020教程】多模态网络表示学习
专知会员服务
129+阅读 · 2020年8月26日
【DeepMind】强化学习教程,83页ppt
专知会员服务
152+阅读 · 2020年8月7日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
CCF推荐 | 国际会议信息10条
Call4Papers
8+阅读 · 2019年5月27日
CCF推荐 | 国际会议信息8条
Call4Papers
9+阅读 · 2019年5月23日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
LibRec 精选:位置感知的长序列会话推荐
LibRec智能推荐
3+阅读 · 2019年5月17日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Threshold-based Network Structural Dynamics
Arxiv
0+阅读 · 2021年3月8日
Arxiv
0+阅读 · 2021年3月8日
VIP会员
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
CCF推荐 | 国际会议信息10条
Call4Papers
8+阅读 · 2019年5月27日
CCF推荐 | 国际会议信息8条
Call4Papers
9+阅读 · 2019年5月23日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
LibRec 精选:位置感知的长序列会话推荐
LibRec智能推荐
3+阅读 · 2019年5月17日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Top
微信扫码咨询专知VIP会员