test Browse by Author Names Browse by Titles of Works Browse by Subjects of Works Browse by Issue Dates of Works

Advanced Search
& Collections
Issue Date   
Sign on to:   
Receive email
My Account
authorized users
Edit Profile   
About T-Space   

T-Space at The University of Toronto Libraries >
School of Graduate Studies - Theses >
Doctoral >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1807/11113

Title: Mechanism Design with Partial Revelation
Authors: Hyafil, Nathanael
Advisor: Boutilier, Craig
Department: Computer Science
Keywords: Mechanism Design
Issue Date: 28-Jul-2008
Abstract: With the emergence of the Internet as a global structure for communication and interaction, many “business to consumer” and “business to business” applications have migrated online, thus increasing the need for software agents that can act on behalf of people, institutions or companies with private and often conflicting interests. The design of such agents, and the protocols (i.e., mechanisms) through which they interact, has therefore naturally become an important research theme. Classical mechanism design techniques from the economics literature do not account for the costs entailed with the full revelation of preferences that they require. The aim of this thesis is to investigate how to design mechanisms that only require the revelation of partial preference information and are applicable in any mechanism design context. We call this partial revelation mechanism design. Reducing revelation costs is thus our main concern. With only partial revelation, the designer has some remaining uncertainty over the agents’ types, even after the mechanism has been executed. Thus, in general, the outcome chosen will not be optimal with respect to the designer’s objective function. This alone raises interesting questions about which (part of the) information should be elicited in order to minimize the degree of sub-optimality incurred by the mechanism. But this sub-optimality of the mechanism’s outcome choice function has additional important consequences: most of the results in classical mechanism design which guarantee that agents will reveal their type truthfully to the mechanism rely on the fact that the optimal outcome is chosen. We must therefore also investigate if, and how, appropriate incentives can be maintained in partial revelation mechanisms. We start by presenting our own model for partial revelation mechanism design. Our second contribution is a negative one regarding the quasi-impossibility of implementing partial revelation mechanisms with exact incentive properties. The rest of the thesis shows, in different settings, how this negative result can be bypassed in various settings, depending on the designer's objective (e.g., social welfare, revenue...) and the interaction type (sequential or one shot). Finally, we study how the approximation of the incentive properties can be further improved when necessary, and in the process, introduce and proves the existence of a new equilibrium concept.
URI: http://hdl.handle.net/1807/11113
Appears in Collections:Doctoral
Department of Computer Science - Doctoral theses

Files in This Item:

File Description SizeFormat
Hyafil_Nathanael_200803_PHD_thesis.pdf1.43 MBAdobe PDF

This item is licensed under a Creative Commons License
Creative Commons

Items in T-Space are protected by copyright, with all rights reserved, unless otherwise indicated.