Truthful allocation in graphs and hypergraphs

DOI10.4230/LIPICS.ICALP.2021.56MaRDI QIDQ7241154zbMATH OpenFDO

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

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2021.56

zbMATH Keywords

algorithmic game theorymechanism designscheduling unrelated machines

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges
• A deterministic truthful PTAS for scheduling related machines
• A lower bound for scheduling mechanisms
• A new lower bound for deterministic truthful scheduling
• A note on graph balancing problems with restrictions
• A unified approach to truthful scheduling on related machines
• Algorithmic mechanism design
• An improved randomized truthful mechanism for scheduling unrelated machines
• Approximating the Nash Social Welfare with Indivisible Items
• Approximation algorithms for scheduling unrelated parallel machines
• Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithms
• Copula-based randomized mechanisms for truthful scheduling on two unrelated machines
• Graph balancing: a special case of scheduling unrelated parallel machines
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• Graph orientation to maximize the minimum weighted outdegree
• Incentives in Teams
• Local search breaks 1.75 for graph balancing
• Mechanism design for fractional scheduling on unrelated machines
• Mechanisms for scheduling with single-bit private values
• No truthful mechanism can be better than n approximate for two natural problems
• On chromatic number of graphs and set-systems
• On simple characterizations of k-trees
• On some special cases of the restricted assignment problem
• On the configuration-LP for scheduling on unrelated machines
• On the Nisan-Ronen conjecture for submodular valuations
• Optimal lower bounds for anonymous scheduling mechanisms
• Prior-independent mechanisms for scheduling
• Setting lower bounds on truthfulness
• The Santa Claus problem
• Truthful approximation schemes for single-parameter agents
• Truthful mechanism design for multidimensional scheduling via cycle monotonicity
• Truthful mechanisms for one-parameter agents
• Truthful mechanisms for two-range-values variant of unrelated scheduling
• Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation

This page was built for publication: Truthful allocation in graphs and hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241154)