1,720,991 research outputs found
On Floridi's method of levels of abstraction
No full textAbstraction is arguably one of the most important methods in modern science in analysing and understanding complex phenomena. In his book The Philosophy of Information, Floridi (The philosophy of information. Oxford University Press, Oxford, 2011) presents the method of levels of abstraction as the main method of the Philosophy of Information. His discussion of abstraction as a method seems inspired by the formal methods and frameworks of computer science, in which abstraction is operationalised extensively in programming languages and design methodologies. Is it really clear what we should understand by levels of abstraction? How should they be specified? We will argue that levels of abstraction should be augmented with annotations, in order to express semantic information for them and reconcile the method of level of abstraction (LoA's) with other approaches. We discuss the extended method when applied e.g. to the analysis of abstract machines. This will lead to an example in which the number of LoA's is unbounded
A note on recursively enumerable classes of partial recursive functions
No full textWe prove that every recursively enumerable class of partial recursive functions with infinite domains must have a recursive witness array. The result gives a powerful method for proving properties of recursively enumerable classes. We show for example that no finitely generated group of recursive permutations can contain all recursive involutions, and neither can it contain all cycle-free recursive permutations
Turing machines with one-sided advice and the acceptance of the co-RE languages
No full textWe resolve an old problem, namely to design a ‘natural’ machine model for accepting the complements of recursively enumerable languages
Tracking maximum ascending subsequences in sequences of partially ordered data
No full textWe consider scenarios in which long sequences of data are analyzed and subsequences must be traced that are monotone and maximum, according to some measure. A classical example is the online Longest Increasing Subsequence Problem for numeric and alphanumeric data. We extend the problem in two ways: (a) we allow data from any partially ordered set, and (b) we maximize subsequences using much more general measures than just length or weight. Let P be a poset of finite width w, and let δ be any data sequence over P. We show that the measure of the maximum monotone subsequences in δ can be maintained in at most O(w log min( n w , Dn)) time and O(min(n, wDn)) memory when the n-th data item is processed, where Dn is the ‘depth’ of the measure at position n (n ≥ 1). The result generalizes all earlier O(log n) time-per-input results for the corresponding longest or heaviest increasing subsequence problems
Pure Nash Equilibria in Graphical Games and Treewidth
Full text linkWe treat PNE-GG, the problem of deciding the existence of a Pure Nash Equilibrium in a graphical game, and the role of treewidth in this problem. PNE-GG is known to be (Formula presented.)-complete in general, but polynomially solvable for graphical games of bounded treewidth. We prove that PNE-GG is (Formula presented.)-Hard when parameterized by treewidth. On the other hand, we give a dynamic programming approach that solves the problem in (Formula presented.) time, where (Formula presented.) is the cardinality of the largest strategy set and (Formula presented.) is the treewidth of the input graph (and (Formula presented.) hides polynomial factors). This proves that PNE-GG is in (Formula presented.) for the combined parameter (Formula presented.). Moreover, we prove that there is no algorithm that solves PNE-GG in (Formula presented.) time for any (Formula presented.), unless the Strong Exponential Time Hypothesis fails. Our lower bounds implicitly assume that (Formula presented.); we show that for (Formula presented.) the problem can be solved in polynomial time. Finally, we discuss the implication for computing pure Nash equilibria in graphical games (PNE-GG) of (Formula presented.) treewidth, the existence of polynomial kernels for PNE-GG parameterized by treewidth, and the construction of a sample and maximum-payoff pure Nash equilibrium
Using Cultures and Values to Support Flexible Coordination
No full textThis thesis proposes a method for supporting flexible coordination in multi-agent systems (MASs). In other words, we aim at influencing societies of artificial agents such that they can handle complex and evolving environments and collective goals (emergency rescue robots capable of handling various hazards, climatic conditions, statuses of victims). Towards acheving this goal, we investigated why humans manage to coordinate relatively flexibly in comparison with their artificial counterparts (agents). We discovered that culture is a key factor of this relative success. Briefly, when humans share a cultural background, they share a common idea about what "working together'' means, supporting flexible coordination. Artificial agents miss this aspect, leading to coordination failures. As a goal, we want to better understand how culture can be integrated within and used for coordinating artificial societies. This goal raises this research question: (how) can human-like culture be used for supporting coordination in artificial societies? As a preliminary step, we need to answer that question: (how) can the influence human-like cultures be integrated within artificial societies? In turn, this question raises a third one: how does culture influence coordination in human societies? As a first step, we conceptualize the influence of culture on coordination, based on available theories. From a generic perspective, we explain that culture influences individual decisions, supporting matching expectations and coherent interaction patterns, leading in turn to (generally) better collective performance. More specifically, we specify how the core acknowledged patterns of the influence of culture (cultural importance given to power status, to rules) apply in the context of coordination (culture influences whether leaders are (made) responsible for giving order vs propositions to subordinates). As a second step, we study how to replicate human-like influences of culture on coordination within artificial societies. First, we investigate the core aspects of culture that impact the most (flexible) coordination in human societies. We discover that values, what people consider as "good'' of "important'' (honesty, obedience, autonomy), constitute such an aspect, by deeply supporting a wide range of (interaction-related) decisions. Then, for illustrating how to replicate influence of culture within artificial societies, we build an value-sensitive agent decision architecture capable of making culturally-sensitive coordination-related decisions. Finally, we illustrate that our architecture can replicate the influence of culture on coordination through two simulations that replicate core known coordination-related cultural phenomena. As a third step, we study how human-like values can be used for coordinating artificial societies. We investigate for which coordination problems values can offer an operational means for supporting coordination. We discover that values are particularly adequate for solving problems involving complex and dynamic environments, requiring agents to make coordination-related decisions. Then, towards concretely implementating values, we study the technical details to consider for supporting flexible coordination with values (concretely designing values, integrating them within agents). In sum, this thesis highlights that key aspects of the influence of culture on coordination can be replicated within artificial societies. Furthermore, we show that this influence can be handled for using culture as a means for supporting flexible coordination in artificial societies
A Formal Account of Opportunism in Multi-agent Systems
Full text linkOpportunistic behavior is a selfish behavior that takes advantage of knowledge asymmetry and results in promoting agents' own value but demoting other agents' value. It is commonly existing in business transactions and social interactions, thereby gaining much attention and investigation from social science. In the context of multi-agent systems, it is normal that knowledge is distributed among different agents, which creates the opportunity for agents to perform opportunistic behavior to other agents. Since opportunistic behavior has undesirable results for other agents in the system, the aim of this thesis is to eliminate such a selfish behavior from the system. We first propose a formal account of opportunism based on the situation calculus, capturing the features of opportunism: knowledge asymmetry, intention and value opposition. Because opportunistic behavior has undesirable results for other agents in the system but cannot be observed indirectly, there has to be a monitoring mechanism that can detect the performance of opportunistic behavior. We secondly provides a logical framework to specify monitoring approaches for opportunism. We investigate how to evaluate agents' actions to be opportunistic with respect to different forms of norms when those actions cannot be observed directly, and study how to reduce the monitoring cost for opportunism. In order for monitoring and eliminating mechanisms to be put in place, it is important to know in which context agents will or are likely to perform opportunistic behavior. Therefore, we develop a framework to reason about agents' opportunistic propensity. Opportunistic propensity refers to the potential for an agent to perform opportunistic behavior. We characterize the situation where agents will perform opportunistic behavior and the contexts where opportunism is impossible to occur. Finally, we reach our goal through designing two mechanisms for eliminating opportunism: in the epistemic approach an agent's knowledge gets updated so that the other agent is not able to perform opportunistic behavior, and in the normative approach the system is updated with a norm so that it is not optimal for an agent to perform opportunistic behavior
A formal account of opportunism based on the situation calculus
No full textIn social interactions, it is common for individuals to possess different amounts of knowledge about a specific transaction, and those who are more knowledgeable might perform opportunistic behavior to others in their interest, which promotes their value but demotes others' value. Such a typical social behavior is called opportunistic behavior (opportunism). In this paper, we propose a formal account of opportunism based on the situation calculus. We first propose a model of opportunism that only considers a single action between two agents, and then extend it to multiple actions and incorporate social context in the model. A simple example of selling a broken cup is used to illustrate our models. Through our models, we can have a thorough understanding of opportunism
Towards a Framework for Predicting Opportunism in Multi-agent Systems
Full text linkOpportunism is a behavior that takes advantage of knowledge asymmetry and results in promoting agents' own value and demoting others' value. We propose a framework to reason about agents' opportunistic propensity and characterize the situation where agents will perform opportunistic behavior
Personalized Educational Games - Developing agent-supported scenario-based training
No full textIn many professions people make decisions under risky and stressful circumstances (e.g. the police force, military, or medical services). In such professions, practical training is often difficult, because erroneous decisions may result in grievous consequences. Yet learners need to gain experience in order to become good decision makers. Scenario-based training (SBT) is an effective training form to provide learners with the experience they need. During SBT, learners are presented with interactive role-playing exercises staged in a simulated environment. SBT has several limitations that prohibit learners from engaging in autonomous, personalized training. For instance, it requires considerable logistic and organizational efforts, and it is often difficult to adjust the scenario once it starts playing. To overcome these limitations, this research investigates a design for automated SBT: a Personalized Educational Game (PEG). A PEG employs a virtual environment to stage the training scenarios. In addition, a PEG employs artificial intelligence techniques to control the events in the simulated environment, as well as the behavior of the characters in the scenario. The scenarios in a PEG are tailored to learners’ individual needs, enabling them to develop their competencies at their own level and pace. For this, a PEG keeps track of relevant information about the learner, uses it to determine a suitable learning goal and difficulty level, and automatically generates a scenario that fits those needs. A PEG also supports and exploits the expertise of instructors. For instance, instructors are able to determine the learning goal, author a scenario, or define the behaviors of the characters. The human instructor is not excluded from or replaced by the PEG, but rather the PEG allows for variable levels of automation, depending on instructors’ preferences and availability. A PEG presents scenarios to the learner as a playable storyline in a virtual world where the learner can interact with virtual characters controlled by intelligent agents. A PEG can execute adaptations while the scenario is playing to ensure that the scenario remains suitable for the learner’s individual competency levels. After a learner has finished playing the scenario, a PEG aims to help learners in acquiring a deeper understanding of the events taking place in the simulated environment. For this, it encourages learners to reflect on their performance and to provide explanations for their decisions. If learners are unable to provide adequate explanations themselves, a PEG provides hints and additional instructional explanations. Most of the PEG’s functions (described above) have been evaluated in pilot studies. In these studies it was found that: (1) realtime adjustments are beneficial for the learning value of the scenarios; (2) the automatically generated scenarios were at least of a quality comparable to scenarios produced by laymen, yet not as good as the ones produced by domain experts; and (3) the quality of both the authoring process and the resulting scenarios increased as a result of a support function that used instructors’ selected learning goals to offer them suggestions for the contents of a scenario. Two remaining functions require additional testing
- …
