text: Online contention resolution schemes (OCRSs) were proposed by Feldman, Svensson, and Zenklusen as a generic technique to round a fractional solution in the matroid polytope in an online fashion. It has found applications in several stochastic combinatorial problems where there is a commitment constraint: on seeing the value of a stochastic element, the algorithm has to immediately and irrevocably decide whether to select it while always maintaining an independent set in the matroid. Although OCRSs immediately lead to prophet inequalities, these prophet inequalities are not optimal. Can we instead use prophet inequalities to design optimal OCRSs? We design the first optimal @math -OCRS for matroids by reducing the problem to designing a matroid prophet inequality where we compare to the stronger benchmark of an ex-ante relaxation. We also introduce and design optimal @math -random order CRSs for matroids, which are similar to OCRSs but the arrival is chosen uniformly at random.
  @cite_18: Consider a gambler who observes a sequence of independent, non-negative random numbers and is allowed to stop the sequence at any time, claiming a reward equal to the most recent observation. The famous prophet inequality of Krengel, Sucheston, and Garling asserts that a gambler who knows the distribution of each random variable can achieve at least half as much reward, in expectation, as a "prophet" who knows the sampled values of each random variable and can choose the largest one. We generalize this result to the setting in which the gambler and the prophet are allowed to make more than one selection, subject to a matroid constraint. We show that the gambler can still achieve at least half as much reward as the prophet; this result is the best possible, since it is known that the ratio cannot be improved even in the original prophet inequality, which corresponds to the special case of rank-one matroids. Generalizing the result still further, we show that under an intersection of p matroid constraints, the prophet's reward exceeds the gambler's by a factor of at most O(p), and this factor is also tight. Beyond their interest as theorems about pure online algorithms or optimal stopping rules, these results also have applications to mechanism design. Our results imply improved bounds on the ability of sequential posted-price mechanisms to approximate Bayesian optimal mechanisms in both single-parameter and multi-parameter settings. In particular, our results imply the first efficiently computable constant-factor approximations to the Bayesian optimal revenue in certain multi-parameter settings.
  @cite_4: Let @math be a monotone submodular set function, and let @math be a matroid. We consider the problem @math . It is known that the greedy algorithm yields a @math -approximation [M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, Math. Programming Stud., no. 8 (1978), pp. 73-87] for this problem. For certain special cases, e.g., @math , the greedy algorithm yields a @math -approximation. It is known that this is optimal both in the value oracle model (where the only access to @math is through a black box returning @math for a given set @math ) [G. L. Nemhauser and L. A. Wolsey, Math. Oper. Res., 3 (1978), pp. 177-188] and for explicitly posed instances assuming @math [U. Feige, J. ACM, 45 (1998), pp. 634-652]. In this paper, we provide a randomized @math -approximation for any monotone submodular function and an arbitrary matroid. The algorithm works in the value oracle model. Our main tools are a variant of the pipage rounding technique of Ageev and Sviridenko [J. Combin. Optim., 8 (2004), pp. 307-328], and a continuous greedy process that may be of independent interest. As a special case, our algorithm implies an optimal approximation for the submodular welfare problem in the value oracle model [J. Vondrak, Proceedings of the @math th ACM Symposium on Theory of Computing, 2008, pp. 67-74]. As a second application, we show that the generalized assignment problem (GAP) is also a special case; although the reduction requires @math to be exponential in the original problem size, we are able to achieve a @math -approximation for GAP, simplifying previously known algorithms. Additionally, the reduction enables us to obtain approximation algorithms for variants of GAP with more general constraints.
  @cite_7: 
  @cite_21: We consider the problem of maximizing a nonnegative submodular set function @math over a ground set @math subject to a variety of packing-type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular, when @math may be a nonmonotone function. Our algorithms are based on (approximately) maximizing the multilinear extension @math of @math over a polytope @math that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully, it has been limited in some important ways. We overcome these limitations as follows. First, we give constant factor approximation algorithms to maximize @math over a downward-closed polytope @math described by an efficient separation oracle. Previously this was known only for monotone functions. For nonmonotone functions, a constant factor was ...
  @cite_1: 
  @cite_17: 
  @cite_6: Recent work on online auctions for digital goods has explored the role of optimal stopping theory -- particularly secretary problems -- in the design of approximately optimal online mechanisms. This work generally assumes that the size of the market (number of bidders) is known a priori, but that the mechanism designer has no knowledge of the distribution of bid values. However, in many real-world applications (such as online ticket sales), the opposite is true: the seller has distributional knowledge of the bid values (e.g., via the history of past transactions in the market), but there is uncertainty about market size. Adopting the perspective of automated mechanism design, introduced by Conitzer and Sandholm, we develop algorithms that compute an optimal, or approximately optimal, online auction mechanism given access to this distributional knowledge. Our main results are twofold. First, we show that when the seller does not know the market size, no constant-approximation to the optimum efficiency or revenue is achievable in the worst case, even under the very strong assumption that bid values are i.i.d. samples from a distribution known to the seller. Second, we show that when the seller has distributional knowledge of the market size as well as the bid values, one can do well in several senses. Perhaps most interestingly, by combining dynamic programming with prophet inequalities (a technique from optimal stopping theory) we are able to design and analyze online mechanisms which are temporally strategyproof (even with respect to arrival and departure times) and approximately efficiency (revenue)-maximizing. In exploring the interplay between automated mechanism design and prophet inequalities, we prove new prophet inequalities motivated by the auction setting.
  @cite_3: 
  @cite_24: 
  @cite_0: For revenue and welfare maximization in single-dimensional Bayesian settings, (STOC10) recently showed that sequential posted-price mechanisms (SPMs), though simple in form, can perform surprisingly well compared to the optimal mechanisms. In this paper, we give a theoretical explanation of this fact, based on a connection to the notion of correlation gap. Loosely speaking, for auction environments with matroid constraints, we can relate the performance of a mechanism to the expectation of a monotone submodular function over a random set. This random set corresponds to the winner set for the optimal mechanism, which is highly correlated, and corresponds to certain demand set for SPMs, which is independent. The notion of correlation gap of (SODA10) quantifies how much we "lose" in the expectation of the function by ignoring correlation in the random set, and hence bounds our loss in using certain SPM instead of the optimal mechanism. Furthermore, the correlation gap of a monotone and submodular function is known to be small, and it follows that certain SPM can approximate the optimal mechanism by a good constant factor. Exploiting this connection, we give tight analysis of a greedy-based SPM of for several environments. In particular, we show that it gives an e (e − 1)-approximation for matroid environments, gives asymptotically a 1 (1--1 √2πk)-approximation for the important sub-case of k-unit auctions, and gives a (p + 1)-approximation for environments with p-independent set system constraints.
  @cite_23: 
  @cite_16: 
  @cite_12: 
  @cite_11: 
summary: Krengel and Sucheston gave the first tight @math -single item prophet inequality @cite_24 @cite_11 . The connection between multiple-choice prophet inequalities and mechanism design was recognized in @cite_6 ; they proved a prophet inequality for uniform matroids. This bound was later improved by Alaei @cite_1 using the , which is an OCRS in disguise. @cite_7 further developed the connection between prophet inequalities and mechanism design, and showed how to be @math -prophet inequality for general matroids in a variant where the algorithm may choose the element order. Yan @cite_0 improved this result to @math -competitive using the for submodular functions, first studied in @cite_16 @cite_4 . @cite_21 adapted correlation gaps to a polytope to design CRSs. Improved correlation gaps were presented in @cite_0 @cite_17 . The matroid prophet inequality was first explicitly formulated in @cite_18 . @cite_23 gave an alternate proof, and extended to Bernoulli submodular functions, using OCRSs. Finally, information theoretic @math -prophet inequalities are also known for general downward-closed constraints @cite_3 @cite_12 .