Consider a platform where independent agents arrive at random times and need to be matched into pairs, eventually after waiting for some time. This, for example, models job markets, gaming platforms, kidney exchange programs, etc. The platform decides how to match agents together while optimizing two conflicting objectives: the quality of the matching produced, and the total waiting time of the agents. This can be modeled as an online problem called Min-cost Perfect Matching with Delays (MPMD). In the case when agents arrive in an adversarial order, no online algorithm can achieve a constant-competitive ratio. In this paper, we study a realistic case where agents’ arrival times follow some stochastic assumptions, and we present two matching mechanisms, which give constant-competitive solutions. The first one is a simple greedy algorithm in which agents act in a distributed manner requiring only local communication. The second one builds global analysis tools in order to obtain even better performance guarantees. This result is surprising as the greedy approach cannot achieve a competitive ratio better than $$O(m^{\log 1.5 + \varepsilon })$$ in the adversarial model, where m denotes the number of agents. Finally, we extend our results to the general delay cost case, the clearing requests with penalty case, and the asymmetric distance case.

Clairvoyant network design with deadlines or delay has been studied extensively, culminating in an O(log n)-competitive general framework, where n is the number of possible request types (Azar and Touitou, FOCS 2020). In the nonclairvoyant setting, the problem becomes much harder, as Ω(√n) lower bounds are known for certain problems (Azar et al., STOC 2017). However, no frameworks are known for the nonclairvoyant setting, and previous work focuses only on specific problems, e.g., multilevel aggregation (Le et al., SODA 2023). In this paper, we present the first nonclairvoyant frameworks for network design with deadlines or delay. These frameworks are nearly optimal: their competitive ratio is Õ(√n), which matches known lower bounds up to logarithmic factors.

This paper presents a new research direction for online Multi-Level Aggregation (MLA) with delays. In this problem, we are given an edge-weighted rooted tree $T$, and we have to serve a sequence of requests arriving at its vertices in an online manner. Each request $r$ is characterized by two parameters: its arrival time $t(r)$ and location $l(r)$ (a vertex). Once a request $r$ arrives, we can either serve it immediately or postpone this action until any time $t > t(r)$. We can serve several pending requests at the same time, and the service cost of a service corresponds to the weight of the subtree that contains all the requests served and the root of $T$. Postponing the service of a request $r$ to time $t > t(r)$ generates an additional delay cost of $t - t(r)$. The goal is to serve all requests in an online manner such that the total cost (i.e., the total sum of service and delay costs) is minimized. The current best algorithm for this problem achieves a competitive ratio of $O(d^2)$ (Azar and Touitou, FOCS'19), where $d$ denotes the depth of the tree. Here, we consider a stochastic version of MLA where the requests follow a Poisson arrival process. We present a deterministic online algorithm which achieves a constant ratio of expectations, meaning that the ratio between the expected costs of the solution generated by our algorithm and the optimal offline solution is bounded by a constant. Our algorithm is obtained by carefully combining two strategies. In the first one, we plan periodic oblivious visits to the subset of frequent vertices, whereas in the second one, we greedily serve the pending requests in the remaining vertices. This problem is complex enough to demonstrate a very rare phenomenon that ``single-minded" or ``sample-average" strategies are not enough in stochastic optimization.

This paper is dedicated to European option pricing under assumption that the underlying asset follows a geometric Levy process. The log-price of a primary financial instrument has the form of a sum of a drift component, a Brownian component, and a linear combination of time-homogeneous Poisson processes, modeling jumps in price. In our approach we apply stochastic analysis, especially the change of probability measure techniques, as well as fuzzy sets theory. To obtain the option valuation formulas we use the minimal variance equivalent martingale measure, which requires an advanced analysis of transformation of Levy characteristic triplets. We obtain analytical option valuation expressions in crisp case. Moreover, we assume that some model parameters are described in an imprecise way and therefore we use their fuzzy counterparts. Applying fuzzy arithmetic, we take into account various types of uncertainty on the market. As a result, we obtain the analytical option pricing formulas with fuzzy parameters. We also propose a method of automatized decision making, which utilizes the fuzzy valuation formulas. Apart from the general pricing expressions, we provide numerical examples to illustrate our theoretical results.