科研之友
微信
新浪微博
Facebook
分享链接
摘要
算法机制设计是计算杨理论科学和机制设计的交叉学科,是当前国际上理论计算机领域里的研究热点之一。算法机制设计的一个主要研究方向是在机制设计中引入计算复杂性理论,对于机制的复杂性进行研究分析,判断相应机制的复杂度。然而很多机制从计算效率考虑是NP难的,这样就迫使人们考虑利用近似算法中的各种技术去设计相应的机制。考虑到随机算法是近似算法中重要的技术手段,那么,对随机机制设计的研究和分析就具有很重要的理论意义和实际应用价值。在本文中,我们首先给出了随机机制设计的确定定义,然后给出了随机诚实机制存在的的充分必要条件。根据该充分必要条件,我们给出了随机算法直接转化为随机诚实机制的框架。在该框架下,我们考虑...
- 单位
