Document Open Access Logo

Truthful Allocation in Graphs and Hypergraphs

Authors George Christodoulou, Elias Koutsoupias , Annamária Kovács

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.56.pdf
  • Filesize: 0.74 MB
  • 20 pages

Document Identifiers

Author Details

George Christodoulou
  • University of Liverpool, UK
Elias Koutsoupias
  • University of Oxford, UK
Annamária Kovács
  • Goethe University, Frankfurt am Main, Germany

Funding

  • Koutsoupias, Elias: This work was partially supported by ERC Advanced Grant 321171 (ALGAME).

Cite As Get BibTex

George Christodoulou, Elias Koutsoupias, and Annamária Kovács. Truthful Allocation in Graphs and Hypergraphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 56:1-56:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.56

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic mechanism design
Keywords
  • Algorithmic Game Theory
  • Scheduling Unrelated Machines
  • Mechanism Design

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Aaron Archer and Éva Tardos. Truthful mechanisms for one-parameter agents. In Proc. of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 482-491, 2001. Google Scholar
  2. Yuichi Asahiro, Jesper Jansson, Eiji Miyano, and Hirotaka Ono. Graph orientation to maximize the minimum weighted outdegree. Int. J. Found. Comput. Sci., 22(3):583-601, 2011. URL: https://doi.org/10.1142/S0129054111008246.
  3. Yuichi Asahiro, Eiji Miyano, and Hirotaka Ono. Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree. Disc. Appl. Math., 159(7):498-508, 2011. Google Scholar
  4. Itai Ashlagi, Shahar Dobzinski, and Ron Lavi. Optimal lower bounds for anonymous scheduling mechanisms. Mathematics of Operations Research, 37(2):244-258, 2012. URL: https://doi.org/10.1287/moor.1110.0534.
  5. Vincenzo Auletta, George Christodoulou, and Paolo Penna. Mechanisms for scheduling with single-bit private values. Theory Comput. Syst., 57(3):523-548, 2015. URL: https://doi.org/10.1007/s00224-015-9625-5.
  6. Nikhil Bansal and Maxim Sviridenko. The Santa Claus problem. In STOC, pages 31-40. ACM, 2006. URL: https://doi.org/10.1145/1132516.1132522.
  7. Sushil Bikhchandani, Shurojit Chatterji, Ron Lavi, Ahuva Mu'alem, Noam Nisan, and Arunava Sen. Weak monotonicity characterizes deterministic dominant strategy implementation. Econometrica, 74(4), 2006. Google Scholar
  8. Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Prior-independent mechanisms for scheduling. In STOC'13, pages 51-60. ACM, 2013. URL: https://doi.org/10.1145/2488608.2488616.
  9. Xujin Chen, Donglei Du, and Luis Fernando Zuluaga. Copula-based randomized mechanisms for truthful scheduling on two unrelated machines. Theory Comput. Syst., 57(3):753-781, 2015. Google Scholar
  10. George Christodoulou, Elias Koutsoupias, and Annamária Kovács. Mechanism design for fractional scheduling on unrelated machines. ACM Transactions on Algorithms, 6(2), 2010. URL: https://doi.org/10.1145/1721837.1721854.
  11. George Christodoulou, Elias Koutsoupias, and Annamária Kovács. On the Nisan-Ronen conjecture. CoRR, abs/2011.14434, 2020. URL: http://arxiv.org/abs/2011.14434.
  12. George Christodoulou, Elias Koutsoupias, and Annamária Kovács. On the Nisan-Ronen conjecture for submodular valuations. In STOC, pages 1086-1096. ACM, 2020. Google Scholar
  13. George Christodoulou, Elias Koutsoupias, and Angelina Vidali. A lower bound for scheduling mechanisms. Algorithmica, 55(4):729-740, 2009. URL: https://doi.org/10.1007/s00453-008-9165-3.
  14. George Christodoulou and Annamária Kovács. A deterministic truthful ptas for scheduling related machines. SIAM J. Comput., 42(4):1572-1595, 2013. URL: https://doi.org/10.1137/120866038.
  15. Edward H. Clarke. Multipart pricing of public goods. Public Choice, 8, 1971. Google Scholar
  16. Richard Cole and Vasilis Gkatzelis. Approximating the Nash social welfare with indivisible items. SIAM Journal on Computing, 47(3):1211-1236, January 2018. Google Scholar
  17. Constantinos Daskalakis and S. Matthew Weinberg. Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithms. In SODA, pages 1934-1952. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.130.
  18. Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi, and Tim Roughgarden. Truthful approximation schemes for single-parameter agents. SIAM J. on Computing, 40(3):915-933, 2011. URL: https://doi.org/10.1137/080744992.
  19. Reinhard Diestel. Graph Theory, 4th Edition. Springer, 2012. Google Scholar
  20. Shahar Dobzinski and Ariel Shaulker. Improved lower bounds for truthful scheduling. CoRR, abs/2007.04362, 2020. URL: http://arxiv.org/abs/2007.04362.
  21. Tomás Ebenlendr, Marek Krcál, and Jirí Sgall. Graph balancing: A special case of scheduling unrelated parallel machines. Algorithmica, 68(1):62-80, 2014. URL: https://doi.org/10.1007/s00453-012-9668-9.
  22. Leah Epstein, Asaf Levin, and Rob van Stee. A unified approach to truthful scheduling on related machines. In Proc. SODA, pages 1243-1252, 2013. Google Scholar
  23. Paul Erdős and András Hajnal. On chromatic number of graphs and set-systems. Acta Mathematica Hungarica, 17(1-2):61-99, 1966. Google Scholar
  24. Yiannis Giannakopoulos, Alexander Hammerl, and Diogo Poças. A new lower bound for deterministic truthful scheduling. In SAGT 2020, volume 12283, pages 226-240. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-57980-7_15.
  25. Yiannis Giannakopoulos and Maria Kyropoulou. The VCG mechanism for bayesian scheduling. ACM Trans. Economics and Comput., 5(4):19:1-19:16, 2017. URL: https://doi.org/10.1145/3105968.
  26. Theodore Groves. Incentives in teams. Econometrica, 41(4):617-631, 1973. Google Scholar
  27. Chien-Chung Huang and Sebastian Ott. A combinatorial approximation algorithm for graph balancing with light hyper edges. In ESA 2016, volume 57 of LIPIcs, pages 49:1-49:15, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.49.
  28. Klaus Jansen and Lars Rohwedder. Local search breaks 1.75 for graph balancing. In ICALP 2019, volume 132 of LIPIcs, pages 74:1-74:14, 2019. Google Scholar
  29. Elias Koutsoupias and Angelina Vidali. A lower bound of 1+ϕ for truthful scheduling mechanisms. Algorithmica, pages 1-13, 2012. Google Scholar
  30. Ron Lavi and Chaitanya Swamy. Truthful mechanism design for multidimensional scheduling via cycle monotonicity. Games and Economic Behavior, 67(1):99-124, 2009. URL: https://doi.org/10.1016/j.geb.2008.08.001.
  31. Kangbok Lee, Joseph Y.-T. Leung, and Michael L. Pinedo. A note on graph balancing problems with restrictions. Inf. Process. Lett., 110(1):24-29, 2009. URL: https://doi.org/10.1016/j.ipl.2009.09.015.
  32. Jan Karel Lenstra, David B Shmoys, and Eva Tardos. Approximation algorithms for scheduling unrelated parallel machines. Mathematical programming, 46(1-3):259-271, 1990. Google Scholar
  33. Stefano Leucci, Akaki Mamageishvili, and Paolo Penna. No truthful mechanism can be better than n approximate for two natural problems. Games and Economic Behavior, 111:64-74, 2018. URL: https://doi.org/10.1016/j.geb.2018.05.003.
  34. Pinyan Lu. On 2-player randomized mechanisms for scheduling. In WINE, volume 5929 of Lecture Notes in Computer Science, pages 30-41. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-10841-9_5.
  35. Pinyan Lu and Changyuan Yu. An improved randomized truthful mechanism for scheduling unrelated machines. In STACS, volume 1 of LIPIcs, pages 527-538, 2008. Google Scholar
  36. Pinyan Lu and Changyuan Yu. Randomized truthful mechanisms for scheduling unrelated machines. In WINE, pages 402-413, 2008. URL: https://doi.org/10.1007/978-3-540-92185-1_46.
  37. Hadi Minooei and Chaitanya Swamy. Truthful mechanism design for multidimensional covering problems. In WINE 2012, volume 7695 of LNCS, pages 448-461. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-35311-6_33.
  38. Ahuva Mu'alem and Michael Schapira. Setting lower bounds on truthfulness. Games and Economic Behavior, 110:174-193, 2018. Google Scholar
  39. Noam Nisan and Amir Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35:166-196, 2001. Google Scholar
  40. Donald J Rose. On simple characterizations of k-trees. Disc. Math., 7(3-4):317-322, 1974. Google Scholar
  41. Michael E. Saks and Lan Yu. Weak monotonicity suffices for truthfulness on convex domains. In Proceedings 6th ACM Conference on Electronic Commerce (EC), pages 286-293, 2005. URL: https://doi.org/10.1145/1064009.1064040.
  42. José Verschae and Andreas Wiese. On the configuration-lp for scheduling on unrelated machines. J. Scheduling, 17(4):371-383, 2014. URL: https://doi.org/10.1007/s10951-013-0359-4.
  43. William Vickrey. Counterspeculations, auctions and competitive sealed tenders. Journal of Finance, 16:8-37, 1961. Google Scholar
  44. Chao Wang and René Sitters. On some special cases of the restricted assignment problem. Inf. Process. Lett., 116(11):723-728, 2016. Google Scholar
  45. Changyuan Yu. Truthful mechanisms for two-range-values variant of unrelated scheduling. Theoretical Computer Science, 410(21-23):2196-2206, 2009. URL: https://doi.org/10.1016/j.tcs.2009.02.001.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact