Ad exchanges are an emerging platform for trading advertisement slots on the web with billions of dollars revenue per year. Every time a user visits a web page, the publisher of that web page can ask an ad exchange to auction off the ad slots on this page to determine which advertisements are shown at which price. Due to the high volume of traffic, ad networks typically act as mediators for individual advertisers at ad exchanges. If multiple advertisers in an ad network are interested in the ad slots of the same auction, the ad network might use a “local” auction to resell the obtained ad slots among its advertisers. In this work we want to deepen the theoretical understanding of these new markets by analyzing them from the viewpoint of combinatorial auctions. Prior work studied mostly single-item auctions, while we allow the advertisers to express richer preferences over multiple items. We develop a game-theoretic model for the entanglement of the central auction at the ad exchange with the local auctions at the ad networks. We consider the incentives of all three involved parties and suggest a three-party competitive equilibrium , an extension of the Walrasian equilibrium that ensures envy-freeness for all participants. We show the existence of a three-party competitive equilibrium and a polynomial-time algorithm to find one for gross-substitute bidder valuations.

Property testing is a rapidly growing field of research. Typically, a property testing algorithm proceeds by quickly determining whether an input can satisfy some condition, under the assumption that most inputs do not satisfy it. If the input is "far" from satisfying the condition, the algorithm is guaranteed to reject it with high probability. Applying this paradigm to image detection is desirable since images are large objects and a lot of time can be saved by quickly rejecting images which are "far" from satisfying a certain condition the user is interested in. Further, typically most inputs are, indeed, "far" from the sought images. We demonstrate this by analyzing the problem of deciding whether a binary image can be partitioned according to a template represented by a rectangular grid, and introduce a quick "rejector," which tests an image extracted from the input image, but whose size, as well as the time required to construct it, are constants which are independent of the input image size. With high probability, the rejector dismisses the inputs which are "far" from the template.

The Target Set Selection problem proposed by Kempe, Kleinberg, and Tardos, gives a nice clean combinatorial formulation for many problems arising in economy, sociology, and medicine. Its input is a graph with vertex thresholds, the social network, and the goal is to find a subset of vertices, the target set, that "activates" a prespecified number of vertices in the graph. Activation of a vertex is defined via a so-called activation process as follows: Initially, all vertices in the target set become active. Then at each step i of the process, each vertex gets activated if the number of its active neighbors at iteration i -- 1 exceeds its threshold. The activation process is "monotone" in the sense that once a vertex is activated, it remains active for the entire process.