Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2017 | Book

On the Push&Pull Protocol for Rumour Spreading Read chapter Read first chapter

Extended Abstracts Summer 2015

Strategic Behavior in Combinatorial Structures; Quantitative Finance

Editors: Josep Díaz, Lefteris Kirousis, Luis Ortiz-Gracia, Maria Serna

Publisher: Springer International Publishing

Book Series : Trends in Mathematics

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This book is divided into two parts, the first of which seeks to connect the phase transitions of various disciplines, including game theory, and to explore the synergies between statistical physics and combinatorics. Phase Transitions has been an active multidisciplinary field of research, bringing together physicists, computer scientists and mathematicians. The main research theme explores how atomic agents that act locally and microscopically lead to discontinuous macroscopic changes. Adopting this perspective has proven to be especially useful in studying the evolution of random and usually complex or large combinatorial objects (like networks or logic formulas) with respect to discontinuous changes in global parameters like connectivity, satisfiability etc. There is, of course, an obvious strategic element in the formation of a transition: the atomic agents “selfishly” seek to optimize a local parameter. However, up to now this game-theoretic aspect of abrupt, locally triggered changes had not been extensively studied.

In turn, the book’s second part is devoted to mathematical and computational methods applied to the pricing of financial contracts and the measurement of financial risks. The tools and techniques used to tackle these problems cover a wide spectrum of fields, like stochastic calculus, numerical analysis, partial differential equations, statistics and econometrics. Quantitative Finance is a highly active field of research and is increasingly attracting the interest of academics and practitioners alike. The material presented addresses a wide variety of new challenges for this audience.

Table of Contents

Frontmatter

Strategic Behavior in Combinatorial Structures

Frontmatter
On the Push&Pull Protocol for Rumour Spreading
Abstract
The asynchronous push&pull protocol, a randomized distributed algorithm for spreading a rumour in a graph G, is defined as follows. Independent exponential clocks of rate 1 are associated with the vertices of G, one to each vertex. Initially, one vertex of G knows the rumour. Whenever the clock of a vertex x rings, it calls a random neighbour y: if x knows the rumour and y does not, then x tells y the rumour (a push operation), and if x does not know the rumour and y knows it, y tells x the rumour (a pull operation). The average spread time of G is the expected time it takes for all vertices to know the rumour, and the guaranteed spread time of G is the smallest time t such that with probability at least 1 − 1∕n, after time t all vertices know the rumour. The synchronous variant of this protocol, in which each clock rings precisely at times 1, 2, …, has been studied extensively.
We prove the following results for any n-vertex graph: in either version, the average spread time is at most linear even if only the pull operation is used, and the guaranteed spread time is within a logarithmic factor of the average spread time, so it is O(nlogn). In the asynchronous version, both the average and guaranteed spread times are \(\Omega (\log n)\). We give examples of graphs illustrating that these bounds are best possible up to constant factors.
We also prove the first theoretical relationships between the guaranteed spread times in the two versions. Firstly, in all graphs the guaranteed spread time in the asynchronous version is within an O(logn) factor of that in the synchronous version, and this is tight. Next, we find examples of graphs whose asynchronous spread times are logarithmic, but the synchronous versions are polynomially large. Finally, we show for any graph that the ratio of the synchronous spread time to the asynchronous spread time is \(O\big(n^{2/3}\big)\).
Hüseyin Acan, Andrea Collevecchio, Abbas Mehrabian, Nick Wormald
Random Walks That Find Perfect Objects and the Lovász Local Lemma
Abstract
We give an algorithmic local lemma by establishing a sufficient condition for the uniform random walk on a directed graph to reach a sink quickly. Our work is inspired by Moser’s entropic method proof of the Lovász Local Lemma (LLL) for satisfiability, and completely bypasses the Probabilistic Method formulation of the LLL. In particular, our method works when the underlying state space is entirely unstructured. Similarly to Moser’s argument, the key point is that the inevitability of reaching a sink is established by bounding the entropy of the walk as a function of time.
Dimitris Achlioptas, Fotis Iliopoulos
Logit Dynamics with Concurrent Updates for Local Interaction Games
Abstract
Game Theory is the main tool used to model the behavior of agents that are guided by their own objective in contexts where their gains depend also on the choices made by neighboring agents. Game theoretic approaches have been often proposed for modeling phenomena in a complex social network, such as the formation of the social network itself. We are interested in the dynamics that govern such phenomena. In this paper, we study a specific class of randomized update rules called the logit choice function which can be coupled with different selection rules so to give different dynamics. We study how the logit choice function behave in an extreme case of concurrency.
Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale, Paolo Penna, Giuseppe Persiano
The Set Chromatic Number of Random Graphs
Abstract
We study the set chromatic number of a random graph \(\mathcal{G}(n,p)\) for a wide range of p = p(n). We show that the set chromatic number, as a function of p, forms an intriguing zigzag shape.
Andrzej Dudek, Dieter Mitsche, Paweł Prałat
Carpooling in Social Networks
Abstract
We consider the online carpool fairness problem of Fagin–Williams (IBM J Res Dev 27(2):133–139, 1983), where an online algorithm is presented with a sequence of pairs drawn from a group of n potential drivers. The online algorithm must select one driver from each pair, with the objective of partitioning the driving burden as fairly as possible for all drivers. The unfairness of an online algorithm is a measure of the worst-case deviation between the number of times a person has driven and the number of times they would have driven if life was completely fair.
We consider the version of the problem in which drivers only carpool with their neighbors in a given social network graph; this is a generalization of the original problem, which corresponds to the social network of the complete graph. We show that, for graphs of degree d, the unfairness of deterministic algorithms against adversarial sequences is exactly d∕2. For randomized algorithms, we show that static algorithms, a natural class of online algorithms, have unfairness \(\tilde{\Theta }(\sqrt{d})\). For random sequences on stars and in bounded-genus graphs, we give a deterministic algorithm with logarithmic unfairness. Interestingly, restricting the random sequences to sparse social network graphs increases the unfairness of the natural greedy algorithm. In particular, for the line social network, this algorithm has expected unfairness \(\Omega (\log ^{1/3}n)\), whereas for the clique social network its expected unfairness is O(loglogn); see Ajtai–Aspnes–Naor–Rabani–Schulman–Waarts (J Algorithm 29(2):306–357, 1998).
Amos Fiat, Anna R. Karlin, Elias Koutsoupias, Claire Mathieu, Rotem Zach
Who to Trust for Truthful Facility Location?
Abstract
We consider approximate mechanisms without money and with selective verification for k-Facility Location problems. We show how a deterministic greedy mechanism and a randomized proportional mechanism become truthful with selective verification.
Dimitris Fotakis, Christos Tzamos, Emmanouil Zampetakis
Metric and Spectral Properties of Dense Inhomogeneous Random Graphs
Abstract
We study metric and spectral properties of dense inhomogeneous random graphs. We generalize results known for the Erdös–Renyi model. In our case an edge (i, j) is present with probability κ(X i , X j )p, where κ ≥ 0 is a fixed kernel and X i are independent variables from a general distribution on a separable metric space.
Nicolas Fraiman, Dieter Mitsche
On-Line List Colouring of Random Graphs
Abstract
The on-line list colouring of binomial random graphs \(\mathcal{G}(n,p)\) is studied. We show that the on-line choice number of \(\mathcal{G}(n,p)\) is asymptotically almost surely asymptotic to the chromatic number of \(\mathcal{G}(n,p)\), provided that the average degree d = p(n − 1) tends to infinity faster than (loglogn)1∕3(logn)2 n 2∕3. For sparser graphs, we are slightly less successful; we show that if d ≥ (logn)2+ɛ for some ɛ > 0, then the on-line choice number is larger than the chromatic number by at most a multiplicative factor of C, where C ∈ [2, 4], depending on the range of d. Also, for d = O(1), the on-line choice number is, by at most, a multiplicative constant factor larger than the chromatic number.
Alan Frieze, Dieter Mitsche, Xavier Pérez-Giménez, Paweł Prałat
Approximation Algorithms for Computing Maximin Share Allocations
Abstract
We study the problem of computing maximin share guarantees, a recently introduced fairness notion. Given a set of n agents and a set of goods, the maximin share of a single agent is the best that she can guarantee to herself, if she would be allowed to partition the goods in any way she prefers, into n bundles, and then receive her least desirable bundle. The objective then in our problem is to find a partition, so that each agent is guaranteed her maximin share. Our main result is a 2∕3-approximation, that runs in polynomial time for any number of agents, improving upon recent results in the literature.
Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, Amin Saberi
An Alternate Proof of the Algorithmic Lovász Local Lemma
Abstract
The algorithm for Lovász Local Lemma by Moser and Tardos gives a constructive way to prove the existence of combinatorial objects satisfying a system of constraints. We present an alternative probabilistic analysis of the algorithm that does not involve reconstructing the history of the algorithm. We apply our technique to improve the best known upper bound to acyclic chromatic index.
Ioannis Giotis, Lefteris Kirousis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos
Learning Game-Theoretic Equilibria Via Query Protocols
Abstract
Query complexity is a very widespread and recurring theme in the analysis of algorithms and computational complexity. Algorithms are assumed to have access to their input data via certain stylised queries, which impose a constraint on the way an algorithm can behave. In the context of computing equilibria of games, this is a relatively recent line of work, which we review here. The talk mostly focuses on the paper Fearnley et al. (Learning equilibria of games via payoff queries. In: Proceedings of the 14th ACM-EC, pp 397–414, 2013).
Paul W. Goldberg
The Lower Tail: Poisson Approximation Revisited
Abstract
The well-known Janson’s inequality gives Poisson-like upper bounds for the lower tail probability \(\mathbb{P}(X\leqslant (1-\varepsilon )\mathbb{E}X)\) when X is the sum of dependent indicator random variables of a special form. In joint work with Svante Janson we showed that, for large deviations, this inequality is optimal whenever X is approximately Poisson, i.e., when the dependencies are weak. For subgraph counts in random graphs, this, e.g., yields new lower tail estimates, extending earlier work (for the special case ɛ = 1) of Janson, Łuczak and Ruciński.
Svante Janson, Lutz Warnke
Population Protocols for Majority in Arbitrary Networks
Abstract
We study the problem of determining the majority type in an arbitrary connected network, each vertex of which has initially two possible types. The vertices may have a few additional possible states and can interact in pairs only if they share an edge. Any (population) protocol is required to stabilize in the initial majority. We first present and analyze a protocol with 4 states per vertex that always computes the initial majority value, under any fair scheduler.This protocol is optimal, in the sense that there does not exist any population protocol that always computes majority with fewer than 4 states per vertex. However, this does not rule out the existence of a protocol with 3 states per vertex that is correct with high probability (whp). To this end, we examine an elegant and very natural majority protocol with 3 states per vertex, introduced in Angluin et al. (Distrib Comput 21:87–102, 2008), where its performance has been analyzed for the clique graph. In particular, we study the performance of this protocol in arbitrary networks, under the probabilistic scheduler. We prove that, when the two initial states are put uniformly at random on the vertices, the protocol of Angluin et al. (Distrib Comput 21:87–102, 2008) converges to the initial majority with probability higher than the probability of converging to the initial minority. In contrast, we show that the resistance of the protocol to failure when the underlying graph is a clique causes the failure of the protocol in general graphs.
This abstract paper is based on our work which appeared in the Proceedings of the 41-st International Colloquium on Automata, Languages, and Programming (ICALP) in 2014.
George B. Mertzios, Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, Paul G. Spirakis
The Asymptotic Value in Finite Stochastic Games
Abstract
In 1976, Bewley and Kohlberg proved that the discounted values v λ of finite zero-sum stochastic games have a limit, as λ tends to 0, using the Tarski–Seidenberg elimination theorem from real algebraic geometry. This was a fundamental step in the development of the theory of stochastic games. The current paper provides a new and direct proof for this result, relying on the explicit description of asymptotically optimal strategies. Both approaches can be used to obtain the existence of the uniform value using the construction from Mertens and Neyman (1981).
Miquel Oliu-Barton
Almost All 5-Regular Graphs Have a 3-Flow
Abstract
Tutte conjectured in 1972 that every 4-edge connected graph has a nowhere-zero 3-flow. This is equivalent to every 5-regular 4-edge-connected graph having an edge orientation in which every out-degree is either 1 or 4. We show that this property holds asymptotically almost surely for random 5-regular graphs.
Paweł Prałat, Nick Wormald

Quantitative Finance

Frontmatter
On the Short-Time Behaviour of the Implied Volatility Skew for Spread Options and Applications
Abstract
By means of Malliavin calculus, we construct a modification of the classical Kirk’s formula for spread option prices. This new approximation is easy to compute and increases the accuracy of Kirk’s formula, specially when the correlation parameter is near to one.
Elisa Alòs, Jorge A. León
An Alternative to CARMA Models via Iterations of Ornstein–Uhlenbeck Processes
Abstract
We present a new construction of continuous ARMA processes based on iterating an Ornstein–Uhlenbeck operator \(\mathcal{O}\mathcal{U}_{\kappa }\) that maps a random variable y(t) onto \(\mathcal{O}\mathcal{U}_{\kappa }y(t) =\int _{ -\infty }^{t}\mathrm{e}^{-\kappa (t-s)}dy(s)\). This construction resembles the procedure to build an AR( p) from an AR(1) and derives in a parsimonious model for continuous autoregression, with fewer parameters to compute than the known CARMA obtained as a solution of a system of stochastic differential equations. We show properties of this operator, give state space representation of the iterated Ornstein–Uhlenbeck process and show how to estimate the parameters of the model.
Argimiro Arratia, Alejandra Cabaña, Enrique M. Cabaña
Euler–Poisson Schemes for Lévy Processes
Abstract
In this note we will contextualize the recently established Wiener–Hopf Monte Carlo (WHMC) simulation technique for Lévy processes from Kuznetsov et al. (Ann Appl Probab 21(6):2171–2190, 2011), into a more general framework allowing us to use the same technique in a larger set of problems. We will briefly show how the scheme can be used to approximate Lévy driven SDEs or how to approximate different types of path dependent quantities. In a way, the present note summarizes and connects a set of results contained in Ferreiro-Castilla et al. (Stochastic Process Appl 124(2):985–1010, 2014; J Appl Probab 52(1):129–148, 2015; J Appl Probab 53(1):262–278, 2016); therefore we intentionally leave most of the technicalities aside for this note.
Albert Ferreiro-Castilla
On Time-Consistent Portfolios with Time-Inconsistent Preferences
Abstract
Time-consistent equilibria are studied for intertemporal problems with general discount functions. An investment consumption model with life insurance is analyzed. Equilibrium strategies are derived for two classes of discount functions: time-distance discounting and heterogeneous discounting.
Jesús Marín-Solano
A Generic Decomposition Formula for Pricing Vanilla Options Under Stochastic Volatility Models
Abstract
We obtain a decomposition of the call option price for a very general stochastic volatility diffusion model, extending a previous decomposition formula for the Heston model. We realize that a new term arises when the stock price does not follow an exponential model. The techniques used for this purpose are non-anticipative. In particular, we also see that equivalent results can be obtained by using Functional Itô Calculus. Using the same generalizing ideas, we also extend to non-exponential models the alternative call option price decomposition formula written in terms of the Malliavin derivative of the volatility process. Finally, we give a general expression for the derivative of the implied volatility under both the anticipative and the non-anticipative cases.
Raúl Merino, Josep Vives
A Highly Efficient Pricing Method for European-Style Options Based on Shannon Wavelets
Abstract
In the search for robust, accurate and highly efficient financial option valuation techniques, we present here the SWIFT method (Shannon Wavelets Inverse Fourier Technique), based on Shannon wavelets. SWIFT comes with control over approximation errors made by means of sharp quantitative error bounds. The nature of the local Shannon wavelets basis enables us to adaptively determine the proper size of the computational interval. Numerical experiments on European-style options confirm the bounds, robustness and efficiency.
Luis Ortiz-Gracia, Cornelis W. Oosterlee
A New Pricing Measure in the Barndorff-Nielsen–Shephard Model for Commodity Markets
Abstract
For a commodity spot price dynamics given by an Ornstein–Uhlenbeck process with Barndorff-Nielsen–Shephard stochastic volatility, we price forward contracts using a new class of pricing measures, extending the classical Esscher transform, that simultaneously allow for change of level and speed in the mean reversion of both the price and the volatility.
Salvador Ortiz-Latorre
Metadata
Title
Extended Abstracts Summer 2015
Editors
Josep Díaz
Lefteris Kirousis
Luis Ortiz-Gracia
Maria Serna
Copyright Year
2017
Electronic ISBN
978-3-319-51753-7
Print ISBN
978-3-319-51752-0
DOI
https://doi.org/10.1007/978-3-319-51753-7

Premium Partner

    Image Credits