In this paper, we study Ranking, a well-known randomized greedy matching algorithm, for general graphs. The algorithm was originally introduced by Karp, Vazirani, and Vazirani [STOC 1990] for the online bipartite matching problem with one-sided vertex arrivals, where it achieves a tight approximation ratio of \(1 -1/e\). It was later extended to bipartite graphs with random vertex arrivals by Mahdian and Yan [STOC 2011] and to general graphs by Goel and Tripathi [FOCS 2012]. The Ranking algorithm for general graphs is as follows: a permutation \(\sigma\) over the vertices is chosen uniformly at random. The vertices are then processed sequentially according to this order, with each vertex being matched to the first available neighbor (if any) according to the same permutation \(\sigma\).

Randomized greedy algorithms form one of the simplest yet most effective approaches for computing approximate matchings in graphs. In this paper, we focus on the class of vertex-iterative (VI) randomized greedy matching algorithms, which process the vertices of a graph G=(V,E) in some order π and, for each vertex v, greedily match it to the first available neighbor (if any) according to a preference order σ(v). Various VI algorithms have been studied, each corresponding to a different distribution over π and σ(v).

In this paper, we study the weighted stochastic matching problem. Let $G=(V, E)$ be a given edge-weighted graph and let its realization $\mathcal{G}$ be a random subgraph of $G$ that includes each edge $e\in E$ independently with a known probability $p_e$. The goal in this problem is to pick a sparse subgraph $Q$ of $G$ without prior knowledge of $G$'s realization, such that the maximum weight matching among the realized edges of $Q$ (i.e. the subgraph $Q\cap \mathcal{G}$) in expectation approximates the maximum weight matching of the entire realization $\mathcal{G}$. Attaining any constant approximation ratio for this problem requires selecting a subgraph of max-degree $Ω(1/p)$ where $p=\min_{e\in E} p_e$. On the positive side, there exists a $(1-ε)$-approximation algorithm by Behnezhad and Derakhshan, albeit at the cost of max-degree having exponential dependence on $1/p$. Within the $\text{poly}(1/p)$ regime, however, the best-known algorithm achieves a $0.536$ approximation ratio due to Dughmi, Kalayci, and Patel improving over the $0.501$ approximation algorithm by Behnezhad, Farhadi, Hajiaghayi, and Reyhani. In this work, we present a 0.68 approximation algorithm with $O(1/p)$ queries per vertex, which is asymptotically tight. This is even an improvement over the best-known approximation ratio of $2/3$ for unweighted graphs within the $\text{poly}(1/p)$ regime due to Assadi and Bernstein. The $2/3$ approximation ratio is proven tight in the presence of a few correlated edges in $\mathcal{G}$, indicating that surpassing the $2/3$ barrier should rely on the independent realization of edges. Our analysis involves reducing the problem to designing a randomized matching algorithm on a given stochastic graph with some variance-bounding properties.

We study the polynomial-time approximability of the optimal online stochastic bipartite matching algorithm, initiated by Papadimitriou et al. (EC’21). Here, nodes on one side of the graph are given upfront, while at each time t, an online node and its edge weights are drawn from a time-dependent distribution. The optimal algorithm is PSPACE-hard to approximate within some universal constant. We refer to this optimal algorithm, which requires time to think (compute), as a philosopher, and refer to polynomial-time online approximations of the above as philosopher inequalities. The best known philosopher inequality for online matching yields a 0.652-approximation. In contrast, the best possible prophet inequality, or approximation of the optimum offline solution, is 0.5.

The competition complexity of an auction setting is the number of additional bidders needed such that the simple mechanism of selling items separately (with additional bidders) achieves greater revenue than the optimal but complex (randomized, prior-dependent, Bayesian-truthful) optimal mechanism without the additional bidders. Our main result settles the competition complexity of n bidders with additive values over m < n independent items at [EQUATION]. The [EQUATION] upper bound is due to [Beyhaghi and Weinberg, 2019], and our main result improves the prior lower bound of Ω (ln n) to [EQUATION].

In a carbon auction, licenses for CO2 emissions are allocated among multiple interested players. Inspired by this setting, we consider repeated multi-unit auctions with uniform pricing, which are widely used in practice. Our contribution is to analyze these auctions in both the offline and online settings, by designing efficient bidding algorithms with low regret and giving regret lower bounds. We also analyze the quality of the equilibria in two main variants of the auction, finding that one variant is susceptible to collusion among the bidders while the other is not.

In the stochastic weighted matching problem, the goal is to find a large-weight matching of a graph when we are uncertain about the existence of its edges. In particular, each edge e has a known weight we but is realized independently with some probability pe. The algorithm may query an edge to see whether it is realized. We consider the well-studied query commit version of the problem, in which any queried edge that happens to be realized must be included in the solution. Gamlath, Kale, and Svensson [SODA'19] showed that when the input graph is bipartite, the problem admits a (1 — 1/e)-approximation. In this paper, we give an algorithm that obtains a (1 — 1/e + δ)-approximation for an absolute constant δ > 0.0014, therefore breaking this prevalent bound.

We study the stochastic vertex cover problem. In this problem, G = (V, E) is an arbitrary known graph, and G⋆ is an unknown random subgraph of G where each edge e is realized independently with probability p. Edges of G⋆ can only be verified using edge queries. The goal in this problem is to find a minimum vertex cover of G⋆ using a small number of queries.

In this paper, we study max-weight stochastic matchings on online bipartite graphs under both vertex and edge arrivals. We focus on designing polynomial time approximation algorithms with respect to the online benchmark, which was first considered by Papadimitriou, Pollner, Saberi, and Wajc [EC'21].

We study the minimum vertex cover problem in the following stochastic setting. Let G be an arbitrary given graph, p ∊ (0, 1] a parameter of the problem, and let Gp be a random subgraph that includes each edge of G independently with probability p. We are unaware of the realization Gp, but can learn if an edge e exists in Gp by querying it. The goal is to find an approximate minimum vertex cover (MVC) of Gp by querying few edges of G non-adaptively. This stochastic setting has been studied extensively for various problems such as minimum spanning trees, matroids, shortest paths, and matchings. To our knowledge, however, no non-trivial bound was known for MVC prior to our work. In this work, we present a: (2 + ∊)-approximation for general graphs which queries edges per vertex, and a 1.367-approximation for bipartite graphs which queries poly(1/p) edges per vertex. Additionally, we show that at the expense of a triple-exponential dependence on p–1 in the number of queries, the approximation ratio can be improved down to (1 + ∊) for bipartite graphs. Our techniques also lead to improved bounds for bipartite stochastic matching. We obtain a 0.731-approximation with nearly-linear in 1/p per-vertex queries. This is the first result to break the prevalent (2/3∼ 0.66)-approximation barrier in the poly(1/p) query regime, improving algorithms of [Behnezhad et al., SODA'19] and [Assadi and Bernstein, SOSA'19].

We study the problem of finding personalized reserve prices for unit-demand buyers in multi-unit eager VCG auctions with correlated buyers. The input to this problem is a dataset of submitted bids of n buyers in a set of auctions. The goal is to find a vector of reserve prices, one for each buyer, that maximizes the total revenue across all auctions. Roughgarden and Wang (2016) showed that this problem is APX-hard but admits a greedy ½-approximation algorithm. Later, Derakhshan, Golrezai, and Paes Leme (2019) gave an LP-based algorithm achieving a 0.68-approximation for the (important) special case of the problem with a single-item, thereby beating greedy. We show in this paper that the algorithm of Derakhshan et al. in fact does not beat greedy for the general multi-item problem. This raises the question of whether or not the general problem admits a better-than-½ approximation. In this paper, we answer this question in the affirmative and provide a polynomial-time algorithm with a significantly better approximation-factor of 0.63. Our solution is based on a novel linear programming formulation, for which we propose two different rounding schemes. We prove that the best of these two and the no-reserve case (all-zero vector) is a 0.63-approximation. Full version. Due to the page limit, this version of the paper does not include all the proofs. The full version of the paper is available at [11].

Let G = (V, E) be a given edge-weighted graph and let its realization G be a random subgraph of G that includes each edge e ∈ E independently with probability p. We study a stochastic matching problem where the goal is to non-adaptively pick a sparse subgraph Q of G (without knowing the realization G), such that the maximum weight matching among the realized edges of Q (i.e. graph Q∩G) in expectation approximates the maximum weight matching of the whole realization G. In this paper, we prove that for any ε ∈ (0,1), every graph G has a subgraph Q that has maximum degree only Oε, p(1) and guarantees a ( 1-ε) -approximation. That is, the maximum degree of Q depends only on ε and p (both of which are known to be necessary) and not for example on the number of nodes in G, the edge-weights, etc. The stochastic matching problem has been studied extensively on both weighted and unweighted graphs. Previously, only existence of (close to) half-approximate subgraphs was known for weighted graphs [Yamaguchi and Maehara, SODA'18; Behnezhad et al., SODA'19]. Our result substantially improves over these works, matches the state-of-the-art for unweighted graphs [Behnezhad et al., STOC'20], and settles the approximation factor.

On online platforms, consumers face an abundance of options that are displayed in the form of a position ranking. Only products placed in the first few positions are readily accessible to the consumer, and she needs to exert effort to access more options. For such platforms, we develop a two-stage sequential search model where in the first stage, the consumer sequentially screens positions to observe the preference weight of the products placed in them and forms a consideration set. In the second stage, she observes the additional idiosyncratic utility that she can derive from each product and chooses the highest-utility product within her consideration set. For this model, we first characterize the optimal sequential search policy of a welfare-maximizing consumer. We then study how platforms with different objectives should rank products. We focus on two objectives: (i) maximizing the platform's market share and (ii) maximizing the consumer's welfare. Somewhat surprisingly, we show that ranking products in decreasing order of their preference weights does not necessarily maximize market share or consumer welfare. Such a ranking may shorten the consumer's consideration set due to the externality effect of high-positioned products on low-positioned ones, leading to insufficient screening. We then show that both problems---maximizing market share and maximizing consumer welfare---are NP-complete. We develop novel near-optimal polynomial-time ranking algorithms for each objective. Further, we show that even though ranking products in decreasing order of their preference weights is suboptimal, such a ranking enjoys strong performance guarantees for both objectives. We complement our theoretical developments with numerical studies using synthetic data in which we show (1) that heuristic versions of our algorithms that do not rely on model primitives perform well and (2) that our model can be effectively estimated using a maximum likelihood estimator.

Suppose that we are given an arbitrary graph G=(V, E) and know that each edge in E is going to be realized independently with some probability p. The goal in the stochastic matching problem is to pick a sparse subgraph Q of G such that the realized edges in Q, in expectation, include a matching that is approximately as large as the maximum matching among the realized edges of G. The maximum degree of Q can depend on p, but not on the size of G. This problem has been subject to extensive studies over the years and the approximation factor has been improved gradually from 0.5 to eventually 2/3 which is a known barrier. In this work, we analyze a natural sampling-based algorithm and show that it can obtain a (1−є) approximation, for any constant є > 0. A key and of possible independent interest component of our analysis is an algorithm that constructs a matching on a stochastic graph, which among some other important properties, guarantees that each vertex is matched independently from the vertices that are sufficiently far. This allows us to bypass a previously known barrier towards achieving (1−є) approximation based on existence of dense Ruzsa-Szemerédi graphs.

A valid edge-coloring of a graph is an assignment of "colors" to its edges such that no two incident edges receive the same color. The goal is to find a proper coloring that uses few colors. (Note that the maximum degree, Delta, is a trivial lower bound.) In this paper, we revisit this fundamental problem in two models of computation specific to massive graphs, the Massively Parallel Computations (MPC) model and the Graph Streaming model: - Massively Parallel Computation: We give a randomized MPC algorithm that with high probability returns a Delta+O~(Delta^(3/4)) edge coloring in O(1) rounds using O(n) space per machine and O(m) total space. The space per machine can also be further improved to n^(1-Omega(1)) if Delta = n^Omega(1). Our algorithm improves upon a previous result of Harvey et al. [SPAA 2018]. - Graph Streaming: Since the output of edge-coloring is as large as its input, we consider a standard variant of the streaming model where the output is also reported in a streaming fashion. The main challenge is that the algorithm cannot "remember" all the reported edge colors, yet has to output a proper edge coloring using few colors. We give a one-pass O~(n)-space streaming algorithm that always returns a valid coloring and uses 5.44 Delta colors with high probability if the edges arrive in a random order. For adversarial order streams, we give another one-pass O~(n)-space algorithm that requires O(Delta^2) colors.

We present the first algorithm for maintaining a maximal independent set (MIS) of a fully dynamic graph-which undergoes both edge insertions and deletions-in polylogarithmic time. Our algorithm is randomized and, per update, takes O(log2Δ log2n) expected time. Furthermore, the algorithm can be adjusted to have O(log2Δ log4n) worst-case update-time with high probability. Here, n denotes the number of vertices and Δ is the maximum degree in the graph. The MIS problem in fully dynamic graphs has attracted significant attention after a breakthrough result of Assadi, Onak, Schieber, and Solomon [STOC'18] who presented an algorithm with O(m3/4) update-time (and thus broke the natural Ω(m) barrier) where m denotes the number of edges in the graph. This result was improved in a series of subsequent papers, though, the update-time remained polynomial. In particular, the fastest algorithm prior to our work had Õ(min{√n, m1/3}) update-time [Assadi et al. SODA'19]. Our algorithm maintains the lexicographically first MIS over a random order of the vertices. As a result, the same algorithm also maintains a 3-approximation of correlation clustering. We also show that a simpler variant of our algorithm can be used to maintain a random-order lexicographically first maximal matching in the same update-time.

The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale parallel computation frameworks and has recently gained a lot of importance, especially in the context of classic graph problems. In this work, we mainly consider maximal matching and maximal independent set problems in the MPC model.

A valid edge-coloring of a graph is an assignment of "colors" to its edges such that no two incident edges receive the same color. The goal is to find a proper coloring that uses few colors. In this paper, we revisit this problem in two models of computation specific to massive graphs, the Massively Parallel Computations (MPC) model and the Graph Streaming model: Massively Parallel Computation. We give a randomized MPC algorithm that w.h.p., returns a (1+o(1))Delta edge coloring in O(1) rounds using O~(n) space per machine and O(m) total space. The space per machine can also be further improved to n^{1-Omega(1)} if Delta = n^{Omega(1)}. This is, to our knowledge, the first constant round algorithm for a natural graph problem in the strongly sublinear regime of MPC. Our algorithm improves a previous result of Harvey et al. [SPAA 2018] which required n^{1+Omega(1)} space to achieve the same result. Graph Streaming. Since the output of edge-coloring is as large as its input, we consider a standard variant of the streaming model where the output is also reported in a streaming fashion. The main challenge is that the algorithm cannot "remember" all the reported edge colors, yet has to output a proper edge coloring using few colors. We give a one-pass O~(n)-space streaming algorithm that always returns a valid coloring and uses 5.44 Delta colors w.h.p., if the edges arrive in a random order. For adversarial order streams, we give another one-pass O~(n)-space algorithm that requires O(Delta^2) colors.

Solving large-scale graph problems is a fundamental task in many real-world applications, and it is an increasingly important problem in data analysis. Despite the large effort in designing scalable graph algorithms, many classic graph problems lack algorithms that require only a sublinear number of machines and space in the input size. Specifically when the input graph is large and sparse, which is indeed the case for many real-world graphs, it becomes impossible to store and access all the vertices in one machine - something that is often taken for granted in designing algorithms for massive graphs. The theoretical model that we consider is the Massively Parallel Communications (MPC) model which is a popular theoretical model of MapReduce-like systems. In this paper, we give an algorithmic framework to adapt a large family of dynamic programs on MPC. We start by introducing two classes of dynamic programming problems, namely "(poly log)-expressible" and "linear-expressible" problems. We show that both classes can be solved efficiently using a sublinear number of machines and a sublinear memory per machine. To achieve this result, we introduce a series of techniques that can be plugged together. To illustrate the generality of our framework, we implement in O(log n) rounds of MPC, the dynamic programming solution of fundamental problems such as minimum bisection, k-spanning tree, maximum independent set, longest path, etc., when the input graph is a tree.

Protecting valuable \em targets from an adversary is an ever-important international concern with far-reaching applications in wildlife protection, border protection, counter-terrorism, protection of ships from piracy, etc. As a successful recent approach, \em security games cast these issues as two-player games between a \em defender and an \em attacker. The defender decides on how to allocate the available \em resources to protect targets against the attacker who strives to inflict damage on them. The main question of interest here is equilibrium computation. Our focus in this paper is on \em spatio-temporal security games. However, inspired by the paper of Xu [EC'16], we start with a general model of security games and show that any approximation (of any factor) for the defender's best response (DBR) problem leads to an approximation of the same factor for the actual game. In most applications of security games, the targets are mobile. This leads to a well-studied class of succinct games, namely \em spatio-temporal security games, that is played in space and time. In such games, the defender has to specify a time-dependent patrolling strategy over a spatial domain to protect a set of moving targets. We give a generalized model of prior spatio-temporal security games that is played on a base graph G . That is, the patrols can be placed on the vertices of G and move along its edges over time. This unifies and generalizes prior spatio-temporal models that only consider specific spatial domains such as lines or grids. Graphs can further model many other domains of practical interest such as roads, internal maps of buildings, etc. Finding an optimal defender strategy becomes NP-hard on general graphs. To overcome this, we give an LP relaxation of the DBR problem and devise a rounding technique to obtain an almost optimal integral solution. More precisely, we show that one can achieve a $(1-ε)$-approximation in polynomial time if we allow the defender to use $łceil łn(1/ε)\rceil$ times more patrols. We later show that this result is in some sense the best possible polynomial time algorithm (unless P=NP). Furthermore, we show that by using a novel \em dependent rounding technique, the same LP relaxation gives an optimal solution for specific domains of interest, such as one-dimensional spaces. This result simplifies and improves upon the prior algorithm of Behnezhad et al. ~[EC'17] on several aspects and can be generalized to other graphs of interest such as cycles. Lastly, we note that most prior algorithms for security games assume that the attacker attacks only once and become intractable for a super-constant number of attacks. Our algorithms are fully polynomial in the input size and work for any given number of attacks.

Mixed strategies are often evaluated based on the expected payoff that they guarantee. This is not always desirable. In this paper, we consider games for which maximizing the expected payoff deviates from the actual goal of the players. To address this issue, we introduce the notion of a (u,p)-maxmin strategy which ensures receiving a minimum utility of u with probability at least p. We then give approximation algorithms for the problem of finding a (u, p)-maxmin strategy for these games. The first game that we consider is Colonel Blotto, a well-studied game that was introduced in 1921. In the Colonel Blotto game, two colonels divide their troops among a set of battlefields. Each battlefield is won by the colonel that puts more troops in it. The payoff of each colonel is the weighted number of battlefields that she wins. We show that maximizing the expected payoff of a player does not necessarily maximize her winning probability for certain applications of Colonel Blotto. For example, in presidential elections, the players’ goal is to maximize the probability of winning more than half of the votes, rather than maximizing the expected number of votes that they get. We give an exact algorithm for a natural variant of continuous version of this game. More generally, we provide constant and logarithmic approximation algorithms for finding (u, p)-maxmin strategies. We also introduce a security game version of Colonel Blotto which we call auditing game. It is played between two players, a defender and an attacker. The goal of the defender is to prevent the attacker from changing the outcome of an instance of Colonel Blotto. Again, maximizing the expected payoff of the defender is not necessarily optimal. Therefore we give a constant approximation for (u, p)-maxmin strategies.

In the Colonel Blotto game, which was initially introduced by Borel in 1921, two colonels simultaneously distribute their troops across different battlefields.The winner of each battlefield is determined independently by a winner-take-all rule. The ultimate payoff of each colonel is the number of battlefields he wins. This game is commonly used for analyzing a wide range of applications such as the U.S presidential election, innovative technology competitions, advertisements, etc. There have been persistent efforts for finding the optimal strategies for the Colonel Blotto game. After almost a century Ahmadinejad, Dehghani, Hajiaghayi, Lucier, Mahini, and Seddighin provided a poly-time algorithm for finding the optimal strategies. They first model the problem by a Linear Program (LP) with exponential number of constraints and use Ellipsoid method to solve it. However, despite the theoretical importance of their algorithm, it ishighly impractical. In general, even Simplex method (despite its exponential running-time) performs better than Ellipsoid method in practice. In this paper, we provide the first polynomial-size LP formulation of the optimal strategies for the Colonel Blotto game. We use linear extension techniques. Roughly speaking, we project the strategy space polytope to a higher dimensional space, which results in a lower number of facets for the polytope.We use this polynomial-size LP to provide a novel, simpler and significantly faster algorithm for finding the optimal strategies for the Colonel Blotto game. We further show this representation is asymptotically tight in terms of the number of constraints. We also extend our approach to multi-dimensional Colonel Blotto games, and implement our algorithm to observe interesting properties of Colonel Blotto; for example, we observe the behavior of players in the discrete model is very similar to the previously studied continuous model.

Graph clustering is a fundamental task in many data-mining and machine-learning pipelines. In particular, identifying a good hierarchical structure is at the same time a fundamental and challenging problem for several applications. The amount of data to analyze is increasing at an astonishing rate each day. Hence there is a need for new solutions to efficiently compute effective hierarchical clusterings on such huge data. The main focus of this paper is on minimum spanning tree (MST) based clusterings. In particular, we propose affinity, a novel hierarchical clustering based on Boruvka's MST algorithm. We prove certain theoretical guarantees for affinity (as well as some other classic algorithms) and show that in practice it is superior to several other state-of-the-art clustering algorithms. Furthermore, we present two MapReduce implementations for affinity. The first one works for the case where the input graph is dense and takes constant rounds. It is based on a Massively Parallel MST algorithm for dense graphs that improves upon the state-of-the-art algorithm of Lattanzi et al. (SPAA 2011). Our second algorithm has no assumption on the density of the input graph and finds the affinity clustering in $O(\log n)$ rounds using Distributed Hash Tables (DHTs). We show experimentally that our algorithms are scalable for huge data sets, e.g., for graphs with trillions of edges.

An ever-important issue is protecting infrastructure and other valuable targets from a range of threats from vandalism to theft to piracy to terrorism. The "defender" can rarely afford the needed resources for a 100% protection. Thus, the key question is, how to provide the best protection using the limited available resources.

In this paper we consider the maximum matching problem in large bipartite graphs. We present a new algorithm that finds the maximum matching in a few iterations of a novel edge sampling technique. This algorithm can be implemented in big data settings such as streaming setting and MapReduce setting, where each iteration of the algorithm maps to one pass over the stream, or one MapReduce round of computation, respectively. We prove that our algorithm provides a 1-\eps approximate solution to the maximum matching in 1/\eps rounds which improves the prior work in terms of the number of passes/rounds. Our algorithm works even better when we run it on real datasets and finds the exact maximum matching in 4 to 8 rounds while sampling only about %1 of the total edges.