Ronald de Haan
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:
- Iris van Rooij
Radboud University
7 shared publications - Mark Blokpoel
Radboud University
4 shared publications - Patricia Rich
Department of Philosophy, University of Bayreuth, Bayreuth, Germany
3 shared publications - Andreas Niskanen
University of Helsinki
2 shared publications - Ari Conati
University of Helsinki, Finland
2 shared publications - Marija Slavkovik
University of Bergen
2 shared publications
Latest Publications
- 13 November 2026
- Published by Springer Nature
- p. 329-344
Finding Stable Partitions in Boolean Hedonic Games
- 13 November 2026
- Published by Springer Nature
- p. 329-344
Finding Stable Partitions in Boolean Hedonic Games
- Open Access
- 16 October 2024
- Published by IOS Press
- p. 3597-3604
Complexity Results and Algorithms for Manipulation and Bribery in Judgment Aggregation
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.
- 16 October 2024
- Published by IOS Press
- p. 3597-3604
Open AccessComplexity Results and Algorithms for Manipulation and Bribery in Judgment Aggregation
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.
- Open Access
- 28 June 2024
- Published by Center for Open Science in PsyArXiv
Intractability obstacles to explanations of communication
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.
- 28 June 2024
- Published by Center for Open Science in PsyArXiv
Open AccessIntractability obstacles to explanations of communication
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
- 1 August 2023
- Published by Center for Open Science in PsyArXiv
Reclaiming AI as a theoretical tool for cognitive science
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.
- 1 August 2023
- Published by Center for Open Science in PsyArXiv
Open AccessReclaiming AI as a theoretical tool for cognitive science
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
- 15 February 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Human-Robot Interaction
- Vol. 12 (1) , 1-45
Swarm Control for Distributed Construction: A Computational Complexity Perspective
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.
- 15 February 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Human-Robot Interaction
- Vol. 12 (1) , 1-45
Open AccessSwarm Control for Distributed Construction: A Computational Complexity Perspective
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
- 12 May 2021
- Published by Center for Open Science in PsyArXiv
Why is scaling up models of language evolution hard?
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.
- 12 May 2021
- Published by Center for Open Science in PsyArXiv
Open AccessWhy is scaling up models of language evolution hard?
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
- 23 April 2021
- Published by Center for Open Science in PsyArXiv
How hard is cognitive science?
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
- 23 April 2021
- Published by Center for Open Science in PsyArXiv
Open AccessHow hard is cognitive science?
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
- 26 March 2021
- Published by Springer Nature in Algorithmica
- Vol. 83 (5) , 1559-1603
Obtaining a Proportional Allocation by Deleting Items
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]$$ -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}}}$$ -hard for six agents, but polynomial-time solvable for two agents, and we show that it is $$\mathsf {W[2]}$$ -hard when parameterized by the number k of- 26 March 2021
- Published by Springer Nature in Algorithmica
- Vol. 83 (5) , 1559-1603
Open AccessObtaining a Proportional Allocation by Deleting Items
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]$$ -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}}}$$ -hard for six agents, but polynomial-time solvable for two agents, and we show that it is $$\mathsf {W[2]}$$ -hard when parameterized by the number k of - Open Access
Egalitarian Judgment Aggregation
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.
Open AccessEgalitarian Judgment Aggregation
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.