Artificial moral agents must not only be able to make competent ethical decisions, but they must do so efectively. This paper explores how ethical theory and algorithmic design impact computational eficiency by assessing the time cost of ethical algorithms. We create a model of an ethical environment and conduct experiments on three diferent ethical algorithms in order to compare computational benefits and disadvantages of deontology and consequentialism respectively. The experimental results highlight the close relationship between ethical theory, algorithmic design, and resource costs, and our work provides an important starting-point for the further examination of these relations. Lastly, we introduce the concept of moral tractability as a venue for future work.
Decisions made by emerging AI technology will undoubtedly have a major impact on human
lives, and the construction of beneficial and reliable machines is one of the most important
tasks of our time. Ethics from a computational perspective — machine ethics — has lately
attracted a lot of attention from AI researchers [
One overlooked but important aspect in machine ethics is the computational cost of ethical algorithms. The choice of theory, along with many aspects of its algorithmic interpretation, can have a big impact on the time required to make a decision, which in turn could yield dire consequences in situations where time is of the essence: self-driving vehicles avoiding collision, or robotic surgeons operating on critical care patients. It is therefore crucial to investigate how theory and implementation afects the trade-of between eficiency and optimality.
To tackle this challenge, this paper explores the time complexity of ethical algorithms. We Sweden create a model of an ethical environment and conduct experiments on three diferent algorithms in order to assess the computational benefits and disadvantages of deontology and consequentialism respectively. The aim is to investigate how algorithmic interpretation of ethical theory has a major impact on time eficiency. Finally, we discuss the concept of moral tractability as a venue for future work.
Implementations in machine ethics can broadly be distinguished along three dimensions: ethics,
implementation, and technology [
There are many ways to build ethical machines, and diferent approaches ofer their own particular advantages and drawbacks. Given its rule-based nature, deontology provides a seemingly straightforward path to implement ethical rules. The problem is that it assumes that we already know which ethical rules are the right ones and how they should be applied in every particular situation. By contrast, consequentialism chooses the action resulting in the best consequence, given by some utility. However, in real-life environments, the possible actions and their consequences can be hard to determine. Should we act on what we already know, or explore the unknown for something that would potentially be better? The situational benefits make it dificult to compare the success of diferent implementations, which is supported by the fact that morality is complicated. Considering the multifaceted nature of morality, and the potentially infinite number of situations one could find oneself in, it is infeasible that human morality could be captured by a single theory, even less so by a particular ethical algorithm. On the grounds that it is dificult to evaluate moral behavior, we can instead measure the resources involved.
A common denominator for all algorithms is their computational complexity, and analyzing
the resource cost of ethical theories might help us to better understand their respective benefits.
Previous work has noted that in complex situations, the estimation of actions and outcomes
yields a heavy cognitive burden for consequentialism relative to deontological algorithms [
To illuminate the complexity of ethical decisions, we provide a preliminary investigation into the eficiency of ethical algorithms. To do so, we first describe a simple model of a simulated ethical environment containing situations with a set number of possible actions and associated consequence values. We then design three ethical algorithms that represent reasonable strategies depending on the situation at hand, and measure their eficiency in terms of the number of state transitions they perform before halting.
Ethical environment — We define an ethical environment as a set of directed acyclic graphs (Fig. 1). Each graph consists of three types of nodes: an ethical situation , a set of possible actions = { 1, 2, … , } given , and a set of consequence values = { 1, 2, … , } for each possible action in . The consequence values are assumed to be specified in the environment and can be represented by any numerical or binary type. Each graph is connected by directed edges, leading from situation to actions to consequence values (i.e., → → ). For instance, the minimal environment 1 (Fig. 1, left) with only one situation, one action, and one consequence value, can be described as the vertices set { 1, 1, 1} and edge set {( 1, 1), ( 1, 1)}.
Ethical agents — An ethical agent consists of an algorithm and a memory. The former is a sequence of instructions governing the behavior of the agent, whereas the latter is used to store and access information. Each algorithm receives an ethical situation from the environment as input and outputs a simulated action. We describe three algorithms based on three diferent ethical strategies:
ConsExplore (Algorithm 1) is a consequentialist algorithm prioritizing exploration. This means that it will check for non-performed actions and try each one of them before choosing the optimal one. This is a viable strategy in situations where the number of possible actions are not known in advance, time resources are of less concern, and no action leads to a devastating consequence. In other words, the algorithm performs an exhaustive search over the consequences and compares the values using a temporary variable in order to ensure optimality [26].
Algorithm 1: ConsExplore 1 foreach possible action in situation do 2 if action is untried then 3 Execute action 4 Save consequence value of 5 end 6 foreach consequence value in do 7 if > ℎℎ then 8 highestValue = 9 Execute action with the highest value 10 end
ConsExploit (Algorithm 2) is another consequentialist algorithm. It prioritizes exploitation over exploration, meaning that it executes already performed actions given that they are satisficing, i.e., have a positive value, or a value above a set threshold. This strategy is useful in situations where time resources are of more concern and any consequence of positive value is permissible.
Algorithm 2: ConsExploit 1 for each possible action in situation do 2 if has a positive consequence value then 3 Execute action 4 end 5 if is untried then 6 Execute action 7 Save consequence value of 8 end
ConsExploreDeo (Algorithm 3) is a consequetialist-deontology hybrid, inspired by rule utilitarianism [27]. It is an extended version of ConsExplore which, once an optimal consequence is found, turns it into a deontological rule such that “if situation X, do action Y”. This combines the exploratory benefits of ConsExplore with the computational eficiency of rules.
Algorithm 3: ConsExploreDeo 1 if action-rule exists for then 2 Execute action 3 end 4 else 5 6 7 8 9 10 11 12 13 14 15 foreach possible action in situation do if is untried then
Execute action Save consequence value of end foreach consequence value in do if > ℎℎ then
highestValue = Execute action with highest value Save as action-rule for end
Resource costs — In our measure of eficiency, we adopt a uniform cost model, which assumes that one machine operation is equal to one unit of time, and a given computer takes a discrete amount of time to carry out each step in the algorithm [28]. Since all steps [ 1... ] are of equal value, we can calculate the time complexity as the amount of state transitions an algorithm does before it halts (reaches end condition).
We tested each algorithm on simulated environments consisting of ten situations with consequence values of integrals set randomly between −40 and +40. While consequence values and number of possible actions are given in the environment, they are initially unknown for the agents.
Experimental results are shown in Figures 2-4. The algorithms all begin by exploring actions and start to converge to their optimal average after approximately 100 decisions. Since ConsExploit (Fig. 3) performs an action as soon as it has found one with a satisfactory consequence, it is significantly faster than ConsExplore (Fig. 2) which iterates over all previously tried actions. On the other hand, while ConsExplore eventually converges to the optimal consequence values given by the environment, ConsExploit only converges to satisfactory ones bounded by its exploit-treshold. The eficiency of turning consequentialist calculations into deontological rules is evident in ConsExploreDeo (Fig. 4). Like ConsExplore, it converges to the optimal values but uses only 1 of the resources.
20
The results show the relative diference in time versus performance between three ethical algorithms that emphasize exploration (ConsExplore), exploitation (ConsExploit), and rule-based exploitation of exploration (ConsExploreDeo). Importantly, it highlights the intimate relationship between theory and resource costs, and how algorithmic design impacts performance. Another interesting observation is how deontological rules can be used to optimize eficiency, as shown in the case of ConsExploreDeo (Algorithm 3). In other contexts, deontology has commonly been assumed to serve as a kind of logical gate preventing certain actions from being performed, such as Isaac Asimov’s Laws of Robotics [29]. By contrast, our results show how deontological rules reduce the cost of consequence calculations, in efect representing a form rule consequentialism. It also resonates with the dual process theory of moral judgement, which separates fast and intuitive-driven judgements from slow conscious deliberation [30]. We believe similar cost-benefit analyses could potentially serve to illuminate and understand the appeal of certain ethical theories due to their computational eficiency.
Real-world environments are, however, far more complex than the simplified ones presented in this work. While we have focused on a few distilled aspects of ethical decisions, a proper analysis of systems in real-world situations has to encompass all relevant functionalities and resources available to carry out the task at hand. In turn, this might render the run-time complexity of the ethical aspects of the system rather insignificant in comparison to other considerations, such as sample and training-time complexity for reinforcement learning agents and neural networks [31, 32], or the use of sensors in autonomous vehicles [33]. For instance, the de facto run-time complexity of a self-driving car facing a certain dilemma (e.g., deciding collision priorities) might be trivial when it is equipped with specialized sensors and has been trained on vast amounts of data. This might suggest that the complexity of moral behavior is implementation-dependent to the extent that no implementation-invariant results can be obtained. It also raises the question: is there a reasonable way to compare the complexity involved of learning an agent to be moral and the complexity involved in solving an ethical problem following a decision procedure?
While our work fails to answer such broad questions, we believe that it opens up a path to address them. It is possible that, under certain conditions, there are general boundaries to consider, and reasons to commit to a certain strategy due to the computational complexity of the dilemma, and not due to moral reasons. An area for future work could therefore be to investigate the relevant trade-ofs of various AI methods that attempts to capture aspects of human morality, e.g., the logical reasoning underpinning rule-following, Bayesian methods dealing with decisions under uncertainty, and machine learning that supports moral learning. As such, it can draw from the vast literature studying the eficiency and tractability of computational methods [34, 31, 35], both in theory (e.g., in terms of complexity classes) and practice (e.g., average, best, and worst-case runtime of algorithms). This might serve our understanding of how algorithms, knowledge, learning, and cognition all come together to produce competent and eficient ethical behavior under resource constrains. This opens up the field of moral tractability, which aims to investigate the computational dimension of ethical theory in terms of resources. Moral tractability could potentially present a number of tasks and measures that give quantitative results in both general and domain-specific areas of ethical decision-making. Beyond artificial agents, if moral cognition in humans is limited by tractability [ 36], the field might also yield results relevant for normative ethics and moral psychology, e.g., by carving out the space of problems an ethical agent can or cannot solve efectively.
In summary, we have measured the time eficiency of ethical algorithms in order to highlight the relationship between ethical theory, algorithmic design, and resource costs. We believe it opens up an interesting space to address more general issues in assessing the performance of artificial moral systems in relation to computational resources, which can pave the way towards the creation of eficient ethical machines.
This work was partially supported by the Wallenberg AI, Autonomous Systems and Software Program – Humanities and Society (WASP-HS) funded by the Marianne and Marcus Wallenberg Foundation and the Marcus and Amalia Wallenberg Foundation. [7] C. Dang, T. Tran, K.-J. Gil, Y.-B. Shin, J.-W. Choi, G.-S. Park, J.-W. Kim, Application of soar cognitive agent based on utilitarian ethics theory for home service robots, in: Ubiquitous Robots and Ambient Intelligence (URAI), 2017 14th International Conference, IEEE, New York, USA, 2017, pp. 155–158. [8] M. Anderson, S. L. Anderson, Ethel: Toward a principled ethical eldercare system, in: AAAI Fall Symposium: AI in Eldercare: New Solutions to Old Problems, AAAI Press, Arlington, Virginia, 2008, pp. 4–11. [9] B. Malle, M. Scheutz, J. Austerweil, Networks of social and moral norms in human and robot agents, in: A World with Robots. Intelligent Systems, Control and Automation: Science and Engineering, volume 84, Springer, Cham, 2017, pp. 3–17. [10] J. Shim, R. Arkin, M. Pettinatti, An intervening ethical governor for a robot mediator in patient-caregiver relationship: Implementation and evaluation, in: 2017 IEEE International Conference on Robotics and Automation (ICRA), IEEE, New York, USA, 2017, pp. 2936–2942. [11] J. Stenseke, Artificial virtuous agents: from theory to machine implementation, AI &
SOCIETY (2021). doi:1 0 . 1 0 0 7 / s 0 0 1 4 6 - 0 2 1 - 0 1 3 2 5 - 7 . [12] N. S. Govindarajulu, S. Bringsjord, R. Ghosh, V. Sarathy, Toward the engineering of virtuous machines, in: Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, 2019, pp. 29–35. [13] M. Dehghani, E. Tomai, M. Klenk, An integrated reasoning approach to moral decisionmaking, in: Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, volume 3, AAAI Press, Chicago, Illinois, 2008, pp. 1280–1286. [14] N. S. Govindarajulu, S. Bringsjord, On automating the doctrine of double efect, in: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, Melbourne, Australia, 2017, pp. 4722–4730. [15] D. Howard, I. Muntean, Artificial moral cognition: Moral functionalism and autonomous moral agency, in: Philosophy and Computing: Essays in Epistemology, Philosophy of Mind, Logic, and Ethics, Springer, Cham, Switzerland, 2017, pp. 121–159. [16] S. Schefler, Consequentialism and its Critics, Oxford University Press on Demand, 1988. [17] I. Kant, Immanuel Kant: Groundwork of the Metaphysics of Morals (1785): A German– English edition, The Cambridge Kant German-English Edition, Cambridge University Press, 2011. [18] R. Hursthouse, On virtue ethics, OUP Oxford, 1999. [19] R. Noothigattu, S. N. S. Gaikwad, E. Awad, S. Dsouza, I. Rahwan, P. Ravikumar, A. D.
Procaccia, A voting-based system for ethical decision making, 2017. a r X i v : 1 7 0 9 . 0 6 6 9 2 . [20] S. Bringsjord, J. Taylor, The divine-command approach to robot ethics, in: Robot Ethics: The Ethical and Social Implications of Robotics, MIT Press, Cambridge, Massachusetts, 2012, pp. 85–108. [21] V. Wiegel, J. van den Berg, Combining moral theory, modal logic and mas to create well-behaving artificial agents, International Journal of Social Robotics 1 (2009) 233–242. [22] W. Wallach, C. Allen, Moral machines: Teaching robots right from wrong, Oxford University Press, 2008. [23] M. Brundage, Limitations and risks of machine ethics, Journal of Experimental & Theoretical Artificial Intelligence 26 (2014) 355–372. a r X i v : h t t p s : / / d o i . o r g / 1 0 . 1 0 8 0 / 0 9 5 2 8 1 3 X . 2 0 1 4 . 8 9 5 1 0 8 . [24] C. J. Reynolds, On the computational complexity of action evaluations, in: 6th International Conference of Computer Ethics: Philosophical Enquiry, University of Twente, Enschede, The Netherlands, 2005. [25] F. Lindner, R. Mattmüller, B. Nebel, Evaluation of the moral permissibility of action plans, Artificial Intelligence 287 (2020) 103350. URL: https://www.sciencedirect.com/science/ article/pii/S0004370219301043. doi:h t t p s : / / d o i . o r g / 1 0 . 1 0 1 6 / j . a r t i n t . 2 0 2 0 . 1 0 3 3 5 0 . [26] J. Nievergelt, R. Gasser, F. Mäser, C. Wirth, All the needles in a haystack: Can exhaustive search overcome combinatorial chaos?, in: Computer Science Today, Springer, 1995, pp. 254–274. [27] B. Hooker, Rule-consequentialism, Mind 99 (1990) 67–77. URL: http://www.jstor.org/ stable/2254891. [28] I. Wegener, Complexity theory: exploring the limits of eficient algorithms, Springer
Science & Business Media, 2005. [29] I. Asimov, Runaround, Astounding Science Fiction 29 (1942) 94–103. [30] J. D. Greene, R. B. Sommerville, L. E. Nystrom, J. M. Darley, J. D. Cohen, An fmri investigation of emotional engagement in moral judgment, Science 293 (2001) 2105–2108. [31] M. J. Kearns, The computational complexity of machine learning, MIT press, 1990. [32] S. Koenig, R. G. Simmons, Complexity analysis of real-time reinforcement learning, in:
AAAI, 1993, pp. 99–107. [33] C. Badue, R. Guidolini, R. V. Carneiro, P. Azevedo, V. B. Cardoso, A. Forechi, L. Jesus, R. Berriel, T. M. Paixao, F. Mutz, et al., Self-driving cars: A survey, Expert Systems with Applications 165 (2021) 113816. [34] N. Immerman, Descriptive complexity, Springer Science & Business Media, 1998. [35] J. Kwisthout, Most probable explanations in bayesian networks: Complexity and tractability, International Journal of Approximate Reasoning 52 (2011) 1452–1469. [36] I. Van Rooij, The tractable cognition thesis, Cognitive science 32 (2008) 939–984.