The field of algorithmic mechanism design is concerned with the design of computationally efficient algorithms for use when inputs are provided by rational agents, who may misreport their private values in order to
strategically manipulate the algorithm for their own benefit.
We revisit classic problems in this field by considering settings of incomplete information, where the players' private values are drawn from publicly-known distributions.
Such Bayesian models of partial information are common in economics, but have been largely unexplored by the computer science community.
In the first part of this thesis we show that, for a very broad class of single-parameter problems, any computationally efficient algorithm can be converted without loss into a mechanism that is truthful in the Bayesian sense of partial information. That is, we exhibit a transformation that
generates mechanisms for which it is in each agent's best (expected) interest to refrain from strategic manipulation. The problem
of constructing mechanisms for use by rational agents therefore reduces to the design of approximation algorithms without consideration of game-theoretic issues. We furthermore prove that no such general
transformation is possible if we require mechanisms that are truthful in the stronger non-Bayesian sense of dominant strategies.
In the second part of the thesis we study simple greedy methods for resolving complex auctions. We show that while such greedy
algorithms are not truthful, they suffer very little loss in worst-case
performance bounds when agents apply strategies at equilibrium, even in settings of partial information. Our analysis applies to various different equilibrium concepts, including Bayes-Nash equilibrium,
regret-minimizing strategies, and asynchronous best-response dynamics. Thus, even though greedy auctions are not truthful, they may be appropriate for use as mechanisms under the goal of achieving high social efficiency at equilibrium. Moreover, we prove that no algorithm in a broad class of greedy-like methods can be used to create a deterministic truthful mechanism while retaining a non-trivial approximation to the optimal social welfare.
Our overall conclusion is that while full-information models of agent rationality
currently dominate the algorithmic mechanism design literature, a relaxation to
settings of partial information is well-motivated and provides additional power
in solving central problems in the field.
| Identifer | oai:union.ndltd.org:TORONTO/oai:tspace.library.utoronto.ca:1807/31843 |
| Date | 10 January 2012 |
| Creators | Lucier, Brendan |
| Contributors | Borodin, Allan, Molloy, Michael |
| Source Sets | University of Toronto |
| Language | en_ca |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0033 seconds