Extending characterizations from subdomains to domains. Angelina Vidali, 7th Workshop in Internet and Network Economics (WINE '11)

[pdf] [SLIDES]

The already extended literature in Combinatorial Auctions, Public Projects and Scheduling demands a more systematic classification of the domains and a clear comparison of the results known. Connecting characterization results for different settings and providing a characterization proof using another characterization result as a black box without having to repeat a tediously similar proof is not only elegant and desirable, but also greatly enhances our intuition and provides a classification of different results and a unified and deeper understanding.

We consider whether one can extend a characterization of a subdomain to a domain in a black-box manner. We show that this is possible for n-player stable mechanisms if the only truthful mechanisms for the subdomain are the affine maximizers. We further show that if the characterization of the subdomain involves a combination of affine maximizers and threshold mechanisms, the threshold mechanisms for the subdomain cannot be extended to truthful mechanisms for the union of the subdomain with a (very slight) affine transformation of it.

We also show that for every truthful mechanism in a domain there exists a corresponding truthful mechanism for any affine transformation of the domain. We finally plug in as a black box to our theorems the characterization of additive 2-player combinatorial auctions that are decisive and allocate all items (which essentially is the domain for scheduling unrelated machines) and show that the 2-player truthful mechanisms of any domain, which is strictly a superdomain of it are only the affine maximizers. This gives a unique characterization proof of the decisive 2-player mechanisms for: Combinatorial Public Projects, Unrestricted domains, as well as for Submodular and Subadditive Combinatorial Auctions that allocate all items.