DOC PREVIEW
CMU CS 15892 - A Theory of Expressiveness in Mechanisms

This preview shows page 1-2-3-23-24-25-26-47-48-49 out of 49 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

A Theory of Expressiveness in MechanismsMichael Benisch and Tuomas SandholmCarnegie Mellon UniversityPittsburgh, PA 15213AbstractWe develop a theory that ties the expressiveness of mechanisms to their efficiency. We introducetwo notions of expressiveness, impact dimension and outcome shattering. We show that an upperbound on the expected efficiency of any mechanism increases strictly as more expressiveness isallowed, and prove that a small increase in expressiveness can lead to an arbitrarily large increasein the bound. We also show that in any private values setting the bound can be implemented witha budget-balanced mechanism in Bayes-Nash equilibrium. However, without full expressivenessdominant-strategy implementation is not always possible. We then discuss the relationship betweenexpressiveness and communication complexity, and conclude with a study of a mechanism class wecall channel based, which subsume most combinatorial and multi-attribute allocation mechanismsand any Vickrey-Clarke-Groves mechanism. We show how our expressiveness notions can be used tocharacterize the often-studied exposure problem faced by participants in channel-based mechanismsthat do not allow rich combinatorial expressions. Using our theoretical framework, we are able toprove that this problem can result in arbitrary inefficiency.Keywords: mechanism design, expressiveness, message space, exposure problem, efficiency,Vickrey-Clarke-Groves mechanism, combinatorial auction, multi-attribute auction, search keywordauction, sponsored search, catalog offers, menus, web commerce.This work has been supported by a Siebel Scholarship, and the National Science Foundation under grants9972762, 0205435, 0427858 and 0905390, and Cyber Trust grant CNS-0627513.1 IntroductionA recent trend in the world—especially in electronic commerce—is a demand for higher levels ofexpressiveness in mechanisms that mediate interactions, such as the allocation of resources or match-ing of peers. The most famous expressive mechanism is a combinatorial auction (CA), which allowsparticipants to express valuations over packages of items [23, 58]. CAs have the recognized benefitof removing the exposure problem, which bidders face when they have preferences over packages but,in traditional auctions, are allowed to submit bids on individual items only. In such traditional inex-pressive auctions, when bidding on an item, a given bidder needs to speculate how others will bid onother items, since this will affect which bundles the bidder can construct and at what prices. As wewill show in this paper, uncertainty about the others’ preferences does, in fact, increase the need forexpressiveness, and, conversely, at a fixed level of expressiveness, greater uncertainty leads to reducedefficiency. CAs also have other acknowledged benefits, and preference expression forms significantlymore compact and more natural than package bidding have been developed (e.g., [23, 33, 63, 65, 66]).Expressiveness also plays a key role in multi-attribute settings where participants can expresspreferences over vectors of attributes of the item or, more generally, of the outcome. Some mar-ket designs are both combinatorial and multi-attribute (e.g., [23, 63, 65, 66]). CAs, multi-attributeauctions, and generalizations thereof are used to trade tens of billions of dollars worth of itemsannually [23, 33, 47, 63, 65]. The trend toward more expressiveness is also reflected in the richnessof preference expression now offered by businesses as diverse as retail sites, like Amazon and Net-flix, and advertising services such as those in sponsored search auctions (e.g., [12, 26]) and displayadvertising mechanisms (e.g., [17, 73]).Intuitively, one might think that more expressiveness leads to higher efficiency (sum of the agents’utilities)—for example, due to better matching of supply and demand. Efficiency improvements haveindeed been reported from combinatorial multi-attribute auctions (e.g., [23, 62, 63, 65]) and expres-sive auctions for advertisement allocation [12, 17, 26]. However, until now we have lacked a generalway of characterizing the expressiveness of different mechanisms, the impact the expressiveness hason the agents’ strategies, and, thereby, the outcome of the mechanism. For example, it was notpreviously known whether there existed a single setting where more expressiveness could always beused to achieve a more efficient outcome. In fact, on the contrary, it has been observed that incertain settings additional expressiveness can give rise to additional equilibria of poor efficiency [48].Finally, it is not obvious that more expressiveness should always yield benefits, since certain naturalincreases in an auction’s expressiveness can lead to a reduction in the auctioneer’s revenue.1Short of empirical tweaking, mechanism designers lack results they can rely on to determine howmuch—and what forms of—expressiveness they need. These questions have vexed mechanism designtheorists, but are not only theoretical in nature. Answers could ensure that ballots are expressed in1For example, consider an auction for an apple and an orange with two bidders, one who wants the apple andanother who wants the orange. Running a fully expressive combinatorial auction would yield no revenue because thetwo bidders would not need to compete. On the other hand, running an inexpressive auction where bids are consideredonly for the bundle of the two items would induce competition, and thus yield some revenue.1a form that matches the issues voters care about, that companies are able to identify suppliers thatbest match their needs, that supply and demand are better matched in B2C and C2C markets, andso on.In this paper, we develop a theory that ties the expressiveness of mechanisms to their efficiency ina domain-independent manner. We begin in Section 2 by introducing two notions of expressiveness:i) impact dimension, which captures the extent to which an individual agent can impact the mecha-nism’s outcome, and ii) outcome shattering, which is based on the concept of shattering, a measureof functional complexity from computational learning theory. We refer to increases (or decreases) inthese measures as increases (or decreases) in expressiveness.In Section 3, we derive an upp er bound on the expected efficiency of any mechanism under itsmost efficient Bayes-Nash equilibrium. We show that in any setting the bound of an optimallydesigned mechanism increases strictly as


View Full Document

CMU CS 15892 - A Theory of Expressiveness in Mechanisms

Documents in this Course
Lecture

Lecture

35 pages

Load more
Download A Theory of Expressiveness in Mechanisms
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view A Theory of Expressiveness in Mechanisms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view A Theory of Expressiveness in Mechanisms 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?