Constraint Satisfaction Problems (CSPs) are a class of decision problems where one usually fixes a structure A and seeks to decide whether or not a given conjunction of atomic formulas is satisfiable in A or not. It has been shown by Bodirsky and Grohe that every computational decision problem is equivalent to some CSP via a polynomial-time Turing reduction. For structures A with finite domain Zhuk and Bulatov both proved an algebraic criterion classifying in which cases the CSP of A is in P and when it is NP-hard. For some classes of structures with infinite domain, there are similar P vs NP-hard dichotomies. This thesis continues the latter line of research for CSPs of first-order theories. In this version of CSPs, a theory is fixed and one seeks to decide whether or not a given conjunction of atomic formulas is satisfiable in some model of T. Assuming that the CSPs of theories T1 and T2 are polynomial-time tractable, we prove necessary and sufficient conditions for polynomial-time tractability of the union of T1 and T2. For some classes of theories, P vs NP-hard dichotomies are proven. To achieve this, various 'combinations' of structures are examined, a technique called 'sampling' is generalized to theories and clones of polymorphisms of temporal structures are examined in detail.

Kollektives Handeln ist erforderlich um nachhaltige Entwicklungspfade in gekoppelten sozial-ökologischen Systemen zu erschließen, fernab von gefährlichen Kippelementen. Ohne anderen Modellierungsprinzipien ihren Nutzen abzuerkennen, schlägt diese Dissertation die Agent-Umwelt Schnittstelle als die mathematische Grundlage für das Modellieren sozial-ökologischer Systeme vor. Zuerst erweitert diese Arbeit eine Methode aus der Literatur der statistischen Physik über Lerndynamiken, um einen deterministischen Grenzübergang von etablierten Verstärkungslernalgorithmen aus der Forschung zu künstlicher Intelligenz herzuleiten. Die resultierenden Lerndynamiken zeigen eine große Bandbreite verschiedener dynamischer Regime wie z.B. Fixpunkte, Grenzzyklen oder deterministisches Chaos. Zweitens werden die hergeleiteten Lerngleichungen auf eine neu eingeführte Umwelt, das Ökologisches Öffentliches Gut, angewendet,. Sie modelliert ein gekoppeltes sozial-ökologisches Dilemma und erweitert damit etablierte soziale Dilemmaspiele um ein ökologisches Kippelement. Bekannte theoretische und empirische Ergebnisse werden reproduziert und neuartige, qualitativ verschiedene Parameterregime aufgezeigt, darunter eines, in dem diese belohnungsoptimierenden Lern-Agenten es vorziehen, gemeinsam unter einem Kollaps der Umwelt zu leiden, als in einer florierenden Umwelt zu kooperieren. Drittens stellt diese Arbeit das Optimierungsparadigma der Lern-Agenten in Frage. Die drei Entscheidungsparadimen ökonomischen Optimierung, Nachhaltigkeit und Sicherheit werden systematisch miteinander verglichen, während sie auf das Management eines umweltlichen Kippelements angewendet werden. Es wird gezeigt, dass kein Paradigma garantiert, Anforderungen anderer Paradigmen zu erfüllen, sowie dass das Fehlen eines Meisterparadigmas von besonderer Bedeutung für das Klimasystem ist, da dieses sich am Rand zwischen Parameterbereichen befinden kann, wo ökonomische Optimierung weder nachhaltig noch sicher wird. / Collective action is required to enter sustainable development pathways in coupled social-ecological systems, safely away from dangerous tipping elements. Without denying the usefulness of other model design principles, this thesis proposes the agent-environment interface as the mathematical foundation for the design of social-ecological system models. First, this work refines techniques from the statistical physics literature on learning dynamics to derive a deterministic limit of established reinforcement learning algorithms from artificial intelligence research. Illustrations of the resulting learning dynamics reveal a wide range of different dynamical regimes, such as fixed points, periodic orbits and deterministic chaos. Second, the derived multi-state learning equations are applied to a newly introduced environment, the Ecological Public Good. It models a coupled social-ecological dilemma, extending established repeated social dilemma games by an ecological tipping element. Known theoretical and empirical results are reproduced and novel qualitatively different parameter regimes are discovered, including one in which these reward-optimizing agents prefer to collectively suffer in environmental collapse rather than cooperating in a prosperous environment. Third, this thesis challenges the reward optimizing paradigm of the learning equations. It presents a novel formal comparison of the three decision paradigms of economic optimization, sustainability and safety for the governance of an environmental tipping element. It is shown that no paradigm guarantees fulfilling requirements imposed by another paradigm. Further, the absence of a master paradigm is shown to be of special relevance for governing the climate system, since the latter may reside at the edge between parameter regimes where economic welfare optimization becomes neither sustainable nor safe.

Einem Konsumenten werden in verschiedensten Situationen Rabatte angeboten. In dieser Dissertation wird die Frage untersucht, wie solche Rabattsituationen aus konsumentensicht formalisiert werden können und wie Kaufentscheidungen getroffen werden können. Um diese Frage zu beantworten, wird ein formaler Rahmen für Rabattsituationen angegeben und zur Analyse einer neuen Gruppe von acht Problemen, die auf alltäglichen Erfahrungen mit Rabattaktionen basieren, angewendet. Diese Probleme werden hinsichtlich der Rabattgrundlage (Stempel / Punkte), dem Kartentyp (Einzelkarte, Gruppenkarte) und der Frage, ob Stempel/Punkte für Käufe mit Rabatt gesammelt werden, unterschieden. Der inhärenten Planungsunsicherheit für Konsumentenentscheidungen wird explizit durch die Betrachtung jedes Problems als eine Onlinesituation Rechnung getragen. Für die Onlineprobleme wird eine zugeschnittene Methode zur Güteabschätzung präsentiert. Jedes der acht Probleme wird als Entscheidungs-, Optimierungs- und Onlineproblem analysiert. Für alle Entscheidungsprobleme wird NP-Vollständigkeit nachgewiesen. Jedes Optimierungsproblem wird mit ganzzahliger linearer Programmierung und einige stempelbasierte Probleme zusätzlich mit dynamischer Programmierung gelöst. Für die Onlineprobleme wird jeweils eine untere Güteschranke gezeigt und für drei Gruppen von Onlinealgorithmen die Güte abgeschätzt.:1. Einleitung 2. Vorbetrachtungen 3. Problemformulierung und Analysemethodik 4. Die Probleme im Detail 5. Zusammenfassung 6. Ausblick A. Implementationen / A consumer is offered discounts in a variety of situations. The central question investigated in this dissertation is how to formalize such discount situations from a consumer perspective and what methods for deducing purchase decisions are possible. To answer this question a formal framework for discount situations is established and used to explore a new group of eight discount problems based on everyday experience with loyalty programs. These problems are distinguished by discount basis (stamps / points), card type (single / group) and whether stamps/-points are collectable if a discount is granted. The inherent uncertainty in consumer decisions is explicitly taken into account by considering each of these problems as an online situation as well. Regarding the online problems, a method for competitive analysis is presented. Each of the eight problems is examined as a decision, an optimization and an online problem. For all decision problems N P-completeness is shown. Each optimization problem is solved via linear integer programming and some stamp based optimization problems are furthermore solved with dynamic programming. For each online problem a lower bound on the competitive ratio is presented together with three groups of online algorithms and the respective bounds on the competitive ratio.:1. Einleitung 2. Vorbetrachtungen 3. Problemformulierung und Analysemethodik 4. Die Probleme im Detail 5. Zusammenfassung 6. Ausblick A. Implementationen