RHRonald de Haan

Ronald de Haan

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Ronald de Haan has a total of 36 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Finding Stable Partitions in Boolean Hedonic Games

    by Ari Conati, Andreas Niskanen, Ronald de Haan, Matti Järvisalo

  • Open Access

    Complexity Results and Algorithms for Manipulation and Bribery in Judgment Aggregation

    by Ari Conati, Andreas Niskanen, Ronald de Haan, Matti Järvisalo

    The study of limits of strategic behavior in collective decision making is a central topic in computational social choice. Focusing on judgment aggregation, we provide complexity results and algorithms for manipulation and bribery under various aggregation rules. Specifically, we show that manipulation and bribery are complete for the second level of the Polynomial Hierarchy and detail aggregation-rule-specific strong refinements for effective counterexample-guided abstraction refinement algorithms based on iterative calls to a maximum satisfiability solver for both manipulation and bribery. We provide an open-source implementation of the approach and empirically evaluate its performance on standard PrefLib datasets, showing that the strong refinement strategies developed in this work enable scaling up to solving more instances.


  • Judgment Aggregation

    by Dorothea Baumeister, Gábor Erdélyi, Ronald de Haan, Jörg Rothe


  • Open Access

    Intractability obstacles to explanations of communication

    by Laura van de Braak, Ronald de Haan, Mark Dingemanse, Ivan Toni, Iris van Rooij, Mark Blokpoel

    This is a preprint version of a published paper. Please cite as: van de Braak, L. D., De Haan, R., Dingemanse, M., Toni, I., Van Rooij, I., and Blokpoel, M. (2024). Intractability obstacles to explanations of communication. Proceedings of the International Conference on Cognitive Modeling, 22.Even when talking about novel things and without a fully shared vocabulary, people can come to understand each other through communicative turn taking (what we call communicative alignment). State-of-the-art computational models cannot yet explain this capacity, because (1) empirically corroborated models only work under shared knowledge and vocabularies, and leave out interactive processes needed to overcome misalignment; (2) models that do include misalignment and interactive processes cannot account for communicative successes under real-world conditions; and (3) models that overcome the limits in (2) use a theoretical `hack'. In this paper, we add a challenge to the list: the interactive processes in both models of type (2) and (3) are intractable. We explore the robustness and implications of this theoretical challenge for models of communicative alignment in general.


  • Open Access

    Reclaiming AI as a theoretical tool for cognitive science

    by Iris van Rooij, Olivia Guest, Federico G Adolfi, Ronald de Haan, Antonina Kolokolova, Patricia Rich

    The idea that human cognition is, or can be understood as, a form of computation is a useful conceptual tool for cognitive science. It was a foundational assumption during the birth of cognitive science as a multidisciplinary field, with Artificial Intelligence (AI) as one of its contributing fields. One conception of AI in this context is as a provider of computational tools (frameworks, concepts, formalisms, models, proofs, simulations, etc.) that support theory building in cognitive science. The contemporary field of AI, however, has taken the theoretical possibility of explaining human cognition as a form of computation to imply the practical feasibility of realising human(-like or -level) cognition in factual computational systems; and, the field frames this realisation as a short-term inevitability. Yet, as we formally prove herein, creating systems with human(-like or -level) cognition is intrinsically computationally intractable. This means that any factual AI systems created in the short-run are at best decoys. When we think these systems capture something deep about ourselves and our thinking, we induce distorted and impoverished images of ourselves and our cognition. In other words, AI in current practice is deteriorating our theoretical understanding of cognition rather than advancing and enhancing it. The situation could be remediated by releasing the grip of the currently dominant view on AI and by returning to the idea of AI as a theoretical tool for cognitive science. In reclaiming this older idea of AI, however, it is important not to repeat conceptual mistakes of the past (and present) that brought us to where we are today.


  • Open Access

    Swarm Control for Distributed Construction: A Computational Complexity Perspective

    by Todd Wareham, Ronald de Haan, Andrew Vardy, Iris van Rooij

    Over the last 20 years, human interaction with robot swarms has been investigated as a means to mitigate problems associated with the control and coordination of such swarms by either human teleoperation or completely autonomous swarms. Ongoing research seeks to characterize those situations in which such interaction is both viable and preferable. In this article, we contribute to this effort by giving the first computational complexity analyses of problems associated with algorithm, environmental influence, and leader selection methods for the control of swarms performing distributed construction tasks. These analyses are done relative to a simple model in which swarms of deterministic finite-state robots operate in a synchronous error-free manner in 2D grid-based environments. We show that all three of our problems are polynomial-time intractable in general and remain intractable under a number of plausible restrictions (both individually and in many combinations) on robot controllers, environments, target structures, and sequences of swarm control commands. We also give the first restrictions relative to which these problems are tractable, as well as discussions of the implications of our results for both the design and deployment of swarm control assistance software tools and the human control of swarms.


  • Open Access

    Why is scaling up models of language evolution hard?

    by Marieke Woensdregt, Matthew Spike, Ronald de Haan, Todd Wareham, Iris van Rooij, Mark Blokpoel

    Computational model simulations have been very fruitful for gaining insight into how the systematic structure we observe in the world’s natural languages could have emerged through cultural evolution. However, these model simulations operate on a toy scale compared to the size of actual human vocabularies, due to the prohibitive computational resource demands that simulations with larger lexicons would pose. Using computational complexity analysis, we show that this is not an implementational artifact, but instead it reflects a deeper theoretical issue: these models are (in their current formulation) computationally intractable. This has important theoretical implications, because it means that there is no way of knowing whether or not the properties and regularities observed for the toy models would scale up. All is not lost however, because awareness of intractability allows us to face the issue of scaling head-on, and can guide the development of our theories.


  • Open Access

    How hard is cognitive science?

    by Patricia Rich, Ronald de Haan, Todd Wareham, Iris van Rooij

    This is a preprint version of a published paper. Please cite as: Rich, P., de Haan, R., Wareham, T., & van Rooij, I. (2021). How hard is cognitive science? Proceedings of the Annual Meeting of the Cognitive Science Society, 43. Retrieved from https://escholarship.org/uc/item/8cr8x1c4


  • Open Access

    Obtaining a Proportional Allocation by Deleting Items

    by Britta Dorn, Ronald de Haan, Ildikó Schlotter

    We consider the following control problem on fair allocation of indivisible goods. Given a set I of items and a set of agents, each having strict linear preferences over the items, we ask for a minimum subset of the items whose deletion guarantees the existence of a proportional allocation in the remaining instance; we call this problem Proportionality by Item Deletion (PID). Our main result is a polynomial-time algorithm that solves PID for three agents. By contrast, we prove that PID is computationally intractable when the number of agents is unbounded, even if the number k of item deletions allowed is small—we show that the problem is $${\mathsf {W}}[3]$$ W [ 3 ] -hard with respect to the parameter k. Additionally, we provide some tight lower and upper bounds on the complexity of PID when regarded as a function of |I| and k. Considering the possibilities for approximation, we prove a strong inapproximability result for PID. Finally, we also study a variant of the problem where we are given an allocation $$\pi $$ π in advance as part of the input, and our aim is to delete a minimum number of items such that $$\pi $$ π is proportional in the remainder; this variant turns out to be $${{\mathsf {N}}}{{\mathsf {P}}}$$ N P -hard for six agents, but polynomial-time solvable for two agents, and we show that it is $$\mathsf {W[2]}$$ W [ 2 ] -hard when parameterized by the number k of


  • Open Access

    Egalitarian Judgment Aggregation

    by Sirin Botan, Ronald de Haan, Marija Slavkovik, Zoi Terzopoulou

    Egalitarian considerations play a central role in many areas of social choice theory. Applications of egalitarian principles range from ensuring everyone gets an equal share of a cake when deciding how to divide it, to guaranteeing balance with respect to gender or ethnicity in committee elections. Yet, the egalitarian approach has received little attention in judgment aggregation -- a powerful framework for aggregating logically interconnected issues. We make the first steps towards filling that gap. We introduce axioms capturing two classical interpretations of egalitarianism in judgment aggregation and situate these within the context of existing axioms in the pertinent framework of belief merging. We then explore the relationship between these axioms and several notions of strategyproofness from social choice theory at large. Finally, a novel egalitarian judgment aggregation rule stems from our analysis; we present complexity results concerning both outcome determination and strategic manipulation for that rule.