A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation
From MaRDI portal
Publication:2436693
DOI10.1007/s10472-012-9328-4zbMath1286.68205MaRDI QIDQ2436693
Magnus Roos, Trung Thanh Nguyen, Jörg Rothe
Publication date: 25 February 2014
Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10472-012-9328-4
computational social choice; multiagent resource allocation; approximability; social welfare optimization
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
91B14: Social choice
68T42: Agent technology and artificial intelligence
Related Items
Approximating the Nash Social Welfare with Indivisible Items, Duplication monotonicity in the allocation of indivisible goods, Generalized graph \(k\)-coloring games, Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games, Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods, Fair assignment of indivisible objects under ordinal preferences, Strategy-proofness of scoring allocation correspondences for indivisible goods, Local fairness in hedonic games via individual threshold coalitions, The price to pay for forgoing normalization in fair division of indivisible goods, Effective deadlock resolution with self-interested partially-rational agents, Exploration costs as a means for improving performance in multiagent systems, A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for scheduling unrelated parallel machines
- Inapproximability results for combinatorial auctions with submodular utility functions
- The exact LPT-bound for maximizing the minimum completion time
- \(k\)-order additive discrete fuzzy measures and their representation
- A polynomial-time approximation scheme for maximizing the minimum machine completion time
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Bundling equilibrium in combinatorial auctions
- Multiagent resource allocation in \(k\)-additive domains: preference representation and complexity
- A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation
- The complexity of contract negotiation
- Complexity theory and cryptology. An introduction to cryptocomplexity.
- Combinatorial auctions with decreasing marginal utilities
- The Santa Claus problem
- Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders
- Truth revelation in approximately efficient combinatorial auctions
- Tight approximation algorithms for maximum general assignment problems
- An improved approximation algorithm for combinatorial auctions with submodular bidders
- Approximation Algorithms for the Max-Min Allocation Problem
- Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
- Exact and Approximate Algorithms for Scheduling Nonidentical Processors
- Computational Complexity of Probabilistic Turing Machines
- On Allocating Goods to Maximize Fairness
- On Maximizing Welfare When Utility Functions Are Subadditive
- An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- [https://portal.mardi4nfdi.de/wiki/Publication:5731810 On the foundations of combinatorial theory I. Theory of M�bius Functions]
