具有常数最大最小份额保证的期望真实机制
Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
Mengfan Ma, Biaoshuai Tao, Fangxiao Wang
AI 速读 基于摘要
作者提出一种期望真实（TIE）的随机分配机制，利用基数估值信息，在每次实现中都保证每位代理人至少获得其截断比例份额（TPS）的 1/6，从而也至少获得其最大最小份额（MMS）的 1/6。
cs.GT
查看原文摘要
We study the truthful and fair allocation of $m$ indivisible goods to $n$ strategic agents with additive valuations. Babaioff, Feige, and Manaker Morag (FOCS~2026) gave a randomized mechanism that uses only the agents' rankings of the goods, is truthful-in-expectation (TIE), and guarantees every agent $1/(H_{n-1}+2)=Θ(1/\log n)$ of her maximin share (MMS) in every realized allocation, where $H_{n-1}$ is the $(n-1)$th harmonic number; this is nearly the best possible with rankings alone. They conjectured that cardinal information allows TIE mechanisms to achieve a constant ex-post MMS guarantee. We confirm this conjecture: our TIE mechanism gives every agent at least $1/6$ of her truncated proportional share (TPS), and hence of her MMS, in every realized allocation. Moreover, the mechanism is ex-ante envy-free and can be implemented in polynomial time as an explicit lottery over at most $m(n-1)+1$ allocations.