Dynamic Fair Division with Partial Information
研究在分配者仅获得有限信息（如单个二元信号）时，能否同时实现公平与效率。针对独立同分布或相关估值，提出一种高概率无嫉妒且接近社会福利最大化的算法。
Fair and Efficient Allocation Algorithms Do Not Require Knowing Exact Item Values Food rescue organizations are tasked with allocating often-unpredictable donations to recipients who need it. For a large class of recipient valuation functions, this can be done in a fair and efficient manner as long as each recipient reports their value for each arriving donation. In practice, however, such valuations are rarely elicited. In “Dynamic Fair Division with Partial Information,” Benadè, Halpern, and Psomas ask whether simultaneous fairness and efficiency remain possible when the allocator receives limited information about recipient valuations, even as little as a single binary signal. For recipients with i.i.d. or correlated values, the paper provides an algorithm which is envy-free and 1-epsilon welfare-maximizing with high probability. Asymptotically tight results are also established for independent, nonidentical agents. This shows that fair and efficient online allocation algorithms do not critically rely on recipients being able to precisely report their utility functions.