
We provide simple and approximately revenueoptimal mechanisms in the
multiitem multibidder settings. We unify and improve all previous results, as
well as generalize the results to broader cases. In particular, we prove that
the better of the following two simple, deterministic and Dominant Strategy
Incentive Compatible mechanisms, a sequential posted price mechanism or an
anonymous sequential posted price mechanism with entry fee, achieves a constant
fraction of the optimal revenue among all randomized, Bayesian Incentive
Compatible mechanisms, when buyers' valuations are XOS over independent items.
If the buyers' valuations are subadditive over independent items, the
approximation factor degrades to $O(\log m)$, where $m$ is the number of items.
We obtain our results by first extending the CaiDevanurWeinberg duality
framework to derive an effective benchmark of the optimal revenue for
subadditive bidders, and then analyzing this upper bound with new techniques.

The seminal impossibility result of Myerson and Satterthwaite (1983) states
that for bilateral trade, there is no mechanism that is individually rational
(IR), incentive compatible (IC), weakly budget balanced, and efficient. This
has led followup work on twosided trade settings to weaken the efficiency
requirement and consider approximately efficient simple mechanisms, while still
demanding the other properties. The current stateoftheart of such mechanisms
for twosided markets can be categorized as giving one (but not both) of the
following two types of approximation guarantees on the gains from trade: a
constant exante guarantee, measured with respect to the secondbest efficiency
benchmark, or an asymptotically optimal expost guarantee, measured with
respect to the firstbest efficiency benchmark. Here the secondbest efficiency
benchmark refers to the highest gains from trade attainable by any IR, IC and
weakly budget balanced mechanism, while the firstbest efficiency benchmark
refers to the maximum gains from trade (attainable by the VCG mechanism, which
is not weakly budget balanced).
In this paper, we construct simple mechanisms for doubleauction and matching
markets that simultaneously achieve both types of guarantees: these are expost
IR, Bayesian IC, and expost weakly budget balanced mechanisms that 1) exante
guarantee a constant fraction of the gains from trade of the secondbest, and
2) expost guarantee a realizationdependent fraction of the gains from trade
of the firstbest, such that this realizationdependent fraction converges to 1
(full efficiency) as the market grows large.

This paper studies the revenue of simple mechanisms in settings where a
thirdparty data provider is present. When no data provider is present, it is
known that simple mechanisms achieve a constant fraction of the revenue of
optimal mechanisms. The results in this paper demonstrate that this is no
longer true in the presence of a third party data provider who can provide the
bidder with a signal that is correlated with the item type. Specifically, we
show that even with a single seller, a single bidder, and a single item of
uncertain type for sale, pricing each itemtype separately (the analog of item
pricing for multiitem auctions) and bundling all itemtypes under a single
price (the analog of grand bundling) can both simultaneously be a logarithmic
factor worse than the optimal revenue. Further, in the presence of a data
provider, itemtype partitioning mechanismsa more general class of
mechanisms which divide itemtypes into disjoint groups and offer prices for
each groupstill cannot achieve within a $\log \log$ factor of the optimal
revenue.

We provide algorithms that learn simple auctions whose revenue is
approximately optimal in multiitem multibidder settings, for a wide range of
valuations including unitdemand, additive, constrained additive, XOS, and
subadditive. We obtain our learning results in two settings. The first is the
commonly studied setting where sample access to the bidders' distributions over
valuations is given, for both regular distributions and arbitrary distributions
with bounded support. Our algorithms require polynomially many samples in the
number of items and bidders. The second is a more general maxmin learning
setting that we introduce, where we are given "approximate distributions," and
we seek to compute an auction whose revenue is approximately optimal
simultaneously for all "true distributions" that are close to the given ones.
These results are more general in that they imply the samplebased results, and
are also applicable in settings where we have no sample access to the
underlying distributions but have estimated them indirectly via market research
or by observation of previously run, potentially nontruthful auctions.
Our results hold for valuation distributions satisfying the standard (and
necessary) independenceacrossitems property. They also generalize and improve
upon recent works, which have provided algorithms that learn approximately
optimal auctions in more restricted settings with additive, subadditive and
unitdemand valuations using sample access to distributions. We generalize
these results to the complete unitdemand, additive, and XOS setting, to i.i.d.
subadditive bidders, and to the maxmin setting.
Our results are enabled by new uniform convergence bounds for hypotheses
classes under product measures. Our bounds result in exponential savings in
sample complexity compared to bounds derived by bounding the VC dimension, and
are of independent interest.

We design simple mechanisms to approximate the Gains from Trade (GFT) in
twosided markets with multiple unitsupply sellers and multiple unitdemand
buyers. A classical impossibility result by Myerson and Satterthwaite showed
that even with only one seller and one buyer, no Individually Rational (IR),
Bayesian Incentive Compatible (BIC) and BudgetBalanced (BB) mechanism can
achieve full GFT (trade whenever buyer's value is higher than the seller's
cost). On the other hand, they proposed the "secondbest" mechanism that
maximizes the GFT subject to IR, BIC and BB constraints, which is unfortunately
rather complex for even the singleseller singlebuyer case. Our mechanism is
simple, IR, BIC and BB, and achieves $\frac{1}{2}$ of the optimal GFT among all
IR, BIC and BB mechanisms. Our result holds for arbitrary distributions of the
buyers' and sellers' values and can accommodate any downwardclosed feasibility
constraints over the allocations. The analysis of our mechanism is facilitated
by extending the CaiWeinbergDevanur duality framework to twosided markets.

The simultaneous multipleround auction (SMRA) and the combinatorial clock
auction (CCA) are the two primary mechanisms used to sell bandwidth. Under
truthful bidding, the SMRA is known to output a Walrasian equilibrium that
maximizes social welfare provided the bidder valuation functions satisfy the
gross substitutes property. Recently, it was shown that the combinatorial clock
auction (CCA) provides good welfare guarantees for general classes of valuation
functions. This motivates the question of whether similar welfare guarantees
hold for the SMRA in the case of general valuation functions.
We show the answer is no. But we prove that good welfare guarantees still
arise if the degree of complementarities in the bidder valuations are bounded.
In particular, if bidder valuations functions are $\alpha$nearsubmodular
then, under truthful bidding, the SMRA has a welfare ratio (the worst case
ratio between the social welfare of the optimal allocation and the auction
allocation) of at most $(1+\alpha)$. The special case of submodular valuations,
namely $\alpha=1$, and produces individually rational solutions. However, for
$\alpha>1$, this is a bicriteria guarantee, to obtain good welfare under
truthful bidding requires relaxing individual rationality.
Finally, we examine what strategies are required to ensure individual
rationality in the SMRA with general valuation functions. First, we provide a
weak characterization, namely \emph{secure bidding}, for individual
rationality. We then show that if the bidders use a profitmaximizing secure
bidding strategy the welfare ratio is at most $1+\alpha$. Consequently, by
bidding securely, it is possible to obtain the same welfare guarantees as
truthful bidding without the loss of individual rationality.

Since the 1990s spectrum auctions have been implemented worldwide. This has
provided for a practical examination of an assortment of auction mechanisms
and, amongst these, two simultaneous ascending price auctions have proved to be
extremely successful. These are the simultaneous multiround ascending auction
(SMRA) and the combinatorial clock auction (CCA). It has long been known that,
for certain classes of valuation functions, the SMRA provides good theoretical
guarantees on social welfare. However, no such guarantees were known for the
CCA.
In this paper, we show that CCA does provide strong guarantees on social
welfare provided the price increment and stopping rule are wellchosen. This is
very surprising in that the choice of price increment has been used primarily
to adjust auction duration and the stopping rule has attracted little
attention. The main result is a polylogarithmic approximation guarantee for
social welfare when the maximum number of items demanded $\mathcal{C}$ by a
bidder is fixed. Specifically, we show that either the revenue of the CCA is at
least an $\Omega\Big(\frac{1}{\mathcal{C}^{2}\log n\log^2m}\Big)$fraction of
the optimal welfare or the welfare of the CCA is at least an
$\Omega\Big(\frac{1}{\log n}\Big)$fraction of the optimal welfare, where $n$
is the number of bidders and $m$ is the number of items. As a corollary, the
welfare ratio  the worst case ratio between the social welfare of the optimum
allocation and the social welfare of the CCA allocation  is at most
$O(\mathcal{C}^2 \cdot \log n \cdot \log^2 m)$. We emphasize that this latter
result requires no assumption on bidders valuation functions. Finally, we prove
that such a dependence on $\mathcal{C}$ is necessary. In particular, we show
that the welfare ratio of the CCA is at least $\Omega \Big(\mathcal{C} \cdot
\frac{\log m}{\log \log m}\Big)$.

We propose an optimum mechanism for providing monetary incentives to the data
sources of a statistical estimator such as linear regression, so that high
quality data is provided at low cost, in the sense that the sum of payments and
estimation error is minimized. The mechanism applies to a broad range of
estimators, including linear and polynomial regression, kernel regression, and,
under some additional assumptions, ridge regression. It also generalizes to
several objectives, including minimizing estimation error subject to budget
constraints. Besides our concrete results for regression problems, we
contribute a mechanism design framework through which to design and analyze
statistical estimators whose examples are supplied by workers with cost for
labeling said examples.

We provide a nearoptimal, computationally efficient algorithm for the
unitdemand pricing problem, where a seller wants to price n items to optimize
revenue against a unitdemand buyer whose values for the items are
independently drawn from known distributions. For any chosen accuracy eps>0 and
item values bounded in [0,1], our algorithm achieves revenue that is optimal up
to an additive error of at most eps, in polynomial time. For values sampled
from Monotone Hazard Rate (MHR) distributions, we achieve a (1eps)fraction of
the optimal revenue in polynomial time, while for values sampled from regular
distributions the same revenue guarantees are achieved in quasipolynomial
time.
Our algorithm for bounded distributions applies probabilistic techniques to
understand the statistical properties of revenue distributions, obtaining a
reduction in the search space of the algorithm via dynamic programming.
Adapting this approach to MHR and regular distributions requires the proof of
novel extreme value theorems for such distributions.
As a byproduct, our techniques establish structural properties of
approximatelyoptimal and nearoptimal solutions. We show that, for values
independently distributed according to MHR distributions, pricing all items at
the same price achieves a constant fraction of the optimal revenue. Moreover,
for all eps >0, g(1/eps) distinct prices suffice to obtain a (1eps)fraction
of the optimal revenue, where g(1/eps) is quadratic in 1/eps and independent of
n. Similarly, for all eps>0 and n>0, at most g(1/(eps log n)) distinct prices
suffice if the values are independently distributed according to regular
distributions, where g() is a polynomial function. Finally, when the values are
i.i.d. from some MHR distribution, we show that, if n is a sufficiently large
function of 1/eps, a single price suffices to achieve a (1eps)fraction of the
optimal revenue.

Daily deals platforms such as Amazon Local, Google Offers, GroupOn, and
LivingSocial have provided a new channel for merchants to directly market to
consumers. In order to maximize consumer acquisition and retention, these
platforms would like to offer deals that give good value to users. Currently,
selecting such deals is done manually; however, the large number of submarkets
and localities necessitates an automatic approach to selecting good deals and
determining merchant payments.
We approach this challenge as a market design problem. We postulate that
merchants already have a good idea of the attractiveness of their deal to
consumers as well as the amount they are willing to pay to offer their deal.
The goal is to design an auction that maximizes a combination of the revenue of
the auctioneer (platform), welfare of the bidders (merchants), and the positive
externality on a third party (the consumer), despite the asymmetry of
information about this consumer benefit. We design auctions that truthfully
elicit this information from the merchants and maximize the social welfare
objective, and we characterize the consumer welfare functions for which this
objective is truthfully implementable. We generalize this characterization to a
very broad mechanismdesign setting and give examples of other applications.

It was recently shown in [http://arxiv.org/abs/1207.5518] that revenue
optimization can be computationally efficiently reduced to welfare optimization
in all multidimensional Bayesian auction problems with arbitrary (possibly
combinatorial) feasibility constraints and independent additive bidders with
arbitrary (possibly combinatorial) demand constraints. This reduction provides
a polytime solution to the optimal mechanism design problem in all auction
settings where welfare optimization can be solved efficiently, but it is
fragile to approximation and cannot provide solutions to settings where welfare
maximization can only be tractably approximated. In this paper, we extend the
reduction to accommodate approximation algorithms, providing an approximation
preserving reduction from (truthful) revenue maximization to (not necessarily
truthful) welfare maximization. The mechanisms output by our reduction choose
allocations via blackbox calls to welfare approximation on randomly selected
inputs, thereby generalizing also our earlier structural results on optimal
multidimensional mechanisms to approximately optimal mechanisms. Unlike
[http://arxiv.org/abs/1207.5518], our results here are obtained through novel
uses of the Ellipsoid algorithm and other optimization techniques over {\em
nonconvex regions}.

We provide a computationally efficient blackbox reduction from mechanism
design to algorithm design in very general settings. Specifically, we give an
approximationpreserving reduction from truthfully maximizing \emph{any}
objective under \emph{arbitrary} feasibility constraints with \emph{arbitrary}
bidder types to (not necessarily truthfully) maximizing the same objective plus
virtual welfare (under the same feasibility constraints). Our reduction is
based on a fundamentally new approach: we describe a mechanism's behavior
indirectly only in terms of the expected value it awards bidders for certain
behavior, and never directly access the allocation rule at all.
Applying our new approach to revenue, we exhibit settings where our reduction
holds \emph{both ways}. That is, we also provide an approximationsensitive
reduction from (nontruthfully) maximizing virtual welfare to (truthfully)
maximizing revenue, and therefore the two problems are computationally
equivalent. With this equivalence in hand, we show that both problems are
NPhard to approximate within any polynomial factor, even for a single monotone
submodular bidder.
We further demonstrate the applicability of our reduction by providing a
truthful mechanism maximizing fractional maxmin fairness. This is the first
instance of a truthful mechanism that optimizes a nonlinear objective.

We provide a Polynomial Time Approximation Scheme (PTAS) for the Bayesian
optimal multiitem multibidder auction problem under two conditions. First,
bidders are independent, have additive valuations and are from the same
population. Second, every bidder's value distributions of items are independent
but not necessarily identical monotone hazard rate (MHR) distributions. For
noni.i.d. bidders, we also provide a PTAS when the number of bidders is small.
Prior to our work, even for a single bidder, only constant factor
approximations are known.
Another appealing feature of our mechanism is the simple allocation rule.
Indeed, the mechanism we use is either the secondprice auction with reserve
price on every item individually, or VCG allocation with a few outlying items
that requires additional treatments. It is surprising that such simple
allocation rules suffice to obtain nearly optimal revenue.

Complementation and determinization are two fundamental notions in automata
theory. The close relationship between the two has been well observed in the
literature. In the case of nondeterministic finite automata on finite words
(NFA), complementation and determinization have the same state complexity,
namely Theta(2^n) where n is the state size. The same similarity between
determinization and complementation was found for Buchi automata, where both
operations were shown to have 2^\Theta(n lg n) state complexity. An intriguing
question is whether there exists a type of omegaautomata whose determinization
is considerably harder than its complementation. In this paper, we show that
for all common types of omegaautomata, the determinization problem has the
same state complexity as the corresponding complementation problem at the
granularity of 2^\Theta(.).

We provide a reduction from revenue maximization to welfare maximization in
multidimensional Bayesian auctions with arbitrary (possibly combinatorial)
feasibility constraints and independent bidders with arbitrary (possibly
combinatorial) demand constraints, appropriately extending Myerson's result to
this setting. We also show that every feasible Bayesian auction can be
implemented as a distribution over virtual VCG allocation rules. A virtual VCG
allocation rule has the following simple form: Every bidder's type t_i is
transformed into a virtual type f_i(t_i), via a bidderspecific function. Then,
the allocation maximizing virtual welfare is chosen. Using this
characterization, we show how to find and run the revenueoptimal auction given
only black box access to an implementation of the VCG allocation rule. We
generalize this result to arbitrarily correlated bidders, introducing the
notion of a secondorder VCG allocation rule.
We obtain our reduction from revenue to welfare optimization via two
algorithmic results on reduced forms in settings with arbitrary feasibility and
demand constraints. First, we provide a separation oracle for determining
feasibility of a reduced form. Second, we provide a geometric algorithm to
decompose any feasible reduced form into a distribution over virtual VCG
allocation rules. In addition, we show how to execute both algorithms given
only black box access to an implementation of the VCG allocation rule.
Our results are computationally efficient for all multidimensional settings
where the bidders are additive. In this case, our mechanisms run in time
polynomial in the total number of bidder types, but not type profiles. For
generic correlated distributions, this is the natural description complexity of
the problem. The runtime can be further improved to poly(#items, #bidders) in
itemsymmetric settings by making use of recent techniques.

We obtain a characterization of feasible, Bayesian, multiitem multibidder
auctions with independent, additive bidders as distributions over hierarchical
mechanisms. Combined with cyclicmonotonicity our results provide a complete
characterization of feasible, Bayesian Incentive Compatible (BIC) auctions for
this setting.
Our characterization is enabled by a novel, constructive proof of Border's
theorem, and a new generalization of this theorem to independent (but not
necessarily iid) bidders. For one item and independent bidders, we show that
any feasible reduced form auction can be implemented as a distribution over
hierarchical mechanisms. We also give a polytime algorithm for determining
feasibility of a reduced form, or finding a separation hyperplane from feasible
reduced forms. Finally, we provide polytime algorithms to find and exactly
sample from a distribution over hierarchical mechanisms consistent with a given
feasible reduced form.
Our results generalize to multiitem reduced forms for independent, additive
bidders. For multiple items, additive bidders with hard demand constraints, and
arbitrary value correlation across items or bidders, we give a proper
generalization of Border's theorem, and characterize feasible reduced forms as
multicommodity flows in related multicommodity flow instances. We show that our
generalization holds for a broader class of feasibility constraints, including
intersections of any two matroids.
As a corollary we obtain revenueoptimal, BIC mechanisms in multiitem
multibidder settings, when each bidder has arbitrarily correlated values over
the items and additive valuations over bundles, and bidders are independent.
Their runtime is polynomial in the total number of bidder types (instead of
type profiles), and is improved to poly(#items, #bidders) using recent
structural results on optimal BIC auctions in itemsymmetric settings.

Finite automata on infinite words ($\omega$automata) proved to be a powerful
weapon for modeling and reasoning infinite behaviors of reactive systems.
Complementation of $\omega$automata is crucial in many of these applications.
But the problem is nontrivial; even after extensive study during the past four
decades, we still have an important type of $\omega$automata, namely Streett
automata, for which the gap between the current best lower bound $2^{\Omega(n
\lg nk)}$ and upper bound $2^{\Omega(nk \lg nk)}$ is substantial, for the
Streett index size $k$ can be exponential in the number of states $n$. In
arXiv:1102.2960 we showed a construction for complementing Streett automata
with the upper bound $2^{O(n \lg n+nk \lg k)}$ for $k = O(n)$ and $2^{O(n^{2}
\lg n)}$ for $k=\omega(n)$. In this paper we establish a matching lower bound
$2^{\Omega(n \lg n+nk \lg k)}$ for $k = O(n)$ and $2^{\Omega(n^{2} \lg n)}$ for
$k = \omega(n)$, and therefore showing that the construction is asymptotically
optimal with respect to the $2^{\Theta(\cdot)}$ notation.

Complementation of finite automata on infinite words is not only a
fundamental problem in automata theory, but also serves as a cornerstone for
solving numerous decision problems in mathematical logic, modelchecking,
program analysis and verification. For Streett complementation, a significant
gap exists between the current lower bound $2^{\Omega(n\lg nk)}$ and upper
bound $2^{O(nk\lg nk)}$, where $n$ is the state size, $k$ is the number of
Streett pairs, and $k$ can be as large as $2^{n}$. Determining the complexity
of Streett complementation has been an open question since the late '80s. In
this paper show a complementation construction with upper bound $2^{O(n \lg
n+nk \lg k)}$ for $k = O(n)$ and $2^{O(n^{2} \lg n)}$ for $k = \omega(n)$,
which matches well the lower bound obtained in \cite{CZ11a}. We also obtain a
tight upper bound $2^{O(n \lg n)}$ for parity complementation.