On the Nisan-Ronen conjecture for submodular valuations
We consider incentive compatible mechanisms for a domain that is very close to the domain of scheduling n unrelated machines: the single exception is that the valuation of just one machine is submodular. For the scheduling problem with such cost functions, we give a lower bound of Ω(√n) on the appro...
| Príomhchruthaitheoirí: | , , |
|---|---|
| Formáid: | Journal article |
| Teanga: | English |
| Foilsithe / Cruthaithe: |
Association for Computing Machinery
2020
|
| _version_ | 1826294482924994560 |
|---|---|
| author | Christodoulou, G Koutsoupias, E Kovács, A |
| author_facet | Christodoulou, G Koutsoupias, E Kovács, A |
| author_sort | Christodoulou, G |
| collection | OXFORD |
| description | We consider incentive compatible mechanisms for a domain that is very close to the domain of scheduling n unrelated machines: the single exception is that the valuation of just one machine is submodular. For the scheduling problem with such cost functions, we give a lower bound of Ω(√n) on the approximation ratio of incentive compatible deterministic mechanisms. This is a strong information-theoretic impossibility result on the approximation ratio of mechanisms that provides strong evidence for the Nisan-Ronen conjecture. This is the first non-constant lower bound that assumes no restriction on the mechanism side; in contrast, all previous general results hold for only special classes of mechanisms such as local, strongly monotone, and anonymous mechanisms. Our approach is based on a novel multi-player characterization of appropriately selected instances that allows us to focus on particular type of algorithms, linear mechanisms, and it is a potential stepping stone towards the full resolution of the conjecture. |
| first_indexed | 2024-03-07T03:46:20Z |
| format | Journal article |
| id | oxford-uuid:bf9bab61-a102-4786-bb98-da16db3da196 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T03:46:20Z |
| publishDate | 2020 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:bf9bab61-a102-4786-bb98-da16db3da1962022-03-27T05:48:39ZOn the Nisan-Ronen conjecture for submodular valuationsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:bf9bab61-a102-4786-bb98-da16db3da196EnglishSymplectic ElementsAssociation for Computing Machinery2020Christodoulou, GKoutsoupias, EKovács, AWe consider incentive compatible mechanisms for a domain that is very close to the domain of scheduling n unrelated machines: the single exception is that the valuation of just one machine is submodular. For the scheduling problem with such cost functions, we give a lower bound of Ω(√n) on the approximation ratio of incentive compatible deterministic mechanisms. This is a strong information-theoretic impossibility result on the approximation ratio of mechanisms that provides strong evidence for the Nisan-Ronen conjecture. This is the first non-constant lower bound that assumes no restriction on the mechanism side; in contrast, all previous general results hold for only special classes of mechanisms such as local, strongly monotone, and anonymous mechanisms. Our approach is based on a novel multi-player characterization of appropriately selected instances that allows us to focus on particular type of algorithms, linear mechanisms, and it is a potential stepping stone towards the full resolution of the conjecture. |
| spellingShingle | Christodoulou, G Koutsoupias, E Kovács, A On the Nisan-Ronen conjecture for submodular valuations |
| title | On the Nisan-Ronen conjecture for submodular valuations |
| title_full | On the Nisan-Ronen conjecture for submodular valuations |
| title_fullStr | On the Nisan-Ronen conjecture for submodular valuations |
| title_full_unstemmed | On the Nisan-Ronen conjecture for submodular valuations |
| title_short | On the Nisan-Ronen conjecture for submodular valuations |
| title_sort | on the nisan ronen conjecture for submodular valuations |
| work_keys_str_mv | AT christodouloug onthenisanronenconjectureforsubmodularvaluations AT koutsoupiase onthenisanronenconjectureforsubmodularvaluations AT kovacsa onthenisanronenconjectureforsubmodularvaluations |