内容：
在线线性规划（online LP）是在线算法中的经典问题：共 T 轮，每轮到达若干请求，各自有价值和多维的资源消耗。算法必须立即决定服务哪个，并在长期资源约束下最大化总价值。经典的 primal-dual 方法把对偶变量当资源的“影子价格”，随消耗及时调整，在价值如实且已知时做到最优 regret。然而在 GPU 分配等场景中，请求的价值只有提交者自己知道，同一批用户还会反复提交。我们发现，primal-dual 恰恰因为反应及时，而容易被策略性用户操纵：现在的报告影响之后的价格，虚报就能把价格拉向对自己有利的方向。
我们提出 incentive-aware primal-dual 机制。在激励方面，我们通过转移支付、冻结更新、随机探索，让虚报的收益抵不过当下的损失。但冻结拖慢了价格更新，在最坏情况下带来 Ω(T^⅔) regret，我们称之为“激励的代价”。有趣的是，绕过这一障碍的工具也来自激励：在近似如实报告时，我们可以估计每个价格将会带来的消耗。通过一个新的乐观在线学习技术（反复解不动点问题），我们同时做到了“效率”（Õ(√T) regret，即使在非策略情形下也几乎最优）、“可行性”（满足所有资源限制）和“激励”（诱导近似如实的均衡），打破了这个看似不可能的三角。我还将简要介绍我的其他工作：如果机制必须从策略性参与者的报告中学习，激励究竟要付出多少代价？
