The Price is (Probably) Right: Learning Market Equilibria from Samples

• URL: http://arxiv.org/abs/2012.14838v2
• Date: Thu, 4 Feb 2021 20:02:16 GMT
• Title: The Price is (Probably) Right: Learning Market Equilibria from Samples
• Authors: Omer Lev, Neel Patel, Vignesh Viswanathan, Yair Zick
• Abstract summary: We consider the setting where player valuations are unknown. Using a PAC learning-theoretic framework, we analyze some classes of common valuation functions. We provide algorithms which output direct PAC equilibrium allocations.
• Score: 23.236452020801337
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Equilibrium computation in markets usually considers settings where player valuation functions are known. We consider the setting where player valuations are unknown; using a PAC learning-theoretic framework, we analyze some classes of common valuation functions, and provide algorithms which output direct PAC equilibrium allocations, not estimates based on attempting to learn valuation functions. Since there exist trivial PAC market outcomes with an unbounded worst-case efficiency loss, we lower-bound the efficiency of our algorithms. While the efficiency loss under general distributions is rather high, we show that in some cases (e.g., unit-demand valuations), it is possible to find a PAC market equilibrium with significantly better utility.

Related papers

• Large-Scale Contextual Market Equilibrium Computation through Deep Learning [10.286961524745966]
  We introduce MarketFCNet, a deep learning-based method for approximating market equilibrium. We show that MarketFCNet delivers competitive performance and significantly lower running times compared to existing methods.
  arXiv  Detail & Related papers  (2024-06-11T03:36:00Z)
• Self-Evaluation Guided Beam Search for Reasoning [61.523627290397556]
  We introduce a stepwise self-evaluation mechanism to guide and calibrate the reasoning process of Large Language Model (LLM) We propose a decoding algorithm integrating the self-evaluation guidance via beam search. Our approach surpasses the corresponding Codex-backboned baselines in few-shot accuracy by $6.34%$, $9.56%$, and $5.46%$ on the GSM8K, AQuA, and StrategyQA.
  arXiv  Detail & Related papers  (2023-05-01T02:37:59Z)
• Does Machine Learning Amplify Pricing Errors in the Housing Market? -- The Economics of Machine Learning Feedback Loops [2.5699371511994777]
  We develop an analytical model of machine learning feedback loops in the context of the housing market. We show that feedback loops lead machine learning algorithms to become overconfident in their own accuracy. We then identify conditions where the economic payoffs for home sellers at the feedback loop equilibrium is worse off than no machine learning.
  arXiv  Detail & Related papers  (2023-02-18T23:20:57Z)
• Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets [32.50099216716867]
  This paper develops learning-augmented algorithms for energy trading in volatile electricity markets. We incorporate machine-learned predictions to design competitive algorithms for online search problems.
  arXiv  Detail & Related papers  (2022-11-12T04:12:10Z)
• Direct Advantage Estimation [63.52264764099532]
  We show that the expected return may depend on the policy in an undesirable way which could slow down learning. We propose the Direct Advantage Estimation (DAE), a novel method that can model the advantage function and estimate it directly from data. If desired, value functions can also be seamlessly integrated into DAE and be updated in a similar way to Temporal Difference Learning.
  arXiv  Detail & Related papers  (2021-09-13T16:09:31Z)
• Optimization-friendly generic mechanisms without money [8.98272353392094]
  We develop a generic framework for converting modern optimization algorithms into mechanisms where inputs come from self-interested agents. Special cases of this setting include voting, allocation of items by lottery, and matching. Key technical contribution is a new meta-algorithm we call apex.
  arXiv  Detail & Related papers  (2021-06-14T20:42:23Z)
• Semi-verified PAC Learning from the Crowd [7.594050968868919]
  We study the problem of crowdsourced PAC learning of threshold functions. We show that under the semi-verified model of Charikar et al., it is possible to PAC learn the underlying hypothesis class with a manageable amount of label queries.
  arXiv  Detail & Related papers  (2021-06-13T20:05:16Z)
• Scalable Personalised Item Ranking through Parametric Density Estimation [53.44830012414444]
  Learning from implicit feedback is challenging because of the difficult nature of the one-class problem. Most conventional methods use a pairwise ranking approach and negative samplers to cope with the one-class problem. We propose a learning-to-rank approach, which achieves convergence speed comparable to the pointwise counterpart.
  arXiv  Detail & Related papers  (2021-05-11T03:38:16Z)
• Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence [66.83161885378192]
  Area under ROC (AUROC) and precision-recall curves (AUPRC) are common metrics for evaluating classification performance for imbalanced problems. We propose a technical method to optimize AUPRC for deep learning.
  arXiv  Detail & Related papers  (2021-04-18T06:22:21Z)
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration [143.43658264904863]
  We show how iteration under a more standard notion of low inherent Bellman error, typically employed in least-square value-style algorithms, can provide strong PAC guarantees on learning a near optimal value function. We present a computationally tractable algorithm for the reward-free setting and show how it can be used to learn a near optimal policy for any (linear) reward function.
  arXiv  Detail & Related papers  (2020-08-18T04:34:21Z)
• PACOH: Bayes-Optimal Meta-Learning with PAC-Guarantees [77.67258935234403]
  We provide a theoretical analysis using the PAC-Bayesian framework and derive novel generalization bounds for meta-learning. We develop a class of PAC-optimal meta-learning algorithms with performance guarantees and a principled meta-level regularization.
  arXiv  Detail & Related papers  (2020-02-13T15:01:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.