We study changes in metrics that are defined on a cartesian product of trees. Such metrics occur naturally in many practical applications, where a global metric (such as revenue) can be broken down along several hierarchical dimensions (such as location, gender, etc).

We study the problem of attributing the prediction of a deep network to its input features, a problem previously studied by several other works. We identify two fundamental axioms—Sensitivity and Implementation Invariance that attribution methods ought to satisfy. We show that they are not satisfied by most known attribution methods, which we consider to be a fundamental weakness of those methods. We use the axioms to guide the design of a new attribution method called Integrated Gradients. Our method requires no modification to the original network and is extremely simple to implement; it just needs a few calls to the standard gradient operator. We apply this method to a couple of image models, a couple of text models and a chemistry model, demonstrating its ability to debug networks, to extract rules from a network, and to enable users to engage with models better.

We describe Analyza, a system that helps lay users explore data. Analyza has been used within two large real world systems. The first is a question-and-answer feature in a spreadsheet product. The second provides convenient access to a revenue/inventory database for a large sales force. Both user bases consist of users who do not necessarily have coding skills, demonstrating Analyza's ability to democratize access to data. We discuss the key design decisions in implementing this system. For instance, how to mix structured and natural language modalities, how to use conversation to disambiguate and simplify querying, how to rely on the ``semantics' of the data to compensate for the lack of syntactic structure, and how to efficiently curate the data.

We design the first truthful-in-expectation, constant-factor approximation mechanisms for NP -hard cases of the welfare maximization problem in combinatorial auctions with nonidentical items and in combinatorial public projects. Our results apply to bidders with valuations that are nonnegative linear combinations of gross-substitute valuations, a class that encompasses many of the most well-studied subclasses of submodular functions, including coverage functions and weighted matroid rank functions. Our mechanisms have an expected polynomial runtime and achieve an approximation factor of 1 − 1/ e . This approximation factor is the best possible for both problems, even for known and explicitly given coverage valuations, assuming P ≠ NP . Recent impossibility results suggest that our results cannot be extended to a significantly larger valuation class. Both of our mechanisms are instantiations of a new framework for designing approximation mechanisms based on randomized rounding algorithms. The high-level idea of this framework is to optimize directly over the (random) output of the rounding algorithm , rather than the usual (and rarely truthful) approach of optimizing over the input to the rounding algorithm. This framework yields truthful-in-expectation mechanisms, which can be implemented efficiently when the corresponding objective function is concave. For bidders with valuations in the cone generated by gross-substitute valuations, we give novel randomized rounding algorithms that lead to both a concave objective function and a (1 − 1/ e )-approximation of the optimal welfare.

In the context of online ad serving, display ads may appear on different types of web-pages, where each page includes several ad slots and therefore multiple ads can be shown on each page. The set of ads that can be assigned to ad slots of the same page needs to satisfy various pre-specified constraints including exclusion constraints, diversity constraints, and the like. Upon arrival of a user, the ad serving system needs to allocate a set of ads to the current web-page respecting these per-page allocation constraints. Previous slot-based settings ignore the important concept of a page, and may lead to highly suboptimal results in general. In this paper, motivated by these applications in display advertising and inspired by the submodular welfare maximization problem with online bidders, we study a general class of page-based ad allocation problems, present the first (tight) constant-factor approximation algorithms for these problems, and confirm the performance of our algorithms experimentally on real-world data sets.

Most results in revenue-maximizing auction design hinge on "getting the price right" --- offering goods to bidders at a price low enough to encourage a sale, but high enough to garner non-trivial revenue. Getting the price right can be hard work, especially when the seller has little or no a priori information about bidders' valuations.

We consider profit maximizing (incentive compatible) mechanism design in general environments that include, e.g., position auctions (for selling advertisements on Internet search engines) and single-minded combinatorial auctions. We analyze optimal envy-free pricings in these settings, and give economic justification for using the optimal revenue of envyfree pricings as a benchmark for prior-free mechanism design and analysis. Moreover, we show that envy-free pricing has a simple nice structure and a strong connection to incentive compatible mechanism design, and we exploit this connection to design prior-free mechanisms with strong approximation guarantees.

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.

We design an expected polynomial time, truthful in expectation, (1-1/e)-approximation mechanism for welfare maximization in a fundamental class of combinatorial auctions. Our results apply to bidders with 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, even for known and explicitly given coverage valuations, assuming P ≠ NP. Ours is the first truthful-in-expectation and polynomial-time mechanism to achieve a constant-factor approximation for an NP-hard welfare maximization problem in combinatorial auctions with heterogeneous goods and restricted valuations.

In a seminal paper, Karp, Vazirani, and Vazirani show that a simple ranking algorithm achieves a competitive ratio of 1-1/e for the online bipartite matching problem in the standard adversarial model, where the ratio of 1-1/e is also shown to be optimal. Their result also implies that in the random arrivals model defined by Goel and Mehta, where the online nodes arrive in a random order, a simple greedy algorithm achieves a competitive ratio of 1-1/e. In this paper, we study the ranking algorithm in the random arrivals model, and show that it has a competitive ratio of at least 0.696, beating the 1-1/e ≈ 0.632 barrier in the adversarial model. Our result also extends to the i.i.d. distribution model of Feldman et al., removing the assumption that the distribution is known.

We design and analyze approximately revenue-maximizing auctions in general single-parameter settings. Bidders have publicly observable attributes, and we assume that the valuations of indistinguishable bidders are independent draws from a common distribution. Crucially, we assume all valuation distributions are a priori unknown to the seller. Despite this handicap, we show how to obtain approximately optimal expected revenue - nearly as large as what could be obtained if the distributions were known in advance - under quite general conditions.

The existing literature on optimal auctions focuses on optimizing the expected revenue of the seller, and is appropriate for risk-neutral sellers. In this paper, we identify good mechanisms for risk-averse sellers. As is standard in the economics literature, we model the risk-aversion of a seller by endowing the seller with a monotone concave utility function. We then seek robust mechanisms that are approximately optimal for all sellers, no matter what their levels of risk-aversion are.

In this paper, we first introduce a lower bound technique for the state complexity of transformations of automata. Namely we suggest first considering the class of full automata in lower bound analysis, and later reducing the size of the large alphabet via alphabet substitutions. Then we apply such technique to the complementation of nondeterministic \omega-automata, and obtain several lower bound results. Particularly, we prove an \omega((0.76n)^n) lower bound for B\"uchi complementation, which also holds for almost every complementation or determinization transformation of nondeterministic omega-automata, and prove an optimal (\omega(nk))^n lower bound for the complementation of generalized B\"uchi automata, which holds for Streett automata as well.