BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Michał Misiurewicz

Michał Misiurewicz appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.DSComputer Science and Game Theorynlin.CDphysics.soc-phecon.GNMachine Learningq-fin.EC

Catalog footprint

What is connected

9works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

preprint2021arXiv

Follow-the-Regularized-Leader Routes to Chaos in Routing Games

We study the emergence of chaotic behavior of Follow-the-Regularized Leader (FoReL) dynamics in games. We focus on the effects of increasing the population size or the scale of costs in congestion games, and generalize recent results on unstable, chaotic behaviors in the Multiplicative Weights Update dynamics to a much larger class of FoReL dynamics. We establish that, even in simple linear non-atomic congestion games with two parallel links and any fixed learning rate, unless the game is fully symmetric, increasing the population size or the scale of costs causes learning dynamics to become unstable and eventually chaotic, in the sense of Li-Yorke and positive topological entropy. Furthermore, we show the existence of novel non-standard phenomena such as the coexistence of stable Nash equilibria and chaos in the same game. We also observe the simultaneous creation of a chaotic attractor as another chaotic attractor gets destroyed. Lastly, although FoReL dynamics can be strange and non-equilibrating, we prove that the time average still converges to an exact equilibrium for any choice of learning rate and any scale of costs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A fresh look at the notion of normality

Let $G$ be a countable cancellative amenable semigroup and let $(F_n)$ be a (left) Følner sequence in $G$. We introduce the notion of an $(F_n)$-normal element of $\{0,1\}^G$. When $G$ = $(\mathbb N,+)$ and $F_n = \{1,2,...,n\}$, the $(F_n)$-normality coincides with the classical notion. We prove that: $\bullet$ If $(F_n)$ is a Følner sequence in $G$, such that for every $α\in(0,1)$ we have $\sum_n α^{|F_n|}<\infty$, then almost every $x\in\{0,1\}^G$ is $(F_n)$-normal. $\bullet$ For any Følner sequence $(F_n)$ in $G$, there exists an Cham\-per\-nowne-like $(F_n)$-normal set. $\bullet$ There is a natural class of "nice" Følner sequences in $(\mathbb N,\times)$. There exists a Champernowne-like set which is $(F_n)$-normal for every nice Følner \sq. $\bullet$ Let $A\subset\mathbb N$ be a classical normal set. Then, for any Følner sequence $(K_n)$ in $(\mathbb N,\times)$ there exists a set $E$ of $(K_n)$-density $1$, such that for any finite subset $\{n_1,n_2,\dots,n_k\}\subset E$, the intersection $A/{n_1}\cap A/{n_2}\cap\ldots\cap A/{n_k}$ has positive upper density in $(\mathbb N,+)$. As a consequence, $A$ contains arbitrarily long geometric progressions, and, more generally, arbitrarily long "geo-arithmetic" configurations of the form $\{a(b+ic)^j,0\le i,j\le k\}$. $\bullet$ For any Følner \sq\ $(F_n)$ in $(\mathbb N,+)$ there exist uncountably many $(F_n)$-normal Liouville numbers. $\bullet$ For any nice Følner sequence $(F_n)$ in $(\mathbb N,\times)$ there exist uncountably many $(F_n)$-normal Liouville numbers.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Coarse entropy

Coarse geometry studies metric spaces on the large scale. Our goal here is to study dynamics from a coarse point of view. To this end we introduce a coarse version of topological entropy, suitable for unbounded metric spaces, consistent with the coarse perspective on such spaces. As is the case with the usual topological entropy, the coarse entropy measures the divergence of orbits. Following Bowen's ideas, we use $(n,\varepsilon)$-separated or $(n,\varepsilon)$-spanning sets. However, we have to let $\varepsilon$ go to infinity rather than to zero.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Flexibility of entropies for piecewise expanding unimodal maps

We investigate the flexibility of the entropy (topological and metric) for the class of piecewise expanding unimodal maps. We show that the only restrictions for the values of the topological and metric entropies in this class are that both are positive, the topological entropy is at most $\log 2$, and by the Variational Principle, the metric entropy is not larger than the topological entropy. In order to have a better control on the metric entropy, we work mainly with topologically mixing piecewise expanding skew tent maps, for which there are only 2 different slopes. For those maps, there is an additional restriction that the topological entropy is larger than $\frac{1}{2}\log2$. We also make the interesting observation that for skew tent maps the sum of reciprocals of derivatives of all iterates of the map at the critical value is zero. It is a generalization and a different interpretation of the Milnor-Thurston formula connecting the topological entropy and the kneading determinant for unimodal maps.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

The route to chaos in routing games: When is Price of Anarchy too optimistic?

Routing games are amongst the most studied classes of games. Their two most well-known properties are that learning dynamics converge to equilibria and that all equilibria are approximately optimal. In this work, we perform a stress test for these classic results by studying the ubiquitous dynamics, Multiplicative Weights Update, in different classes of congestion games, uncovering intricate non-equilibrium phenomena. As the system demand increases, the learning dynamics go through period-doubling bifurcations, leading to instabilities, chaos and large inefficiencies even in the simplest case of non-atomic routing games with two paths of linear cost where the Price of Anarchy is equal to one. Starting with this simple class, we show that every system has a carrying capacity, above which it becomes unstable. If the equilibrium flow is a symmetric $50-50\%$ split, the system exhibits one period-doubling bifurcation. A single periodic attractor of period two replaces the attracting fixed point. Although the Price of Anarchy is equal to one, in the large population limit the time-average social cost for all but a zero measure set of initial conditions converges to its worst possible value. For asymmetric equilibrium flows, increasing the demand eventually forces the system into Li-Yorke chaos with positive topological entropy and periodic orbits of all possible periods. Remarkably, in all non-equilibrating regimes, the time-average flows on the paths converge exactly to the equilibrium flows, a property akin to no-regret learning in zero-sum games. These results are robust. We extend them to routing games with arbitrarily many strategies, polynomial cost functions, non-atomic as well as atomic routing games and heteregenous users. Our results are also applicable to any sequence of shrinking learning rates, e.g., $1/\sqrt{T}$, by allowing for a dynamically increasing population size.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Forcing among patterns with no block structure

Define the following order among all natural numbers except for 2 and 1: \[ 4\gg 6\gg 3\gg \dots \gg 4n\gg 4n+2\gg 2n+1\gg 4n+4\gg\dots \] Let $f$ be a continuous interval map. We show that if $m\gg s$ and $f$ has a cycle with no division (no block structure) of period $m$ then $f$ has also a cycle with no division (no block structure) of period $s$. We describe possible sets of periods of cycles of $f$ with no division and no block structure.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Semiconjugacy to a map of a constant slope

It is well known that a continuous piecewise monotone interval map with positive topological entropy is semiconjugate to a map of a constant slope and the same entropy, and if it is additionally transitive then this semiconjugacy is actually a conjugacy. We generalize this result to piecewise continuous piecewise monotone interval maps, and as a consequence, get it also for piecewise monotone graph maps. We show that assigning to a continuous transitive piecewise monotone map of positive entropy a map of constant slope conjugate to it defines an operator, and show that this operator is not continuous.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Random interval homeomorphisms

We investigate homeomorphisms of a compact interval, applied randomly. We consider this system as a skew product with the two-sided Bernoulli shift in the base. If on the open interval there is a metric in which almost all maps are contractions, then (with mild additional assumptions) there exists a global pullback attractor, which is a graph of a function from the base to the fiber. It is also a forward attractor. However, the value of this function depends only on the past, so when we take the one-sided shift in the base, it disappears. We illustrate those phenomena on an example, where there are two piecewise linear homeomorphisms, one moving points to the right and the other one to the left.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Skew Product Attractors and concavity

We propose an approach to the attractors of skew products that tries to avoid unnecessary structures on the base space and rejects the assumption on the invariance of an attractor. When nonivertible maps in the base are allowed, one can encounter the mystery of the vanishing attractor. In the second part of the paper, we show that if the fiber maps are concave interval maps then contraction in the fibers does not depend on the map in the base.

0 citations0 reviewsNo code linkedOpen access