Search

We present a mathematical formulation of liquidity provision in decentralized exchanges. We focus on constant function market makers of utility indifference type, which include constant product market makers with concentrated liquidity as a special case. First, we examine no-arbitrage conditions for a liquidity pool and compute an optimal arbitrage strategy when there is an external liquid market. Second, we show that liquidity provision suffers from impermanent loss unless a transaction fee is levied under the general framework with concentrated liquidity. Third, we establish the well-definedness of arbitrage-free reserve processes of a liquidity pool in continuous-time and show that there is no loss-versus-rebalancing under a nonzero fee if the external market price is continuous. We then argue that liquidity provision by multiple liquidity providers can be understood as liquidity provision by a representative liquidity provider, meaning that the analysis boils down to that for a single liquidity provider. Last, but not least, we give an answer to the fundamental question in which sense the very construction of constant function market makers with concentrated liquidity in the popular platform Uniswap v3 is optimal.

This study proposes a simple procedure to compute Efficient Pseudo Likelihood (EPL) estimator proposed by Dearing and Blevins (2024) for estimating dynamic discrete games, without computing Jacobians of equilibrium constraints. EPL estimator is efficient, convergent, and computationally fast. However, the original algorithm requires deriving and coding the Jacobians, which are cumbersome and prone to coding mistakes especially when considering complicated models. The current study proposes to avoid the computation of Jacobians by combining the ideas of numerical derivatives (for computing Jacobian-vector products) and the Krylov method (for solving linear equations). It shows good computational performance of the proposed method by numerical experiments.

Procedural video understanding is gaining attention in the vision and language community. Deep learning-based video analysis requires extensive data. Consequently, existing works often use web videos as training resources, making it challenging to query instructional contents from raw video observations. To address this issue, we propose a new dataset, COM Kitchens. The dataset consists of unedited overhead-view videos captured by smartphones, in which participants performed food preparation based on given recipes. Fixed-viewpoint video datasets often lack environmental diversity due to high camera setup costs. We used modern wide-angle smartphone lenses to cover cooking counters from sink to cooktop in an overhead view, capturing activity without in-person assistance. With this setup, we collected a diverse dataset by distributing smartphones to participants. With this dataset, we propose the novel video-to-text retrieval task Online Recipe Retrieval (OnRR) and new video captioning domain Dense Video Captioning on unedited Overhead-View videos (DVC-OV). Our experiments verified the capabilities and limitations of current web-video-based SOTA methods in handling these tasks., Comment: ECCV2024 accepted

In the minimum spanning tree (MST) interdiction problem, we are given a graph $G=(V,E)$ with edge weights, and want to find some $X\subseteq E$ satisfying a knapsack constraint such that the MST weight in $(V,E\setminus X)$ is maximized. Since MSTs of $G$ are the minimum weight bases in the graphic matroid of $G$, this problem is a special case of matroid interdiction on a matroid $M=(E,\mathcal{I})$, in which the objective is instead to maximize the minimum weight of a basis of $M$ which is disjoint from $X$. By reduction from 0-1 knapsack, matroid interdiction is NP-complete, even for uniform matroids. We develop a new exact algorithm to solve the matroid interdiction problem. One of the key components of our algorithm is a dynamic programming upper bound which only requires that a simpler discrete derivative problem can be calculated/approximated for the given matroid. Our exact algorithm then uses this bound within a custom branch-and-bound algorithm. For different matroids, we show how this discrete derivative can be calculated/approximated. In particular, for partition matroids, this yields a pseudopolynomial time algorithm. For graphic matroids, an approximation can be obtained by solving a sequence of minimum cut problems, which we apply to the MST interdiction problem. The running time of our algorithm is asymptotically faster than the best known MST interdiction algorithm, up to polylog factors. Furthermore, our algorithm achieves state-of-the-art computational performance: we solved all available instances from the literature, and in many cases reduced the best running time from hours to seconds., Comment: 29 pages, 2 figures

This study investigates computationally efficient algorithms for solving discrete-time infinite-horizon single-agent/multi-agent dynamic models with continuous actions. It shows that we can easily reduce the computational costs by slightly changing basic algorithms using value functions, such as the Value Function Iteration (VFI) and the Policy Iteration (PI). The PI method with a Krylov iterative method (GMRES), which can be easily implemented using built-in packages, works much better than VFI-based algorithms even when considering continuous state models. Concerning the VFI algorithm, we can largely speed up the convergence by introducing acceleration methods of fixed-point iterations. The current study also proposes the VF-PGI-Spectral (Value Function-Policy Gradient Iteration Spectral) algorithm, which is a slight modification of the VFI. It shows numerical results where the VF-PGI-Spectral performs much better than the VFI- and PI-based algorithms especially in multi-agent dynamic games. Finally, it shows that using relative value functions further reduces the computational cost of these methods.

Economic experiments offer a controlled setting for researchers to observe human decision-making and test diverse theories and hypotheses; however, substantial costs and efforts are incurred to gather many individuals as experimental participants. To address this, with the development of large language models (LLMs), some researchers have recently attempted to develop simulated economic experiments using LLMs-driven agents, called generative agents. If generative agents can replicate human-like decision-making in economic experiments, the cost problem of economic experiments can be alleviated. However, such a simulation framework has not been yet established. Considering the previous research and the current evolutionary stage of LLMs, this study focuses on the reasoning ability of generative agents as a key factor toward establishing a framework for such a new methodology. A multi-agent simulation, designed to improve the reasoning ability of generative agents through prompting methods, was developed to reproduce the result of an actual economic experiment on the ultimatum game. The results demonstrated that the higher the reasoning ability of the agents, the closer the results were to the theoretical solution than to the real experimental result. The results also suggest that setting the personas of the generative agents may be important for reproducing the results of real economic experiments. These findings are valuable for the future definition of a framework for replacing human participants with generative agents in economic experiments when LLMs are further developed., Comment: 10 pages, 5 figures

Achieving maximum electron beam brightness in photoinjectors requires detailed control of the 3D bunch shape and precise tuning of the beam focusing. Even in state-of-the-art designs, slice emittance growth due to nonlinear space charge forces and partial nonlaminarity often remains non-negligible. In this work we introduce a new means to linearize the transverse slice phase space: a sacrificial portion of the bunch's own charge distribution, formed into a wavebroken shock front by highly nonlinear space charge forces within the gun, whose downstream purpose is to dynamically linearize the desired bunch core. We show that linearization of an appropriately prepared bunch can be achieved via strongly nonlaminar focusing of the sacrificial shock front, while the inner core focuses laminarly. This leads to a natural spatial separation of the two distributions: a dense core surrounded by a diffuse halo of sacrificial charge that can be collimated. Multi-objective genetic algorithm optimizations of the ultra-compact x-ray free electron laser (UCXFEL) injector employ this concept, and we interpret it with an analytic model that agrees well with the simulations. In simulation we demonstrate a final bunch charge of 100 pC, peak current $\sim 30$ A, and a sacrificial charge of 150 pC (250 pC total emitted from cathode) with normalized emittance growth of $<20$ nm-rad due to space charge. This implies a maximum achievable brightness approximately an order of magnitude greater than existing FEL injector designs., Comment: 11 pages, 11 figures, submitted to PRAB

This study investigates computationally efficient inner-loop algorithms for estimating static/dynamic BLP models. It provides the following ideas to reduce the number of inner-loop iterations: (1). Add a term concerning the outside option share in the BLP contraction mapping; (2). Analytically represent mean product utilities as a function of value functions and solve for the value functions (for dynamic BLP); (3). Combine an acceleration method of fixed point iterations, especially Anderson acceleration. They are independent and easy to implement. This study shows good performance of these methods by numerical experiments.

Prior work on multilingual sentence embedding has demonstrated that the efficient use of natural language inference (NLI) data to build high-performance models can outperform conventional methods. However, the potential benefits from the recent ``exponential'' growth of language models with billions of parameters have not yet been fully explored. In this paper, we introduce Multilingual Sentence T5 (m-ST5), as a larger model of NLI-based multilingual sentence embedding, by extending Sentence T5, an existing monolingual model. By employing the low-rank adaptation (LoRA) technique, we have achieved a successful scaling of the model's size to 5.7 billion parameters. We conducted experiments to evaluate the performance of sentence embedding and verified that the method outperforms the NLI-based prior approach. Furthermore, we also have confirmed a positive correlation between the size of the model and its performance. It was particularly noteworthy that languages with fewer resources or those with less linguistic similarity to English benefited more from the parameter increase. Our model is available at https://huggingface.co/pkshatech/m-ST5., Comment: Accepted in LREC-COLING 2024

We introduce an optimization-based reconstruction attack capable of completely or near-completely reconstructing a dataset utilized for training a random forest. Notably, our approach relies solely on information readily available in commonly used libraries such as scikit-learn. To achieve this, we formulate the reconstruction problem as a combinatorial problem under a maximum likelihood objective. We demonstrate that this problem is NP-hard, though solvable at scale using constraint programming -- an approach rooted in constraint propagation and solution-domain reduction. Through an extensive computational investigation, we demonstrate that random forests trained without bootstrap aggregation but with feature randomization are susceptible to a complete reconstruction. This holds true even with a small number of trees. Even with bootstrap aggregation, the majority of the data can also be reconstructed. These findings underscore a critical vulnerability inherent in widely adopted ensemble methods, warranting attention and mitigation. Although the potential for such reconstruction attacks has been discussed in privacy research, our study provides clear empirical evidence of their practicability.

High-throughput screening using cell images is an efficient method for screening new candidates for pharmaceutical drugs. To complete the screening process, it is essential to have an efficient process for analyzing cell images. This paper presents a new method for efficiently tracking cells and quantitatively detecting the signal ratio between cytoplasm and nuclei. Existing methods include those that use image processing techniques and those that utilize artificial intelligence (AI). However, these methods do not consider the correspondence of cells between images, or require a significant amount of new learning data to train AI. Therefore, our method uses automatic thresholding and labeling algorithms to compare the position of each cell between images, and continuously measure and analyze the signal ratio of cells. This paper describes the algorithm of our method. Using the method, we experimented to investigate the effect of the number of opening and closing operations during the binarization process on the tracking of the cells. Through the experiment, we determined the appropriate number of opening and closing processes., Comment: 5 pages, 7 figures

We study backward stochastic difference equations (BS{\Delta}E) driven by a d-dimensional stochastic process on a lattice whose increments have only d + 1 possible values that generates the lattice. Regarding the driving process as a d dimensional asset price process, we give applications to an optimal investment problem and a market equilibrium analysis, where utility functionals are defined through BS{\Delta}E.

This paper shows the universal representations of symmetric functions with multidimensional variable-size variables, which help assessing the justification of approximation methods aggregating the information of each variable by moments. It then discusses how the results give insights into game theoretic applications, including two-step policy function estimation, Moment-based Markov Equilibrium (MME), and aggregative games. Regarding policy function estimations, it is justifiable to estimate a common policy function as a function of own firm's states and the sums of polynomial terms (moments) of competitors' states under some conditions, regardless of the number of firms in each market, as long as the number of moments is sufficiently large. Concerning the MME, this study shows that MME is equivalent to the Markov Perfect Equilibrium if the number of moments reaches a certain level and regularity conditions are satisfied. Regarding aggregative games, we can easily show that any games satisfying a condition of symmetry and continuity of payoff functions can be represented as multidimensional generalized aggregative, which introduces multidimensional aggregates in the generalized (fully) aggregative games previous studies have intensively studied.

A constant weight asset allocation is a popular investment strategy and is optimal under a suitable continuous model. We study the tracking error for the target continuous rebalancing strategy by a feasible discrete-in-time rebalancing under a general multi-dimensional Brownian semimartingale model of asset prices. In a high-frequency asymptotic framework, we derive an asymptotically efficient sequence of simple predictable strategies.

This paper introduces the notion of a Galois point for a finite graph, using the theory of linear systems of divisors for graphs discovered by Baker and Norine. We present a new characterization of complete graphs in terms of Galois points., Comment: 13 pages, 2 figures

A connection between Galois points of an algebraic curve and those of a quotient curve is presented; in particular, the notion of a descendant of algebraic curves admitting two Galois points is introduced. It is shown that all descendants of a Fermat curve are Fermat curves; in particular, a Fermat curve does not have a descendant if and only if the degree is a prime., Comment: 9 pages

We study the limit of the joint distribution of a multidimensional Generalized Tempered Stable (GTS) process and its quadratic covariation process when the stable index tends to two. Under a proper scaling, the GTS processes converges to a Brownian motion that is a stable process with stable index two. We renormalize their quadratic covariation processes so that they have a nondegenerate limit distribution. We show that the limit is a stable process with stable index one and is independent of the limit Brownian motion of the GTS processes. In addition, we apply this convergence result to finance. By using the scaled GTS process defined above, we construct a pure jump asset price model approaching to the Black-Scholes model. To evaluate how $\alpha$-stable jumps affect the implied volatility, we obtain the asymptotic expansion of the at-the-money implied volatility skew when the model approaches to the Black-Scholes model., Comment: 25 pages