Truthful allocation in graphs and hypergraphs
We study truthful mechanisms for allocation problems in graphs, both for the minimization (i.e., scheduling) and maximization (i.e., auctions) setting. The minimization problem is a special case of the well-studied unrelated machines scheduling problem, in which every given task can be executed only...
| मुख्य लेखकों: | , , |
|---|---|
| स्वरूप: | Conference item |
| भाषा: | English |
| प्रकाशित: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2021
|
| _version_ | 1826312304865574912 |
|---|---|
| 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 study truthful mechanisms for allocation problems in graphs, both for the minimization (i.e., scheduling) and maximization (i.e., auctions) setting. The minimization problem is a special case of the well-studied unrelated machines scheduling problem, in which every given task can be executed only by two pre-specified machines in the case of graphs or a given subset of machines in the case of hypergraphs. This corresponds to a multigraph whose nodes are the machines and its hyperedges are the tasks. This class of problems belongs to multidimensional mechanism design, for which there are no known general mechanisms other than the VCG and its generalization to affine minimizers. We propose a new class of mechanisms that are truthful and have significantly better performance than affine minimizers in many settings. Specifically, we provide upper and lower bounds for truthful mechanisms for general multigraphs, as well as special classes of graphs such as stars, trees, planar graphs, k-degenerate graphs, and graphs of a given treewidth. We also consider the objective of minimizing or maximizing the L^p-norm of the values of the players, a generalization of the makespan minimization that corresponds to p = ∞, and extend the results to any p > 0. |
| first_indexed | 2024-03-07T08:27:02Z |
| format | Conference item |
| id | oxford-uuid:ff2ca20d-784f-4b68-8a81-fc4cd5873496 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:27:02Z |
| publishDate | 2021 |
| publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| record_format | dspace |
| spelling | oxford-uuid:ff2ca20d-784f-4b68-8a81-fc4cd58734962024-02-16T10:59:01ZTruthful allocation in graphs and hypergraphsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:ff2ca20d-784f-4b68-8a81-fc4cd5873496EnglishSymplectic ElementsSchloss Dagstuhl - Leibniz-Zentrum für Informatik2021Christodoulou, GKoutsoupias, EKovács, AWe study truthful mechanisms for allocation problems in graphs, both for the minimization (i.e., scheduling) and maximization (i.e., auctions) setting. The minimization problem is a special case of the well-studied unrelated machines scheduling problem, in which every given task can be executed only by two pre-specified machines in the case of graphs or a given subset of machines in the case of hypergraphs. This corresponds to a multigraph whose nodes are the machines and its hyperedges are the tasks. This class of problems belongs to multidimensional mechanism design, for which there are no known general mechanisms other than the VCG and its generalization to affine minimizers. We propose a new class of mechanisms that are truthful and have significantly better performance than affine minimizers in many settings. Specifically, we provide upper and lower bounds for truthful mechanisms for general multigraphs, as well as special classes of graphs such as stars, trees, planar graphs, k-degenerate graphs, and graphs of a given treewidth. We also consider the objective of minimizing or maximizing the L^p-norm of the values of the players, a generalization of the makespan minimization that corresponds to p = ∞, and extend the results to any p > 0. |
| spellingShingle | Christodoulou, G Koutsoupias, E Kovács, A Truthful allocation in graphs and hypergraphs |
| title | Truthful allocation in graphs and hypergraphs |
| title_full | Truthful allocation in graphs and hypergraphs |
| title_fullStr | Truthful allocation in graphs and hypergraphs |
| title_full_unstemmed | Truthful allocation in graphs and hypergraphs |
| title_short | Truthful allocation in graphs and hypergraphs |
| title_sort | truthful allocation in graphs and hypergraphs |
| work_keys_str_mv | AT christodouloug truthfulallocationingraphsandhypergraphs AT koutsoupiase truthfulallocationingraphsandhypergraphs AT kovacsa truthfulallocationingraphsandhypergraphs |