## Fachbereich Mathematik

### Refine

#### Year of publication

- 2009 (29) (remove)

#### Document Type

- Doctoral Thesis (16)
- Preprint (7)
- Report (5)
- Master's Thesis (1)

#### Has Fulltext

- yes (29) (remove)

#### Keywords

- Derivat <Wertpapier> (2)
- hidden variables (2)
- mixture (2)
- nonparametric regression (2)
- series-parallel graphs (2)
- AR-ARCH (1)
- Advanced Encryption Standard (1)
- Algebraic geometry (1)
- Algebraische Geometrie (1)
- Algebraische Geometrie (1)

- Truthful Mechanisms for Selfish Routing and Two-Parameter Agents (2009)
- We prove a general monotonicity result about Nash flows in directed networks and use it for the design of truthful mechanisms in the setting where each edge of the network is controlled by a different selfish agent, who incurs costs when her edge is used. The costs for each edge are assumed to be linear in the load on the edge. To compensate for these costs, the agents impose tolls for the usage of edges. When nonatomic selfish network users choose their paths through the network independently and each user tries to minimize a weighted sum of her latency and the toll she has to pay to the edges, a Nash flow is obtained. Our monotonicity result implies that the load on an edge in this setting can not increase when the toll on the edge is increased, so the assignment of load to the edges by a Nash flow yields a monotone algorithm. By a well-known result, the monotonicity of the algorithm then allows us to design truthful mechanisms based on the load assignment by Nash flows. Moreover, we consider a mechanism design setting with two-parameter agents, which is a generalization of the case of one-parameter agents considered in a seminal paper of Archer and Tardos. While the private data of an agent in the one-parameter case consists of a single nonnegative real number specifying the agent's cost per unit of load assigned to her, the private data of a two-parameter agent consists of a pair of nonnegative real numbers, where the first one specifies the cost of the agent per unit load as in the one-parameter case, and the second one specifies a fixed cost, which the agent incurs independently of the load assignment. We give a complete characterization of the set of output functions that can be turned into truthful mechanisms for two-parameter agents. Namely, we prove that an output function for the two-parameter setting can be turned into a truthful mechanism if and only if the load assigned to every agent is nonincreasing in the agent's bid for her per unit cost and, for almost all fixed bids for the agent's per unit cost, the load assigned to her is independent of the agent's bid for her fixed cost. When the load assigned to an agent is continuous in the agent's bid for her per unit cost, it must be completely independent of the agent's bid for her fixed cost. These results motivate our choice of linear cost functions without fixed costs for the edges in the selfish routing setting, but the results also seem to be interesting in the context of algorithmic mechanism design themselves.

- A Note On Inverse Max Flow Problem Under Chebyshev Norm (2009)
- In this paper, we study the inverse maximum flow problem under \(\ell_\infty\)-norm and show that this problem can be solved by finding a maximum capacity path on a modified graph. Moreover, we consider an extension of the problem where we minimize the number of perturbations among all the optimal solutions of Chebyshev norm. This bicriteria version of the inverse maximum flow problem can also be solved in strongly polynomial time by finding a minimum \(s - t\) cut on the modified graph with a new capacity function.

- Neue Methoden zur Lösung von Vorwärts-Rückwärts-Stochastischen-Differentialgleichungen (2009)
- Das zentrale Thema dieser Arbeit sind vollständig gekoppelte reflektierte Vorwärts-Rückwärts-Stochastische-Differentialgleichungen (FBSDE). Zunächst wird ein Spezialfall, die teilweise gekoppelten FBSDE, betrachtet und deren Verbindung zur Bewertung Amerikanischer Optionen aufgezeigt. Für die Lösung dieser Gleichung wird Monte-Carlo-Simulation benötigt, daher werden verschiedene Varianzreduktionsmaßnahmen erarbeitet und miteinander verglichen. Im Folgenden wird der allgemeinere Fall der vollständig gekoppelten reflektierten FBSDE behandelt. Es wird gezeigt, wie das Problem der Lösung dieser Gleichungen in ein Optimierungsproblem übertragen werden kann und infolgedessen mit numerischen Methoden aus diesem Bereich der Mathematik bearbeitet werden kann. Abschließend folgen Vergleiche der verschiedenen numerischen Ansätze mit bereits existierenden Verfahren.

- Interdisziplinäres Seminar: „Fachdidaktik Chemie und Mathematik“ - Ausarbeitungen und Unterrichtsentwürfe (2009)
- Im Sommersemester 2008 führte die AG Optimierung, FB Mathematik zusammen mit dem FB Chemie und dem FB Pädagogik ein interdisziplinäres Seminar zur „Fachdidaktik Chemie und Mathematik“ durch. Durch dieses integrative Lehrveranstaltungskonzept sollte die Nachhaltigkeit der Ausbildung gestärkt und die Verknüpfung von Allgemeiner Didaktik mit der Fachdidaktik sowie zwischen verschiedenen Fachbereichen gefördert werden. In dieser speziellen Veranstaltung erarbeiteten sich die Teilnehmer Inhalte in der Schnittmenge von Chemie und Mathematik, nämlich Kristallgeometrie, Analysis und Titration sowie Graphentheorie und Trennverfahren. Ihre Erkenntnisse wurden im Rahmen von Seminarvorträgen präsentiert und ausgearbeitet. Im folgenden Report befinden sich die Ausarbeitungen, welche Lernziele und Kompetenzen, Sach-, Methodische und Didaktische Analysen sowie Unterrichtsentwürfe umfassen.

- Modification of Simpson moduli spaces of 1-dimensional sheaves by vector bundles, an experimental example (2009)
- This thesis deals with the following question. Given a moduli space of coherent sheaves on a projective variety with a fixed Hilbert polynomial, to find a natural construction that replaces the subvariety of the sheaves that are not locally free on their support (we call such sheaves singular) by some variety consisting of sheaves that are locally free on their support. We consider this problem on the example of the coherent sheaves on \(\mathbb P_2\) with Hilbert polynomial 3m+1. Given a singular coherent sheaf \(\mathcal F\) with singular curve C as its support we replace \(\mathcal F\) by locally free sheaves \(\mathcal E\) supported on a reducible curve \(C_0\cup C_1\), where \(C_0\) is a partial normalization of C and \(C_1\) is an extra curve bearing the degree of \(\mathcal E\). These bundles resemble the bundles considered by Nagaraj and Seshadri. Many properties of the singular 3m+1 sheaves are inherited by the new sheaves we introduce in this thesis (we call them R-bundles). We consider R-bundles as natural replacements of the singular sheaves. R-bundles refine the information about 3m+1 sheaves on \(\mathbb P_2\). Namely, for every isomorphism class of singular 3m+1 sheaves there are \(\mathbb P_1\) many equivalence classes of R-bundles. There is a variety \(\tilde M\) of dimension 10 that may be considered as the space of all the isomorphism classes of the non-singular 3m+1 sheaves on \(\mathbb P_2\) together with all the equivalence classes of all R-bundles. This variety is obtained by blowing up the moduli space of 3m+1 sheaves on \(\mathbb P_2\) along the subvariety of singular sheaves. We modify the definition of a 3m+1 family and obtain a notion of a new family over an arbitrary variety S. In particular 3m+1 families of the non-singular sheaves on \(\mathbb P_2\) are families in this sense. New families over one point are either non-singular 3m+1 sheaves or R-bundles. For every variety S we introduce an equivalence relation on the set of all new families over S. The notion of equivalence for families over one point coincides with isomorphism for non-singular 3m+1 sheaves and with equivalence for R-bundles. We obtain a moduli functor \(\tilde{\mathcal M}:(Sch) \rightarrow (Sets)\) that assigns to every variety S the set of the equivalence classes of the new families over S. There is a natural transformation of functors \(\tilde{\mathcal M}\rightarrow \mathcal M\) that establishes a relation between \(\tilde{\mathcal M}\) and the moduli functor \(\mathcal M\) of the 3m+1 moduli problem on \(\mathbb P_2\). There is also a natural transformation \(\tilde{\mathcal M} \rightarrow Hom(\__ ,\tilde M)\), inducing a bijection \(\tilde{\mathcal M}(pt)\cong \tilde M\), which means that \(\tilde M\) is a coarse moduli space of the moduli problem \(\tilde{\mathcal M}\).

- Volatilitätsarbitrage und ein Markoff-Modell für CDOs (2009)
- Diese Doktorarbeit befasst sich mit Volatilitätsarbitrage bei europäischen Kaufoptionen und mit der Modellierung von Collateralized Debt Obligations (CDOs). Zuerst wird anhand einer Idee von Carr gezeigt, dass es stochastische Arbitrage in einem Black-Scholes-ähnlichen Modell geben kann. Danach optimieren wir den Arbitrage- Gewinn mithilfe des Erwartungswert-Varianz-Ansatzes von Markowitz und der Martingaltheorie. Stochastische Arbitrage im stochastischen Volatilitätsmodell von Heston wird auch untersucht. Ferner stellen wir ein Markoff-Modell für CDOs vor. Wir zeigen dann, dass man relativ schnell an die Grenzen dieses Modells stößt: Nach dem Ausfall einer Firma steigen die Ausfallintensitäten der überlebenden Firmen an, und kehren nie wieder zu ihrem Ausgangsniveau zurück. Dieses Verhalten stimmt aber nicht mit Beobachtungen am Markt überein: Nach Turbulenzen auf dem Markt stabilisiert sich der Markt wieder und daher würde man erwarten, dass die Ausfallintensitäten der überlebenden Firmen ebenfalls wieder abflachen. Wir ersetzen daher das Markoff-Modell durch ein Semi-Markoff-Modell, das den Markt viel besser nachbildet.

- Stochastic Impulse Control and Asset Allocation with Liquidity Breakdowns (2009)
- Continuous stochastic control theory has found many applications in optimal investment. However, it lacks some reality, as it is based on the assumption that interventions are costless, which yields optimal strategies where the controller has to intervene at every time instant. This thesis consists of the examination of two types of more realistic control methods with possible applications. In the first chapter, we study the stochastic impulse control of a diffusion process. We suppose that the controller minimizes expected discounted costs accumulating as running and controlling cost, respectively. Each control action causes costs which are bounded from below by some positive constant. This makes a continuous control impossible as it would lead to an immediate ruin of the controller. We give a rigorous development of the relevant theory, where our guideline is to establish verification and convergence results under minimal assumptions, without focusing on the existence of solutions to the corresponding (quasi-)variational inequalities. If the impulse control problem can be characterized or approximated by (quasi-)variational inequalities, it remains to solve these equations. In Section 1.2, we solve the stochastic impulse control problem for a one-dimensional diffusion process with constant coefficients and convex running costs. Further, in Section 1.3, we solve a particular multi-dimensional example, where the uncontrolled process is given by an at least two-dimensional Brownian motion and the cost functions are rotationally symmetric. By symmetry, this problem can be reduced to a one-dimensional problem. In the last section of the first chapter, we suggest a new impulse control problem, where the controller is in addition allowed to invest his initial capital into a market consisting of a money market account and a risky asset. The costs which arise upon controlling the diffusion process and upon trading in this market have to be paid out of the controller's bond holdings. The aim of the controller is to minimize the running costs, caused by the abstract diffusion process, without getting ruined. The second chapter is based on a paper which is joint work with Holger Kraft and Frank Seifried. We analyze the portfolio decision of an investor trading in a market where the economy switches randomly between two possible states, a normal state where trading takes place continuously, and an illiquidity state where trading is not allowed at all. We allow for jumps in the market prices at the beginning and at the end of a trading interruption. Section 2.1 provides an explicit representation of the investor's portfolio dynamics in the illiquidity state in an abstract market consisting of two assets. In Section 2.2 we specify this market model and assume that the investor maximizes expected utility from terminal wealth. We establish convergence results, if the maximal number of liquidity breakdowns goes to infinity. In the Markovian framework of Section 2.3, we provide the corresponding Hamilton-Jacobi-Bellman equations and prove a verification result. We apply these results to study the portfolio problem for a logarithmic investor and an investor with a power utility function, respectively. Further, we extend this model to an economy with three regimes. For instance, the third state could model an additional financial crisis where trading is still possible, but the excess return is lower and the volatility is higher than in the normal state.

- Mixtures of Nonparametric Autoregressions (2009)
- We consider data generating mechanisms which can be represented as mixtures of finitely many regression or autoregression models. We propose nonparametric estimators for the functions characterizing the various mixture components based on a local quasi maximum likelihood approach and prove their consistency. We present an EM algorithm for calculating the estimates numerically which is mainly based on iteratively applying common local smoothers and discuss its convergence properties.

- Polynomial system solving for decoding linear codes and algebraic cryptanalysis (2009)
- This thesis is devoted to applying symbolic methods to the problems of decoding linear codes and of algebraic cryptanalysis. The paradigm we employ here is as follows. We reformulate the initial problem in terms of systems of polynomial equations over a finite field. The solution(s) of such systems should yield a way to solve the initial problem. Our main tools for handling polynomials and polynomial systems in such a paradigm is the technique of Gröbner bases and normal form reductions. The first part of the thesis is devoted to formulating and solving specific polynomial systems that reduce the problem of decoding linear codes to the problem of polynomial system solving. We analyze the existing methods (mainly for the cyclic codes) and propose an original method for arbitrary linear codes that in some sense generalizes the Newton identities method widely known for cyclic codes. We investigate the structure of the underlying ideals and show how one can solve the decoding problem - both the so-called bounded decoding and more general nearest codeword decoding - by finding reduced Gröbner bases of these ideals. The main feature of the method is that unlike usual methods based on Gröbner bases for "finite field" situations, we do not add the so-called field equations. This tremendously simplifies the underlying ideals, thus making feasible working with quite large parameters of codes. Further we address complexity issues, by giving some insight to the Macaulay matrix of the underlying systems. By making a series of assumptions we are able to provide an upper bound for the complexity coefficient of our method. We address also finding the minimum distance and the weight distribution. We provide solid experimental material and comparisons with some of the existing methods in this area. In the second part we deal with the algebraic cryptanalysis of block iterative ciphers. Namely, we analyze the small-scale variants of the Advanced Encryption Standard (AES), which is a widely used modern block cipher. Here a cryptanalyst composes the polynomial systems which solutions should yield a secret key used by communicating parties in a symmetric cryptosystem. We analyze the systems formulated by researchers for the algebraic cryptanalysis, and identify the problem that conventional systems have many auxiliary variables that are not actually needed for the key recovery. Moreover, having many such auxiliary variables, specific to a given plaintext/ciphertext pair, complicates the use of several pairs which is common in cryptanalysis. We thus provide a new system where the auxiliary variables are eliminated via normal form reductions. The resulting system in key-variables only is then solved. We present experimental evidence that such an approach is quite good for small scaled ciphers. We investigate further our approach and employ the so-called meet-in-the-middle principle to see how far one can go in analyzing just 2-3 rounds of scaled ciphers. Additional "tuning techniques" are discussed together with experimental material. Overall, we believe that the material of this part of the thesis makes a step further in algebraic cryptanalysis of block ciphers.

- On Inverse Network Problems and their Generalizations (2009)
- In the context of inverse optimization, inverse versions of maximum flow and minimum cost flow problems have thoroughly been investigated. In these network flow problems there are two important problem parameters: flow capacities of the arcs and costs incurred by sending a unit flow on these arcs. Capacity changes for maximum flow problems and cost changes for minimum cost flow problems have been studied under several distance measures such as rectilinear, Chebyshev, and Hamming distances. This thesis also deals with inverse network flow problems and their counterparts tension problems under the aforementioned distance measures. The major goals are to enrich the inverse optimization theory by introducing new inverse network problems that have not yet been treated in the literature, and to extend the well-known combinatorial results of inverse network flows for more general classes of problems with inherent combinatorial properties such as matroid flows on regular matroids and monotropic programming. To accomplish the first objective, the inverse maximum flow problem under Chebyshev norm is analyzed and the capacity inverse minimum cost flow problem, in which only arc capacities are perturbed, is introduced. In this way, it is attempted to close the gap between the capacity perturbing inverse network problems and the cost perturbing ones. The foremost purpose of studying inverse tension problems on networks is to achieve a well-established generalization of the inverse network problems. Since tensions are duals of network flows, carrying the theoretical results of network flows over to tensions follows quite intuitively. Using this intuitive link between network flows and tensions, a generalization to matroid flows and monotropic programs is built gradually up.