A Unifying Hierarchy of Valuations with Complements and Substitutes
Authors: Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Brendan Lucier, Vasilis Syrgkanis
AAAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We introduce a new hierarchy over monotone set functions, that we refer to as MPH (Maximum over Positive Hypergraphs). Levels of the hierarchy correspond to the degree of complementarity in a given function. ... We present additional results that demonstrate the expressiveness power of MPH-k. One can obtain good approximation ratios for some natural optimization problems, provided that functions are required to lie in low levels of the MPH hierarchy. We present two such applications. One shows that the maximum welfare problem can be approximated within a ratio of k + 1 if all players hold valuation functions in MPH-k. The other is an upper bound of 2k on the price of anarchy of simultaneous first price auctions. ... 3 Proofs In this section we include a part of our proofs. Due to space constraints, we defer the other proofs to the appendix. |
| Researcher Affiliation | Collaboration | Uriel Feige Weizmann Institute of Science uriel.feige@weizmann.ac.il Michal Feldman Tel-Aviv University mfeldman@tau.ac.il Nicole Immorlica Microsoft Research nicimm@gmail.com Rani Izsak Weizmann Institute of Science ran.izsak@weizmann.ac.il Brendan Lucier Microsoft Research brlucier@microsoft.com Vasilis Syrgkanis Microsoft Research vasy@microsoft.com |
| Pseudocode | No | The paper describes algorithmic approaches and linear program formulations in prose, but it does not contain structured pseudocode or algorithm blocks with formal labels. |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not involve empirical evaluation on publicly available datasets; it discusses abstract combinatorial auction settings. |
| Dataset Splits | No | The paper is theoretical and does not involve training/validation/test dataset splits. It does not provide specific details on data partitioning. |
| Hardware Specification | No | The paper mentions using 'Microsoft .NET together with Gurobi (Gurobi Optimization 2014) and IBM CPLEX and also Wolfram Mathematica' for 'computer-assisted simulations,' but it does not provide specific hardware details like CPU or GPU models. |
| Software Dependencies | Yes | We used computer-assisted simulations in order to find feasible solutions for the dual LPs. Specifically, we used Microsoft .NET together with Gurobi (Gurobi Optimization 2014) and IBM CPLEX and also Wolfram Mathematica. |
| Experiment Setup | No | The paper is theoretical, presenting mathematical formulations and proofs. It does not provide specific experimental setup details such as concrete hyperparameter values or training configurations typically found in empirical studies. |