Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Cap-and-Penalize: Competitive Mechanisms for Multi-Phase Regularized Online Allocation
Authors: Seyedehkimia Alaviyar, Faraz Zargari, John Tyler, Yunwei Ryan Li, Xiaoqi Tan
IJCAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our contributions are twofold: (1) we propose an online mechanism for CNP-regularized allocation without per-step resource constraints, which operates as a simple and intuitive posted-price mechanism, but achieves the best-possible guarantee among all possible online algorithms; (2) we tackle the more complex setting with per-step resource constraints by decomposing the regularizer into local components, yielding a similar mechanism with time-dependent marginal pricing functions. To establish the tightness of our results in both settings, we introduce a representative function-based approach that transforms the lower-bound proof into the problem of solving an ordinary differential equation with boundary conditions. We initiate the study of CNP-regularized online allocation with a multi-phase, non-separable regularizer. Unlike prior studies that focus on developing online mechanisms with sublinear regret over the time horizon, our work emphasizes competitive analysis, deriving the optimal online mechanism with the best-possible competitive ratio in the setting without resource constraints. |
| Researcher Affiliation | Academia | Seyedehkimia Alaviyar , Faraz Zargari , John Tyler , Yunwei Ryan Li , Xiaoqi Tan University of Alberta, Edmonton, AB, Canada EMAIL |
| Pseudocode | Yes | Algorithm 1 Online Mechanism for CNP-ROA (PPM-Φ) 1: Inputs: Iknown and Φ 2: Initialization: Capacity utilization u(0) = 0 3: while a new agent n arrives do 4: Post pricing function p(n) for agent n: p(n)(z) = Z u(n 1)+z u(n 1) Φ(s) ds. (2) 5: Agent n decides its own profile ˆxn: ˆxn = arg max xn Xn vn(xn) p(n) X t Tn wtxt n 6: Agent n makes the payment πn: πn = p(n) X t Tn wtˆxt n 7: Update the utilization:u(n) = u(n 1) + P t Tn wtˆxt n. 8: end while |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code for the methodology, nor does it provide a link to a code repository. |
| Open Datasets | No | The paper is theoretical and does not describe experiments that use specific datasets. While it mentions practical applications and policies, it does not provide access information for any open datasets used in its methodology or evaluation. |
| Dataset Splits | No | The paper is theoretical and focuses on algorithm design and competitive analysis, rather than empirical evaluation. Therefore, it does not provide any information about dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical, presenting algorithm design and proofs. It does not conduct experiments requiring specific hardware, so no hardware specifications are mentioned. |
| Software Dependencies | No | The paper presents theoretical algorithms and competitive analysis, without describing any specific software implementations or dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on the design and analysis of online mechanisms. It does not include empirical experiments, and therefore no specific experimental setup details or hyperparameters are provided. |