Search

Persuasion, defined as the act of exploiting an informational advantage in order to inuence the decisions of others, is ubiquitous. Indeed, persuasive communication has been estimated to account for almost a third of all economic activity in the U.S. This paper examines persuasion through a computational lens, focusing on what is perhaps the most basic and fundamental model in this space: the celebrated Bayesian persuasion model of Kamenica and Gentzkow [Am. Econ. Rev., 101 (2011), pp. 2590-2615]. Here there are two players, a sender and a receiver. The receiver must take one of a number of actions with an a priori unknown payoff, and the sender has access to additional information regarding the payoffs of the various actions for both players. The sender can commit to revealing a noisy signal regarding the realization of the payoffs of various actions, and would like to do so to maximize her own payoff in expectation assuming that the receiver rationally acts to maximize his own payoff. When the payoffs of various actions follow a joint distribution (the common prior), the sender's problem is nontrivial, and its computational complexity depends on the representation of this prior. We examine the sender's optimization task in three of the most natural input models for this problem, and essentially pin down its computational complexity in each. When the payoff distributions of the different actions are independently and identically distributed (i.i.d.) and given explicitly, we exhibit a polynomial-time (exact) algorithmic solution, and a "simple" (1-1=e)-approximation algorithm. Our optimal scheme for the i.i.d. setting involves an analogy to auction theory, and makes use of Border's characterization of the space of reduced-forms for single-item auctions. When action payoffs are independent but nonidentical with marginal distributions given explicitly, we show that it is #P-hard to compute the optimal expected sender utility. In doing so, we rule out a generalized Border's theorem, in the sense of Gopalan, Nisan, and Roughgarden [Public projects, boolean functions, and the borders of Border's theorem, in Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, ACM, New York, 2015, p. 395], for this setting. Finally, we consider a general (possibly correlated) joint distribution of action payoffs presented by a black box sampling oracle, and exhibit a fully polynomial-time approximation scheme (FPTAS) with a bicriteria guarantee. Our FPTAS is based on Monte Carlo sampling, and its analysis relies on the principle of deferred decisions. Moreover, we show that this result is the best possible in the black-box model for information-theoretic reasons. [ABSTRACT FROM AUTHOR]

We give a lower bound on the iteration complexity of a natural class of Lagrangianrelaxation algorithms for approximately solving packing/covering linear programs. We show that, given an input with m random 0/1-constraints on n variables, with high probability, any such algorithm requires Ω(ρ log(m)/ϵ2) iterations to compute a (1 + ϵ)-approximate solution, where ρ is the width of the input. The bound is tight for a range of the parameters (m, n, ρ, ϵ). The algorithms in the class include Dantzig-Wolfe decomposition, Benders' decomposition, Lagrangian relaxation as developed by Held and Karp for lower-bounding TSP, and many others (e.g., those by Plotkin, Shmoys, and Tardos and Grigoriadis and Khachiyan). To prove the bound, we use a discrepancy argument to show an analogous lower bound on the support size of (1 + ϵ)-approximate mixed strategies for random two-player zero-sum 0/1-matrix games. [ABSTRACT FROM AUTHOR]

In a classic optimization problem, the complete input data is assumed to be known to the algorithm. This assumption may not be true anymore in optimization problems motivated by the Internet where part of the input data is private knowledge of independent selfish agents. The goal of algorithmic mechanism design is to provide (in polynomial time) a solution to the optimization problem and a set of incentives for the agents such that disclosing the input data is a dominant strategy for the agents. In the case of NP-hard problems, the solution computed should also be a good approximation of the optimum. In this paper we focus on mechanism design for multiobjective optimization problems. In this setting we are given a main objective function and a set of secondary objectives which are modeled via budget constraints. Multiobjective optimization is a natural setting for mechanism design as many economical choices ask for a compromise between different, partially conflicting goals. The main contribution of this paper is showing that two of the main tools for the design of approximation algorithms for multiobjective optimization problems, namely, approximate Pareto sets and Lagrangian relaxation, can lead to truthful approximation schemes. By exploiting the method of approximate Pareto sets, we devise truthful deterministic and randomized multicriteria fully polynomial-time approximation schemes (FPTASs) for multiobjective optimization problems whose exact version admits a pseudopolynomial-time algorithm, as, for instance, the multibudgeted versions of minimum spanning tree, shortest path, maximum (perfect) matching,and matroid intersection. Our construction also applies to multidimensional knapsack and multiunit combinatorial auctions. Our FPTASs compute a (1+ε)-approximate solution violating each budget constraint by a factor (1+ ε). When feasible solutions induce an independence system, i.e., when subsets of feasible solutions are feasible as well, we present a PTAS (not violating any constraint), which combines the approach above with a novel monotone way to guess the heaviest elements in the optimum solution. Finally, we present a universally truthful Las Vegas PTAS for minimum spanning tree with a single budget constraint, where one wants to compute a minimum cost spanning tree whose length is at most a given value L. This result is based on the Lagrangian relaxation method, in combination with our monotone guessing step and with a random perturbation step (ensuring low expected running time). This result can be derandomized in the case of integral lengths. All the mentioned results match the best known approximation ratios, which are, however, obtained by nontruthful algorithms. [ABSTRACT FROM AUTHOR]

In the unsplittable flow problem on a path, we are given a capacitated path P and n tasks, each task having a demand, a profit, and start and end vertices. The goal is to compute a maximum profit set of tasks such that, for each edge e of P, the total demand of selected tasks that use e does not exceed the capacity of e. This is a well-studied problem that has been described under alternative names, such as resource allocation, bandwidth allocation, resource constrained scheduling, temporal knapsack, and interval packing. We present a polynomial time constant-factor approximation algorithm for this problem. This improves on the previous best known approximation ratio of O(log n). The approximation ratio of our algorithm is 7 + ∈ for any ∈ > 0. We introduce several novel algorithmic techniques, which might be of independent interest: a framework which reduces the problem to instances with a bounded range of capacities, and a new geometrically inspired dynamic program which solves to optimality a special case of the problem of finding a maximum weight independent set of rectangles. In the setting of resource augmentation, wherein the capacities can be slightly violated, we give a (2 + ∈)-approximation algorithm. In addition, we show that the problem is strongly NP-hard even if all edge capacities are equal and all demands are either 1, 2, or 3. [ABSTRACT FROM AUTHOR]

The traveling salesman problem (TSP) is a canonical NP-complete problem which is proved by Trevisan [SIAM J. Comput., 30 (2000), pp. 475-485] to be MAX-SNP hard even on high-dimensional Euclidean metrics. To circumvent this hardness, researchers have been developing approximation schemes for "simpler" instances of the problem. For instance, the algorithms of Arora and of Talwar show how to approximate TSP on low-dimensional metrics (for different notions of metric dimension). However, a feature of most current notions of metric dimension is that they are "local": the definitions require every local neighborhood to be well-behaved. In this paper, we define a global notion of dimension that generalizes the popular notion of doubling dimension, but still allows some small dense regions; e.g., it allows some metrics that contain cliques of size √n. Given a metric with global dimension dimC, we give a (1+ε)-approximation algorithm that runs in subexponential time, i.e., in exp(O(nδε-4dimC ))-time for every constant 0 < δ < 1. As mentioned above, metrics with bounded dimC may contain metrics of size O(√n) on which the TSP problem is hard to approximate to within (1 + ε). Hence, to do better than a running time of Ω(exp{√n}), our algorithms find O(1)-approximations to some portions of the tour, and (1 + ε)-approximations for other portions, and stitch them together. Moreover, we show that such globally bounded metrics have spanners that preserve distances to arbitrary accuracy and have size θ(n1.5). [ABSTRACT FROM AUTHOR]

We present a data structure for answering approximate shortest path queries in a planar subdivision from a fixed source. Let ρ? ⩾ 1 be a real number. Distances in each face of this subdivision are measured by a possibly asymmetric convex distance function whose unit disk is contained in a concentric unit Euclidean disk and contains a concentric Euclidean disk with radius 1/ρ?. Different convex distance functions may be used for different faces, and obstacles are allowed. Let ϵ be any number strictly between 0 and 1. Our data structure returns a (1+ϵ) approximation of the shortest path cost from the fixed source to a query destination in O(log ρn/ϵ ) time. Afterwards, a (1 +ϵ)-approximate shortest path can be reported in O(log n) time plus the complexity of the path. The data structure uses O(ρ2n3ϵ2 log ρn/ϵ ) space and can be built in O( ρ2n3/ϵ2 (log ρρn/ ϵ )2) time. Our time and space bounds do not depend on any other parameter; in particular, they do not depend on any geometric parameter of the subdivision such as the minimum angle. [ABSTRACT FROM AUTHOR]

A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L. The weight of a cycle cover of an edge-weighted graph is the sum of the weights of its edges. We come close to settling the complexity and approximability of computing L-cycle covers. On the one hand, we show that, for almost all L, computing L-cycle covers of maximum weight in directed and undirected graphs is APX-hard. Most of our hardness results hold even if the edge weights are restricted to zero and one. On the other hand, we show that the problem of computing L-cycle covers of maximum weight can be approximated within a factor of 2 for undirected graphs and within a factor of 8/3 in the case of directed graphs. This holds for arbitrary sets L. [ABSTRACT FROM AUTHOR]

For circuit classes R, the fundamental computational problem Min-R asks for the minimum R-size of a Boolean function presented as a truth table. Prominent examples of this problem include Min-DNF, which asks whether a given Boolean function presented as a truth table has a k-term disjunctive normal form (DNF), and Min-Circuit (also called the minimum circuit size problem (MCSP)), which asks whether a Boolean function presented as a truth table has a size k Boolean circuit. We present a new reduction proving that Min-DNF is NP-complete. It is significantly simpler than the known reduction of Masek [Some NP-Complete Set Covering Problems, manuscript, 1979], which is from Circuit-SAT. We then give a more complex reduction, yielding the result that Min-DNF cannot be approximated to within a factor smaller than (log N)γ, for some constant γ > 0, assuming that NP is not contained in quasi-polynomial time. The standard greedy algorithm for Set Cover is often used in practice to approximate Min-DNF. The question of whether Min-DNF can be approximated to within a factor of o(log N) remains open, but we construct an instance of Min-DNF on which the solution produced by the greedy algorithm is Ω(log N) larger than optimal. Finally, we turn to the question of approximating circuit size for slightly more general classes of circuits. DNF formulas are depth-two circuits of AND and OR gates. Depth-d circuits are denoted by ACd0. We show that it is hard to approximate the size of ACd0 circuits (for large enough d) under cryptographic assumptions. [ABSTRACT FROM AUTHOR]

In this paper, we give the first constant-factor approximation algorithm for the rooted Orienteering problem, as well as a new problem that we call the Discounted-Reward traveling salesman problem (TSP), motivated by robot navigation. In both problems, we are given a graph with lengths on edges and rewards on nodes, and a start node s. In the Orienteering problem, the goal is to find a path starting at s that maximizes the reward collected, subject to a hard limit on the total length of the path. In the Discounted-Reward TSP, instead of a length limit we are given a discount factor γ, and the goal is to maximize the total discounted reward collected, where the reward for a node reached at time t is discounted by γt. This problem is motivated by an approximation to a planning problem in the Markov decision process (MDP) framework under the commonly employed infinite horizon discounted reward optimality criterion. The approximation arises from a need to deal with exponentially large state spaces that emerge when trying to model one-time events and nonrepeatable rewards (such as for package deliveries). We also consider tree and multiple-path variants of these problems and provide approximations for those as well. Although the unrooted Orienteering problem, where there is no fixed start node s, has been known to be approximable using algorithms for related problems such as k-TSP (in which the amount of reward to be collected is fixed and the total length is approximately minimized), ours is the first to approximate the rooted question, solving an open problem in [E. M. Arkin, J. S. B. Mitchell, and G. Narasimhan, Proceedings of the 14th ACM Symposium on Computational Geometry, 1998, pp. 307–316] and [B. Awerbuch, Y. Azar, A. Blum, and S. Vempala, SIAM J. Comput., 28 (1998), pp. 254–262]. We complement our approximation result for Orienteering by showing that the problem is APX-hard. [ABSTRACT FROM AUTHOR]

We consider the problem of computing the outer-radii of point sets. In this problem, we are given integers n, d, and k, where k ≤ d, and a set P of n points in ℜd. The goal is to compute the outer k-radius of P, denoted by Rk(P), which is the minimum over all (d - k)-dimensional flats F of maxp∊P d(p, F), where d(p, F) is the Euclidean distance between the point p and flat F. Computing the radii of point sets is a fundamental problem in computational convexity with many significant applications. The problem admits a polynomial time algorithm when the dimension d is constant [U. Faigle, W. Kern, and M. Streng, Math. Program., 73 (1996), pp. 1–5]. Here we are interested in the general case in which the dimension d is not fixed and can be as large as n, where the problem becomes NP-hard even for k = 1. It is known that Rk(P) can be approximated in polynomial time by a factor of (1 + ϵ) for any ϵ > 0 when d - k is a fixed constant [M. Bădoiu, S. Har-Peled, and P. Indyk, in Proceedings of the ACM Symposium on the Theory of Computing, 2002; S. Har-Peled and K. Varadarajan, in Proceedings of the ACM Symposium on Computing Geometry, 2002]. A polynomial time algorithm that guarantees a factor of O(√log n ) approximation for R1(P), the width of the point set P, is implied by the results of Nemirovski, Roos, and Terlaky [Math. Program., 86 (1999), pp. 463–473] and Nesterov [Handbook of Semidefinite Programming Theory, Algorithms, Kluwer Academic Publishers, Norwell, MA, 2000]. In this paper, we show that Rk(P) can be pproximated by a ratio of O(√log n ) for any 1 ≤ k ≤ d, thus matching the previously best known ratio for approximating the special case R1(P), the width of point set P. Our algorithm is based on semidefinite programming relaxation with a new mixed deterministic and randomized rounding procedure. We also prove an inapproximability result that gives evidence that our approximation algorithm is doing well for a large range of k. We show that there exists a constant δ > 0 such that the following holds for any 0 < ϵ < 1: there is no polynomial time algorithm that approximates Rk(P) within (log n)δ for all k such that k ≤ d - dϵ unless NP ⊆ DTIME [2(log m)O(1) ]. Our inapproximability result for Rk(P) extends a previously known hardness result of Brieden [Discrete Comput. Geom., 28 (2002), pp. 201–209] and is proved by modifying Brieden's construction using basic ideas from probabilistically checkable proofs (PCP) theory. [ABSTRACT FROM AUTHOR]

Local search algorithms for combinatorial optimization problems are generally of pseudopolynomial running time, and polynomial-time algorithms are not often known for finding locally optimal solutions for NP-hard optimization problems. We introduce the concept of ε-local optimality and show that, for every ε > 0, an ε-local optimum can be identified in time polynomial in the problem size and 1/ε whenever the corresponding neighborhood can be searched in polynomial time. If the neighborhood can be searched in polynomial time for a ε-local optimum, a variation of our main algorithm produces a (δ+ ε)-local optimum in time polynomial in the problem size and 1/ε. As a consequence, a combinatorial optimization problem has a fully polynomial-time approximation scheme if and only if the problem of determining a better neighbor in an exact neighborhood has a fully polynomial-time approximation scheme. [ABSTRACT FROM AUTHOR]

We present an 8-approximation algorithm for the problem of finding a minimum weight subset feedback vertex set (or subset-fvs, in short). The input in this problem consists of an undirected graph G = (V, E) with vertex weights c(v) and a subset of vertices S called special vertices. A cycle is called interesting if it contains at least one special vertex. A subset of vertices is called a subset-fvs with respect to S if it intersects every interesting cycle. The goal is to find a minimum weight subset-fvs. The best previous algorithm for the general case provided only a logarithmic approximation factor. The minimum weight subset-fvs problem generalizes two NP-complete problems: the minimum weight feedback vertex set problem in undirected graphs and the minimum weight multiway vertex cut problem. The main tool that we use in our algorithm and its analysis is a new version of multicommodity flow, which we call relaxed multicommodity flow. Relaxed multicommodity flow is a hybrid of multicommodity flow and multiterminal flow. [ABSTRACT FROM AUTHOR]

We attempt to reconcile the two distinct views of approximation classes: syntactic and computational. Syntactic classes such as MAX SNP permit structural results and have natural complete problems, while computational classes such as APX allow us to work with classes of problems whose approximability is well understood. Our results provide a syntactic characterization of computational classes and give a computational framework for syntactic classes. We compare the syntactically defined class MAX SNP with the computationally defined class APX and show that every problem in APX can be "placed" (i.e., has approximation-preserving reduction to a problem) in MAX SNP. Our methods introduce a simple, yet general, technique for creating approximation-preserving reductions which shows that any "well" -approximable problem can be reduced in an approximation-preserving manner to a problem which is hard to approximate to corresponding factors. The reduction then follows easily from the recent nonapproximability results for MAX SNP-hard problems. We demonstrate the generality of this technique by applying it to other classes such as MAX SNP-RMAX(2) and MIN F[SUP+] Π[SUB2] (1) which have the clique problem and the set cover problem, respectively, as complete problems. The syntactic nature of MAX SNP was used by Papadimitriou and Yannakakis [J. Comput. System Sci., 43 (1991), pp. 425-440] to provide approximation algorithms for every problem in the class. We provide an alternate approach to demonstrating this result using the syntactic nature of MAX SNP. We develop a general paradigm, nonoblivious local search, useful for developing simple yet efficient approximation algorithms. We show that such algorithms can find good approximations for all MAX SNP problems, yielding approximation ratios comparable to the best known for a variety of specific MAX SNP-hard problems. [ABSTRACT FROM AUTHOR]