SU\G(𝔸)/K·U
Sign Up for free Log In

Author Description

Login to generate an author description

Ask a Question About This Mathematician

An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation

2019-01-01
Eric Balkanski , Aviad Rubinstein , Yaron Singer
In this paper we study the adaptivity of submodular maximization. Adaptivity quantifies the number of sequential rounds that an algorithm makes when function evaluations can be executed in parallel. Adaptivity … In this paper we study the adaptivity of submodular maximization. Adaptivity quantifies the number of sequential rounds that an algorithm makes when function evaluations can be executed in parallel. Adaptivity is a fundamental concept that is heavily studied across a variety of areas in computer science, largely due to the need for parallelizing computation. For the canonical problem of maximizing a monotone submodular function under a cardinality constraint, it is well known that a simple greedy algorithm achieves a 1 – 1/e approximation [NWF78] and that this approximation is optimal for polynomial-time algorithms [NW78]. Somewhat surprisingly, despite extensive efforts on submodular optimization for large-scale datasets, until very recently there was no known algorithm that achieves a constant factor approximation for this problem whose adaptivity is sublinear in the size of the ground set n.Recent work by [BS18] describes an algorithm that obtains an approximation arbitrarily close to 1/3 in O(log n) adaptive rounds and shows that no algorithm can obtain a constant factor approximation in õ(log n) adaptive rounds. This approach achieves an exponential speedup in adaptivity (and parallel running time) at the expense of approximation quality.In this paper we describe a novel approach that yields an algorithm whose approximation is arbitrarily close to the optimal 1 – 1/e guarantee in O(log n) adaptive rounds. This algorithm therefore achieves an exponential speedup in parallel running time for submodular maximization at the expense of an arbitrarily small loss in approximation quality. This guarantee is optimal in both approximation and adaptivity, up to lower order terms.
View PDF Chat

The limitations of optimization from samples

2017-06-15
Eric Balkanski , Aviad Rubinstein , Yaron Singer
In this paper we consider the following question: can we optimize objective functions from the training data we use to learn them? We formalize this question through a novel framework … In this paper we consider the following question: can we optimize objective functions from the training data we use to learn them? We formalize this question through a novel framework we call optimization from samples (OPS). In OPS, we are given sampled values of a function drawn from some distribution and the objective is to optimize the function under some constraint.
View PDF Chat

Bayesian Budget Feasibility with Posted Pricing

2016-04-11
Eric Balkanski , Jason D. Hartline
We consider the problem of budget feasible mechanism design proposed by Singer, but in a Bayesian setting. A principal has a public value for hiring a subset of the agents … We consider the problem of budget feasible mechanism design proposed by Singer, but in a Bayesian setting. A principal has a public value for hiring a subset of the agents and a budget, while the agents have private costs for being hired. We consider both additive and submodular value functions of the principal. We show that there are simple, practical, ex post budget balanced posted pricing mechanisms that approximate the value obtained by the Bayesian optimal mechanism that is budget balanced only in expectation. A main motivating application for this work is crowdsourcing, e.g., on Mechanical Turk, where workers are drawn from a large population and posted pricing is standard. Our analysis methods relate to contention resolution schemes in submodular optimization of Vondràk et al. and the correlation gap analysis of Yan.
View PDF Chat

An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model

2019-06-20
Eric Balkanski , Aviad Rubinstein , Yaron Singer
In this paper we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization to quantify the … In this paper we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization to quantify the information theoretic complexity of black-box optimization in a parallel computation model. Informally, the adaptivity of an algorithm is the number of sequential rounds it makes when each round can execute polynomially-many function evaluations in parallel. Since submodular optimization is regularly applied on large datasets we seek algorithms with low adaptivity to enable speedups via parallelization. Consequently, a recent line of work has been devoted to designing constant factor approximation algorithms for maximizing submodular functions under various constraints in the adaptive complexity model.
View PDF Chat

Non-monotone Submodular Maximization in Exponentially Fewer Iterations

2018-01-01
Eric Balkanski , Adam Breuer , Yaron Singer
In this paper we consider parallelization for applications whose objective can be expressed as maximizing a non-monotone submodular function under a cardinality constraint. Our main result is an algorithm whose … In this paper we consider parallelization for applications whose objective can be expressed as maximizing a non-monotone submodular function under a cardinality constraint. Our main result is an algorithm whose approximation is arbitrarily close to $1/2e$ in $O(\log^2 n)$ adaptive rounds, where $n$ is the size of the ground set. This is an exponential speedup in parallel running time over any previously studied algorithm for constrained non-monotone submodular maximization. Beyond its provable guarantees, the algorithm performs well in practice. Specifically, experiments on traffic monitoring and personalized data summarization applications show that the algorithm finds solutions whose values are competitive with state-of-the-art algorithms while running in exponentially fewer parallel iterations.

Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimization

2018-01-01
Eric Balkanski , Yaron Singer
In this paper we study the limitations of parallelization in convex optimization. A convenient approach to study parallelization is through the prism of \emph{adaptivity} which is an information theoretic measure … In this paper we study the limitations of parallelization in convex optimization. A convenient approach to study parallelization is through the prism of \emph{adaptivity} which is an information theoretic measure of the parallel runtime of an algorithm [BS18]. Informally, adaptivity is the number of sequential rounds an algorithm needs to make when it can execute polynomially-many queries in parallel at every round. For combinatorial optimization with black-box oracle access, the study of adaptivity has recently led to exponential accelerations in parallel runtime and the natural question is whether dramatic accelerations are achievable for convex optimization. For the problem of minimizing a non-smooth convex function $f:[0,1]^n\to \mathbb{R}$ over the unit Euclidean ball, we give a tight lower bound that shows that even when $\texttt{poly}(n)$ queries can be executed in parallel, there is no randomized algorithm with $\tilde{o}(n^{1/3})$ rounds of adaptivity that has convergence rate that is better than those achievable with a one-query-per-round algorithm. A similar lower bound was obtained by Nemirovski [Nem94], however that result holds for the $\ell_{\infty}$-setting instead of $\ell_2$. In addition, we also show a tight lower bound that holds for Lipschitz and strongly convex functions. At the time of writing this manuscript we were not aware of Nemirovski's result. The construction we use is similar to the one in [Nem94], though our analysis is different. Due to the close relationship between this work and [Nem94], we view the research contribution of this manuscript limited and it should serve as an instructful approach to understanding lower bounds for parallel optimization.

Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location

2022-07-12
Priyank Agrawal , Eric Balkanski , Vasilis Gkatzelis +2 more
In this work we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in "learning-augmented algorithms". Aiming to … In this work we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in "learning-augmented algorithms". Aiming to complement the traditional approach in computer science, which analyzes the performance of algorithms based on worst-case instances, this line of work has focused on the design and analysis of algorithms that are enhanced with machine-learned predictions regarding the optimal solution. The algorithms can use the predictions as a guide to inform their decisions, and the goal is to achieve much stronger performance guarantees when these predictions are accurate (consistency), while also maintaining near-optimal worst-case guarantees, even if these predictions are very inaccurate (robustness). So far, these results have been limited to algorithms, but in this work we argue that another fertile ground for this framework is in mechanism design.
View PDF Chat

The FAST Algorithm for Submodular Maximization

2019-01-01
Adam Breuer , Eric Balkanski , Yaron Singer
In this paper we describe a new algorithm called Fast Adaptive Sequencing Technique (FAST) for maximizing a monotone submodular function under a cardinality constraint $k$ whose approximation ratio is arbitrarily … In this paper we describe a new algorithm called Fast Adaptive Sequencing Technique (FAST) for maximizing a monotone submodular function under a cardinality constraint $k$ whose approximation ratio is arbitrarily close to $1-1/e$, is $O(\log(n) \log^2(\log k))$ adaptive, and uses a total of $O(n \log\log(k))$ queries. Recent algorithms have comparable guarantees in terms of asymptotic worst case analysis, but their actual number of rounds and query complexity depend on very large constants and polynomials in terms of precision and confidence, making them impractical for large data sets. Our main contribution is a design that is extremely efficient both in terms of its non-asymptotic worst case query complexity and number of rounds, and in terms of its practical runtime. We show that this algorithm outperforms any algorithm for submodular maximization we are aware of, including hyper-optimized parallel versions of state-of-the-art serial algorithms, by running experiments on large data sets. These experiments show FAST is orders of magnitude faster than the state-of-the-art.

The Sample Complexity of Optimizing a Convex Function

2017-06-18
Eric Balkanski , Yaron Singer

An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model

2021-12-28
Eric Balkanski , Aviad Rubinstein , Yaron Singer
An Exponentially Faster Algorithm for Submodular Maximization Under a Matroid Constraint This paper studies the problem of submodular maximization under a matroid constraint. It is known since the 1970s that … An Exponentially Faster Algorithm for Submodular Maximization Under a Matroid Constraint This paper studies the problem of submodular maximization under a matroid constraint. It is known since the 1970s that the greedy algorithm obtains a constant-factor approximation guarantee for this problem. Twelve years ago, a breakthrough result by Vondrák obtained the optimal 1 − 1/e approximation. Previous algorithms for this fundamental problem all have linear parallel runtime, which was considered impossible to accelerate until recently. The main contribution of this paper is a novel algorithm that provides an exponential speedup in the parallel runtime of submodular maximization under a matroid constraint, without loss in the approximation guarantee.
View PDF Chat

Statistical Cost Sharing

2017-01-01
Eric Balkanski , Umar Syed , Sergei Vassilvitskii
We study the cost sharing problem for cooperative games in situations where the cost function $C$ is not available via oracle queries, but must instead be derived from data, represented … We study the cost sharing problem for cooperative games in situations where the cost function $C$ is not available via oracle queries, but must instead be derived from data, represented as tuples $(S, C(S))$, for different subsets $S$ of players. We formalize this approach, which we call statistical cost sharing, and consider the computation of the core and the Shapley value, when the tuples are drawn from some distribution $\mathcal{D}$. Previous work by Balcan et al. in this setting showed how to compute cost shares that satisfy the core property with high probability for limited classes of functions. We expand on their work and give an algorithm that computes such cost shares for any function with a non-empty core. We complement these results by proving an inapproximability lower bound for a weaker relaxation. We then turn our attention to the Shapley value. We first show that when cost functions come from the family of submodular functions with bounded curvature, $κ$, the Shapley value can be approximated from samples up to a $\sqrt{1 - κ}$ factor, and that the bound is tight. We then define statistical analogues of the Shapley axioms, and derive a notion of statistical Shapley value. We show that these can always be approximated arbitrarily well for general functions over any distribution $\mathcal{D}$.

Deterministic Budget-Feasible Clock Auctions

2022-01-01
Eric Balkanski , Pranav Garimidi , Vasilis Gkatzelis +2 more
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Deterministic Budget-Feasible Clock AuctionsEric Balkanski, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin, and Xizhi TanEric … Previous chapter Next chapter Full AccessProceedings Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Deterministic Budget-Feasible Clock AuctionsEric Balkanski, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin, and Xizhi TanEric Balkanski, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin, and Xizhi Tanpp.2940 - 2963Chapter DOI:https://doi.org/10.1137/1.9781611977073.114PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the last decade, several strategyproof budget-feasible procurement auctions have been proposed, aiming to maximize the value of the buyer, while eliciting each seller's true cost for providing their service. These solutions predominantly take the form of randomized sealed-bid auctions: they ask the sellers to report their private costs and then use randomization to determine which subset of services will be procured and how much each of the chosen providers will be paid, ensuring that the total payment does not exceed the buyer's budget. Our main result in this paper is a novel method for designing budget-feasible auctions, leading to solutions that outperform the previously proposed auctions in multiple ways. First, our solutions take the form of descending clock auctions, and thus satisfy a list of very appealing properties, such as obvious strategyproofness, group strategyproofness, transparency, and unconditional winner privacy; this makes these auctions much more likely to be used in practice. Second, in contrast to previous results that heavily depend on randomization, our auctions are deterministic. As a result, we provide an affirmative answer to one of the main open questions in this literature, asking whether a deterministic strategyproof auction can achieve a constant approximation when the buyer's valuation function is submodular over the set of services. In addition to this, we also provide the first deterministic budget-feasible auction that matches the approximation bound of the best-known randomized auction for the class of subadditive valuations. Finally, using our method, we improve the best-known approximation factor for monotone submodular valuations, which has been the focus of most of the prior work. Previous chapter Next chapter RelatedDetails Published:2022eISBN:978-1-61197-707-3 https://doi.org/10.1137/1.9781611977073Book Series Name:ProceedingsBook Code:PRDA22Book Pages:xvii + 3771
View PDF Chat

The Importance of Communities for Learning to Influence

2018-01-01
Eric Balkanski , Nicole Immorlica , Yaron Singer
We consider the canonical problem of influence maximization in social networks. Since the seminal work of Kempe, Kleinberg, and Tardos, there have been two largely disjoint efforts on this problem. … We consider the canonical problem of influence maximization in social networks. Since the seminal work of Kempe, Kleinberg, and Tardos, there have been two largely disjoint efforts on this problem. The first studies the problem associated with learning the parameters of the generative influence model. The second focuses on the algorithmic challenge of identifying a set of influencers, assuming the parameters of the generative model are known. Recent results on learning and optimization imply that in general, if the generative model is not known but rather learned from training data, no algorithm can yield a constant factor approximation guarantee using polynomially-many samples, drawn from any distribution. In this paper, we design a simple heuristic that overcomes this negative result in practice by leveraging the strong community structure of social networks. Although in general the approximation guarantee of our algorithm is necessarily unbounded, we show that this algorithm performs well experimentally. To justify its performance, we prove our algorithm obtains a constant factor approximation guarantee on graphs generated through the stochastic block model, traditionally used to model networks with community structure.

On the Construction of Substitutes

2019-07-18
Eric Balkanski , Renato Paes Leme
Gross substitutability is a central concept in economics and is connected to important notions in discrete convex analysis, number theory, and the analysis of greedy algorithms in computer science. Many … Gross substitutability is a central concept in economics and is connected to important notions in discrete convex analysis, number theory, and the analysis of greedy algorithms in computer science. Many different characterizations are known for this class, but providing a constructive description remains a major open problem. The construction problem asks how to construct all gross substitutes from a class of simpler functions using a set of operations. Because gross substitutes are a natural generalization of matroids to real-valued functions, matroid rank functions form a desirable such class of simpler functions. Shioura proved that a rich class of gross substitutes can be expressed as sums of matroid rank functions, but it is open whether all gross substitutes can be constructed this way. Our main result is a negative answer showing that some gross substitutes cannot be expressed as positive linear combinations of matroid rank functions. En route, we provide necessary and sufficient conditions for the sum to preserve substitutability, uncover a new operation preserving substitutability, and fully describe all substitutes with at most four items.
View PDF Chat

On the Construction of Substitutes

2018-06-11
Eric Balkanski , Renato Paes Leme
Gross substitutability is a central concept in Economics and is connected to important notions in Discrete Convex Analysis, Number Theory and the analysis of Greedy algorithms in Computer Science. Many … Gross substitutability is a central concept in Economics and is connected to important notions in Discrete Convex Analysis, Number Theory and the analysis of Greedy algorithms in Computer Science. Many different characterizations are known for this class, but providing a constructive description remains a major open problem. The construction problem asks how to construct all gross substitutes from a class of simpler functions using a set of operations. Since gross substitutes are a natural generalization of matroids to real-valued functions, matroid rank functions form a desirable such class of simpler functions. Shioura proved that a rich class of gross substitutes can be expressed as sums of matroid rank functions, but it is open whether all gross substitutes can be constructed this way. Our main result is a negative answer showing that some gross substitutes cannot be expressed as positive linear combinations of matroid rank functions. En route, we provide necessary and sufficient conditions for the sum to preserve substitutability, uncover a new operation preserving substitutability and fully describe all substitutes with at most 4 items.
View PDF Chat

Bayesian Budget Feasibility with Posted Pricing

2015-06-12
Eric Balkanski , Jason D. Hartline
We consider the problem of budget feasible mechanism design proposed by Singer (2010), but in a Bayesian setting. A principal has a public value for hiring a subset of the … We consider the problem of budget feasible mechanism design proposed by Singer (2010), but in a Bayesian setting. A principal has a public value for hiring a subset of the agents and a budget, while the agents have private costs for being hired. We consider both additive and submodular value functions of the principal. We show that there are simple, practical, ex post budget balanced posted pricing mechanisms that approximate the value obtained by the Bayesian optimal mechanism that is budget balanced only in expectation. A main motivating application for this work is the crowdsourcing large projects, e.g., on Mechanical Turk, where workers are drawn from a large population and posted pricing is standard. Our analysis methods relate to contention resolution schemes in submodular optimization of Vondrak et al. (2011) and the correlation gap analysis of Yan (2011).

Adversarial Attacks on Binary Image Recognition Systems

2020-01-01
Eric Balkanski , Harrison Chase , Kojin Oshiba +3 more
We initiate the study of adversarial attacks on models for binary (i.e. black and white) image classification. Although there has been a great deal of work on attacking models for … We initiate the study of adversarial attacks on models for binary (i.e. black and white) image classification. Although there has been a great deal of work on attacking models for colored and grayscale images, little is known about attacks on models for binary images. Models trained to classify binary images are used in text recognition applications such as check processing, license plate recognition, invoice processing, and many others. In contrast to colored and grayscale images, the search space of attacks on binary images is extremely restricted and noise cannot be hidden with minor perturbations in each pixel. Thus, the optimization landscape of attacks on binary images introduces new fundamental challenges. In this paper we introduce a new attack algorithm called SCAR, designed to fool classifiers of binary images. We show that SCAR significantly outperforms existing $L_0$ attacks applied to the binary setting and use it to demonstrate the vulnerability of real-world text recognition systems. SCAR's strong performance in practice contrasts with the existence of classifiers that are provably robust to large perturbations. In many cases, altering a single pixel is sufficient to trick Tesseract, a popular open-source text recognition system, to misclassify a word as a different word in the English dictionary. We also license software from providers of check processing systems to most of the major US banks and demonstrate the vulnerability of check recognitions for mobile deposits. These systems are substantially harder to fool since they classify both the handwritten amounts in digits and letters, independently. Nevertheless, we generalize SCAR to design attacks that fool state-of-the-art check processing systems using unnoticeable perturbations that lead to misclassification of deposit amounts. Consequently, this is a powerful method to perform financial fraud.
View PDF Chat

The Power of Greedy for Online Minimum Cost Matching on the Line

2023-07-07
Eric Balkanski , Yuri Faenza , Noémie Périvier
In the online minimum cost matching problem, there are n servers and, at each of n time steps, a request arrives and must be irrevocably matched to a server that … In the online minimum cost matching problem, there are n servers and, at each of n time steps, a request arrives and must be irrevocably matched to a server that has not yet been matched, with the goal of minimizing the sum of the distances between the matched pairs. Online minimum cost matching is a central problem in applications such as ride-hailing platforms and food delivery services. Despite achieving a worst-case competitive ratio that is exponential in n even on the line, the simple greedy algorithm, which matches each request to its nearest available server, performs well in practice and has a number of attractive features such as strategyproofness. A major question is thus to explain greedy's strong empirical performance. In this paper, we aim to understand the performance of greedy on the line over instances that are at least partially random.
View PDF Chat

Scheduling with Speed Predictions

2024-05-09
Eric Balkanski , Tingting Ou , Clifford Stein +1 more
<title>Abstract</title> Algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, very recent work has … <title>Abstract</title> Algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, very recent work has leveraged machine-learned predictions to design algorithms that achieve improved approximation ratios in settings where the processing times of the jobs are initially unknown. In this paper, we study the speed-robust scheduling problem where the speeds of the machines, instead of the processing times of the jobs, are unknown and augment this problem with predictions. Our main result is an algorithm that achieves a $\min\{\eta^2(1+\alpha), (2 + 2/\alpha)\}$ approximation, for any $\alpha \in (0,1)$, where $\eta \geq 1$ is the prediction error. When the predictions are accurate, this approximation outperforms the best known approximation for speed-robust scheduling without predictions of $2-1/m$, where $m$ is the number of machines, while simultaneously maintaining a worst-case approximation of $2 + 2/\alpha$ even when the predictions are arbitrarily wrong. In addition, we obtain improved approximations for three special cases: equal job sizes, infinitesimal job sizes, and binary machine speeds. We also complement our algorithmic results with lower bounds. Finally, we empirically evaluate our algorithm against existing algorithms for speed-robust scheduling.
View PDF Chat

The Limitations of Optimization from Samples

2022-05-11
Eric Balkanski , Aviad Rubinstein , Yaron Singer
In this article, we consider the following question: Can we optimize objective functions from the training data we use to learn them? We formalize this question through a novel framework … In this article, we consider the following question: Can we optimize objective functions from the training data we use to learn them? We formalize this question through a novel framework we call optimization from samples ( OPS ). In OPS , we are given sampled values of a function drawn from some distribution and the objective is to optimize the function under some constraint. While there are interesting classes of functions that can be optimized from samples, our main result is an impossibility. We show that there are classes of functions that are statistically learnable and optimizable, but for which no reasonable approximation for optimization from samples is achievable. In particular, our main result shows that there is no constant factor approximation for maximizing coverage functions under a cardinality constraint using polynomially-many samples drawn from any distribution. We also show tight approximation guarantees for maximization under a cardinality constraint of several interesting classes of functions including unit-demand, additive, and general monotone submodular functions, as well as a constant factor approximation for monotone submodular functions with bounded curvature.
View PDF Chat

Instance Specific Approximations for Submodular Maximization

2021-01-01
Eric Balkanski , Sharon Qian , Yaron Singer
For many optimization problems in machine learning, finding an optimal solution is computationally intractable and we seek algorithms that perform well in practice. Since computational intractability often results from pathological … For many optimization problems in machine learning, finding an optimal solution is computationally intractable and we seek algorithms that perform well in practice. Since computational intractability often results from pathological instances, we look for methods to benchmark the performance of algorithms against optimal solutions on real-world instances. The main challenge is that an optimal solution cannot be efficiently computed for intractable problems, and we therefore often do not know how far a solution is from being optimal. A major question is therefore how to measure the performance of an algorithm in comparison to an optimal solution on instances we encounter in practice. In this paper, we address this question in the context of submodular optimization problems. For the canonical problem of submodular maximization under a cardinality constraint, it is intractable to compute a solution that is better than a $1-1/e \approx 0.63$ fraction of the optimum. Algorithms like the celebrated greedy algorithm are guaranteed to achieve this $1-1/e$ bound on any instance and are used in practice. Our main contribution is not a new algorithm for submodular maximization but an analytical method that measures how close an algorithm for submodular maximization is to optimal on a given problem instance. We use this method to show that on a wide variety of real-world datasets and objectives, the approximation of the solution found by greedy goes well beyond $1-1/e$ and is often at least 0.95. We develop this method using a novel technique that lower bounds the objective of a dual minimization problem to obtain an upper bound on the value of an optimal solution to the primal maximization problem.

Secretary Ranking with Minimal Inversions

2018-01-01
Sepehr Assadi , Eric Balkanski , Renato Paes Leme
We study a twist on the classic secretary problem, which we term the secretary ranking problem: elements from an ordered set arrive in random order and instead of picking the … We study a twist on the classic secretary problem, which we term the secretary ranking problem: elements from an ordered set arrive in random order and instead of picking the maximum element, the algorithm is asked to assign a rank, or position, to each of the elements. The rank assigned is irrevocable and is given knowing only the pairwise comparisons with elements previously arrived. The goal is to minimize the distance of the rank produced to the true rank of the elements measured by the Kendall-Tau distance, which corresponds to the number of pairs that are inverted with respect to the true order. Our main result is a matching upper and lower bound for the secretary ranking problem. We present an algorithm that ranks $n$ elements with only $O(n^{3/2})$ inversions in expectation, and show that any algorithm necessarily suffers $\Omega(n^{3/2})$ inversions when there are $n$ available positions. In terms of techniques, the analysis of our algorithm draws connections to linear probing in the hashing literature, while our lower bound result relies on a general anti-concentration bound for a generic balls and bins sampling process. We also consider the case where the number of positions $m$ can be larger than the number of secretaries $n$ and provide an improved bound by showing a connection of this problem with random binary trees.
View PDF Chat

An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model

2018-01-01
Eric Balkanski , Aviad Rubinstein , Yaron Singer
In this paper we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization in [BS18a] to … In this paper we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization in [BS18a] to quantify the information theoretic complexity of black-box optimization in a parallel computation model. Informally, the adaptivity of an algorithm is the number of sequential rounds it makes when each round can execute polynomially-many function evaluations in parallel. Since submodular optimization is regularly applied on large datasets we seek algorithms with low adaptivity to enable speedups via parallelization. Consequently, a recent line of work has been devoted to designing constant factor approximation algorithms for maximizing submodular functions under various constraints in the adaptive complexity model [BS18a, BS18b, BBS18, BRS19, EN19, FMZ19, CQ19, ENV18, FMZ18]. Despite the burst in work on submodular maximization in the adaptive complexity model the fundamental problem of maximizing a monotone submodular function under a matroid constraint has remained elusive. In particular, all known techniques fail for this problem and there are no known constant factor approximation algorithms whose adaptivity is sublinear in the rank of the matroid $k$ or in the worst case sublinear in the size of the ground set $n$. In this paper we present an approximation algorithm for the problem of maximizing a monotone submodular function under a matroid constraint in the adaptive complexity model. The approximation guarantee of the algorithm is arbitrarily close to the optimal $1-1/e$ and it has near optimal adaptivity of $O(\log(n)\log(k))$. This result is obtained using a novel technique of adaptive sequencing which departs from previous techniques for submodular maximization in the adaptive complexity model.

Strategyproof Scheduling with Predictions

2022-01-01
Eric Balkanski , Vasilis Gkatzelis , Xizhi Tan
In their seminal paper that initiated the field of algorithmic mechanism design, \citet{NR99} studied the problem of designing strategyproof mechanisms for scheduling jobs on unrelated machines aiming to minimize the … In their seminal paper that initiated the field of algorithmic mechanism design, \citet{NR99} studied the problem of designing strategyproof mechanisms for scheduling jobs on unrelated machines aiming to minimize the makespan. They provided a strategyproof mechanism that achieves an $n$-approximation and they made the bold conjecture that this is the best approximation achievable by any deterministic strategyproof scheduling mechanism. After more than two decades and several efforts, $n$ remains the best known approximation and very recent work by \citet{CKK21} has been able to prove an $\Omega(\sqrt{n})$ approximation lower bound for all deterministic strategyproof mechanisms. This strong negative result, however, heavily depends on the fact that the performance of these mechanisms is evaluated using worst-case analysis. To overcome such overly pessimistic, and often uninformative, worst-case bounds, a surge of recent work has focused on the ``learning-augmented framework'', whose goal is to leverage machine-learned predictions to obtain improved approximations when these predictions are accurate (consistency), while also achieving near-optimal worst-case approximations even when the predictions are arbitrarily wrong (robustness). In this work, we study the classic strategic scheduling problem of~\citet{NR99} using the learning-augmented framework and give a deterministic polynomial-time strategyproof mechanism that is $6$-consistent and $2n$-robust. We thus achieve the ``best of both worlds'': an $O(1)$ consistency and an $O(n)$ robustness that asymptotically matches the best-known approximation. We then extend this result to provide more general worst-case approximation guarantees as a function of the prediction error. Finally, we complement our positive results by showing that any $1$-consistent deterministic strategyproof mechanism has unbounded robustness.
View PDF Chat

Bayesian Budget Feasibility with Posted Pricing

2015-01-01
Eric Balkanski , Jason D. Hartline
We consider the problem of budget feasible mechanism design proposed by Singer (2010), but in a Bayesian setting. A principal has a public value for hiring a subset of the … We consider the problem of budget feasible mechanism design proposed by Singer (2010), but in a Bayesian setting. A principal has a public value for hiring a subset of the agents and a budget, while the agents have private costs for being hired. We consider both additive and submodular value functions of the principal. We show that there are simple, practical, ex post budget balanced posted pricing mechanisms that approximate the value obtained by the Bayesian optimal mechanism that is budget balanced only in expectation. A main motivating application for this work is the crowdsourcing large projects, e.g., on Mechanical Turk, where workers are drawn from a large population and posted pricing is standard. Our analysis methods relate to contention resolution schemes in submodular optimization of Vondrak et al. (2011) and the correlation gap analysis of Yan (2011).
View PDF Chat

An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation

2018-01-01
Eric Balkanski , Aviad Rubinstein , Yaron Singer
In this paper we study the adaptivity of submodular maximization. Adaptivity quantifies the number of sequential rounds that an algorithm makes when function evaluations can be executed in parallel. Adaptivity … In this paper we study the adaptivity of submodular maximization. Adaptivity quantifies the number of sequential rounds that an algorithm makes when function evaluations can be executed in parallel. Adaptivity is a fundamental concept that is heavily studied across a variety of areas in computer science, largely due to the need for parallelizing computation. For the canonical problem of maximizing a monotone submodular function under a cardinality constraint, it is well known that a simple greedy algorithm achieves a $1-1/e$ approximation and that this approximation is optimal for polynomial-time algorithms. Somewhat surprisingly, despite extensive efforts on submodular optimization for large-scale datasets, until very recently there was no known algorithm that achieves a constant factor approximation for this problem whose adaptivity is sublinear in the size of the ground set $n$. Recent work by Balkanski and Singer describes an algorithm that obtains an approximation arbitrarily close to $1/3$ in $\mathcal{O}(\log n)$ adaptive rounds and shows that no algorithm can obtain a constant factor approximation in $\tilde{o}(\log n)$ adaptive rounds. This approach achieves an exponential speedup in adaptivity (and parallel running time) at the expense of approximation quality. In this paper we describe a novel approach that yields an algorithm whose approximation is arbitrarily close to the optimal $1-1/e$ guarantee in $\mathcal{O}(\log n)$ adaptive rounds. This algorithm therefore achieves an exponential speedup in parallel running time for submodular maximization at the expense of an arbitrarily small loss in approximation quality. This guarantee is optimal in both approximation and adaptivity, up to lower order terms.
View PDF Chat

Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location

2023-12-27
Priyank Agrawal , Eric Balkanski , Vasilis Gkatzelis +2 more
In this work, we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in “learning-augmented algorithms.” Aiming to … In this work, we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in “learning-augmented algorithms.” Aiming to complement the traditional worst-case analysis approach in computer science, this line of work has focused on the design and analysis of algorithms that are enhanced with machine-learned predictions. The algorithms can use the predictions as a guide to inform their decisions, aiming to achieve much stronger performance guarantees when these predictions are accurate (consistency), while also maintaining near-optimal worst-case guarantees, even if these predictions are inaccurate (robustness). We initiate the design and analysis of strategyproof mechanisms that are augmented with predictions regarding the private information of the participating agents. To exhibit the important benefits of this approach, we revisit the canonical problem of facility location with strategic agents in the two-dimensional Euclidean space. We study both the egalitarian and utilitarian social cost functions, and we propose new strategyproof mechanisms that leverage predictions to guarantee an optimal trade-off between consistency and robustness. Furthermore, we also prove parameterized approximation results as a function of the prediction error, showing that our mechanisms perform well, even when the predictions are not fully accurate. Funding: The work of E. Balkanski was supported in part by the National Science Foundation [Grants CCF-2210501 and IIS-2147361]. The work of V. Gkatzelis and X. Tan was supported in part by the National Science Foundation [Grant CCF-2210502] and [CAREER Award CCF-2047907].
View PDF Chat

Energy-Efficient Scheduling with Predictions

2024-02-26
Eric Balkanski , Noémie Périvier , Clifford Stein +1 more
An important goal of modern scheduling systems is to efficiently manage power usage. In energy-efficient scheduling, the operating system controls the speed at which a machine is processing jobs with … An important goal of modern scheduling systems is to efficiently manage power usage. In energy-efficient scheduling, the operating system controls the speed at which a machine is processing jobs with the dual objective of minimizing energy consumption and optimizing the quality of service cost of the resulting schedule. Since machine-learned predictions about future requests can often be learned from historical data, a recent line of work on learning-augmented algorithms aims to achieve improved performance guarantees by leveraging predictions. In particular, for energy-efficient scheduling, Bamas et. al. [BamasMRS20] and Antoniadis et. al. [antoniadis2021novel] designed algorithms with predictions for the energy minimization with deadlines problem and achieved an improved competitive ratio when the prediction error is small while also maintaining worst-case bounds even when the prediction error is arbitrarily large. In this paper, we consider a general setting for energy-efficient scheduling and provide a flexible learning-augmented algorithmic framework that takes as input an offline and an online algorithm for the desired energy-efficient scheduling problem. We show that, when the prediction error is small, this framework gives improved competitive ratios for many different energy-efficient scheduling problems, including energy minimization with deadlines, while also maintaining a bounded competitive ratio regardless of the prediction error. Finally, we empirically demonstrate that this framework achieves an improved performance on real and synthetic datasets.
View PDF Chat

Mechanism Design with Predictions: An Annotated Reading List

2023-06-01
Eric Balkanski , Vasilis Gkatzelis , Xizhi Tan
A surge of recent work has focused on analyzing the performance of algorithms guided by predictions, aiming to enhance their worst-case performance guarantees with improved guarantees when the predictions are … A surge of recent work has focused on analyzing the performance of algorithms guided by predictions, aiming to enhance their worst-case performance guarantees with improved guarantees when the predictions are accurate. This "learning-augmented" framework was recently also extended to mechanism design settings involving strategic agents and we provide an overview of these results.

On the Construction of Substitutes

2018-05-09
Eric Balkanski , Renato Paes Leme
Gross substitutability is a central concept in Economics and is connected to important notions in Discrete Convex Analysis, Number Theory and the analysis of Greedy algorithms in Computer Science. Many … Gross substitutability is a central concept in Economics and is connected to important notions in Discrete Convex Analysis, Number Theory and the analysis of Greedy algorithms in Computer Science. Many different characterizations are known for this class, but providing a constructive description remains a major open problem. The construction problem asks how to construct all gross substitutes from a class of simpler functions using a set of operations. Since gross substitutes are a natural generalization of matroids to real-valued functions, matroid rank functions form a desirable such class of simpler functions. Shioura proved that a rich class of gross substitutes can be expressed as sums of matroid rank functions, but it is open whether all gross substitutes can be constructed this way. Our main result is a negative answer showing that some gross substitutes cannot be expressed as positive linear combinations of matroid rank functions. En route, we provide necessary and sufficient conditions for the sum to preserve substitutability, uncover a new operation preserving substitutability and fully describe all substitutes with at most 4 items.

Dynamic First Price Auctions Robust to Heterogeneous Buyers

2019-01-01
Shipra Agrawal , Eric Balkanski , Vahab Mirrokni +1 more
We study dynamic mechanisms for optimizing revenue in repeated auctions, that are robust to heterogeneous forward-looking and learning behavior of the buyers. Typically it is assumed that the buyers are … We study dynamic mechanisms for optimizing revenue in repeated auctions, that are robust to heterogeneous forward-looking and learning behavior of the buyers. Typically it is assumed that the buyers are either all myopic or are all infinite lookahead, and that buyers understand and trust the mechanism. These assumptions raise the following question: is it possible to design approximately revenue optimal mechanisms when the buyer pool is heterogeneous? Facing a heterogeneous population of buyers with an unknown mixture of $k$-lookahead buyers, myopic buyers, no-regret-learners and no-policy-regret learners, we design a simple state-based mechanism that achieves a constant fraction of the optimal achievable revenue.

Deterministic Budget-Feasible Clock Auctions

2021-01-01
Eric Balkanski , Pranav Garimidi , Vasilis Gkatzelis +2 more
We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the … We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the last decade, several strategyproof budget-feasible procurement auctions have been proposed, aiming to maximize the value of the buyer, while eliciting each seller's true cost for providing their service. These solutions predominantly take the form of randomized sealed-bid auctions: they ask the sellers to report their private costs and then use randomization to determine which subset of services will be procured and how much each of the chosen providers will be paid, ensuring that the total payment does not exceed budget. Our main result in this paper is a novel method for designing budget-feasible auctions, leading to solutions that outperform the previously proposed auctions in multiple ways. First, our solutions take the form of descending clock auctions, and thus satisfy a list of properties, such as obvious strategyproofness, group strategyproofness, transparency, and unconditional winner privacy; this makes these auctions much more likely to be used in practice. Second, in contrast to previous results that heavily depend on randomization, our auctions are deterministic. As a result, we provide an affirmative answer to one of the main open questions in this literature, asking whether a deterministic strategyproof auction can achieve a constant approximation when the buyer's valuation function is submodular over the set of services. In addition, we also provide the first deterministic budget-feasible auction that matches the approximation bound of the best-known randomized auction for the class of subadditive valuations. Finally, using our method, we improve the best-known approximation factor for monotone submodular valuations, which has been the focus of most of the prior work.

Learning Low Degree Hypergraphs

2022-01-01
Eric Balkanski , Oussama Hanguir , Shatian Wang
We study the problem of learning a hypergraph via edge detecting queries. In this problem, a learner queries subsets of vertices of a hidden hypergraph and observes whether these subsets … We study the problem of learning a hypergraph via edge detecting queries. In this problem, a learner queries subsets of vertices of a hidden hypergraph and observes whether these subsets contain an edge or not. In general, learning a hypergraph with $m$ edges of maximum size $d$ requires $\Omega((2m/d)^{d/2})$ queries. In this paper, we aim to identify families of hypergraphs that can be learned without suffering from a query complexity that grows exponentially in the size of the edges. We show that hypermatchings and low-degree near-uniform hypergraphs with $n$ vertices are learnable with poly$(n)$ queries. For learning hypermatchings (hypergraphs of maximum degree $ 1$), we give an $O(\log^3 n)$-round algorithm with $O(n \log^5 n)$ queries. We complement this upper bound by showing that there are no algorithms with poly$(n)$ queries that learn hypermatchings in $o(\log \log n)$ adaptive rounds. For hypergraphs with maximum degree $\Delta$ and edge size ratio $\rho$, we give a non-adaptive algorithm with $O((2n)^{\rho \Delta+1}\log^2 n)$ queries. To the best of our knowledge, these are the first algorithms with poly$(n, m)$ query complexity for learning non-trivial families of hypergraphs that have a super-constant number of edges of super-constant size.
View PDF Chat

Scheduling with Speed Predictions

2022-01-01
Eric Balkanski , Tingting Ou , Clifford Stein +1 more
Algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, very recent work has leveraged … Algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, very recent work has leveraged machine-learned predictions to design algorithms that achieve improved approximation ratios in settings where the processing times of the jobs are initially unknown. In this paper, we study the speed-robust scheduling problem where the speeds of the machines, instead of the processing times of the jobs, are unknown and augment this problem with predictions. Our main result is an algorithm that achieves a $\min\{\eta^2(1+\alpha), (2 + 2/\alpha)\}$ approximation, for any $\alpha \in (0,1)$, where $\eta \geq 1$ is the prediction error. When the predictions are accurate, this approximation outperforms the best known approximation for speed-robust scheduling without predictions of $2-1/m$, where $m$ is the number of machines, while simultaneously maintaining a worst-case approximation of $2 + 2/\alpha$ even when the predictions are arbitrarily wrong. In addition, we obtain improved approximations for three special cases: equal job sizes, infinitesimal job sizes, and binary machine speeds. We also complement our algorithmic results with lower bounds. Finally, we empirically evaluate our algorithm against existing algorithms for speed-robust scheduling.
View PDF Chat

Adversarial Attacks on Binary Image Recognition Systems

2020-10-22
Eric Balkanski , Harrison Chase , Kojin Oshiba +3 more
We initiate the study of adversarial attacks on models for binary (i.e. black and white) image classification. Although there has been a great deal of work on attacking models for … We initiate the study of adversarial attacks on models for binary (i.e. black and white) image classification. Although there has been a great deal of work on attacking models for colored and grayscale images, little is known about attacks on models for binary images. Models trained to classify binary images are used in text recognition applications such as check processing, license plate recognition, invoice processing, and many others. In contrast to colored and grayscale images, the search space of attacks on binary images is extremely restricted and noise cannot be hidden with minor perturbations in each pixel. Thus, the optimization landscape of attacks on binary images introduces new fundamental challenges. In this paper we introduce a new attack algorithm called SCAR, designed to fool classifiers of binary images. We show that SCAR significantly outperforms existing $L_0$ attacks applied to the binary setting and use it to demonstrate the vulnerability of real-world text recognition systems. SCAR's strong performance in practice contrasts with the existence of classifiers that are provably robust to large perturbations. In many cases, altering a single pixel is sufficient to trick Tesseract, a popular open-source text recognition system, to misclassify a word as a different word in the English dictionary. We also license software from providers of check processing systems to most of the major US banks and demonstrate the vulnerability of check recognitions for mobile deposits. These systems are substantially harder to fool since they classify both the handwritten amounts in digits and letters, independently. Nevertheless, we generalize SCAR to design attacks that fool state-of-the-art check processing systems using unnoticeable perturbations that lead to misclassification of deposit amounts. Consequently, this is a powerful method to perform financial fraud.
View PDF Chat

Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location

2022-01-01
Priyank Agrawal , Eric Balkanski , Vasilis Gkatzelis +2 more
In this work we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in "learning-augmented algorithms". Aiming to … In this work we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in "learning-augmented algorithms". Aiming to complement the traditional approach in computer science, which analyzes the performance of algorithms based on worst-case instances, this line of work has focused on the design and analysis of algorithms that are enhanced with machine-learned predictions regarding the optimal solution. The algorithms can use the predictions as a guide to inform their decisions, and the goal is to achieve much stronger performance guarantees when these predictions are accurate (consistency), while also maintaining near-optimal worst-case guarantees, even if these predictions are very inaccurate (robustness). So far, these results have been limited to algorithms, but in this work we argue that another fertile ground for this framework is in mechanism design. We initiate the design and analysis of strategyproof mechanisms that are augmented with predictions regarding the private information of the participating agents. To exhibit the important benefits of this approach, we revisit the canonical problem of facility location with strategic agents in the two-dimensional Euclidean space. We study both the egalitarian and utilitarian social cost functions, and we propose new strategyproof mechanisms that leverage predictions to guarantee an optimal trade-off between consistency and robustness guarantees. This provides the designer with a menu of mechanism options to choose from, depending on her confidence regarding the prediction accuracy. Furthermore, we also prove parameterized approximation results as a function of the prediction error, showing that our mechanisms perform well even when the predictions are not fully accurate.
View PDF Chat

The Limitations of Optimization from Samples

2015-01-01
Eric Balkanski , Aviad Rubinstein , Yaron Singer
In this paper we consider the following question: can we optimize objective functions from the training data we use to learn them? We formalize this question through a novel framework … In this paper we consider the following question: can we optimize objective functions from the training data we use to learn them? We formalize this question through a novel framework we call optimization from samples (OPS). In OPS, we are given sampled values of a function drawn from some distribution and the objective is to optimize the function under some constraint. While there are interesting classes of functions that can be optimized from samples, our main result is an impossibility. We show that there are classes of functions which are statistically learnable and optimizable, but for which no reasonable approximation for optimization from samples is achievable. In particular, our main result shows that there is no constant factor approximation for maximizing coverage functions under a cardinality constraint using polynomially-many samples drawn from any distribution. We also show tight approximation guarantees for maximization under a cardinality constraint of several interesting classes of functions including unit-demand, additive, and general monotone submodular functions, as well as a constant factor approximation for monotone submodular functions with bounded curvature.
View PDF Chat

On the Construction of Substitutes

2018-01-01
Eric Balkanski , Renato Paes Leme
Gross substitutability is a central concept in Economics and is connected to important notions in Discrete Convex Analysis, Number Theory and the analysis of Greedy algorithms in Computer Science. Many … Gross substitutability is a central concept in Economics and is connected to important notions in Discrete Convex Analysis, Number Theory and the analysis of Greedy algorithms in Computer Science. Many different characterizations are known for this class, but providing a constructive description remains a major open problem. The construction problem asks how to construct all gross substitutes from a class of simpler functions using a set of operations. Since gross substitutes are a natural generalization of matroids to real-valued functions, matroid rank functions form a desirable such class of simpler functions. Shioura proved that a rich class of gross substitutes can be expressed as sums of matroid rank functions, but it is open whether all gross substitutes can be constructed this way. Our main result is a negative answer showing that some gross substitutes cannot be expressed as positive linear combinations of matroid rank functions. En route, we provide necessary and sufficient conditions for the sum to preserve substitutability, uncover a new operation preserving substitutability and fully describe all substitutes with at most 4 items.
View PDF Chat

Online Mechanism Design with Predictions

2023-01-01
Eric Balkanski , Vasilis Gkatzelis , Xizhi Tan +1 more
Aiming to overcome some of the limitations of worst-case analysis, the recently proposed framework of "algorithms with predictions" allows algorithms to be augmented with a (possibly erroneous) machine-learned prediction that … Aiming to overcome some of the limitations of worst-case analysis, the recently proposed framework of "algorithms with predictions" allows algorithms to be augmented with a (possibly erroneous) machine-learned prediction that they can use as a guide. In this framework, the goal is to obtain improved guarantees when the prediction is correct, which is called \emph{consistency}, while simultaneously guaranteeing some worst-case bounds even when the prediction is arbitrarily wrong, which is called \emph{robustness}. The vast majority of the work on this framework has focused on a refined analysis of online algorithms augmented with predictions regarding the future input. A subsequent line of work has also successfully adapted this framework to mechanism design, where the prediction is regarding the private information of strategic agents. In this paper, we initiate the study of online mechanism design with predictions, which combines the challenges of online algorithms with predictions and mechanism design with predictions. We consider the well-studied problem of designing a revenue-maximizing auction to sell a single item to strategic bidders who arrive and depart over time, each with an unknown, private, value for the item. We study the learning-augmented version of this problem where the auction designer is given a prediction regarding the maximum value over all agents. Our main result is a strategyproof mechanism whose revenue guarantees are $\alpha$-consistent with respect to the highest value and $(1-\alpha^2)/4$-robust with respect to the second-highest value, for $\alpha \in [0,1]$. We show that this tradeoff is optimal within a broad and natural family of auctions, meaning that any $\alpha$-consistent mechanism in that family has robustness at most $(1-\alpha^2)/4$. Finally, we extend our mechanism to also achieve expected revenues proportional to the prediction quality.
View PDF Chat

Learning-Augmented Dynamic Submodular Maximization

2023-01-01
Arpit Agarwal , Eric Balkanski
In dynamic submodular maximization, the goal is to maintain a high-value solution over a sequence of element insertions and deletions with a fast update time. Motivated by large-scale applications and … In dynamic submodular maximization, the goal is to maintain a high-value solution over a sequence of element insertions and deletions with a fast update time. Motivated by large-scale applications and the fact that dynamic data often exhibits patterns, we ask the following question: can predictions be used to accelerate the update time of dynamic submodular maximization algorithms? We consider the model for dynamic algorithms with predictions where predictions regarding the insertion and deletion times of elements can be used for preprocessing. Our main result is an algorithm with an $O(poly(\log \eta, \log w, \log k))$ amortized update time over the sequence of updates that achieves a $1/2 - \epsilon$ approximation in expectation for dynamic monotone submodular maximization under a cardinality constraint $k$, where the prediction error $\eta$ is the number of elements that are not inserted and deleted within $w$ time steps of their predicted insertion and deletion times. This amortized update time is independent of the length of the stream and instead depends on the prediction error.

Submodular Maximization in Exactly $n$ Queries

2024-05-31
Eric Balkanski , Steven DiSilvio , Alan Kuhnle
In this work, we study the classical problem of maximizing a submodular function subject to a matroid constraint. We develop deterministic algorithms that are very parsimonious with respect to querying … In this work, we study the classical problem of maximizing a submodular function subject to a matroid constraint. We develop deterministic algorithms that are very parsimonious with respect to querying the submodular function, for both the case when the submodular function is monotone and the general submodular case. In particular, we present a 1/4 approximation algorithm for the monotone case that uses exactly one query per element, which gives the same total number of queries n as the number of queries required to compute the maximum singleton. For the general case, we present a constant factor approximation algorithm that requires 2 queries per element, which is the first algorithm for this problem with linear query complexity in the size of the ground set.
View PDF Chat

An Algorithm for the Assignment Game Beyond Additive Valuations

2024-06-19
Eric Balkanski , Christopher En , Yuri Faenza
The assignment game, introduced by Shapley and Shubik (1971), is a classic model for two-sided matching markets between buyers and sellers. In the original assignment game, it is assumed that … The assignment game, introduced by Shapley and Shubik (1971), is a classic model for two-sided matching markets between buyers and sellers. In the original assignment game, it is assumed that payments lead to transferable utility and that buyers have unit-demand valuations for the items being sold. Two important and mostly independent lines of work have studied more general settings with imperfectly transferable utility and gross substitutes valuations. Multiple efficient algorithms have been proposed for computing a competitive equilibrium, the standard solution concept in assignment games, in these two settings. Our main result is an efficient algorithm for computing competitive equilibria in a setting with both imperfectly transferable utility and gross substitutes valuations. Our algorithm combines augmenting path techniques from maximum matching and algorithms for matroid intersection. We also show that, in a mild generalization of our model, computing a competitive equilibrium is NP-hard.
View PDF Chat

Randomized Strategic Facility Location with Predictions

2024-09-11
Eric Balkanski , Vasilis Gkatzelis , Golnoosh Shahkarami
We revisit the canonical problem of strategic facility location and study the power and limitations of randomization in the design of truthful mechanisms augmented with machine-learned predictions. In the strategic … We revisit the canonical problem of strategic facility location and study the power and limitations of randomization in the design of truthful mechanisms augmented with machine-learned predictions. In the strategic facility location problem, a set of agents are asked to report their locations in some metric space and the goal is to use these reported locations to determine where to open a new facility, aiming to optimize some aggregate measure of distance of the agents from that facility. However, the agents are strategic and can misreport their locations if this may lead to a facility location choice that they prefer. The goal is to design truthful mechanisms, which ensure the agents cannot benefit by misreporting. A lot of prior work has studied this problem from a worst-case perspective, but a recent line of work proposed a framework to refine these results when the designer is provided with some, potentially very inaccurate, predictions regarding the agents' true locations. The goal is to simultaneously provide strong consistency guarantees (i.e., guarantees when the predictions provided to the mechanism are correct) and near-optimal robustness guarantees (i.e., guarantees that hold irrespective of how inaccurate the predictions may be). In this work we focus on the power of randomization in this problem and analyze the best approximation guarantees achievable with respect to the egalitarian social cost measure for one- and two-dimensional Euclidean spaces.
View PDF Chat

An Algorithm for the Assignment Game Beyond Additive Valuations

2024-07-08
Eric Balkanski , Christopher En , Yuri Faenza
View PDF Chat

Online Mechanism Design with Predictions

2024-07-08
Eric Balkanski , Vasilis Gkatzelis , Xizhi Tan +1 more
View PDF Chat

Randomized Strategic Facility Location with Predictions

2024-09-11
Eric Balkanski , Vasilis Gkatzelis , Golnoosh Shahkarami
We revisit the canonical problem of strategic facility location and study the power and limitations of randomization in the design of truthful mechanisms augmented with machine-learned predictions. In the strategic … We revisit the canonical problem of strategic facility location and study the power and limitations of randomization in the design of truthful mechanisms augmented with machine-learned predictions. In the strategic facility location problem, a set of agents are asked to report their locations in some metric space and the goal is to use these reported locations to determine where to open a new facility, aiming to optimize some aggregate measure of distance of the agents from that facility. However, the agents are strategic and can misreport their locations if this may lead to a facility location choice that they prefer. The goal is to design truthful mechanisms, which ensure the agents cannot benefit by misreporting. A lot of prior work has studied this problem from a worst-case perspective, but a recent line of work proposed a framework to refine these results when the designer is provided with some, potentially very inaccurate, predictions regarding the agents' true locations. The goal is to simultaneously provide strong consistency guarantees (i.e., guarantees when the predictions provided to the mechanism are correct) and near-optimal robustness guarantees (i.e., guarantees that hold irrespective of how inaccurate the predictions may be). In this work we focus on the power of randomization in this problem and analyze the best approximation guarantees achievable with respect to the egalitarian social cost measure for one- and two-dimensional Euclidean spaces.
View PDF Chat

An Algorithm for the Assignment Game Beyond Additive Valuations

2024-07-08
Eric Balkanski , Christopher En , Yuri Faenza
View PDF Chat

Online Mechanism Design with Predictions

2024-07-08
Eric Balkanski , Vasilis Gkatzelis , Xizhi Tan +1 more
View PDF Chat

An Algorithm for the Assignment Game Beyond Additive Valuations

2024-06-19
Eric Balkanski , Christopher En , Yuri Faenza
The assignment game, introduced by Shapley and Shubik (1971), is a classic model for two-sided matching markets between buyers and sellers. In the original assignment game, it is assumed that … The assignment game, introduced by Shapley and Shubik (1971), is a classic model for two-sided matching markets between buyers and sellers. In the original assignment game, it is assumed that payments lead to transferable utility and that buyers have unit-demand valuations for the items being sold. Two important and mostly independent lines of work have studied more general settings with imperfectly transferable utility and gross substitutes valuations. Multiple efficient algorithms have been proposed for computing a competitive equilibrium, the standard solution concept in assignment games, in these two settings. Our main result is an efficient algorithm for computing competitive equilibria in a setting with both imperfectly transferable utility and gross substitutes valuations. Our algorithm combines augmenting path techniques from maximum matching and algorithms for matroid intersection. We also show that, in a mild generalization of our model, computing a competitive equilibrium is NP-hard.
View PDF Chat

Submodular Maximization in Exactly $n$ Queries

2024-05-31
Eric Balkanski , Steven DiSilvio , Alan Kuhnle
In this work, we study the classical problem of maximizing a submodular function subject to a matroid constraint. We develop deterministic algorithms that are very parsimonious with respect to querying … In this work, we study the classical problem of maximizing a submodular function subject to a matroid constraint. We develop deterministic algorithms that are very parsimonious with respect to querying the submodular function, for both the case when the submodular function is monotone and the general submodular case. In particular, we present a 1/4 approximation algorithm for the monotone case that uses exactly one query per element, which gives the same total number of queries n as the number of queries required to compute the maximum singleton. For the general case, we present a constant factor approximation algorithm that requires 2 queries per element, which is the first algorithm for this problem with linear query complexity in the size of the ground set.
View PDF Chat

Scheduling with Speed Predictions

2024-05-09
Eric Balkanski , Tingting Ou , Clifford Stein +1 more
<title>Abstract</title> Algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, very recent work has … <title>Abstract</title> Algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, very recent work has leveraged machine-learned predictions to design algorithms that achieve improved approximation ratios in settings where the processing times of the jobs are initially unknown. In this paper, we study the speed-robust scheduling problem where the speeds of the machines, instead of the processing times of the jobs, are unknown and augment this problem with predictions. Our main result is an algorithm that achieves a $\min\{\eta^2(1+\alpha), (2 + 2/\alpha)\}$ approximation, for any $\alpha \in (0,1)$, where $\eta \geq 1$ is the prediction error. When the predictions are accurate, this approximation outperforms the best known approximation for speed-robust scheduling without predictions of $2-1/m$, where $m$ is the number of machines, while simultaneously maintaining a worst-case approximation of $2 + 2/\alpha$ even when the predictions are arbitrarily wrong. In addition, we obtain improved approximations for three special cases: equal job sizes, infinitesimal job sizes, and binary machine speeds. We also complement our algorithmic results with lower bounds. Finally, we empirically evaluate our algorithm against existing algorithms for speed-robust scheduling.
View PDF Chat

Energy-Efficient Scheduling with Predictions

2024-02-26
Eric Balkanski , Noémie Périvier , Clifford Stein +1 more
An important goal of modern scheduling systems is to efficiently manage power usage. In energy-efficient scheduling, the operating system controls the speed at which a machine is processing jobs with … An important goal of modern scheduling systems is to efficiently manage power usage. In energy-efficient scheduling, the operating system controls the speed at which a machine is processing jobs with the dual objective of minimizing energy consumption and optimizing the quality of service cost of the resulting schedule. Since machine-learned predictions about future requests can often be learned from historical data, a recent line of work on learning-augmented algorithms aims to achieve improved performance guarantees by leveraging predictions. In particular, for energy-efficient scheduling, Bamas et. al. [BamasMRS20] and Antoniadis et. al. [antoniadis2021novel] designed algorithms with predictions for the energy minimization with deadlines problem and achieved an improved competitive ratio when the prediction error is small while also maintaining worst-case bounds even when the prediction error is arbitrarily large. In this paper, we consider a general setting for energy-efficient scheduling and provide a flexible learning-augmented algorithmic framework that takes as input an offline and an online algorithm for the desired energy-efficient scheduling problem. We show that, when the prediction error is small, this framework gives improved competitive ratios for many different energy-efficient scheduling problems, including energy minimization with deadlines, while also maintaining a bounded competitive ratio regardless of the prediction error. Finally, we empirically demonstrate that this framework achieves an improved performance on real and synthetic datasets.
View PDF Chat

Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location

2023-12-27
Priyank Agrawal , Eric Balkanski , Vasilis Gkatzelis +2 more
In this work, we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in “learning-augmented algorithms.” Aiming to … In this work, we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in “learning-augmented algorithms.” Aiming to complement the traditional worst-case analysis approach in computer science, this line of work has focused on the design and analysis of algorithms that are enhanced with machine-learned predictions. The algorithms can use the predictions as a guide to inform their decisions, aiming to achieve much stronger performance guarantees when these predictions are accurate (consistency), while also maintaining near-optimal worst-case guarantees, even if these predictions are inaccurate (robustness). We initiate the design and analysis of strategyproof mechanisms that are augmented with predictions regarding the private information of the participating agents. To exhibit the important benefits of this approach, we revisit the canonical problem of facility location with strategic agents in the two-dimensional Euclidean space. We study both the egalitarian and utilitarian social cost functions, and we propose new strategyproof mechanisms that leverage predictions to guarantee an optimal trade-off between consistency and robustness. Furthermore, we also prove parameterized approximation results as a function of the prediction error, showing that our mechanisms perform well, even when the predictions are not fully accurate. Funding: The work of E. Balkanski was supported in part by the National Science Foundation [Grants CCF-2210501 and IIS-2147361]. The work of V. Gkatzelis and X. Tan was supported in part by the National Science Foundation [Grant CCF-2210502] and [CAREER Award CCF-2047907].
View PDF Chat

The Power of Greedy for Online Minimum Cost Matching on the Line

2023-07-07
Eric Balkanski , Yuri Faenza , Noémie Périvier
In the online minimum cost matching problem, there are n servers and, at each of n time steps, a request arrives and must be irrevocably matched to a server that … In the online minimum cost matching problem, there are n servers and, at each of n time steps, a request arrives and must be irrevocably matched to a server that has not yet been matched, with the goal of minimizing the sum of the distances between the matched pairs. Online minimum cost matching is a central problem in applications such as ride-hailing platforms and food delivery services. Despite achieving a worst-case competitive ratio that is exponential in n even on the line, the simple greedy algorithm, which matches each request to its nearest available server, performs well in practice and has a number of attractive features such as strategyproofness. A major question is thus to explain greedy's strong empirical performance. In this paper, we aim to understand the performance of greedy on the line over instances that are at least partially random.
View PDF Chat

Mechanism Design with Predictions: An Annotated Reading List

2023-06-01
Eric Balkanski , Vasilis Gkatzelis , Xizhi Tan
A surge of recent work has focused on analyzing the performance of algorithms guided by predictions, aiming to enhance their worst-case performance guarantees with improved guarantees when the predictions are … A surge of recent work has focused on analyzing the performance of algorithms guided by predictions, aiming to enhance their worst-case performance guarantees with improved guarantees when the predictions are accurate. This "learning-augmented" framework was recently also extended to mechanism design settings involving strategic agents and we provide an overview of these results.

Online Mechanism Design with Predictions

2023-01-01
Eric Balkanski , Vasilis Gkatzelis , Xizhi Tan +1 more
Aiming to overcome some of the limitations of worst-case analysis, the recently proposed framework of "algorithms with predictions" allows algorithms to be augmented with a (possibly erroneous) machine-learned prediction that … Aiming to overcome some of the limitations of worst-case analysis, the recently proposed framework of "algorithms with predictions" allows algorithms to be augmented with a (possibly erroneous) machine-learned prediction that they can use as a guide. In this framework, the goal is to obtain improved guarantees when the prediction is correct, which is called \emph{consistency}, while simultaneously guaranteeing some worst-case bounds even when the prediction is arbitrarily wrong, which is called \emph{robustness}. The vast majority of the work on this framework has focused on a refined analysis of online algorithms augmented with predictions regarding the future input. A subsequent line of work has also successfully adapted this framework to mechanism design, where the prediction is regarding the private information of strategic agents. In this paper, we initiate the study of online mechanism design with predictions, which combines the challenges of online algorithms with predictions and mechanism design with predictions. We consider the well-studied problem of designing a revenue-maximizing auction to sell a single item to strategic bidders who arrive and depart over time, each with an unknown, private, value for the item. We study the learning-augmented version of this problem where the auction designer is given a prediction regarding the maximum value over all agents. Our main result is a strategyproof mechanism whose revenue guarantees are $\alpha$-consistent with respect to the highest value and $(1-\alpha^2)/4$-robust with respect to the second-highest value, for $\alpha \in [0,1]$. We show that this tradeoff is optimal within a broad and natural family of auctions, meaning that any $\alpha$-consistent mechanism in that family has robustness at most $(1-\alpha^2)/4$. Finally, we extend our mechanism to also achieve expected revenues proportional to the prediction quality.
View PDF Chat

Learning-Augmented Dynamic Submodular Maximization

2023-01-01
Arpit Agarwal , Eric Balkanski
In dynamic submodular maximization, the goal is to maintain a high-value solution over a sequence of element insertions and deletions with a fast update time. Motivated by large-scale applications and … In dynamic submodular maximization, the goal is to maintain a high-value solution over a sequence of element insertions and deletions with a fast update time. Motivated by large-scale applications and the fact that dynamic data often exhibits patterns, we ask the following question: can predictions be used to accelerate the update time of dynamic submodular maximization algorithms? We consider the model for dynamic algorithms with predictions where predictions regarding the insertion and deletion times of elements can be used for preprocessing. Our main result is an algorithm with an $O(poly(\log \eta, \log w, \log k))$ amortized update time over the sequence of updates that achieves a $1/2 - \epsilon$ approximation in expectation for dynamic monotone submodular maximization under a cardinality constraint $k$, where the prediction error $\eta$ is the number of elements that are not inserted and deleted within $w$ time steps of their predicted insertion and deletion times. This amortized update time is independent of the length of the stream and instead depends on the prediction error.

Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location

2022-07-12
Priyank Agrawal , Eric Balkanski , Vasilis Gkatzelis +2 more
In this work we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in "learning-augmented algorithms". Aiming to … In this work we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in "learning-augmented algorithms". Aiming to complement the traditional approach in computer science, which analyzes the performance of algorithms based on worst-case instances, this line of work has focused on the design and analysis of algorithms that are enhanced with machine-learned predictions regarding the optimal solution. The algorithms can use the predictions as a guide to inform their decisions, and the goal is to achieve much stronger performance guarantees when these predictions are accurate (consistency), while also maintaining near-optimal worst-case guarantees, even if these predictions are very inaccurate (robustness). So far, these results have been limited to algorithms, but in this work we argue that another fertile ground for this framework is in mechanism design.
View PDF Chat

The Limitations of Optimization from Samples

2022-05-11
Eric Balkanski , Aviad Rubinstein , Yaron Singer
In this article, we consider the following question: Can we optimize objective functions from the training data we use to learn them? We formalize this question through a novel framework … In this article, we consider the following question: Can we optimize objective functions from the training data we use to learn them? We formalize this question through a novel framework we call optimization from samples ( OPS ). In OPS , we are given sampled values of a function drawn from some distribution and the objective is to optimize the function under some constraint. While there are interesting classes of functions that can be optimized from samples, our main result is an impossibility. We show that there are classes of functions that are statistically learnable and optimizable, but for which no reasonable approximation for optimization from samples is achievable. In particular, our main result shows that there is no constant factor approximation for maximizing coverage functions under a cardinality constraint using polynomially-many samples drawn from any distribution. We also show tight approximation guarantees for maximization under a cardinality constraint of several interesting classes of functions including unit-demand, additive, and general monotone submodular functions, as well as a constant factor approximation for monotone submodular functions with bounded curvature.
View PDF Chat

Deterministic Budget-Feasible Clock Auctions

2022-01-01
Eric Balkanski , Pranav Garimidi , Vasilis Gkatzelis +2 more
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Deterministic Budget-Feasible Clock AuctionsEric Balkanski, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin, and Xizhi TanEric … Previous chapter Next chapter Full AccessProceedings Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Deterministic Budget-Feasible Clock AuctionsEric Balkanski, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin, and Xizhi TanEric Balkanski, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin, and Xizhi Tanpp.2940 - 2963Chapter DOI:https://doi.org/10.1137/1.9781611977073.114PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the last decade, several strategyproof budget-feasible procurement auctions have been proposed, aiming to maximize the value of the buyer, while eliciting each seller's true cost for providing their service. These solutions predominantly take the form of randomized sealed-bid auctions: they ask the sellers to report their private costs and then use randomization to determine which subset of services will be procured and how much each of the chosen providers will be paid, ensuring that the total payment does not exceed the buyer's budget. Our main result in this paper is a novel method for designing budget-feasible auctions, leading to solutions that outperform the previously proposed auctions in multiple ways. First, our solutions take the form of descending clock auctions, and thus satisfy a list of very appealing properties, such as obvious strategyproofness, group strategyproofness, transparency, and unconditional winner privacy; this makes these auctions much more likely to be used in practice. Second, in contrast to previous results that heavily depend on randomization, our auctions are deterministic. As a result, we provide an affirmative answer to one of the main open questions in this literature, asking whether a deterministic strategyproof auction can achieve a constant approximation when the buyer's valuation function is submodular over the set of services. In addition to this, we also provide the first deterministic budget-feasible auction that matches the approximation bound of the best-known randomized auction for the class of subadditive valuations. Finally, using our method, we improve the best-known approximation factor for monotone submodular valuations, which has been the focus of most of the prior work. Previous chapter Next chapter RelatedDetails Published:2022eISBN:978-1-61197-707-3 https://doi.org/10.1137/1.9781611977073Book Series Name:ProceedingsBook Code:PRDA22Book Pages:xvii + 3771
View PDF Chat

Learning Low Degree Hypergraphs

2022-01-01
Eric Balkanski , Oussama Hanguir , Shatian Wang
We study the problem of learning a hypergraph via edge detecting queries. In this problem, a learner queries subsets of vertices of a hidden hypergraph and observes whether these subsets … We study the problem of learning a hypergraph via edge detecting queries. In this problem, a learner queries subsets of vertices of a hidden hypergraph and observes whether these subsets contain an edge or not. In general, learning a hypergraph with $m$ edges of maximum size $d$ requires $\Omega((2m/d)^{d/2})$ queries. In this paper, we aim to identify families of hypergraphs that can be learned without suffering from a query complexity that grows exponentially in the size of the edges. We show that hypermatchings and low-degree near-uniform hypergraphs with $n$ vertices are learnable with poly$(n)$ queries. For learning hypermatchings (hypergraphs of maximum degree $ 1$), we give an $O(\log^3 n)$-round algorithm with $O(n \log^5 n)$ queries. We complement this upper bound by showing that there are no algorithms with poly$(n)$ queries that learn hypermatchings in $o(\log \log n)$ adaptive rounds. For hypergraphs with maximum degree $\Delta$ and edge size ratio $\rho$, we give a non-adaptive algorithm with $O((2n)^{\rho \Delta+1}\log^2 n)$ queries. To the best of our knowledge, these are the first algorithms with poly$(n, m)$ query complexity for learning non-trivial families of hypergraphs that have a super-constant number of edges of super-constant size.
View PDF Chat

Scheduling with Speed Predictions

2022-01-01
Eric Balkanski , Tingting Ou , Clifford Stein +1 more
Algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, very recent work has leveraged … Algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, very recent work has leveraged machine-learned predictions to design algorithms that achieve improved approximation ratios in settings where the processing times of the jobs are initially unknown. In this paper, we study the speed-robust scheduling problem where the speeds of the machines, instead of the processing times of the jobs, are unknown and augment this problem with predictions. Our main result is an algorithm that achieves a $\min\{\eta^2(1+\alpha), (2 + 2/\alpha)\}$ approximation, for any $\alpha \in (0,1)$, where $\eta \geq 1$ is the prediction error. When the predictions are accurate, this approximation outperforms the best known approximation for speed-robust scheduling without predictions of $2-1/m$, where $m$ is the number of machines, while simultaneously maintaining a worst-case approximation of $2 + 2/\alpha$ even when the predictions are arbitrarily wrong. In addition, we obtain improved approximations for three special cases: equal job sizes, infinitesimal job sizes, and binary machine speeds. We also complement our algorithmic results with lower bounds. Finally, we empirically evaluate our algorithm against existing algorithms for speed-robust scheduling.
View PDF Chat

Strategyproof Scheduling with Predictions

2022-01-01
Eric Balkanski , Vasilis Gkatzelis , Xizhi Tan
In their seminal paper that initiated the field of algorithmic mechanism design, \citet{NR99} studied the problem of designing strategyproof mechanisms for scheduling jobs on unrelated machines aiming to minimize the … In their seminal paper that initiated the field of algorithmic mechanism design, \citet{NR99} studied the problem of designing strategyproof mechanisms for scheduling jobs on unrelated machines aiming to minimize the makespan. They provided a strategyproof mechanism that achieves an $n$-approximation and they made the bold conjecture that this is the best approximation achievable by any deterministic strategyproof scheduling mechanism. After more than two decades and several efforts, $n$ remains the best known approximation and very recent work by \citet{CKK21} has been able to prove an $\Omega(\sqrt{n})$ approximation lower bound for all deterministic strategyproof mechanisms. This strong negative result, however, heavily depends on the fact that the performance of these mechanisms is evaluated using worst-case analysis. To overcome such overly pessimistic, and often uninformative, worst-case bounds, a surge of recent work has focused on the ``learning-augmented framework'', whose goal is to leverage machine-learned predictions to obtain improved approximations when these predictions are accurate (consistency), while also achieving near-optimal worst-case approximations even when the predictions are arbitrarily wrong (robustness). In this work, we study the classic strategic scheduling problem of~\citet{NR99} using the learning-augmented framework and give a deterministic polynomial-time strategyproof mechanism that is $6$-consistent and $2n$-robust. We thus achieve the ``best of both worlds'': an $O(1)$ consistency and an $O(n)$ robustness that asymptotically matches the best-known approximation. We then extend this result to provide more general worst-case approximation guarantees as a function of the prediction error. Finally, we complement our positive results by showing that any $1$-consistent deterministic strategyproof mechanism has unbounded robustness.
View PDF Chat

Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location

2022-01-01
Priyank Agrawal , Eric Balkanski , Vasilis Gkatzelis +2 more
In this work we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in "learning-augmented algorithms". Aiming to … In this work we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in "learning-augmented algorithms". Aiming to complement the traditional approach in computer science, which analyzes the performance of algorithms based on worst-case instances, this line of work has focused on the design and analysis of algorithms that are enhanced with machine-learned predictions regarding the optimal solution. The algorithms can use the predictions as a guide to inform their decisions, and the goal is to achieve much stronger performance guarantees when these predictions are accurate (consistency), while also maintaining near-optimal worst-case guarantees, even if these predictions are very inaccurate (robustness). So far, these results have been limited to algorithms, but in this work we argue that another fertile ground for this framework is in mechanism design. We initiate the design and analysis of strategyproof mechanisms that are augmented with predictions regarding the private information of the participating agents. To exhibit the important benefits of this approach, we revisit the canonical problem of facility location with strategic agents in the two-dimensional Euclidean space. We study both the egalitarian and utilitarian social cost functions, and we propose new strategyproof mechanisms that leverage predictions to guarantee an optimal trade-off between consistency and robustness guarantees. This provides the designer with a menu of mechanism options to choose from, depending on her confidence regarding the prediction accuracy. Furthermore, we also prove parameterized approximation results as a function of the prediction error, showing that our mechanisms perform well even when the predictions are not fully accurate.
View PDF Chat

An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model

2021-12-28
Eric Balkanski , Aviad Rubinstein , Yaron Singer
An Exponentially Faster Algorithm for Submodular Maximization Under a Matroid Constraint This paper studies the problem of submodular maximization under a matroid constraint. It is known since the 1970s that … An Exponentially Faster Algorithm for Submodular Maximization Under a Matroid Constraint This paper studies the problem of submodular maximization under a matroid constraint. It is known since the 1970s that the greedy algorithm obtains a constant-factor approximation guarantee for this problem. Twelve years ago, a breakthrough result by Vondrák obtained the optimal 1 − 1/e approximation. Previous algorithms for this fundamental problem all have linear parallel runtime, which was considered impossible to accelerate until recently. The main contribution of this paper is a novel algorithm that provides an exponential speedup in the parallel runtime of submodular maximization under a matroid constraint, without loss in the approximation guarantee.
View PDF Chat

Instance Specific Approximations for Submodular Maximization

2021-01-01
Eric Balkanski , Sharon Qian , Yaron Singer
For many optimization problems in machine learning, finding an optimal solution is computationally intractable and we seek algorithms that perform well in practice. Since computational intractability often results from pathological … For many optimization problems in machine learning, finding an optimal solution is computationally intractable and we seek algorithms that perform well in practice. Since computational intractability often results from pathological instances, we look for methods to benchmark the performance of algorithms against optimal solutions on real-world instances. The main challenge is that an optimal solution cannot be efficiently computed for intractable problems, and we therefore often do not know how far a solution is from being optimal. A major question is therefore how to measure the performance of an algorithm in comparison to an optimal solution on instances we encounter in practice. In this paper, we address this question in the context of submodular optimization problems. For the canonical problem of submodular maximization under a cardinality constraint, it is intractable to compute a solution that is better than a $1-1/e \approx 0.63$ fraction of the optimum. Algorithms like the celebrated greedy algorithm are guaranteed to achieve this $1-1/e$ bound on any instance and are used in practice. Our main contribution is not a new algorithm for submodular maximization but an analytical method that measures how close an algorithm for submodular maximization is to optimal on a given problem instance. We use this method to show that on a wide variety of real-world datasets and objectives, the approximation of the solution found by greedy goes well beyond $1-1/e$ and is often at least 0.95. We develop this method using a novel technique that lower bounds the objective of a dual minimization problem to obtain an upper bound on the value of an optimal solution to the primal maximization problem.

Deterministic Budget-Feasible Clock Auctions

2021-01-01
Eric Balkanski , Pranav Garimidi , Vasilis Gkatzelis +2 more
We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the … We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the last decade, several strategyproof budget-feasible procurement auctions have been proposed, aiming to maximize the value of the buyer, while eliciting each seller's true cost for providing their service. These solutions predominantly take the form of randomized sealed-bid auctions: they ask the sellers to report their private costs and then use randomization to determine which subset of services will be procured and how much each of the chosen providers will be paid, ensuring that the total payment does not exceed budget. Our main result in this paper is a novel method for designing budget-feasible auctions, leading to solutions that outperform the previously proposed auctions in multiple ways. First, our solutions take the form of descending clock auctions, and thus satisfy a list of properties, such as obvious strategyproofness, group strategyproofness, transparency, and unconditional winner privacy; this makes these auctions much more likely to be used in practice. Second, in contrast to previous results that heavily depend on randomization, our auctions are deterministic. As a result, we provide an affirmative answer to one of the main open questions in this literature, asking whether a deterministic strategyproof auction can achieve a constant approximation when the buyer's valuation function is submodular over the set of services. In addition, we also provide the first deterministic budget-feasible auction that matches the approximation bound of the best-known randomized auction for the class of subadditive valuations. Finally, using our method, we improve the best-known approximation factor for monotone submodular valuations, which has been the focus of most of the prior work.

Adversarial Attacks on Binary Image Recognition Systems

2020-10-22
Eric Balkanski , Harrison Chase , Kojin Oshiba +3 more
We initiate the study of adversarial attacks on models for binary (i.e. black and white) image classification. Although there has been a great deal of work on attacking models for … We initiate the study of adversarial attacks on models for binary (i.e. black and white) image classification. Although there has been a great deal of work on attacking models for colored and grayscale images, little is known about attacks on models for binary images. Models trained to classify binary images are used in text recognition applications such as check processing, license plate recognition, invoice processing, and many others. In contrast to colored and grayscale images, the search space of attacks on binary images is extremely restricted and noise cannot be hidden with minor perturbations in each pixel. Thus, the optimization landscape of attacks on binary images introduces new fundamental challenges. In this paper we introduce a new attack algorithm called SCAR, designed to fool classifiers of binary images. We show that SCAR significantly outperforms existing $L_0$ attacks applied to the binary setting and use it to demonstrate the vulnerability of real-world text recognition systems. SCAR's strong performance in practice contrasts with the existence of classifiers that are provably robust to large perturbations. In many cases, altering a single pixel is sufficient to trick Tesseract, a popular open-source text recognition system, to misclassify a word as a different word in the English dictionary. We also license software from providers of check processing systems to most of the major US banks and demonstrate the vulnerability of check recognitions for mobile deposits. These systems are substantially harder to fool since they classify both the handwritten amounts in digits and letters, independently. Nevertheless, we generalize SCAR to design attacks that fool state-of-the-art check processing systems using unnoticeable perturbations that lead to misclassification of deposit amounts. Consequently, this is a powerful method to perform financial fraud.
View PDF Chat

Adversarial Attacks on Binary Image Recognition Systems

2020-01-01
Eric Balkanski , Harrison Chase , Kojin Oshiba +3 more
We initiate the study of adversarial attacks on models for binary (i.e. black and white) image classification. Although there has been a great deal of work on attacking models for … We initiate the study of adversarial attacks on models for binary (i.e. black and white) image classification. Although there has been a great deal of work on attacking models for colored and grayscale images, little is known about attacks on models for binary images. Models trained to classify binary images are used in text recognition applications such as check processing, license plate recognition, invoice processing, and many others. In contrast to colored and grayscale images, the search space of attacks on binary images is extremely restricted and noise cannot be hidden with minor perturbations in each pixel. Thus, the optimization landscape of attacks on binary images introduces new fundamental challenges. In this paper we introduce a new attack algorithm called SCAR, designed to fool classifiers of binary images. We show that SCAR significantly outperforms existing $L_0$ attacks applied to the binary setting and use it to demonstrate the vulnerability of real-world text recognition systems. SCAR's strong performance in practice contrasts with the existence of classifiers that are provably robust to large perturbations. In many cases, altering a single pixel is sufficient to trick Tesseract, a popular open-source text recognition system, to misclassify a word as a different word in the English dictionary. We also license software from providers of check processing systems to most of the major US banks and demonstrate the vulnerability of check recognitions for mobile deposits. These systems are substantially harder to fool since they classify both the handwritten amounts in digits and letters, independently. Nevertheless, we generalize SCAR to design attacks that fool state-of-the-art check processing systems using unnoticeable perturbations that lead to misclassification of deposit amounts. Consequently, this is a powerful method to perform financial fraud.
View PDF Chat

On the Construction of Substitutes

2019-07-18
Eric Balkanski , Renato Paes Leme
Gross substitutability is a central concept in economics and is connected to important notions in discrete convex analysis, number theory, and the analysis of greedy algorithms in computer science. Many … Gross substitutability is a central concept in economics and is connected to important notions in discrete convex analysis, number theory, and the analysis of greedy algorithms in computer science. Many different characterizations are known for this class, but providing a constructive description remains a major open problem. The construction problem asks how to construct all gross substitutes from a class of simpler functions using a set of operations. Because gross substitutes are a natural generalization of matroids to real-valued functions, matroid rank functions form a desirable such class of simpler functions. Shioura proved that a rich class of gross substitutes can be expressed as sums of matroid rank functions, but it is open whether all gross substitutes can be constructed this way. Our main result is a negative answer showing that some gross substitutes cannot be expressed as positive linear combinations of matroid rank functions. En route, we provide necessary and sufficient conditions for the sum to preserve substitutability, uncover a new operation preserving substitutability, and fully describe all substitutes with at most four items.
View PDF Chat

An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model

2019-06-20
Eric Balkanski , Aviad Rubinstein , Yaron Singer
In this paper we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization to quantify the … In this paper we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization to quantify the information theoretic complexity of black-box optimization in a parallel computation model. Informally, the adaptivity of an algorithm is the number of sequential rounds it makes when each round can execute polynomially-many function evaluations in parallel. Since submodular optimization is regularly applied on large datasets we seek algorithms with low adaptivity to enable speedups via parallelization. Consequently, a recent line of work has been devoted to designing constant factor approximation algorithms for maximizing submodular functions under various constraints in the adaptive complexity model.
View PDF Chat

An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation

2019-01-01
Eric Balkanski , Aviad Rubinstein , Yaron Singer
In this paper we study the adaptivity of submodular maximization. Adaptivity quantifies the number of sequential rounds that an algorithm makes when function evaluations can be executed in parallel. Adaptivity … In this paper we study the adaptivity of submodular maximization. Adaptivity quantifies the number of sequential rounds that an algorithm makes when function evaluations can be executed in parallel. Adaptivity is a fundamental concept that is heavily studied across a variety of areas in computer science, largely due to the need for parallelizing computation. For the canonical problem of maximizing a monotone submodular function under a cardinality constraint, it is well known that a simple greedy algorithm achieves a 1 – 1/e approximation [NWF78] and that this approximation is optimal for polynomial-time algorithms [NW78]. Somewhat surprisingly, despite extensive efforts on submodular optimization for large-scale datasets, until very recently there was no known algorithm that achieves a constant factor approximation for this problem whose adaptivity is sublinear in the size of the ground set n.Recent work by [BS18] describes an algorithm that obtains an approximation arbitrarily close to 1/3 in O(log n) adaptive rounds and shows that no algorithm can obtain a constant factor approximation in õ(log n) adaptive rounds. This approach achieves an exponential speedup in adaptivity (and parallel running time) at the expense of approximation quality.In this paper we describe a novel approach that yields an algorithm whose approximation is arbitrarily close to the optimal 1 – 1/e guarantee in O(log n) adaptive rounds. This algorithm therefore achieves an exponential speedup in parallel running time for submodular maximization at the expense of an arbitrarily small loss in approximation quality. This guarantee is optimal in both approximation and adaptivity, up to lower order terms.
View PDF Chat

Dynamic First Price Auctions Robust to Heterogeneous Buyers

2019-01-01
Shipra Agrawal , Eric Balkanski , Vahab Mirrokni +1 more
We study dynamic mechanisms for optimizing revenue in repeated auctions, that are robust to heterogeneous forward-looking and learning behavior of the buyers. Typically it is assumed that the buyers are … We study dynamic mechanisms for optimizing revenue in repeated auctions, that are robust to heterogeneous forward-looking and learning behavior of the buyers. Typically it is assumed that the buyers are either all myopic or are all infinite lookahead, and that buyers understand and trust the mechanism. These assumptions raise the following question: is it possible to design approximately revenue optimal mechanisms when the buyer pool is heterogeneous? Facing a heterogeneous population of buyers with an unknown mixture of $k$-lookahead buyers, myopic buyers, no-regret-learners and no-policy-regret learners, we design a simple state-based mechanism that achieves a constant fraction of the optimal achievable revenue.

The FAST Algorithm for Submodular Maximization

2019-01-01
Adam Breuer , Eric Balkanski , Yaron Singer
In this paper we describe a new algorithm called Fast Adaptive Sequencing Technique (FAST) for maximizing a monotone submodular function under a cardinality constraint $k$ whose approximation ratio is arbitrarily … In this paper we describe a new algorithm called Fast Adaptive Sequencing Technique (FAST) for maximizing a monotone submodular function under a cardinality constraint $k$ whose approximation ratio is arbitrarily close to $1-1/e$, is $O(\log(n) \log^2(\log k))$ adaptive, and uses a total of $O(n \log\log(k))$ queries. Recent algorithms have comparable guarantees in terms of asymptotic worst case analysis, but their actual number of rounds and query complexity depend on very large constants and polynomials in terms of precision and confidence, making them impractical for large data sets. Our main contribution is a design that is extremely efficient both in terms of its non-asymptotic worst case query complexity and number of rounds, and in terms of its practical runtime. We show that this algorithm outperforms any algorithm for submodular maximization we are aware of, including hyper-optimized parallel versions of state-of-the-art serial algorithms, by running experiments on large data sets. These experiments show FAST is orders of magnitude faster than the state-of-the-art.

On the Construction of Substitutes

2018-06-11
Eric Balkanski , Renato Paes Leme
Gross substitutability is a central concept in Economics and is connected to important notions in Discrete Convex Analysis, Number Theory and the analysis of Greedy algorithms in Computer Science. Many … Gross substitutability is a central concept in Economics and is connected to important notions in Discrete Convex Analysis, Number Theory and the analysis of Greedy algorithms in Computer Science. Many different characterizations are known for this class, but providing a constructive description remains a major open problem. The construction problem asks how to construct all gross substitutes from a class of simpler functions using a set of operations. Since gross substitutes are a natural generalization of matroids to real-valued functions, matroid rank functions form a desirable such class of simpler functions. Shioura proved that a rich class of gross substitutes can be expressed as sums of matroid rank functions, but it is open whether all gross substitutes can be constructed this way. Our main result is a negative answer showing that some gross substitutes cannot be expressed as positive linear combinations of matroid rank functions. En route, we provide necessary and sufficient conditions for the sum to preserve substitutability, uncover a new operation preserving substitutability and fully describe all substitutes with at most 4 items.
View PDF Chat

On the Construction of Substitutes

2018-05-09
Eric Balkanski , Renato Paes Leme
Gross substitutability is a central concept in Economics and is connected to important notions in Discrete Convex Analysis, Number Theory and the analysis of Greedy algorithms in Computer Science. Many … Gross substitutability is a central concept in Economics and is connected to important notions in Discrete Convex Analysis, Number Theory and the analysis of Greedy algorithms in Computer Science. Many different characterizations are known for this class, but providing a constructive description remains a major open problem. The construction problem asks how to construct all gross substitutes from a class of simpler functions using a set of operations. Since gross substitutes are a natural generalization of matroids to real-valued functions, matroid rank functions form a desirable such class of simpler functions. Shioura proved that a rich class of gross substitutes can be expressed as sums of matroid rank functions, but it is open whether all gross substitutes can be constructed this way. Our main result is a negative answer showing that some gross substitutes cannot be expressed as positive linear combinations of matroid rank functions. En route, we provide necessary and sufficient conditions for the sum to preserve substitutability, uncover a new operation preserving substitutability and fully describe all substitutes with at most 4 items.

The Importance of Communities for Learning to Influence

2018-01-01
Eric Balkanski , Nicole Immorlica , Yaron Singer
We consider the canonical problem of influence maximization in social networks. Since the seminal work of Kempe, Kleinberg, and Tardos, there have been two largely disjoint efforts on this problem. … We consider the canonical problem of influence maximization in social networks. Since the seminal work of Kempe, Kleinberg, and Tardos, there have been two largely disjoint efforts on this problem. The first studies the problem associated with learning the parameters of the generative influence model. The second focuses on the algorithmic challenge of identifying a set of influencers, assuming the parameters of the generative model are known. Recent results on learning and optimization imply that in general, if the generative model is not known but rather learned from training data, no algorithm can yield a constant factor approximation guarantee using polynomially-many samples, drawn from any distribution. In this paper, we design a simple heuristic that overcomes this negative result in practice by leveraging the strong community structure of social networks. Although in general the approximation guarantee of our algorithm is necessarily unbounded, we show that this algorithm performs well experimentally. To justify its performance, we prove our algorithm obtains a constant factor approximation guarantee on graphs generated through the stochastic block model, traditionally used to model networks with community structure.

Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimization

2018-01-01
Eric Balkanski , Yaron Singer
In this paper we study the limitations of parallelization in convex optimization. A convenient approach to study parallelization is through the prism of \emph{adaptivity} which is an information theoretic measure … In this paper we study the limitations of parallelization in convex optimization. A convenient approach to study parallelization is through the prism of \emph{adaptivity} which is an information theoretic measure of the parallel runtime of an algorithm [BS18]. Informally, adaptivity is the number of sequential rounds an algorithm needs to make when it can execute polynomially-many queries in parallel at every round. For combinatorial optimization with black-box oracle access, the study of adaptivity has recently led to exponential accelerations in parallel runtime and the natural question is whether dramatic accelerations are achievable for convex optimization. For the problem of minimizing a non-smooth convex function $f:[0,1]^n\to \mathbb{R}$ over the unit Euclidean ball, we give a tight lower bound that shows that even when $\texttt{poly}(n)$ queries can be executed in parallel, there is no randomized algorithm with $\tilde{o}(n^{1/3})$ rounds of adaptivity that has convergence rate that is better than those achievable with a one-query-per-round algorithm. A similar lower bound was obtained by Nemirovski [Nem94], however that result holds for the $\ell_{\infty}$-setting instead of $\ell_2$. In addition, we also show a tight lower bound that holds for Lipschitz and strongly convex functions. At the time of writing this manuscript we were not aware of Nemirovski's result. The construction we use is similar to the one in [Nem94], though our analysis is different. Due to the close relationship between this work and [Nem94], we view the research contribution of this manuscript limited and it should serve as an instructful approach to understanding lower bounds for parallel optimization.

Non-monotone Submodular Maximization in Exponentially Fewer Iterations

2018-01-01
Eric Balkanski , Adam Breuer , Yaron Singer
In this paper we consider parallelization for applications whose objective can be expressed as maximizing a non-monotone submodular function under a cardinality constraint. Our main result is an algorithm whose … In this paper we consider parallelization for applications whose objective can be expressed as maximizing a non-monotone submodular function under a cardinality constraint. Our main result is an algorithm whose approximation is arbitrarily close to $1/2e$ in $O(\log^2 n)$ adaptive rounds, where $n$ is the size of the ground set. This is an exponential speedup in parallel running time over any previously studied algorithm for constrained non-monotone submodular maximization. Beyond its provable guarantees, the algorithm performs well in practice. Specifically, experiments on traffic monitoring and personalized data summarization applications show that the algorithm finds solutions whose values are competitive with state-of-the-art algorithms while running in exponentially fewer parallel iterations.

Secretary Ranking with Minimal Inversions

2018-01-01
Sepehr Assadi , Eric Balkanski , Renato Paes Leme
We study a twist on the classic secretary problem, which we term the secretary ranking problem: elements from an ordered set arrive in random order and instead of picking the … We study a twist on the classic secretary problem, which we term the secretary ranking problem: elements from an ordered set arrive in random order and instead of picking the maximum element, the algorithm is asked to assign a rank, or position, to each of the elements. The rank assigned is irrevocable and is given knowing only the pairwise comparisons with elements previously arrived. The goal is to minimize the distance of the rank produced to the true rank of the elements measured by the Kendall-Tau distance, which corresponds to the number of pairs that are inverted with respect to the true order. Our main result is a matching upper and lower bound for the secretary ranking problem. We present an algorithm that ranks $n$ elements with only $O(n^{3/2})$ inversions in expectation, and show that any algorithm necessarily suffers $\Omega(n^{3/2})$ inversions when there are $n$ available positions. In terms of techniques, the analysis of our algorithm draws connections to linear probing in the hashing literature, while our lower bound result relies on a general anti-concentration bound for a generic balls and bins sampling process. We also consider the case where the number of positions $m$ can be larger than the number of secretaries $n$ and provide an improved bound by showing a connection of this problem with random binary trees.
View PDF Chat

An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model

2018-01-01
Eric Balkanski , Aviad Rubinstein , Yaron Singer
In this paper we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization in [BS18a] to … In this paper we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization in [BS18a] to quantify the information theoretic complexity of black-box optimization in a parallel computation model. Informally, the adaptivity of an algorithm is the number of sequential rounds it makes when each round can execute polynomially-many function evaluations in parallel. Since submodular optimization is regularly applied on large datasets we seek algorithms with low adaptivity to enable speedups via parallelization. Consequently, a recent line of work has been devoted to designing constant factor approximation algorithms for maximizing submodular functions under various constraints in the adaptive complexity model [BS18a, BS18b, BBS18, BRS19, EN19, FMZ19, CQ19, ENV18, FMZ18]. Despite the burst in work on submodular maximization in the adaptive complexity model the fundamental problem of maximizing a monotone submodular function under a matroid constraint has remained elusive. In particular, all known techniques fail for this problem and there are no known constant factor approximation algorithms whose adaptivity is sublinear in the rank of the matroid $k$ or in the worst case sublinear in the size of the ground set $n$. In this paper we present an approximation algorithm for the problem of maximizing a monotone submodular function under a matroid constraint in the adaptive complexity model. The approximation guarantee of the algorithm is arbitrarily close to the optimal $1-1/e$ and it has near optimal adaptivity of $O(\log(n)\log(k))$. This result is obtained using a novel technique of adaptive sequencing which departs from previous techniques for submodular maximization in the adaptive complexity model.

On the Construction of Substitutes

2018-01-01
Eric Balkanski , Renato Paes Leme
Gross substitutability is a central concept in Economics and is connected to important notions in Discrete Convex Analysis, Number Theory and the analysis of Greedy algorithms in Computer Science. Many … Gross substitutability is a central concept in Economics and is connected to important notions in Discrete Convex Analysis, Number Theory and the analysis of Greedy algorithms in Computer Science. Many different characterizations are known for this class, but providing a constructive description remains a major open problem. The construction problem asks how to construct all gross substitutes from a class of simpler functions using a set of operations. Since gross substitutes are a natural generalization of matroids to real-valued functions, matroid rank functions form a desirable such class of simpler functions. Shioura proved that a rich class of gross substitutes can be expressed as sums of matroid rank functions, but it is open whether all gross substitutes can be constructed this way. Our main result is a negative answer showing that some gross substitutes cannot be expressed as positive linear combinations of matroid rank functions. En route, we provide necessary and sufficient conditions for the sum to preserve substitutability, uncover a new operation preserving substitutability and fully describe all substitutes with at most 4 items.
View PDF Chat

An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation

2018-01-01
Eric Balkanski , Aviad Rubinstein , Yaron Singer
In this paper we study the adaptivity of submodular maximization. Adaptivity quantifies the number of sequential rounds that an algorithm makes when function evaluations can be executed in parallel. Adaptivity … In this paper we study the adaptivity of submodular maximization. Adaptivity quantifies the number of sequential rounds that an algorithm makes when function evaluations can be executed in parallel. Adaptivity is a fundamental concept that is heavily studied across a variety of areas in computer science, largely due to the need for parallelizing computation. For the canonical problem of maximizing a monotone submodular function under a cardinality constraint, it is well known that a simple greedy algorithm achieves a $1-1/e$ approximation and that this approximation is optimal for polynomial-time algorithms. Somewhat surprisingly, despite extensive efforts on submodular optimization for large-scale datasets, until very recently there was no known algorithm that achieves a constant factor approximation for this problem whose adaptivity is sublinear in the size of the ground set $n$. Recent work by Balkanski and Singer describes an algorithm that obtains an approximation arbitrarily close to $1/3$ in $\mathcal{O}(\log n)$ adaptive rounds and shows that no algorithm can obtain a constant factor approximation in $\tilde{o}(\log n)$ adaptive rounds. This approach achieves an exponential speedup in adaptivity (and parallel running time) at the expense of approximation quality. In this paper we describe a novel approach that yields an algorithm whose approximation is arbitrarily close to the optimal $1-1/e$ guarantee in $\mathcal{O}(\log n)$ adaptive rounds. This algorithm therefore achieves an exponential speedup in parallel running time for submodular maximization at the expense of an arbitrarily small loss in approximation quality. This guarantee is optimal in both approximation and adaptivity, up to lower order terms.
View PDF Chat

The Sample Complexity of Optimizing a Convex Function

2017-06-18
Eric Balkanski , Yaron Singer

The limitations of optimization from samples

2017-06-15
Eric Balkanski , Aviad Rubinstein , Yaron Singer
In this paper we consider the following question: can we optimize objective functions from the training data we use to learn them? We formalize this question through a novel framework … In this paper we consider the following question: can we optimize objective functions from the training data we use to learn them? We formalize this question through a novel framework we call optimization from samples (OPS). In OPS, we are given sampled values of a function drawn from some distribution and the objective is to optimize the function under some constraint.
View PDF Chat

Statistical Cost Sharing

2017-01-01
Eric Balkanski , Umar Syed , Sergei Vassilvitskii
We study the cost sharing problem for cooperative games in situations where the cost function $C$ is not available via oracle queries, but must instead be derived from data, represented … We study the cost sharing problem for cooperative games in situations where the cost function $C$ is not available via oracle queries, but must instead be derived from data, represented as tuples $(S, C(S))$, for different subsets $S$ of players. We formalize this approach, which we call statistical cost sharing, and consider the computation of the core and the Shapley value, when the tuples are drawn from some distribution $\mathcal{D}$. Previous work by Balcan et al. in this setting showed how to compute cost shares that satisfy the core property with high probability for limited classes of functions. We expand on their work and give an algorithm that computes such cost shares for any function with a non-empty core. We complement these results by proving an inapproximability lower bound for a weaker relaxation. We then turn our attention to the Shapley value. We first show that when cost functions come from the family of submodular functions with bounded curvature, $κ$, the Shapley value can be approximated from samples up to a $\sqrt{1 - κ}$ factor, and that the bound is tight. We then define statistical analogues of the Shapley axioms, and derive a notion of statistical Shapley value. We show that these can always be approximated arbitrarily well for general functions over any distribution $\mathcal{D}$.

Bayesian Budget Feasibility with Posted Pricing

2016-04-11
Eric Balkanski , Jason D. Hartline
We consider the problem of budget feasible mechanism design proposed by Singer, but in a Bayesian setting. A principal has a public value for hiring a subset of the agents … We consider the problem of budget feasible mechanism design proposed by Singer, but in a Bayesian setting. A principal has a public value for hiring a subset of the agents and a budget, while the agents have private costs for being hired. We consider both additive and submodular value functions of the principal. We show that there are simple, practical, ex post budget balanced posted pricing mechanisms that approximate the value obtained by the Bayesian optimal mechanism that is budget balanced only in expectation. A main motivating application for this work is crowdsourcing, e.g., on Mechanical Turk, where workers are drawn from a large population and posted pricing is standard. Our analysis methods relate to contention resolution schemes in submodular optimization of Vondràk et al. and the correlation gap analysis of Yan.
View PDF Chat

Bayesian Budget Feasibility with Posted Pricing

2015-06-12
Eric Balkanski , Jason D. Hartline
We consider the problem of budget feasible mechanism design proposed by Singer (2010), but in a Bayesian setting. A principal has a public value for hiring a subset of the … We consider the problem of budget feasible mechanism design proposed by Singer (2010), but in a Bayesian setting. A principal has a public value for hiring a subset of the agents and a budget, while the agents have private costs for being hired. We consider both additive and submodular value functions of the principal. We show that there are simple, practical, ex post budget balanced posted pricing mechanisms that approximate the value obtained by the Bayesian optimal mechanism that is budget balanced only in expectation. A main motivating application for this work is the crowdsourcing large projects, e.g., on Mechanical Turk, where workers are drawn from a large population and posted pricing is standard. Our analysis methods relate to contention resolution schemes in submodular optimization of Vondrak et al. (2011) and the correlation gap analysis of Yan (2011).

Bayesian Budget Feasibility with Posted Pricing

2015-01-01
Eric Balkanski , Jason D. Hartline
We consider the problem of budget feasible mechanism design proposed by Singer (2010), but in a Bayesian setting. A principal has a public value for hiring a subset of the … We consider the problem of budget feasible mechanism design proposed by Singer (2010), but in a Bayesian setting. A principal has a public value for hiring a subset of the agents and a budget, while the agents have private costs for being hired. We consider both additive and submodular value functions of the principal. We show that there are simple, practical, ex post budget balanced posted pricing mechanisms that approximate the value obtained by the Bayesian optimal mechanism that is budget balanced only in expectation. A main motivating application for this work is the crowdsourcing large projects, e.g., on Mechanical Turk, where workers are drawn from a large population and posted pricing is standard. Our analysis methods relate to contention resolution schemes in submodular optimization of Vondrak et al. (2011) and the correlation gap analysis of Yan (2011).
View PDF Chat

The Limitations of Optimization from Samples

2015-01-01
Eric Balkanski , Aviad Rubinstein , Yaron Singer
In this paper we consider the following question: can we optimize objective functions from the training data we use to learn them? We formalize this question through a novel framework … In this paper we consider the following question: can we optimize objective functions from the training data we use to learn them? We formalize this question through a novel framework we call optimization from samples (OPS). In OPS, we are given sampled values of a function drawn from some distribution and the objective is to optimize the function under some constraint. While there are interesting classes of functions that can be optimized from samples, our main result is an impossibility. We show that there are classes of functions which are statistically learnable and optimizable, but for which no reasonable approximation for optimization from samples is achievable. In particular, our main result shows that there is no constant factor approximation for maximizing coverage functions under a cardinality constraint using polynomially-many samples drawn from any distribution. We also show tight approximation guarantees for maximization under a cardinality constraint of several interesting classes of functions including unit-demand, additive, and general monotone submodular functions, as well as a constant factor approximation for monotone submodular functions with bounded curvature.
View PDF Chat
Coauthor Papers Together
Yaron Singer 16
Vasilis Gkatzelis 10
Xizhi Tan 9
Aviad Rubinstein 8
Tingting Ou 5
Renato Paes Leme 5
Hao-Ting Wei 3
Clifford Stein 3
Yuri Faenza 3
Priyank Agrawal 3
Jason D. Hartline 3
Pranav Garimidi 2
Cherlin Zhu 2
Daniel Schoepflin 2
Adam Breuer 2
Harrison Chase 2
Noémie Périvier 2
Alexander Rilee 2
Christopher En 2
Richard Wang 2
Kojin Oshiba 2
Umar Syed 1
Vahab Mirrokni 1
Shatian Wang 1
Alan Kuhnle 1
Oussama Hanguir 1
Balasubramanian Sivan 1
Shipra Agrawal 1
Arpit Agarwal 1
Golnoosh Shahkarami 1
Sepehr Assadi 1
Nicole Immorlica 1
Sharon Qian 1
Sergei Vassilvitskii 1
Steven DiSilvio 1

The sample complexity of revenue maximization

2014-05-31
Richard Cole , Tim Roughgarden
In the design and analysis of revenue-maximizing auctions, auction performance is typically measured with respect to a prior distribution over inputs. The most obvious source for such a distribution is … In the design and analysis of revenue-maximizing auctions, auction performance is typically measured with respect to a prior distribution over inputs. The most obvious source for such a distribution is past data. The goal of this paper is to understand how much data is necessary and sufficient to guarantee near-optimal expected revenue.
View PDF Chat

Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time

2019-01-06
Alina Ene , Huy L. Nguyễn
In this paper, we study the tradeoff between the approximation guarantee and adaptivity for the problem of maximizing a monotone submodular function subject to a cardinality constraint. The adaptivity of … In this paper, we study the tradeoff between the approximation guarantee and adaptivity for the problem of maximizing a monotone submodular function subject to a cardinality constraint. The adaptivity of an algorithm is the number of sequential rounds of queries it makes to the evaluation oracle of the function, where in every round the algorithm is allowed to make polynomially-many parallel queries. Adaptivity is an important consideration in settings where the objective function is estimated using samples and in applications where adaptivity is the main running time bottleneck. Previous algorithms achieving a nearly-optimal 1 − 1/e − e approximation require Ω(n) rounds of adaptivity. In this work, we give the first algorithm that achieves a 1 − 1/e − e approximation using O(In n/e2) rounds of adaptivity. The number of function evaluations and additional running time of the algorithm are O(n poly(logn, 1/e)).

Symmetry and Approximability of Submodular Maximization Problems

2013-01-01
J. Vondrák
A number of recent results on optimization problems involving submodular functions have made use of the multilinear relaxation of the problem. These results hold typically in the value oracle model, … A number of recent results on optimization problems involving submodular functions have made use of the multilinear relaxation of the problem. These results hold typically in the value oracle model, where the objective function is accessible via a black box returning $f(S)$ for a given $S$. We present a general approach to deriving inapproximability results in the value oracle model, based on the notion of symmetry gap. Our main result is that for any fixed instance that exhibits a certain symmetry gap in its multilinear relaxation, there is a naturally related class of instances for which a better approximation factor than the symmetry gap would require exponentially many oracle queries. This unifies several known hardness results for submodular maximization, e.g., the optimality of $(1-1/e)$-approximation for monotone submodular maximization under a cardinality constraint and the impossibility of $(\frac12+\epsilon)$-approximation for unconstrained (nonmonotone) submodular maximization. As a new application, we consider the problem of maximizing a nonmonotone submodular function over the bases of a matroid. A $(\frac16-o(1))$-approximation has been developed for this problem, assuming that the matroid contains two disjoint bases. We show that the best approximation one can achieve is indeed related to packings of bases in the matroid. Specifically, for any $k \geq 2$, there is a class of matroids of fractional base packing number $\nu = \frac{k}{k-1}$ such that any algorithm achieving a better than $(1-\frac{1}{\nu}) = \frac{1}{k}$-approximation for this class would require exponentially many value queries. In particular, there is no constant factor approximation for maximizing a nonmonotone submodular function over the bases of a general matroid. On the positive side, we present a $\frac12 (1-\frac{1}{\nu}-o(1))$-approximation algorithm assuming fractional base packing number at least $\nu$, where $\nu \in (1,2]$. We also present an improved $0.309$-approximation for maximization of a nonmonotone submodular function subject to a matroid independence constraint, improving the previously known factor of $\frac14-\epsilon$. For this problem, we obtain a hardness of $(\frac12 + \epsilon)$-approximation for any fixed $\epsilon>0$.
View PDF Chat

On the approximability of budget feasible mechanisms

2011-01-23
Ning Chen , Nick Gravin , Pinyan Lu
Budget feasible mechanisms, recently initiated by Singer (FOCS 2010), extend algorithmic mechanism design problems to a realistic setting with a budget constraint. We consider the problem of designing truthful budget … Budget feasible mechanisms, recently initiated by Singer (FOCS 2010), extend algorithmic mechanism design problems to a realistic setting with a budget constraint. We consider the problem of designing truthful budget feasible mechanisms for monotone submodular functions: We give a randomized mechanism with an approximation ratio of 7.91 (improving on the previous best-known result 233.83), and a deterministic mechanism with an approximation ratio of 8.34. We also study the knapsack problem, which is a special submodular function, give a 2 + √2 approximation deterministic mechanism (improving on the previous best-known result 5), and a 3 approximation randomized mechanism. We provide similar results for an extended knapsack problem with heterogeneous items, where items are divided into groups and one can pick at most one item from each group.Finally we show a lower bound of 1 + √2 for the approximation ratio of deterministic mechanisms and 2 for randomized mechanisms for knapsack, as well as the general monotone submodular functions. Our lower bounds are unconditional, and do not rely on any computational or complexity assumptions.

Budget Feasible Mechanisms

2010-10-01
Yaron Singer
We study a novel class of mechanism design problems in which the outcomes are constrained by the payments. This basic class of mechanism design problems captures many common economic situations, … We study a novel class of mechanism design problems in which the outcomes are constrained by the payments. This basic class of mechanism design problems captures many common economic situations, and yet it has not been studied, to our knowledge, in the past. We focus on the case of procurement auctions in which sellers have private costs, and the auctioneer aims to maximize a utility function on subsets of items, under the constraint that the sum of the payments provided by the mechanism does not exceed a given budget. Standard mechanism design ideas such as the VCG mechanism and its variants are not applicable here. We show that, for general functions, the budget constraint can render mechanisms arbitrarily bad in terms of the utility of the buyer. However, our main result shows that for the important class of sub modular functions, a bounded approximation ratio is achievable. Better approximation results are obtained for subclasses of the sub modular functions. We explore the space of budget feasible mechanisms in other domains and give a characterization under more restricted conditions.
View PDF Chat

Mechanism design for data science

2014-05-30
Shuchi Chawla , Jason D. Hartline , Denis Nekipelov
The promise of data science is that if data from a system can be recorded and understood then this understanding can potentially be utilized to improve the system. Behavioral and … The promise of data science is that if data from a system can be recorded and understood then this understanding can potentially be utilized to improve the system. Behavioral and economic data, however, is different from scientific data in that it is subjective to the system. Behavior changes when the system changes, and to predict behavior for any given system change or to optimize over system changes, the behavioral model that generates the data must be inferred from the data. The ease with which this inference can be performed generally also depends on the system. Trivially, a system that ignores behavior does not admit any inference of a behavior generating model that can be used to predict behavior in a system that is responsive to behavior.
View PDF Chat

Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees

2013-04-02
Vitaly Feldman , Pravesh K. Kothari , J. Vondrák
We study the complexity of approximate representation and learning of submodular functions over the uniform distribution on the Boolean hypercube $\{0,1\}^n$. Our main result is the following structural theorem: any … We study the complexity of approximate representation and learning of submodular functions over the uniform distribution on the Boolean hypercube $\{0,1\}^n$. Our main result is the following structural theorem: any submodular function is $\epsilon$-close in $\ell_2$ to a real-valued decision tree (DT) of depth $O(1/\epsilon^2)$. This immediately implies that any submodular function is $\epsilon$-close to a function of at most $2^{O(1/\epsilon^2)}$ variables and has a spectral $\ell_1$ norm of $2^{O(1/\epsilon^2)}$. It also implies the closest previous result that states that submodular functions can be approximated by polynomials of degree $O(1/\epsilon^2)$ (Cheraghchi et al., 2012). Our result is proved by constructing an approximation of a submodular function by a DT of rank $4/\epsilon^2$ and a proof that any rank-$r$ DT can be $\epsilon$-approximated by a DT of depth $\frac{5}{2}(r+\log(1/\epsilon))$. We show that these structural results can be exploited to give an attribute-efficient PAC learning algorithm for submodular functions running in time $\tilde{O}(n^2) \cdot 2^{O(1/\epsilon^{4})}$. The best previous algorithm for the problem requires $n^{O(1/\epsilon^{2})}$ time and examples (Cheraghchi et al., 2012) but works also in the agnostic setting. In addition, we give improved learning algorithms for a number of related settings. We also prove that our PAC and agnostic learning algorithms are essentially optimal via two lower bounds: (1) an information-theoretic lower bound of $2^{\Omega(1/\epsilon^{2/3})}$ on the complexity of learning monotone submodular functions in any reasonable model; (2) computational lower bound of $n^{\Omega(1/\epsilon^{2/3})}$ based on a reduction to learning of sparse parities with noise, widely-believed to be intractable. These are the first lower bounds for learning of submodular functions over the uniform distribution.

On k-Column Sparse Packing Programs

2010-01-01
Nikhil Bansal , Nitish Korula , Viswanath Nagarajan +1 more
View PDF Chat

The limitations of optimization from samples

2017-06-15
Eric Balkanski , Aviad Rubinstein , Yaron Singer
In this paper we consider the following question: can we optimize objective functions from the training data we use to learn them? We formalize this question through a novel framework … In this paper we consider the following question: can we optimize objective functions from the training data we use to learn them? We formalize this question through a novel framework we call optimization from samples (OPS). In OPS, we are given sampled values of a function drawn from some distribution and the objective is to optimize the function under some constraint.
View PDF Chat

Online Graph Algorithms with Predictions

2022-01-01
Yossi Azar , Debmalya Panigrahi , Noam Touitou
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Online Graph Algorithms with PredictionsYossi Azar, Debmalya Panigrahi, and Noam TouitouYossi Azar, Debmalya Panigrahi, … Previous chapter Next chapter Full AccessProceedings Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Online Graph Algorithms with PredictionsYossi Azar, Debmalya Panigrahi, and Noam TouitouYossi Azar, Debmalya Panigrahi, and Noam Touitoupp.35 - 66Chapter DOI:https://doi.org/10.1137/1.9781611977073.3PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract Online algorithms with predictions is a popular and elegant framework for bypassing pessimistic lower bounds in competitive analysis. In this model, online algorithms are supplied with future predictions and the goal is for the competitive ratio to smoothly interpolate between the best offline and online bounds as a function of the prediction error. In this paper, we study online graph problems with predictions. Our contributions are the following: The first question is defining prediction error. For graph/metric problems, there can be two types of error, locations that are not predicted, and locations that are predicted but the predicted and actual locations do not coincide exactly. We design a novel definition of prediction error called metric error with outliers to simultaneously capture both types of errors, which thereby generalizes previous definitions of error that only capture one of the two error types. We give a general framework for obtaining online algorithms with predictions that combines, in a "black box" fashion, existing online and offline algorithms, under certain technical conditions. To the best of our knowledge, this is the first general-purpose tool for obtaining online algorithms with predictions. Using our framework, we obtain tight bounds on the competitive ratio of several classical graph problems as a function of metric error with outliers: Steiner tree, Steiner forest, priority Steiner tree/forest, and uncapacitated/capacitated facility location. Both the definition of metric error with outliers and the general framework for combining offline and online algorithms are not specific to the problems that we consider in this paper. We hope that these will be useful for future work on other problems in this domain. Previous chapter Next chapter RelatedDetails Published:2022eISBN:978-1-61197-707-3 https://doi.org/10.1137/1.9781611977073Book Series Name:ProceedingsBook Code:PRDA22Book Pages:xvii + 3771
View PDF Chat

Robust Influence Maximization

2016-08-08
Xinran He , David Kempe
Uncertainty about models and data is ubiquitous in the computational social sciences, and it creates a need for robust social network algorithms, which can simultaneously provide guarantees across a spectrum … Uncertainty about models and data is ubiquitous in the computational social sciences, and it creates a need for robust social network algorithms, which can simultaneously provide guarantees across a spectrum of models and parameter settings. We begin an investigation into this broad domain by studying robust algorithms for the Influence Maximization problem, in which the goal is to identify a set of k nodes in a social network whose joint influence on the network is maximized. We define a Robust Influence Maximization framework wherein an algorithm is presented with a set of influence functions, typically derived from different influence models or different parameter settings for the same model. The different parameter settings could be derived from observed cascades on different topics, under different conditions, or at different times. The algorithm's goal is to identify a set of k nodes who are simultaneously influential for all influence functions, compared to the (function-specific) optimum solutions.
View PDF Chat

Prior-free auctions for budgeted agents

2013-06-16
Nikhil R. Devanur , Bach Q. Ha , Jason D. Hartline
We consider prior-free auctions for revenue and welfare maximization when agents have a common budget. The abstract environments we consider are ones where there is a downward-closed and symmetric feasibility … We consider prior-free auctions for revenue and welfare maximization when agents have a common budget. The abstract environments we consider are ones where there is a downward-closed and symmetric feasibility constraint on the probabilities of service of the agents. These environments include position auctions where slots with decreasing click-through rates are auctioned to advertisers. We generalize and characterize the envy-free benchmark from Hartline and Yan [2011] to settings with budgets and characterize the optimal envy-free outcomes for both welfare and revenue. We give prior-free mechanisms that approximate these benchmarks. A building block in our mechanism is a clinching auction for position auction environments. This auction is a generalization of the multi-unit clinching auction of Dobzinski et al. [2008] and a special case of the polyhedral clinching auction of Goel et al. [2012]. For welfare maximization, we show that this clinching auction is a good approximation to the envy-free optimal welfare for position auction environments. For profit maximization, we generalize the random sampling profit extraction auction from Fiat et al. [2002] for digital goods to give a 10.0-approximation to the envy-free optimal revenue in symmetric, downward-closed environments. Even without budgets this revenue maximization question is of interest and we obtain an improved approximation bound of 7.5 (from 30.4 by Ha and Hartline [2012]).
View PDF Chat

On the Power of Deterministic Mechanisms for Facility Location Games

2014-10-28
Dimitris Fotakis , Christos Tzamos
We consider K -Facility Location games, where n strategic agents report their locations in a metric space and a mechanism maps them to K facilities. The agents seek to minimize … We consider K -Facility Location games, where n strategic agents report their locations in a metric space and a mechanism maps them to K facilities. The agents seek to minimize their connection cost, namely the distance of their true location to the nearest facility, and may misreport their location. We are interested in deterministic mechanisms that are strategyproof, that is, ensure that no agent can benefit from misreporting her location, do not resort to monetary transfers, and achieve a bounded approximation ratio to the total connection cost of the agents (or to the L p norm of the connection costs, for some p ∈ [1, ∞) or for p = ∞). Our main result is an elegant characterization of deterministic strategyproof mechanisms with a bounded approximation ratio for 2-Facility Location on the line. In particular, we show that for instances with n ≥ 5 agents, any such mechanism either admits a unique dictator or always places the facilities at the leftmost and the rightmost location of the instance. As a corollary, we obtain that the best approximation ratio achievable by deterministic strategyproof mechanisms for the problem of locating 2 facilities on the line to minimize the total connection cost is precisely n -2. Another rather surprising consequence is that the Two-Extremes mechanism of Procaccia and Tennenholtz [2009] is the only deterministic anonymous strategyproof mechanism with a bounded approximation ratio for 2-Facility Location on the line. The proof of the characterization employs several new ideas and technical tools, which provide new insights into the behavior of deterministic strategyproof mechanisms for K -Facility Location games and may be of independent interest. Employing one of these tools, we show that for every K ≥ 3, there do not exist any deterministic anonymous strategyproof mechanisms with a bounded approximation ratio for K -Facility Location on the line, even for simple instances with K +1 agents. Moreover, building on the characterization for the line, we show that there do not exist any deterministic strategyproof mechanisms with a bounded approximation ratio for 2-Facility Location and instances with n ≥ 3 agents located in a star.
View PDF Chat

Walrasian's characterization and a universal ascending auction

2017-06-03
Oren Ben-Zwi
View PDF Chat

Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas

2013-07-12
Vitaly Feldman , Jan Vondrák
We investigate the approximability of several classes of real-valued functions by functions of a small number of variables ({\em juntas}). Our main results are tight bounds on the number of … We investigate the approximability of several classes of real-valued functions by functions of a small number of variables ({\em juntas}). Our main results are tight bounds on the number of variables required to approximate a function $f:\{0,1\}^n \rightarrow [0,1]$ within $\ell_2$-error $\epsilon$ over the uniform distribution: 1. If $f$ is submodular, then it is $\epsilon$-close to a function of $O(\frac{1}{\epsilon^2} \log \frac{1}{\epsilon})$ variables. This is an exponential improvement over previously known results. We note that $\Omega(\frac{1}{\epsilon^2})$ variables are necessary even for linear functions. 2. If $f$ is fractionally subadditive (XOS) it is $\epsilon$-close to a function of $2^{O(1/\epsilon^2)}$ variables. This result holds for all functions with low total $\ell_1$-influence and is a real-valued analogue of Friedgut's theorem for boolean functions. We show that $2^{\Omega(1/\epsilon)}$ variables are necessary even for XOS functions. As applications of these results, we provide learning algorithms over the uniform distribution. For XOS functions, we give a PAC learning algorithm that runs in time $2^{poly(1/\epsilon)} poly(n)$. For submodular functions we give an algorithm in the more demanding PMAC learning model (Balcan and Harvey, 2011) which requires a multiplicative $1+\gamma$ factor approximation with probability at least $1-\epsilon$ over the target distribution. Our uniform distribution algorithm runs in time $2^{poly(1/(\gamma\epsilon))} poly(n)$. This is the first algorithm in the PMAC model that over the uniform distribution can achieve a constant approximation factor arbitrarily close to 1 for all submodular functions. As follows from the lower bounds in (Feldman et al., 2013) both of these algorithms are close to optimal. We also give applications for proper learning, testing and agnostic learning with value queries of these classes.

An Adaptivity Hierarchy Theorem for Property Testing

2017-02-19
Clément L. Canonne , Tom Gur
Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of \emph{adaptive} testing algorithms, … Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of \emph{adaptive} testing algorithms, wherein each query may be determined by the answers received to prior queries, and their \emph{non-adaptive} counterparts, in which all queries are independent of answers obtained from previous queries. In this work, we investigate the role of in property testing at a finer level. We first quantify the degree of of a testing algorithm by considering the number of of adaptivity it uses. More accurately, we say that a tester is $k$-(round) adaptive if it makes queries in $k+1$ rounds, where the queries in the $i$'th round may depend on the answers obtained in the previous $i-1$ rounds. Then, we ask the following question: Does the power of testing algorithms smoothly grow with the number of rounds of adaptivity? We provide a positive answer to the foregoing question by proving an hierarchy theorem for property testing. Specifically, our main result shows that for every $n\in \mathbb{N}$ and $0 \le k \le n^{0.99}$ there exists a property $\mathcal{P}_{n,k}$ of functions for which (1) there exists a $k$-adaptive tester for $\mathcal{P}_{n,k}$ with query complexity $\tilde{O}(k)$, yet (2) any $(k-1)$-adaptive tester for $\mathcal{P}_{n,k}$ must make $\Omega(n)$ queries. In addition, we show that such a qualitative hierarchy can be witnessed for testing natural properties of graphs.

The non-adaptive query complexity of testing k-parities

2012-01-01
Harry Buhrman , David García-Soriano , Arie Matsliah +1 more
We prove tight bounds of Theta(k log k) queries for non-adaptively testing whether a function f:{0,1}^n -&gt; {0,1} is a k-parity or far from any k-parity. The lower bound combines … We prove tight bounds of Theta(k log k) queries for non-adaptively testing whether a function f:{0,1}^n -&gt; {0,1} is a k-parity or far from any k-parity. The lower bound combines a recent method of Blais, Brody and Matulef [BBM11] to get lower bounds for testing from communication complexity with an Omega(k \log k) lower bound for the one-way communication complexity of k-disjointness.

Limitations of randomized mechanisms for combinatorial auctions

2014-01-31
Shaddin Dughmi , Jan Vondrák
View PDF Chat

Inferring networks of diffusion and influence

2010-07-25
Manuel Gomez-Rodriguez , Jure Leskovec , Andreas Krause
Information diffusion and virus propagation are fundamental processes talking place in networks. While it is often possible to directly observe when nodes become infected, observing individual transmissions (i.e., who infects … Information diffusion and virus propagation are fundamental processes talking place in networks. While it is often possible to directly observe when nodes become infected, observing individual transmissions (i.e., who infects whom or who influences whom) is typically very difficult. Furthermore, in many applications, the underlying network over which the diffusions and propagations spread is actually unobserved. We tackle these challenges by developing a method for tracing paths of diffusion and influence through networks and inferring the networks over which contagions propagate. Given the times when nodes adopt pieces of information or become infected, we identify the optimal network that best explains the observed infection times. Since the optimization problem is NP-hard to solve exactly, we develop an efficient approximation algorithm that scales to large datasets and in practice gives provably near-optimal performance. We demonstrate the effectiveness of our approach by tracing information cascades in a set of 170 million blogs and news articles over a one year period to infer how information flows through the online media space. We find that the diffusion network of news tends to have a core-periphery structure with a small set of core media sites that diffuse information to the rest of the Web. These sites tend to have stable circles of influence with more general news media sites acting as connectors between them.
View PDF Chat

Non-monotone Submodular Maximization with Nearly Optimal Adaptivity Complexity.

2018-08-19
Matthew Fahrbach , Vahab Mirrokni , Morteza Zadimoghaddam
As a generalization of many classic problems in combinatorial optimization, submodular optimization has found a wide range of applications in machine learning (e.g., in feature engineering and active learning). For … As a generalization of many classic problems in combinatorial optimization, submodular optimization has found a wide range of applications in machine learning (e.g., in feature engineering and active learning). For many large-scale optimization problems, we are often concerned with the adaptivity complexity of an algorithm, which quantifies the number of sequential rounds where polynomially-many independent function evaluations can be executed in parallel. While low adaptivity is ideal, it is not sufficient for a distributed algorithm to be efficient, since in many practical applications of submodular optimization the number of function evaluations becomes prohibitively expensive. Motivated by such applications, we study the adaptivity and query complexity of non-monotone submodular optimization. We provide the first constant approximation algorithm for maximizing a non-monotone submodular function with cardinality constraint $k$ that has nearly-optimal adaptivity complexity $O(\log(n))$. Furthermore, our algorithm makes only $O(\log(k))$ calls per element to the function evaluation oracle in expectation.

Settling the query complexity of non-adaptive junta testing

2017-01-01
Xi Chen , Rocco A. Servedio , Li-Yang Tan +2 more
We prove that any non-adaptive algorithm that tests whether an unknown Boolean function $f: \{0, 1\}^n\to \{0, 1\}$ is a $k$-junta or $\epsilon$-far from every $k$-junta must make $\widetilde{\Omega}(k^{3/2} / … We prove that any non-adaptive algorithm that tests whether an unknown Boolean function $f: \{0, 1\}^n\to \{0, 1\}$ is a $k$-junta or $\epsilon$-far from every $k$-junta must make $\widetilde{\Omega}(k^{3/2} / \epsilon)$ many queries for a wide range of parameters $k$ and $\epsilon$. Our result dramatically improves previous lower bounds from [BGSMdW13, STW15], and is essentially optimal given Blais's non-adaptive junta tester from [Blais08], which makes $\widetilde{O}(k^{3/2})/\epsilon$ queries. Combined with the adaptive tester of [Blais09] which makes $O(k\log k + k /\epsilon)$ queries, our result shows that adaptivity enables polynomial savings in query complexity for junta testing.
View PDF Chat

On the Power of Adaptivity in Sparse Recovery

2011-10-17
Piotr Indyk , Eric Price , David P. Woodruff
The goal of (stable) sparse recovery is to recover a $k$-sparse approximation $x*$ of a vector $x$ from linear measurements of $x$. Specifically, the goal is to recover $x*$ such … The goal of (stable) sparse recovery is to recover a $k$-sparse approximation $x*$ of a vector $x$ from linear measurements of $x$. Specifically, the goal is to recover $x*$ such that ||x-x*||_p <= C min_{k-sparse x'} ||x-x'||_q for some constant $C$ and norm parameters $p$ and $q$. It is known that, for $p=q=1$ or $p=q=2$, this task can be accomplished using $m=O(k \log (n/k))$ non-adaptive measurements [CRT06] and that this bound is tight [DIPW10,FPRU10,PW11]. In this paper we show that if one is allowed to perform measurements that are adaptive, then the number of measurements can be considerably reduced. Specifically, for $C=1+eps$ and $p=q=2$ we show - A scheme with $m=O((1/eps)k log log (n eps/k))$ measurements that uses $O(log* k \log \log (n eps/k))$ rounds. This is a significant improvement over the best possible non-adaptive bound. - A scheme with $m=O((1/eps) k log (k/eps) + k \log (n/k))$ measurements that uses /two/ rounds. This improves over the best possible non-adaptive bound. To the best of our knowledge, these are the first results of this type. As an independent application, we show how to solve the problem of finding a duplicate in a data stream of $n$ items drawn from ${1, 2, ..., n-1}$ using $O(log n)$ bits of space and $O(log log n)$ passes, improving over the best possible space complexity achievable using a single pass.

Dependent Randomized Rounding for Matroid Polytopes and Applications

2009-01-01
Chandra Chekuri , J. Vondrák , Rico Zenklusen
Motivated by several applications, we consider the problem of randomly rounding a fractional solution in a matroid (base) polytope to an integral one. We consider the pipage rounding technique and … Motivated by several applications, we consider the problem of randomly rounding a fractional solution in a matroid (base) polytope to an integral one. We consider the pipage rounding technique and also present a new technique, randomized swap rounding. Our main technical results are concentration bounds for functions of random variables arising from these rounding techniques. We prove Chernoff-type concentration bounds for linear functions of random variables arising from both techniques, and also a lower-tail exponential bound for monotone submodular functions of variables arising from randomized swap rounding. The following are examples of our applications: (1) We give a (1-1/e-epsilon)-approximation algorithm for the problem of maximizing a monotone submodular function subject to 1 matroid and k linear constraints, for any constant k and epsilon&gt;0. (2) We present a result on minimax packing problems that involve a matroid base constraint. We give an O(log m / log log m)-approximation for the general problem Min {lambda: x \in {0,1}^N, x \in B(M), Ax &lt;= lambda b}, where m is the number of packing constraints. (3) We generalize the continuous greedy algorithm to problems involving multiple submodular functions, and use it to find a (1-1/e-epsilon)-approximate pareto set for the problem of maximizing a constant number of monotone submodular functions subject to a matroid constraint. An example is the Submodular Welfare Problem where we are looking for an approximate pareto set with respect to individual players' utilities.

Mixture Selection, Mechanism Design, and Signaling

2015-10-01
Yu Cheng , Ho Yee Cheung , Shaddin Dughmi +3 more
We pose and study a fundamental algorithmic problem which we term mixture selection, arising as a building block in a number of game-theoretic applications: Given a function g from the … We pose and study a fundamental algorithmic problem which we term mixture selection, arising as a building block in a number of game-theoretic applications: Given a function g from the n-dimensional hypercube to the bounded interval [-1, 1], and an n × rn matrix A with bounded entries, maximize g(Ax) over x in the m-dimensional simplex. This problem arises naturally when one seeks to design a lottery over items for sale in an auction, or craft the posterior beliefs for agents in a Bayesian game through the provision of information (a.k.a. signaling). We present an approximation algorithm for this problem when g simultaneously satisfies two "smoothness" properties: Lipschitz continuity with respect to the L <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∞</sup> norm, and noise stability. The latter notion, which we define and cater to our setting, controls the degree to which low-probability - and possibly correlated - errors in the inputs of g can impact its output. The approximation guarantee of our algorithm degrades gracefully as a function of the Lipschitz continuity and noise stability of g. In particular, when g is both 0(1)-Lipschitz continuous and 0(1)-stable, we obtain an (additive) polynomial-time approximation scheme (PTAS) for mixture selection. We also show that neither assumption suffices by itself for an additive PTAS, and both assumptions together do not suffice for an additive fully polynomial-time approximation scheme (FPTAS). We apply our algorithm for mixture selection to a number of different game-theoretic applications, focusing on problems from mechanism design and optimal signaling. In particular, we make progress on a number of open problems suggested in prior work by easily reducing them to mixture selection: we resolve an important special case of the small-menu lottery design problem posed by Dughmi, Han, and Nisan [10]; we resolve the problem of revenue-maximizing signaling in Bayesian secondprice auctions posed by Emek et al. [12] and Miltersen and Sheffet [5]; we design a quasipolynomial-time approximation scheme for the optimal signaling problem in normal form games suggested by Dughmi [9]; and we design an approximation algorithm for the optimal signaling problem in the voting model of Alonso and Camara [3].
View PDF Chat

Discrete convex analysis: A tool for economics and game theory

2016-12-14
Kazuo Murota
This paper presents discrete convex analysis as a tool for use in economics and game theory.Discrete convex analysis is a new framework of discrete mathematics and optimization, developed during the … This paper presents discrete convex analysis as a tool for use in economics and game theory.Discrete convex analysis is a new framework of discrete mathematics and optimization, developed during the last two decades.Recently, it has been recognized as a powerful tool for analyzing economic or game models with indivisibilities.The main feature of discrete convex analysis is the distinction of two convexity concepts, M-convexity and L-convexity, for functions in integer or binary variables, together with their conjugacy relationship.The crucial fact is that M-concavity in its variant is equivalent to the gross substitutes property in economics.Fundamental theorems in discrete convex analysis such as the M-L conjugacy theorems, discrete separation theorems and discrete fixed point theorems yield structural results in economics such as the existence of equilibria and the lattice structure of equilibrium price vectors.Algorithms in discrete convex analysis provide iterative auction algorithms for finding equilibria.
View PDF Chat

The Sample Complexity of Optimizing a Convex Function

2017-06-18
Eric Balkanski , Yaron Singer

Rewarding Maps: On Greedy Optimization of Set Functions

1995-12-01
Andreas Dress , Werner Terhalle

Matroid rank functions and discrete concavity

2012-06-19
Akiyoshi Shioura

Budget feasible mechanism design: from prior-free to bayesian

2012-05-19
Xiaohui Bei , Ning Chen , Nick Gravin +1 more
Budget feasible mechanism design studies procurement combinatorial auctions in the sellers have private costs to produce items, and the buyer (auctioneer) aims to maximize a social valuation function on subsets … Budget feasible mechanism design studies procurement combinatorial auctions in the sellers have private costs to produce items, and the buyer (auctioneer) aims to maximize a social valuation function on subsets of items, under the budget constraint on the total payment. One of the most important questions in the field is which valuation domains admit truthful budget feasible mechanisms with 'small' approximations (compared to the social optimum)? Singer [35] showed that additive and submodular functions have a constant approximation mechanism. Recently, Dobzinski, Papadimitriou, and Singer [20] gave an O(log2n) approximation mechanism for subadditive functions; further, they remarked that: A fundamental question is whether, regardless of computational constraints, a constant-factor budget feasible mechanism exists for subadditive In this paper, we address this question from two viewpoints: prior-free worst case analysis and Bayesian analysis, are two standard approaches from computer science and economics, respectively. - For the prior-free framework, we use a linear program (LP) that describes the fractional cover of the valuation function; the LP is also connected to the concept of approximate core in cooperative game theory. We provide a mechanism for subadditive functions whose approximation is O(I), via the worst case integrality gap I of this LP. This implies an O(log n)-approximation for subadditive valuations, O(1)-approximation for XOS valuations, as well as for valuations having a constant integrality gap. XOS valuations are an important class of functions and lie between the submodular and the subadditive classes of valuations. We further give another polynomial time O(log n/(log log n)) sub-logarithmic approximation mechanism for subadditive functions. Both of our mechanisms improve the best known approximation ratio O(log2 n). - For the Bayesian framework, we provide a constant approximation mechanism for all subadditive functions, using the above prior-free mechanism for XOS valuations as a subroutine. Our mechanism allows correlations in the distribution of private information and is universally truthful.
View PDF Chat

Submodular function maximization via the multilinear relaxation and contention resolution schemes

2011-06-06
Chandra Chekuri , Jan Vondrák , Rico Zenklusen
We consider the problem of maximizing a non-negative submodular set function f:2N -> RR+ over a ground set N subject to a variety of packing type constraints including (multiple) matroid … We consider the problem of maximizing a non-negative submodular set function f:2N -> RR+ over a ground set N 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 f may be a non-monotone function. Our algorithms are based on (approximately) solving the multilinear extension F of f [5] over a polytope P that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully in some settings [6, 22, 24, 13, 3], it has been limited in some important ways. We overcome these limitations as follows.
View PDF Chat

Making the Most of Your Samples

2015-06-12
Zhiyi Huang , Yishay Mansour , Tim Roughgarden
We study the problem of setting a price for a potential buyer with a valuation drawn from an unknown distribution D. The seller has "data" about D in the form … We study the problem of setting a price for a potential buyer with a valuation drawn from an unknown distribution D. The seller has "data" about D in the form of m ≥ 1 i.i.d. samples, and the algorithmic challenge is to use these samples to obtain expected revenue as close as possible to what could be achieved with advance knowledge of D.
View PDF Chat

Mechanism Design via Correlation Gap

2010-01-01
Qiqi Yan
For revenue and welfare maximization in single-dimensional Bayesian settings, Chawla et al. (STOC10) recently showed that sequential posted-price mechanisms (SPMs), though simple in form, can perform surprisingly well compared to … For revenue and welfare maximization in single-dimensional Bayesian settings, Chawla et al. (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 Agrawal et al.\ (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 Chawla et al.\ for several environments. In particular, we show that it gives an $e/(e-1)$-approximation for matroid environments, gives asymptotically a $1/(1-1/\sqrt{2\pi 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.
View PDF Chat

Introduction to Online Convex Optimization

2016-01-01
Elad Hazan
Introduction to Online Convex Optimization portrays optimization as a process. In many practical applications the environment is so complex that it is infeasible to lay out a comprehensive theoretical model … Introduction to Online Convex Optimization portrays optimization as a process. In many practical applications the environment is so complex that it is infeasible to lay out a comprehensive theoretical model and use classical algorithmic theory and mathematical optimization. It is necessary as well as beneficial to take a robust approach, by applying an optimization method that learns as one goes along, learning from experience as more aspects of the problem are observed. This view of optimization as a process has become prominent in varied fields and has led to some spectacular success in modeling and systems that are now part of our daily lives. Introduction to Online Convex Optimization is intended to serve as a reference for a self-contained course on online convex optimization and the convex optimization approach to machine learning for the educated graduate student in computer science/electrical engineering/ operations research/statistics and related fields. It is also an ideal reference for the researcher diving into this fascinating world at the intersection of optimization and machine learning.
View PDF Chat

Comments on bases in dependence structures

1969-08-01
Richard A. Brualdi
Dependence structures (in the finite case, matroids) arise when one tries to abstract the properties of linear dependence of vectors in a vector space. With the help of a theorem … Dependence structures (in the finite case, matroids) arise when one tries to abstract the properties of linear dependence of vectors in a vector space. With the help of a theorem due to P. Hall and M. Hall, Jr concerning systems of distinct representatives of families of finite sets, it is proved that if B 1 and B 2 are bases of a dependence structure, then there is an injection σ: B 1 → B 2 such that ( B 2 / {σ( e )}) ∩ { e } is a basis for all e in B 1 . A corollary is the theorem of R. Rado that all bases have the same cardinal number. In particular, it applies to bases of a vector space. Also proved is the fact that if B 1 and B 2 are bases of a dependence structure then given e in B 1 there is an f in B 2 such that both ( B 1 / { e }) ∩ { f } and ( B 2 / { f }) ∩ { e } are bases. This is a symmetrical kind of replacement theorem.
View PDF Chat

Mechanism Design for Crowdsourcing: An Optimal 1-1/e Competitive Budget-Feasible Mechanism for Large Markets

2014-10-01
Nima Anari , Gagan Goel , Afshin Nikzad
In this paper we consider a mechanism design problem in the context of large-scale crowdsourcing markets such as Amazon's Mechanical Turk mturk, ClickWorker clickworker, CrowdFlower crowdflower. In these markets, there … In this paper we consider a mechanism design problem in the context of large-scale crowdsourcing markets such as Amazon's Mechanical Turk mturk, ClickWorker clickworker, CrowdFlower crowdflower. In these markets, there is a requester who wants to hire workers to accomplish some tasks. Each worker is assumed to give some utility to the requester on getting hired. Moreover each worker has a minimum cost that he wants to get paid for getting hired. This minimum cost is assumed to be private information of the workers. The question then is -- if the requester has a limited budget, how to design a direct revelation mechanism that picks the right set of workers to hire in order to maximize the requester's utility? We note that although the previous work (Singer (2010) chen et al. (2011)) has studied this problem, a crucial difference in which we deviate from earlier work is the notion of large-scale markets that we introduce in our model. Without the large market assumption, it is known that no mechanism can achieve a competitive ratio better than 0.414 and 0.5 for deterministic and randomized mechanisms respectively (while the best known deterministic and randomized mechanisms achieve an approximation ratio of 0.292 and 0.33 respectively). In this paper, we design a budget-feasible mechanism for large markets that achieves a competitive ratio of 1 - 1/e ≃ 0.63. Our mechanism can be seen as a generalization of an alternate way to look at the proportional share mechanism, which is used in all the previous works so far on this problem. Interestingly, we can also show that our mechanism is optimal by showing that no truthful mechanism can achieve a factor better than 1 - 1/e, thus, fully resolving this setting. Finally we consider the more general case of submodular utility functions and give new and improved mechanisms for the case when the market is large.
View PDF Chat

Strategyproof Facility Location for Concave Cost Functions

2015-07-13
Dimitris Fotakis , Christos Tzamos
View PDF Chat

A truthful randomized mechanism for combinatorial public projects via convex optimization

2011-06-05
Shaddin Dughmi
In Combinatorial Public Projects, there is a set of projects that may be undertaken, and a set of self-interested players with a stake in the set of projects chosen. A … In Combinatorial Public Projects, there is a set of projects that may be undertaken, and a set of self-interested players with a stake in the set of projects chosen. A public planner must choose a subset of these projects, subject to a resource constraint, with the goal of maximizing social welfare. Combinatorial Public Projects has emerged as one of the paradigmatic problems in Algorithmic Mechanism Design, a field concerned with solving fundamental resource allocation problems in the presence of both selfish behavior and the computational constraint of polynomial time. We design a polynomial-time, truthful-in-expectation, (1-1/e)-approximation mechanism for welfare maximization in a fundamental variant of combinatorial public projects. Our results apply to combinatorial public projects when players have valuations that are matroid rank sums (MRS), which encompass most concrete examples of submodular functions studied in this context, including coverage functions and matroid weighted-rank functions. Our approximation factor is the best possible, assuming P ≠ NP. Ours is the first mechanism that achieves a constant factor approximation for a natural NP-hard variant of combinatorial public projects.
View PDF Chat

Optimal approximation for submodular and supermodular optimization with bounded curvature

2015-01-04
Maxim Sviridenko , Jan Vondrák , Justin Ward
We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to … We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a nondecreasing submodular function or minimize a nonincreasing supermodular function in the setting of bounded total curvature c. In the case of submodular maximization with curvature c, we obtain a (1 − c/e)-approximation --- the first improvement over the greedy (1 − e--c)/c-approximation of Conforti and Cornuejols from 1984, which holds for a cardinality constraint, as well as recent approaches that hold for an arbitrary matroid constraint.Our approach is based on modifications of the continuous greedy algorithm and non-oblivious local search, and allows us to approximately maximize the sum of a nonnegative, nondecreasing submodular function and a (possibly negative) linear function. We show how to reduce both submodular maximization and supermodular minimization to this general problem when the objective function has bounded total curvature.We prove that the approximation results we obtain are the best possible in the value oracle model, even in the case of a cardinality constraint. Finally, we give two concrete applications of our results in the settings of maximum entropy sampling, and the column-subset selection problem.

Learning Time-Varying Coverage Functions.

2014-12-08
Nan Du , Yingyu Liang , Maria-Florina Balcan +1 more
Coverage functions are an important class of discrete functions that capture the law of diminishing returns arising naturally from applications in social network analysis, machine learning, and algorithmic game theory. … Coverage functions are an important class of discrete functions that capture the law of diminishing returns arising naturally from applications in social network analysis, machine learning, and algorithmic game theory. In this paper, we propose a new problem of learning time-varying coverage functions, and develop a novel parametrization of these functions using random features. Based on the connection between time-varying coverage functions and counting processes, we also propose an efficient parameter learning algorithm based on likelihood maximization, and provide a sample complexity analysis. We applied our algorithm to the influence function estimation problem in information diffusion in social networks, and show that with few assumptions about the diffusion processes, our algorithm is able to estimate influence significantly more accurately than existing approaches on both synthetic and real world data.

Sampling and Representation Complexity of Revenue Maximization

2014-01-01
Shaddin Dughmi , Li Han , Noam Nisan
View PDF Chat

Social Status and Badge Design

2015-05-18
Nicole Immorlica , Greg Stoddard , Vasilis Syrgkanis
Many websites encourage user participation via the use of virtual rewards like badges. While badges typically have no explicit value, they act as symbols of social status within a community. … Many websites encourage user participation via the use of virtual rewards like badges. While badges typically have no explicit value, they act as symbols of social status within a community. In this paper, we study how to design virtual incentive mechanisms that maximize total contributions to a website when users are motivated by social status. We consider a game-theoretic model where users exert costly effort to make contributions and, in return, are awarded with badges. The value of a badge is determined endogenously by the number of users who earn an equal or higher badge; as more users earn a particular badge, the value of that badge diminishes for all users. We show that among all possible mechanisms for assigning status-driven rewards, the optimal mechanism is a leaderboard with a cutoff: users that contribute less than a certain threshold receive nothing while the remaining are ranked by contribution. We next study the necessary features of approximately optimal mechanisms and find that approximate optimality is influenced by the the convexity of status valuations. When status valuations are concave, any approximately optimal mechanism must contain a coarse status partition, i.e. a partition of users into status classes whose size will grow as the population grows. Conversely when status valuations are convex, we prove that fine partitioning, that is a partition of users into status classes whose size stays constant as the population grows, is necessary for approximate optimality.
View PDF Chat

Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity

2019-01-01
Matthew Fahrbach , Vahab Mirrokni , Morteza Zadimoghaddam
Submodular optimization generalizes many classic problems in combinatorial optimization and has recently found a wide range of applications in machine learning (e.g., feature engineering and active learning). For many large-scale … Submodular optimization generalizes many classic problems in combinatorial optimization and has recently found a wide range of applications in machine learning (e.g., feature engineering and active learning). For many large-scale optimization problems, we are often concerned with the adaptivity complexity of an algorithm, which quantifies the number of sequential rounds where polynomially-many independent function evaluations can be executed in parallel. While low adaptivity is ideal, it is not sufficient for a distributed algorithm to be efficient, since in many practical applications of submodular optimization the number of function evaluations becomes prohibitively expensive. Motivated by these applications, we study the adaptivity and query complexity of adaptive submodular optimization. Our main result is a distributed algorithm for maximizing a monotone submodular function with cardinality constraint $k$ that achieves a $(1-1/e-\varepsilon)$-approximation in expectation. This algorithm runs in $O(\log(n))$ adaptive rounds and makes $O(n)$ calls to the function evaluation oracle in expectation. The approximation guarantee and query complexity are optimal, and the adaptivity is nearly optimal. Moreover, the number of queries is substantially less than in previous works. Last, we extend our results to the submodular cover problem to demonstrate the generality of our algorithm and techniques.
View PDF Chat

Parallel Algorithms for Select and Partition with Noisy Comparisons

2016-03-16
Mark Braverman , Jieming Mao , S. Matthew Weinberg
We consider the problem of finding the $k^{th}$ highest element in a totally ordered set of $n$ elements (select), and partitioning a totally ordered set into the top $k$ and … We consider the problem of finding the $k^{th}$ highest element in a totally ordered set of $n$ elements (select), and partitioning a totally ordered set into the top $k$ and bottom $n-k$ elements (partition) using pairwise comparisons. Motivated by settings like peer grading or crowdsourcing, where multiple rounds of interaction are costly and queried comparisons may be inconsistent with the ground truth, we evaluate algorithms based both on their total runtime and the number of interactive rounds in three comparison models: noiseless (where the comparisons are correct), erasure (where comparisons are erased with probability $1-\gamma$), and noisy (where comparisons are correct with probability $1/2+\gamma/2$ and incorrect otherwise). We provide numerous matching upper and lower bounds in all three models. Even our results in the noiseless model, which is quite well-studied in the TCS literature on parallel algorithms, are novel.

Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas

2013-10-01
Vitaly Feldman , Jan Vondrák
We investigate the approximability of several classes of real-valued functions by functions of a small number of variables (juntas). Our main results are tight bounds on the number of variables … We investigate the approximability of several classes of real-valued functions by functions of a small number of variables (juntas). Our main results are tight bounds on the number of variables required to approximate a function f:{0, 1} <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> → [0,1] within ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> -error ϵ over the uniform distribution: If f is sub modular, then it is ϵ-close to a function of O(1/ϵ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> log 1/ϵ) variables. This is an exponential improvement over previously known results FeldmanKV:13. We note that Ω(1/ϵ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) variables are necessary even for linear functions. If f is fractionally sub additive (XOS) it is ε-close to a function of 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(1/ϵ2)</sup> variables. This result holds for all functions with low total ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -influence and is a real-valued analogue of Fried gut's theorem for boolean functions. We show that 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Ω(1/ϵ)</sup> variables are necessary even for XOS functions. As applications of these results, we provide learning algorithms over the uniform distribution. For XOS functions, we give a PAC learning algorithm that runs in time 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/poly(ϵ)</sup> poly(n). For sub modular functions we give an algorithm in the more demanding PMAC learning model BalcanHarvey:[12] which requires a multiplicative (1 + γ) factor approximation with probability at least 1 - ϵ over the target distribution. Our uniform distribution algorithm runs in time 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/poly(γϵ)</sup> poly(n). This is the first algorithm in the PMAC model that can achieve a constant approximation factor arbitrarily close to 1 for all sub modular functions (even over the uniform distribution). It relies crucially on our approximation by junta result. As follows from the lower bounds in FeldmanKV:13 both of these algorithms are close to optimal. We also give applications for proper learning, testing and agnostic learning with value queries of these classes.
View PDF Chat

On the Power of Adaptivity in Sparse Recovery

2011-10-01
Piotr Indyk , Eric Price , David P. Woodruff
The goal of (stable) sparse recovery is to recover a k-sparse approximation x* of a vector x from linear measurements of x. Specifically, the goal is to recover x* such … The goal of (stable) sparse recovery is to recover a k-sparse approximation x* of a vector x from linear measurements of x. Specifically, the goal is to recover x* such that ∥x-x*∥ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub> ≤ C min, k-sparse x, ∥x-x'∥ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</sub> for some constant C and norm parameters p and q. It is known that, for p = q=l or p = q = 2, this task can be accomplished using m = O(k log(n/k)) non-adaptive measurements [3] and that this bound is tight [9], [12], [28]. In this paper we show that if one is allowed to perform measurements that are adaptive, then the number of measurements can be considerably reduced. Specifically, for C = 1+∈ and p = q = 2 we show · A scheme with m= O(1/∈ log log (n∈/k)) measurements that uses O(log* k · log log(n∈/k)) rounds. This is a significant improvement over the best possible non-adaptive bound. · A scheme with m = O(1/∈k log(k/∈) + k log(n/k)) measurements that uses two rounds. This improves over the best possible non-adaptive bound. To the best of our knowledge, these are the first results of this type.
View PDF Chat

Incentivizing High Quality Crowdwork

2015-05-18
Chien-Ju Ho , Aleksandrs Slivkins , Siddharth Suri +1 more
We study the causal effects of financial incentives on the quality of crowdwork. We focus on performance-based payments (PBPs), bonus payments awarded to workers for producing high quality work. We … We study the causal effects of financial incentives on the quality of crowdwork. We focus on performance-based payments (PBPs), bonus payments awarded to workers for producing high quality work. We design and run randomized behavioral experiments on the popular crowdsourcing platform Amazon Mechanical Turk with the goal of understanding when, where, and why PBPs help, identifying properties of the payment, payment structure, and the task itself that make them most effective. We provide examples of tasks for which PBPs do improve quality. For such tasks, the effectiveness of PBPs is not too sensitive to the threshold for quality required to receive the bonus, while the magnitude of the bonus must be large enough to make the reward salient. We also present examples of tasks for which PBPs do not improve quality. Our results suggest that for PBPs to improve quality, the task must be effort-responsive: the task must allow workers to produce higher quality work by exerting more effort. We also give a simple method to determine if a task is effort-responsive a priori. Furthermore, our experiments suggest that all payments on Mechanical Turk are, to some degree, implicitly performance-based in that workers believe their work may be rejected if their performance is sufficiently poor. Finally, we propose a new model of worker behavior that extends the standard principal-agent model from economics to include a worker's subjective beliefs about his likelihood of being paid, and show that the predictions of this model are in line with our experimental findings. This model may be useful as a foundation for theoretical studies of incentives in crowdsourcing markets.
View PDF Chat

Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers

2014-01-01
Saeed Alaei
We present a general framework for approximately reducing the mechanism design problem for multiple agents to single agent subproblems in the context of Bayesian combinatorial auctions. Our framework can be … We present a general framework for approximately reducing the mechanism design problem for multiple agents to single agent subproblems in the context of Bayesian combinatorial auctions. Our framework can be applied to any setting which roughly satisfies the following assumptions: (i) agents' types are distributed independently (not necessarily identically), (ii) objective function is additively separable over the agents, and (iii) there are no interagent constraints except for the supply constraints (i.e., that the total allocation of each item should not exceed the supply). Our framework is general in the sense that it makes no direct assumption about agents' valuations, type distributions, or single agent constraints (e.g., budget, incentive compatibility, etc.). We present two generic multiagent mechanisms which use single agent mechanisms as black boxes. If an $\alpha$-approximate single agent mechanism is available for each agent, and assuming no agent ever demands more than $\frac{1}{k}$ of all units of each item, our generic multiagent mechanisms are $\gamma_{k}\alpha$-approximations of the optimal multiagent mechanism, where $\gamma_{k}$ is a constant which is at least $1-\frac{1}{\sqrt{k+3}}$. As a byproduct of our construction, we present a generalization of prophet inequalities where both gambler and prophet are allowed to pick $k$ numbers each to receive a reward equal to their sum. Finally, we use our framework to obtain multiagent mechanisms with improved approximation factor for several settings from the literature.
View PDF Chat

Privately Releasing Conjunctions and the Statistical Query Barrier

2013-01-01
Anupam Gupta , Moritz Hardt , Aaron Roth +1 more
Suppose we would like to know all answers to a set of statistical queries $C$ on a data set up to small error, but we can access the data itself … Suppose we would like to know all answers to a set of statistical queries $C$ on a data set up to small error, but we can access the data itself only by using statistical queries. A trivial solution is to exhaustively ask all queries in $C$. In this paper, we investigate how and when we can do better than this naïve approach. We show that the number of statistical queries necessary and sufficient for this task is---up to polynomial factors---equal to the agnostic learning complexity of $C$ in Kearns' statistical query (SQ) model. This gives a complete answer to the question when run-time is not a concern. We then show that the problem can be solved efficiently (allowing arbitrary error on a small fraction of queries) whenever the answers to $C$ can be described by a submodular function. This includes many natural concept classes, such as graph cuts and Boolean disjunctions and conjunctions. These results are interesting not only from a learning theoretic point of view, but also from the perspective of privacy-preserving data analysis. In this context, our second result leads to an algorithm that efficiently releases differentially private answers to all Boolean conjunctions with 1% average error. This presents significant progress on a key open problem in privacy-preserving data analysis. Our first result, on the other hand, gives unconditional lower bounds on any differentially private algorithm that admits a (potentially non--privacy-preserving) implementation using only statistical queries. Not only our algorithms but also most known private algorithms can be implemented using only statistical queries and hence are constrained by these lower bounds. Our result therefore isolates the complexity of agnostic learning in the SQ model as a new barrier in the design of differentially private algorithms.
View PDF Chat

Convexity and Steinitz's Exchange Property

1996-12-01
Kazuo Murota

Online Nash Social Welfare Maximization with Predictions

2022-01-01
Siddhartha Banerjee , Vasilis Gkatzelis , Artur Gorokh +1 more
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Online Nash Social Welfare Maximization with PredictionsSiddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy … Previous chapter Next chapter Full AccessProceedings Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Online Nash Social Welfare Maximization with PredictionsSiddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy JinSiddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy Jinpp.1 - 19Chapter DOI:https://doi.org/10.1137/1.9781611977073.1PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We consider the problem of allocating a set of divisible goods to N agents in an online manner, aiming to maximize the Nash social welfare, a widely studied objective which provides a balance between fairness and efficiency. The goods arrive in a sequence of T periods and the value of each agent for a good is adversarially chosen when the good arrives. We first observe that no online algorithm can achieve a competitive ratio better than the trivial O(N), unless it is given additional information about the agents' values. Then, in line with the emerging area of "algorithms with predictions", we consider a setting where for each agent, the online algorithm is only given a prediction of her monopolist utility, i.e., her utility if all goods were given to her alone (corresponding to the sum of her values over the T periods). Our main result is an online algorithm whose competitive ratio is parameterized by the multiplicative errors in these predictions. The algorithm achieves a competitive ratio of O(log N) and O(log T) if the predictions are perfectly accurate. Moreover, the competitive ratio degrades smoothly with the errors in the predictions, and is surprisingly robust: the logarithmic competitive ratio holds even if the predictions are very inaccurate. We complement this positive result by showing that our bounds are essentially tight: no online algorithm, even if provided with perfectly accurate predictions, can achieve a competitive ratio of O(log1–∊ N) or O(log1–∊ T) for any constant ∊ > 0. Previous chapter Next chapter RelatedDetails Published:2022eISBN:978-1-61197-707-3 https://doi.org/10.1137/1.9781611977073Book Series Name:ProceedingsBook Code:PRDA22Book Pages:xvii + 3771
View PDF Chat