An official website of the United States government
Abstract In a Mean Field Game (MFG) each decision maker cares about the cross sectional distribution of the state and the dynamics of the distribution is generated by the agents’ optimal decisions. We prove the uniqueness of the equilibrium in a class of MFG where the decision maker controls the state at optimally chosen times. This setup accommodates several problems featuring non-convex adjustment costs, and complements the well known drift-control case studied by Lasry–Lions. Examples of such problems are described by Caballero and Engel in several papers, which introduce the concept of the generalized hazard function of adjustment. We extend the analysis to a general “impulse control problem” by introducing the concept of the “Impulse Hamiltonian”. Under the monotonicity assumption (a form of strategic substitutability), we establish the uniqueness of equilibrium. In this context, the Impulse Hamiltonian and its derivative play a similar role to the classical Hamiltonian that arises in the drift-control case.
more »
« less
Maker Breaker on Digraphs
We study two biased Maker-Breaker games played on the complete digraph $$\vec{K}_n$$. In the strong connectivity game, Maker wants to build a strongly connected subgraph. We determine the asymptotic optimal bias for this game viz. $$\frac{n}{\log n}$$. In the Hamiltonian game, Maker wants to build a Hamiltonian subgraph. We determine the asymptotic optimal bias for this game up to a constant factor.
more »
« less
- Award ID(s):
- 1952285
- PAR ID:
- 10320467
- Date Published:
- Journal Name:
- Journal of graph theory
- Volume:
- 98
- ISSN:
- 0364-9024
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
An ordered graph is a graph with a linear ordering on its vertices. The online Ramsey game for ordered graphs $$G$$ and $$H$$ is played on an infinite sequence of vertices; on each turn, Builder draws an edge between two vertices, and Painter colors it red or blue. Builder tries to create a red $$G$$ or a blue $$H$$ as quickly as possible, while Painter wants the opposite. The online ordered Ramsey number $$r_o(G,H)$$ is the number of turns the game lasts with optimal play. In this paper, we consider the behavior of $$r_o(G,P_n)$$ for fixed $$G$$, where $$P_n$$ is the monotone ordered path. We prove an $$O(n \log n)$$ bound on $$r_o(G,P_n)$$ for all $$G$$ and an $O(n)$ bound when $$G$$ is $$3$$-ichromatic; we partially classify graphs $$G$$ with $$r_o(G,P_n) = n + O(1)$$. Many of these results extend to $$r_o(G,C_n)$$, where $$C_n$$ is an ordered cycle obtained from $$P_n$$ by adding one edge.more » « less
-
Censor-Hillel, Keren; Grandoni, Fabrizio; Ouaknine, Joel; Puppis, Gabriele (Ed.)We study the classic problem of subgraph counting, where we wish to determine the number of occurrences of a fixed pattern graph H in an input graph G of n vertices. Our focus is on bounded degeneracy inputs, a rich family of graph classes that also characterizes real-world massive networks. Building on the seminal techniques introduced by Chiba-Nishizeki (SICOMP 1985), a recent line of work has built subgraph counting algorithms for bounded degeneracy graphs. Assuming fine-grained complexity conjectures, there is a complete characterization of patterns H for which linear time subgraph counting is possible. For every r ≥ 6, there exists an H with r vertices that cannot be counted in linear time. In this paper, we initiate a study of subquadratic algorithms for subgraph counting on bounded degeneracy graphs. We prove that when H has at most 9 vertices, subgraph counting can be done in Õ(n^{5/3}) time. As a secondary result, we give improved algorithms for counting cycles of length at most 10. Previously, no subquadratic algorithms were known for the above problems on bounded degeneracy graphs. Our main conceptual contribution is a framework that reduces subgraph counting in bounded degeneracy graphs to counting smaller hypergraphs in arbitrary graphs. We believe that our results will help build a general theory of subgraph counting for bounded degeneracy graphs.more » « less
-
A Brownian bridge is a continuous random walk conditioned to end in a given region by adding an effective drift to guide paths toward the desired region of phase space. This idea has many applications in chemical science where one wants to control the endpoint of a stochastic process—e.g., polymer physics, chemical reaction pathways, heat/mass transfer, and Brownian dynamics simulations. Despite its broad applicability, the biggest limitation of the Brownian bridge technique is that it is often difficult to determine the effective drift as it comes from a solution of a Backward Fokker–Planck (BFP) equation that is infeasible to compute for complex or high-dimensional systems. This paper introduces a fast approximation method to generate a Brownian bridge process without solving the BFP equation explicitly. Specifically, this paper uses the asymptotic properties of the BFP equation to generate an approximate drift and determine ways to correct (i.e., re-weight) any errors incurred from this approximation. Because such a procedure avoids the solution of the BFP equation, we show that it drastically accelerates the generation of conditioned random walks. We also show that this approach offers reasonable improvement compared to other sampling approaches using simple bias potentials.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1002/jgt.22719
