带预测的在线广告分配优化问题

一个大型的媒体厂商可能同时有数万个广告合同，这些合同对营销对象的需求可能有重叠。例如，某个广告主可能希望寻找18到26岁之间的纽约人打广告，而另一个广告主可能需要针对所有美国境内的18-26岁的人打广告。当一个曼哈顿的25岁的计算机科学家在访问一个时尚网站的时候，那么媒体供应商就需要考虑对于一个满足了多个广告合同的广告位分配给谁的问题。它必须保证所有的广告合同都能被满足。

这个问题可以当做一个分配的问题，考虑如下一个二部图$G=(I \cup J, E)$。这里的$I$代表访问的用户，$J$代表担保合同，如果某个用户$i$满足了某个合同$j$的影响需要的时候，它们之间就有一条边$(i,j) \in E$。此外，每个广告主都有一个总的需求$d_j$，而一个用户也有一个供应参数$s_i$，代表了在给定时间段内，用户出现的次数。媒体供应商的目标就是找出一种分配策略使得所有的供应和需求都能被满足：每个用户访问的时候都最多只能出现一个广告（供应限制），所有的广关主的需求都能被满足（需求限制）。下图是一个简单的例子。

进一步的，媒体供应商和广告主都不会满足这种简单的担保投放结果。广告主并不希望他们一个月的广告预算在一天内被一个州的用户消耗完。实际上这是一个长期的过程。因此，这是一个更加复杂的分配问题。

幸运的是，只要未来的广告库存是已知的，我们就能找到一种最优化的分配方法来满足上述目标。但是实际中，这有很多困难。

首先，上述的图$G$很大，尽管我们可以对其进行抽样，但是对于抽样结果的解决方案和实际也许有较大的差距，当用户并不是来自于抽样的时候，我们没有任何信息，进而无法做到很好的分配。

其次，假设我们使用完整的$G$来找出了一个最优化的方案，实际也无法实行。它必须要求我们识别出一个特定的、预测出的用户访问才能实施最优化方案，实际上有数十亿的用户访问，实际中不可能做到这种。

最后是鲁棒性，即使我们对$G$有很好的预测，也不完美。因为我们希望处理那些在预测之外的用户访问。

本文提出了一种方法，来解决上述问题。