论文部分内容阅读
社会计算(computational social choice)是一个将传统的社会计算理论和现代计算机理论科学中建模、算法设计、新技术和新思想融合在一起的一个多学科交叉的火热研究领域。近年来,计算机科学和人工智能的发展大大的促进了社会计算的研究热度。在计算机人工智能顶级会议中,每年都有大量关于社会计算的文章被接收,其研究十分火热且具有前景。偏好融合是社会计算中研究的非常火热和在实际中应用非常广泛的一类问题,其研究如何通过群体中个人的偏好,得到整个群体统一的、融合后的偏好。当一个群体在做决定的时候,群体中每个人的偏好可能不尽相同,这时需要使用偏好融合的方法,来得到一个统一的偏好,作为这个群体的偏好的代表。偏好融合有许多实际应用场景,如胜者选举、决策问题等。随着网络通信技术的发展,特别是人工智能的出现,使得偏好融合的应用变得更加广泛。本文为主要研究了偏好融合中的三个具体问题,首先是基于Kemeny规则下的偏好融合问题研究,该问题是NP-难的,本文从理论的角度出发,提出了“生成骨架”的概念,并从最小生成树的两个经典算法出发,设计了两个启发式算法,改进了D&在之前提出的启发式算法的运行时间。并基于Copeland算法和Borda算法,给出了类似的“对偶”启发式算法。实验表明,我们的算法表现较好。接着本文研究了基于打分规则下的分数融合问题。本文从几何和代数的角度分别分析研究了分数融合问题,将该问题建模成一个具有具体目标函数的优化问题,为该问题设计了谱分析方法,并从理论上证明了谱分析方法的最优性。最后我们给出了一个一致性分析指标——信噪比,来刻画结果的好坏和输入数据的一致性。最后我们研究了基于打分规则下的分数融合问题中的一个特殊情况:同行评价问题。在同行评价问题中,每个人既是投票者又是候选者。本文为同行评价问题赋予几何意义,设计了最小几何二乘距离方法,并分析了最小几何二乘方法两个较好性质。