On black-box transformations in downward-closed environments
Black-box transformations have been extensively studied in algorithmic mechanism design as a generic tool for converting algorithms into truthful mechanisms without degrading the approximation guarantees. While such transformations have been designed for a variety of settings, Chawla et al. showed t...
| Main Author: | |
|---|---|
| Format: | Journal article |
| Published: |
Springer US
2018
|
| _version_ | 1797062106523107328 |
|---|---|
| author | Suksompong, W |
| author_facet | Suksompong, W |
| author_sort | Suksompong, W |
| collection | OXFORD |
| description | Black-box transformations have been extensively studied in algorithmic mechanism design as a generic tool for converting algorithms into truthful mechanisms without degrading the approximation guarantees. While such transformations have been designed for a variety of settings, Chawla et al. showed that no fully general black-box transformation exists for single-parameter environments. In this paper, we investigate the potentials and limits of black-box transformations in the prior-free (i.e., non-Bayesian) setting in downward-closed single-parameter environments, a large and important class of environments in mechanism design. On the positive side, we show that such a transformation can preserve a constant fraction of the welfare at every input if the private valuations of the agents take on a constant number of values that are far apart, while on the negative side, we show that this task is not possible for general private valuations. |
| first_indexed | 2024-03-06T20:40:49Z |
| format | Journal article |
| id | oxford-uuid:3438bada-ee1a-4a6e-b0b0-8f711e8a0d03 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T20:40:49Z |
| publishDate | 2018 |
| publisher | Springer US |
| record_format | dspace |
| spelling | oxford-uuid:3438bada-ee1a-4a6e-b0b0-8f711e8a0d032022-03-26T13:24:41ZOn black-box transformations in downward-closed environmentsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:3438bada-ee1a-4a6e-b0b0-8f711e8a0d03Symplectic Elements at OxfordSpringer US2018Suksompong, WBlack-box transformations have been extensively studied in algorithmic mechanism design as a generic tool for converting algorithms into truthful mechanisms without degrading the approximation guarantees. While such transformations have been designed for a variety of settings, Chawla et al. showed that no fully general black-box transformation exists for single-parameter environments. In this paper, we investigate the potentials and limits of black-box transformations in the prior-free (i.e., non-Bayesian) setting in downward-closed single-parameter environments, a large and important class of environments in mechanism design. On the positive side, we show that such a transformation can preserve a constant fraction of the welfare at every input if the private valuations of the agents take on a constant number of values that are far apart, while on the negative side, we show that this task is not possible for general private valuations. |
| spellingShingle | Suksompong, W On black-box transformations in downward-closed environments |
| title | On black-box transformations in downward-closed environments |
| title_full | On black-box transformations in downward-closed environments |
| title_fullStr | On black-box transformations in downward-closed environments |
| title_full_unstemmed | On black-box transformations in downward-closed environments |
| title_short | On black-box transformations in downward-closed environments |
| title_sort | on black box transformations in downward closed environments |
| work_keys_str_mv | AT suksompongw onblackboxtransformationsindownwardclosedenvironments |