Market Pricing for Data Streams
Authors: Melika Abolhassani, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Brendan Lucier, Hadi Yami
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present an envy-free mechanism for social welfare maximization problem in the streaming setting using O(k2l) space, where k is the number of different goods and l is the number of available items of each good. We also provide an α-approximation mechanism for revenue maximization in this setting given an α-approximation mechanism for the corresponding offline problem exists. Moreover, we provide mechanisms to approximate the optimum social welfare (or revenue) within 1 ϵ factor, in space independent of l which would be favorable in case l is large compared to k. Finally, we present hardness results showing approximation of optimal prices that maximize social welfare (or revenue) in the streaming setting needs Ω(l) space. We achieve our results by developing a powerful sampling technique for bipartite networks. |
| Researcher Affiliation | Collaboration | Univeristy of Maryland, Microsoft Research brlucier@microsoft.com, {melika, hossein, hajiagha, hadiyami}@cs.umd.edu |
| Pseudocode | Yes | Algorithm 1: Input: Weighted bipartite graph G with set of vertices B V , l number of available items from each item type, and constants ϵ, δ > 0. Output: Price vector p which yields a (1 2ϵ)-approximation of opt SW and an envy-free assignment with probability 1 δ. ... Algorithm 2: Input: Weighted bipartite graph G with set of vertices B V , l number of available items from each item type, and constants ϵ, δ > 0. Output: Price vector p which yields a (1 2ϵ)-approximation of opt revenue and an envy-free assignment with probability 1 δ. |
| Open Source Code | No | The paper does not provide any explicit statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | This paper focuses on theoretical algorithm design and analysis in a streaming model, not on empirical evaluation using specific datasets. Thus, it does not provide access information for a public dataset. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments with datasets, so it does not mention training, validation, or test splits. |
| Hardware Specification | No | The paper is theoretical and does not involve experimental evaluations. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical, focusing on algorithm design and proofs, rather than empirical implementation. Therefore, specific software dependencies with version numbers are not mentioned. |
| Experiment Setup | No | The paper is theoretical, focusing on algorithm design and proofs. It does not describe an experimental setup with specific hyperparameters or training configurations. |