Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents
| Autor: | Hanrui Zhang |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
Theory of computation → Stochastic approximation
General Computer Science Inequality Matching (graph theory) Computer Networks and Communications Applied Mathematics media_common.quotation_subject (Approximate) Subadditivity Maximization Prophet Inequalities Theory of computation → Algorithmic game theory and mechanism design Theoretical Computer Science Submodular set function Combinatorics Combinatorial Welfare Maximization Computational Theory and Mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Subadditivity MathematicsofComputing_DISCRETEMATHEMATICS Mathematics Complement (set theory) media_common |
| Zdroj: | Journal of Computer and System Sciences. 123:143-156 |
| ISSN: | 0022-0000 |
| DOI: | 10.1016/j.jcss.2021.08.003 |
| Popis: | We give a framework for designing prophet inequalities for combinatorial welfare maximization. Instantiated with different parameters, our framework implies (1) an O ( log m / log log m ) -competitive prophet inequality for subadditive agents, (2) an O ( D log m / log log m ) -competitive prophet inequality for D-approximately subadditive agents, where D ∈ { 1 , … , m − 1 } measures the maximum number of items that complement each other, and (3) as a byproduct, an O ( 1 ) -competitive prophet inequality for submodular or fractionally subadditive (a.k.a. XOS) agents, matching the optimal ratio asymptotically. Our framework is computationally efficient given sample access to the prior, value queries and demand queries. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect