关于策略无懈可击和公正选取序列的研究:第一位玩家不可全选
通过简单的顺序分配程序,共享不可分割的物品,当代理人采取轮流选择物品时,预计可以计算每个代理人的效用到多项式时间复杂度,而当代理人行为策略变化时,预期 utilitarian social welfare 时最大化的。
Apr, 2013
本研究探讨了序贯配置下的策略性行为,特别是考虑到 Nash 均衡、纯策略 均衡的计算和 Pareto 最优。研究表明,即使对于两个代理人,更好的应对也可以循环。研究结果提供了一个在纯 Nash 均衡下的结果,并且可以通过 “bluff profile” 的形式实现。此外,研究还展示了针对两个代理人的最佳 Stackelberg 策略的动态规划。
May, 2017
讨论了三个优秀的投票规则,其中条件功利规则是一个策略性稳健且容易计算的规则,其最坏和平均效率在代理人数量较小时都是低的,而效率最高的 Nash Max Product 规则虽然可以实现任何联盟的最强福利保障,但不符合排斥策略性稳健性,而有效的平等主义规则保护个体代理人但不保护联盟。
Dec, 2017
本文研究了可划分和必需的分配问题,重点关注了一些常用的链式分配机制。对于五个天然的链式分配机制,本文分别给出了平衡、递归平衡、平衡交替、严格交替和所有策略的分配特征,并同时检查了这几个类别中分配问题的计算复杂性。
Dec, 2014
本文研究了在没有货币支付的情况下,将 N 个物品分配给 N 个拥有完整、私有偏好列表和单位需求的代理的社会福利。研究了两个自然社会福利的度量方式,并分析了两种常见的匹配机制,即随机串独裁和概率串行机制,给出了这些机制的效能保证。
Apr, 2011
研究针对代理人与物体之间的离散分配问题,使用分数或随机分配的随机支配关系系统地定义了不同的比例公正和不嫉妒的概念,提出了多个公正概念并设计了多项式时间算法,扩展到不平等权利的情况,并且提出了一些公正概念,其中最优比例和最优弱比例是可取的。
Dec, 2013
研究了在代理人对有限物品具有不受限制的基数偏好时,近似社会福利最大化(无货币)的问题,在此问题中随机优先级是一个非常著名的期望真实机制,证明了随机优先级的近似比率是 Θ(n ^ {-1 / 2}),而没有期望真实机制可以实现比 O(n^{-1/2})更好的近似比率。此外,证明了所有序数(不一定是期望真实的)机制的近似比率都是 O(n^{-1/2}),表明随机优先级是问题的渐近最好的期望真实机制和最好的序数机制。
Mar, 2014
研究了使用 PS 规则的平衡问题,首先展示了 Nash 偏离的可能和纯策略 Nash 平衡的存在性,接着证明了验证给定档案是否为纯策略 Nash 平衡是 coNP - 完全的,计算纯策略 Nash 平衡是 NP 困难的。最后,使用实验验证了纯策略 Nash 平衡下的社会福利大多数至少与诚实档案相当。
Feb, 2015