...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Mathematical methods of operations research >It is difficult to tell if there is a Condorcet spanning tree
【24h】

It is difficult to tell if there is a Condorcet spanning tree

机译：很难确定是否有秃鹰生成树

获取原文
获取原文并翻译 | 示例
   

获取外文期刊封面封底 >>

       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We apply the well-known Condorcet criterion from voting theory outside of its classical framework and link it with spanning trees of an undirected graph. In situations in which a network, represented by a spanning tree of an undirected graph, needs to be installed, decision-makers typically do not agree on the network to be implemented. Instead, each of these decision-makers has her own ideal conception of the network. In order to derive a group decision, i.e., a single spanning tree for the entire group of decision-makers, the goal would be a spanning tree that beats each other spanning tree in a simple majority comparison. When comparing two dedicated spanning trees, a decision-maker will be considered to be more satisfied with the one that is "closer" to her proposal. In this context, the most basic and natural measure of distance is the usual set difference: we simply count the number of edges the spanning tree has in common with the proposal of the decision-maker. In this work, we show that it is computationally intractable to decide (1) if such a spanning tree exists, and (2) if a given spanning tree satisfies the Condorcet criterion.
机译：我们从投票理论的经典框架之外应用众所周知的Condorcet准则，并将其与无向图的生成树链接。在需要安装由无向图的生成树表示的网络的情况下，决策者通常不同意要实施的网络。相反，每个决策者都有自己理想的网络概念。为了得出一个群体决策，即整个决策者群体的一棵生成树，目标将是一棵生成树，在简单的多数比较中击败彼此的生成树。比较两棵专用生成树时，将认为决策者对与其提案“更接近”的决策者更加满意。在这种情况下，距离的最基本，最自然的度量是通常的集合差异：我们只需计算生成树与决策者的建议共同拥有的边数。在这项工作中，我们表明确定（1）是否存在这样的生成树，以及（2）给定的生成树是否满足Condorcet准则在计算上是棘手的。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号