We consider an optimal stopping problem with n correlated offers where the goal is to design a (randomised) stopping strategy that maximises the expected value of the offer at which we stop. Instead of assuming to know the complete correlation structure, which is unrealistic in practice, we only assume to have knowledge of the distribution of the maximum value $$X_{\max }$$ of the sequence, and want to analyse the worst-case correlation structure whose maximum follows this distribution. This can be seen as a trade-off between the setting in which no distributional information is known, and the Bayesian setting in which the (possibly correlated) distributions of all the individual offers are known. As our first main result we show that a deterministic threshold strategy using the monopoly price of the distribution of the maximum value is asymptotically optimal assuming that the expectation of the maximum value grows sublinearly in n. In our second main result, we further tighten this bound by deriving a tight quadratic convergence guarantee for sufficiently smooth distributions of the maximum value. Our results also give rise to a more fine-grained picture regarding prophet inequalities with correlated values, for which distribution-free bounds only yield a performance guarantee of the order 1/n.

Abstract. The approximate uniform sampling of graphs with a given degree sequence is a well-known, extensively studied problem in theoretical computer science and has significant applications, e.g., in the analysis of social networks. In this work we study a generalization of the problem, where degree intervals are specified instead of a single degree sequence. We are interested in sampling and counting graphs whose degree sequences satisfy the corresponding degree interval constraints. A natural scenario where this problem arises is in hypothesis testing on networks that are only partially observed. We provide the first fully polynomial almost uniform sampler (FPAUS) as well as the first fully polynomial randomized approximation scheme (FPRAS) for sampling and counting, respectively, graphs with near-regular degree intervals, i.e., graphs in which every node has a degree from an interval not too far away from a given [Formula: see text]. In order to design our FPAUS, we rely on various state-of-the-art tools from Markov chain theory and combinatorics. In particular, by carefully using Markov chain decomposition and comparison arguments, we reduce part of our problem to the recent breakthrough of Anari et al. [ Proceedings of the 51 st Annual ACM SIGACT Symposium on Theory of Computing, 2019, pp. 1–12] on sampling a base of a matroid under a strongly log-concave probability distribution, and we provide the first nontrivial algorithmic application of a breakthrough asymptotic enumeration formula of Liebenau and Wormald [ J. Eur. Math. Soc., 26 (2023), pp. 1–40]. As a more direct approach, we also study a natural Markov chain recently introduced by Rechner, Strowick and Müller-Hannemann [ J. Complex Netw., 6 (2018), pp. 833–858], based on three local operations—switches, hinge flips, and additions/deletions of an edge. We obtain the first theoretical results for this Markov chain, showing it is rapidly mixing for the case of near-regular degree intervals of size at most one.

The approximate uniform sampling of graphs with a given degree sequence is a well-known, extensively studied problem in theoretical computer science and has significant applications, e.g., in the analysis of social networks. In this work we study a generalization of the problem, where degree intervals are specified instead of a single degree sequence. We are interested in sampling and counting graphs whose degree sequences satisfy the corresponding degree interval constraints. A natural scenario where this problem arises is in hypothesis testing on networks that are only partially observed. We provide the first fully polynomial almost uniform sampler (FPAUS) as well as the first fully polynomial randomized approximation scheme (FPRAS) for sampling and counting, respectively, graphs with near-regular degree intervals, i.e., graphs in which every node has a degree from an interval not too far away from a given r ∈ ℕ. In order to design our FPAUS, we rely on various state-of-the-art tools from Markov chain theory and combinatorics. In particular, by carefully using Markov chain decomposition and comparison arguments, we reduce part of our problem to the recent breakthrough of Anari, Liu, Oveis Gharan, and Vinzant (2019) on sampling a base of a matroid under a strongly log-concave probability distribution, and we provide the first non-trivial algorithmic application of a breakthrough asymptotic enumeration formula of Liebenau and Wormald (2017). As a more direct approach, we also study a natural Markov chain recently introduced by Rechner, Strowick and Müller-Hannemann (2018), based on three local operations - switches, hinge flips, and additions/deletions of an edge. We obtain the first theoretical results for this Markov chain, showing it is rapidly mixing for the case of near-regular degree intervals of size at most one.

We give tight bounds on the relation between the primal and dual of various combinatorial dimensions, such as the pseudo-dimension and fat-shattering dimension, for multi-valued function classes. These dimensional notions play an important role in the area of learning theory. We first review some classical results that bound the dual dimension of a function class in terms of its primal, and after that give (almost) matching lower bounds. In particular, we give an appropriate generalization to multi-valued function classes of a well-known bound due to Assouad (1983), that relates the primal and dual VC-dimension of a binary function class.

The switch Markov chain has been extensively studied as the most natural Markov chain Monte Carlo approach for sampling graphs with prescribed degree sequences. In this work we study the problem of uniformly sampling graphs for which, in addition to the degree sequence, joint degree constraints are given. These constraints specify how many edges there should be between two given degree classes (i.e., subsets of nodes that all have the same degree). Although the problem was formalized over a decade ago, and despite its practical significance in generating synthetic network topologies, small progress has been made on the random sampling of such graphs. In the case of one degree class, the problem reduces to the sampling of regular graphs (i.e., graphs in which all nodes have the same degree), but beyond this very little is known. We fully resolve the case of two degree classes, by showing that the switch Markov chain is always rapidly mixing. We do this by combining a recent embedding argument developed by the authors in combination with ideas of Bhatnagar et al. [ Algorithmica, 50 (2008), pp. 418--445] introduced in the context of sampling bichromatic matchings.

Logit dynamics is a form of randomized game dynamics where players have a bias towards strategic deviations that give a higher improvement in cost [3, 6]. It is used extensively in practice, but not well-understood from a theoretical perspective. In congestion (or potential) games [8], the dynamics converges to the so-called Gibbs distribution over the set of all strategy profiles, when interpreted as a Markov chain (see, e.g., [2]). In general, logit dynamics might converge slowly to the Gibbs distribution (i.e., the corresponding Markov chain is slowly mixing), but beyond that, not much is known about its algorithmic aspects, nor that of the Gibbs distribution.

The classical analysis of online algorithms, due to its worst-case nature, can be quite pessimistic when the input instance at hand is far from worst-case. Often this is not an issue with machine learning approaches, which shine in exploiting patterns in past inputs in order to predict the future. However, such predictions, although usually accurate, can be arbitrarily poor. Inspired by a recent line of work, we augment three well-known online settings with machine learned predictions about the future, and develop algorithms that take them into account. In particular, we study the following online selection problems: (i) the classical secretary problem, (ii) online bipartite matching and (iii) the graphic matroid secretary problem. Our algorithms still come with a worst-case performance guarantee in the case that predictions are subpar while obtaining an improved competitive ratio (over the best-known classical online algorithm for each problem) when the predictions are sufficiently accurate. For each algorithm, we establish a trade-off between the competitive ratios obtained in the two respective cases.

The switch Markov chain has been extensively studied as the most natural Markov Chain Monte Carlo approach for sampling graphs with prescribed degree sequences. We use comparison arguments with other—less natural but simpler to analyze—Markov chains, to show that the switch chain mixes rapidly in two different settings. We first study the classic problem of uniformly sampling simple undirected, as well as bipartite, graphs with a given degree sequence. We apply an embedding argument, involving a Markov chain defined by Jerrum and Sinclair (TCS, 1990) for sampling graphs that almost have a given degree sequence, to show rapid mixing for degree sequences satisfying strong stability, a notion closely related to P-stability. This results in a much shorter proof that unifies the currently known rapid mixing results of the switch chain and extends them up to sharp characterizations of P-stability. In particular, our work resolves an open problem posed by Green-hill (SODA, 2015). Secondly, in order to illustrate the power of our approach, we study the problem of uniformly sampling graphs for which, in addition to the degree sequence, a joint degree distribution is given. Although the problem was formalized over a decade ago, and despite its practical significance in generating synthetic network topologies, small progress has been made on the random sampling of such graphs. The case of a single degree class reduces to sampling of regular graphs, but beyond this almost nothing is known. We fully resolve the case of two degree classes, by showing that the switch Markov chain is always rapidly mixing. Again, we first analyze an auxiliary chain for strongly stable instances on an augmented state space and then use an embedding argument.

The Curveball algorithm is a variation on well-known switch-based Markov chain approaches for uniformly sampling binary matrices with fixed row and column sums. Instead of a switch, the Curveball algorithm performs a so-called binomial trade in every iteration of the algorithm. Intuitively, this could lead to a better convergence rate for reaching the stationary (uniform) distribution in certain cases. Some experimental evidence for this has been given in the literature. In this note we give a spectral gap comparison between two switch-based chains and the Curveball chain. In particular, this comparison allows us to conclude that the Curveball Markov chain is rapidly mixing whenever one of the two switch chains is rapidly mixing. Our analysis directly extends to the case of sampling binary matrices with forbidden entries (under the assumption of irreducibility). This in particular captures the case of sampling simple directed graphs with given degrees. As a by-product of our analysis, we show that the switch Markov chain of the Kannan-Tetali-Vempala conjecture only has non-negative eigenvalues if the sampled binary matrices have at least three columns. This shows that the Markov chain does not have to be made lazy, which is of independent interest. We also obtain an improved bound on the smallest eigenvalue for the switch Markov chain studied by Greenhill for uniformly sampling simple directed regular graphs.

We study the inefficiency and computation of pure Nash equilibria in unweighted congestion games, where the strategies of each player i are given implicitly by the binary vectors of a polytope $P_i$. Given these polytopes, a strategy profile naturally corresponds to an integral vector in the aggregation polytope PN = ∑i Pi. We identify two general properties of the aggregation polytope $P_N$ that are sufficient for our results to go through, namely the integer decomposition property (IDP) and the box-totally dual integrality property (box-TDI). Intuitively, the IDP is needed to decompose a load profile in PN into a respective strategy profile of the players, and box-TDI ensures that the intersection of a polytope with an arbitrary integer box is an integral polytope. Examples of polytopal congestion games which satisfy IDP and box-TDI include common source network congestion games, symmetric totally unimodular congestion games, non-symmetric matroid congestion games and symmetric matroid intersection congestion games (in particular, r-arborescences and strongly base-orderable matroids).