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

János Flesch

János Flesch appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCComputer Science and Game Theorymath.PRecon.THMachine Learningmath.CAmath.GNmath.LOmath.MG

Catalog footprint

What is connected

11works
9topics
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

11 published item(s)

preprint2022arXiv

Absorbing Blackwell Games

It was shown in Flesch and Solan (2022) with a rather involved proof that all two-player stochastic games with finite state and action spaces and shift-invariant payoffs admit an $ε$-equilibrium, for every $ε>0$. Their proof also holds for two-player absorbing games with tail-measurable payoffs. In this paper we provide a simpler proof for the existence of $ε$-equilibrium in two-player absorbing games with tail-measurable payoffs, by combining recent mathematical tools for such payoff functions with classical tools for absorbing games.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Regularity of the minmax value and equilibria in multiplayer Blackwell games

A real-valued function $φ$ that is defined over all Borel sets of a topological space is \emph{regular} if for every Borel set $W$, $φ(W)$ is the supremum of $φ(C)$, over all closed sets $C$ that are contained in $W$, and the infimum of $φ(O)$, over all open sets $O$ that contain $W$. We study Blackwell games with finitely many players. We show that when each player has a countable set of actions and the objective of a certain player is represented by a Borel winning set, that player's minmax value is regular. We then use the regularity of the minmax value to establish the existence of $\varepsilon$-equilibria in two distinct classes of Blackwell games. One is the class of $n$-player Blackwell games where each player has a finite action space and an analytic winning set, and the sum of the minmax values over the players exceeds $n-1$. The other class is that of Blackwell games with bounded upper semi-analytic payoff functions, history-independent finite action spaces, and history-independent minmax values. For the latter class, we obtain a characterization of the set of equilibrium payoffs.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Repeated Games with Tail-Measurable Payoffs

We study multiplayer Blackwell games, which are repeated games where the payoff of each player is a bounded and Borel-measurable function of the infinite stream of actions played by the players during the game. These games are an extension of the two-player perfect-information games studied by David Gale and Frank Stewart (1953). Recently, various new ideas have been discovered to study Blackwell games. In this paper, we give an overview of these ideas by proving, in four different ways, that Blackwell games with a finite number of players, finite action sets, and tail-measurable payoffs admit an $\varepsilon$-equilibrium, for all $\varepsilon>0$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Stochastic Games with General Payoff Functions

We consider multiplayer stochastic games in which the payoff of each player is a bounded and Borel-measurable function of the infinite play. By using a generalization of the technique of Martin (1998) and Maitra and Sudderth (1998), we show four different existence results. In each stochastic game, it holds for every $ε>0$ that (i) each player has a strategy that guarantees in each subgame that this player's payoff is at least her maxmin value up to $ε$, (ii) there exists a strategy profile under which in each subgame each player's payoff is at least her minmax value up to $ε$, (iii) the game admits an extensive-form correlated $ε$-equilibrium, and (iv) there exists a subgame that admits an $ε$-equilibrium.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A competitive search game with a moving target

We introduce a discrete-time search game, in which two players compete to find an object first. The object moves according to a time-varying Markov chain on finitely many states. The players know the Markov chain and the initial probability distribution of the object, but do not observe the current state of the object. The players are active in turns. The active player chooses a state, and this choice is observed by the other player. If the object is in the chosen state, this player wins and the game ends. Otherwise, the object moves according to the Markov chain and the game continues at the next period. We show that this game admits a value, and for any error-term $\veps>0$, each player has a pure (subgame-perfect) $\veps$-optimal strategy. Interestingly, a 0-optimal strategy does not always exist. The $\veps$-optimal strategies are robust in the sense that they are $2\veps$-optimal on all finite but sufficiently long horizons, and also $2\veps$-optimal in the discounted version of the game provided that the discount factor is close to 1. We derive results on the analytic and structural properties of the value and the $\veps$-optimal strategies. Moreover, we examine the performance of the finite truncation strategies, which are easy to calculate and to implement. We devote special attention to the important time-homogeneous case, where additional results hold.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Incentive compatibility in sender-receiver stopping games

We introduce a model of sender-receiver stopping games, where the state of the world follows an iid--process throughout the game. At each period, the sender observes the current state, and sends a message to the receiver, suggesting either to stop or to continue. The receiver, only seeing the message but not the state, decides either to stop the game, or to continue which takes the game to the next period. The payoff to each player is a function of the state when the receiver quits, with higher states leading to better payoffs. The horizon of the game can be finite or infinite. We prove existence and uniqueness of responsive (i.e. non-babbling) Perfect Bayesian Equilibrium (PBE) under mild conditions on the game primitives in the case where the players are sufficiently patient. The responsive PBE has a remarkably simple structure, which builds on the identification of an easy-to-implement and compute class of threshold strategies for the sender. With the help of these threshold strategies, we derive simple expressions describing this PBE. It turns out that in this PBE the receiver obediently follows the recommendations of the sender. Hence, surprisingly, the sender alone plays the decisive role, and regardless of the payoff function of the receiver the sender always obtains the best possible payoff for himself.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Search for a moving target in a competitive environment

We consider a discrete-time dynamic search game in which a number of players compete to find an invisible object that is moving according to a time-varying Markov chain. We examine the subgame perfect equilibria of these games. The main result of the paper is that the set of subgame perfect equilibria is exactly the set of greedy strategy profiles, i.e. those strategy profiles in which the players always choose an action that maximizes their probability of immediately finding the object. We discuss various variations and extensions of the model.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The doubling metric and doubling measures

We introduce the so--called doubling metric on the collection of non--empty bounded open subsets of a metric space. Given a subset $U$ of a metric space $X$, the predecessor $U_{*}$ of $U$ is defined by doubling the radii of all open balls contained inside $U$, and taking their union. If $U$ is open, the predecessor of $U$ is an open set containing $U$. The directed doubling distance between $U$ and another subset $V$ is the number of times that the predecessor operation needs to be applied to $U$ to obtain a set that contains $V$. Finally, the doubling distance between $U$ and $V$ is the maximum of the directed distance between $U$ and $V$ and the directed distance between $V$ and $U$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Approachability of convex sets in generalized quitting games

We consider Blackwell approachability, a very powerful and geometric tool in game theory, used for example to design strategies of the uninformed player in repeated games with incomplete information. We extend this theory to "generalized quitting games" , a class of repeated stochastic games in which each player may have quitting actions, such as the Big-Match. We provide three simple geometric and strongly related conditions for the weak approachability of a convex target set. The first is sufficient: it guarantees that, for any fixed horizon, a player has a strategy ensuring that the expected time-average payoff vector converges to the target set as horizon goes to infinity. The third is necessary: if it is not satisfied, the opponent can weakly exclude the target set. In the special case where only the approaching player can quit the game (Big-Match of type I), the three conditions are equivalent and coincide with Blackwell's condition. Consequently, we obtain a full characterization and prove that the game is weakly determined-every convex set is either weakly approachable or weakly excludable. In games where only the opponent can quit (Big-Match of type II), none of our conditions is both sufficient and necessary for weak approachability. We provide a continuous time sufficient condition using techniques coming from differential games, and show its usefulness in practice, in the spirit of Vieille's seminal work for weak approachability.Finally, we study uniform approachability where the strategy should not depend on the horizon and demonstrate that, in contrast with classical Blackwell approacha-bility for convex sets, weak approachability does not imply uniform approachability.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Existence of Secure Equilibrium in Multi-Player Games with Perfect Information

Secure equilibrium is a refinement of Nash equilibrium, which provides some security to the players against deviations when a player changes his strategy to another best response strategy. The concept of secure equilibrium is specifically developed for assume-guarantee synthesis and has already been applied in this context. Yet, not much is known about its existence in games with more than two players. In this paper, we establish the existence of secure equilibrium in two classes of multi-player perfect information turn-based games: (1) in games with possibly probabilistic transitions, having countable state and finite action spaces and bounded and continuous payoff functions, and (2) in games with only deterministic transitions, having arbitrary state and action spaces and Borel payoff functions with a finite range (in particular, qualitative Borel payoff functions). We show that these results apply to several types of games studied in the literature.

0 citations0 reviewsNo code linkedOpen access