Hunting for Tractable Languages for Judgment Aggregation

  • 2018-08-09 07:16:56
  • Ronald de Haan
  • 1

Abstract

Judgment aggregation is a general framework for collective decision makingthat can be used to model many different settings. Due to its general nature,the worst case complexity of essentially all relevant problems in thisframework is very high. However, these intractability results are mainly due tothe fact that the language to represent the aggregation domain is overlyexpressive. We initiate an investigation of representation languages forjudgment aggregation that strike a balance between (1) being limited enough toyield computational tractability results and (2) being expressive enough tomodel relevant applications. In particular, we consider the languages of Kromformulas, (definite) Horn formulas, and Boolean circuits in decomposablenegation normal form (DNNF). We illustrate the use of the positive complexityresults that we obtain for these languages with a concrete application: votingon how to spend a budget (i.e., participatory budgeting).

 

Quick Read (beta)

loading the full paper ...