Explaining the Law of Supply and Demand via Online Learning

Thank you very much for all your work and for appreciating the motivation of our work. Up next we adrress your main concerns.

1.While the theoretical results are interesting and non-trivial, they might not meet the standard of a NeurIPS paper.

The Law of Supply and Demand is arguably the most fundamental principle in modern economics. We believe that establishing that it can emerge from a learning process among competing sellers is both a novel and significant contribution. We remark that the latter is not guaranteed—since prices could perpetually oscillate. Our results show that, under mild assumptions, convergence to market equilibrium occurs, which we see as a meaningful insight into market dynamics.

2.No-swap regret might be unrealistic in practice.

No-swap regret algorithms have been extensively studied in the literature as models for the learning behavior of competing agents [1,2]. More recently, several works have shown important advantages of no-swap regret, especially in terms of robustness to exploitation [3,4,5]. The latter suggest that no-swap regret is a compelling modeling choice in strategic multi-agent settings.

References:

[1] Hart & Mas-Colell, A Simple Adaptive Procedure Leading to Correlated Equilibrium

[2] Foster & Vohra, Calibrated Learning and Correlated Equilibrium

[3] Arunachaleswaran et al., Swap Regret and Correlated Equilibria Beyond Normal-Form Games

[4] Arunachaleswaran et al., Pareto-Optimal Algorithms for Learning in Games

[5] Mansour et al., Strategizing against Learners in Bayesian Games

3. Assumes full information, also somewhat unrealistic.

Our results do not require any full information assumption. If agents use any no-swap learning algorithm with bandit feedback (only the revenue of the selected price is learned), they will converge to a CE and our results will apply. The same holds in case of noisy perturbations on the reward.

4.Model is a bit too simplistic. Since our model captures the essence of Law of Supply and Demand, we believe that simplicity is a plus.

Questions

How robust are the results to noise, incomplete information, or heterogeneous learning rates?

Our results continue to apply in case of noise / incomplete information / heterogeneous learning rates and even heterogenous algorithms. Our main result establishes any CE is a market clearing price. We remark that convergence to CE is achieved even if agents use different no-swap regret algorithms. At the same time, there are various no-swap regret algorithms that work with noisy perturbations of the reward or even with bandit feedback (only the revenue of the selected price is revealed to the seller). Even in such limited information settings, if agents use such no-swap regret algorithms they will converge to CE and thus our results apply.

We hope the latter clarify your concerns and encourage a reconsideration of your score. We would be happy to provide further clarifications if needed.

Thank you very much for all your work and for appreciating the innovative aspects of our work. Up next we address your main concerns.

On the other hand, the paper...to elaborate on what constitutes these "specific classes."

With specific classes we refer to the mean-based algorithms. Notice that we write "Ιt is likely that a certain classes of no-regret algorithms, such as mean-based algorithms, may be able to always converge to the market clearing price".

Mean-based algorithms [4] is a natural class of no-regret algorithms (including Hedge) with the following property: if the cumulative reward of two actions differs by at most $\mathcal{O}(\gamma \cdot T)$ then the respective probabilities differ by at most by $\mathcal{O}(\gamma)$. Mean-based nο-regret algorithms are known to avoid degenerate CCE in various games (e.g. auctions, potential games [1,2,3]). As a result, we conjecture that this may be the case for Supply and Demand games. The latter is aligned with our experimental evaluations.

In the revised version of our work, we will add the above discussion to clarify the situation. We will also add additional experimental evaluations of no-regret algorithms (FTRL, Online Mirror Descent, Regret Matching etc.). We will additionally correct the typos and add error bars.

Remark: The main result of our work is formally establishing that Correlated Equilibrium (CE) corresponds to the market clearing price in the case of Supply and Demand games. We remark that the discussion on no-regret algorithms does not constitute neither an argument nor a result of the current paper, but rather a conjecture and a suggestion for future research direction.

We hope the latter clarify your concerns and will help reconsider your score.

[1] Deng et al. Nash convergence of mean-based learning algorithms in first price auctions.

[2] Feng et al. Convergence Analysis of No-Regret Bidding Algorithms in Repeated Auctions.

[3] Heliou et al. Learning with Bandit Feedback in Potential Games.

[4] Braverman et al. Selling to a No-Regret Buyer.

Thank you very much for all your work and the positive feedback on our work. Up next we address your main concerns.

1.Section 1.1 reviews...this work and prior studies.

In the revised version of our work, we will discuss in further detail the related literature.

2.The model assumes that...preference heterogeneity.

The law of Supply and Demand assumes that all provided goods are indistiguishable. When buyer preferences vary (preference heterogeneity) the law of Supply and Demand no longer holds. Also notice that in case of indistinguishable goods, strategic buyer behavior reduces to simply purchasing from the cheapest available seller.

3.The experimental evaluation...online algorithms. The primary focus of our work is to formally establish the law of supply and demand as an emergent behavior of learning dynamics among sellers. That being said, in the revised version, we will include additional experimental evaluations using a broader set of no-regret algorithms, including FTRL, Regret Matching, Online Mirror Descent, and others.

Questions

1.The analysis assumes...in the continuous case?

We believe that our results and techniques extend to the continuous price model by considering the respective LPs with infinite number of constraints. In the current work we chose the discrete price model since it leads to simpler analysis and better reflects practice where prices are typically discrete.

2.How would the convergence results be affected by noise in seller feedback or slight uncertainty in buyer valuations?

The are not affected at all. There are no-swap regret algorithms that work under noisy perturbations on the payoffs or even bandit feedback (only the revenue of the selected price is observed). If agents adopt such algorithms the overall system will converge to a CE and thus our results apply.

3.Theorem 2 presents a negative result...no-swap regret algorithms.

In the revised version, we will present further experimental evaluations of various no-regret algorithms. However we conjecture that natural no-regret algorithms avoid bad Coarse Correlated Equilibria (CCE) and instead converge to the market-clearing price. Our negative result in Theorem 2 highlights the limitations of reasoning about general CCEs, suggesting that future analysis should focus on specific no-regret algorithms rather than on general CCEs.

Thank you very much for all the very detailed review and positive feedback on our paper. In the revised version of our paper, we will fix all the typos and minor comments.

Up next we address your main questions and concerns.

1. The sellers...A brief note would be useful here. You are right and we apologize for the confusion. Wlog was supposed to refer on the ordering of the sellers. We will add a brief note to clarify.

2. According to Lemma 1...somewhat restrictive. We believe that our results hold even without this assumption however in such a case one would need to deal with tedious technical details. We chose to use this assumption that greatly simplifies the analysis since in case of sufficiently large discretization, it is natural to assume that each seller admits a slightly different price.

3. Def 4 could possibly be standard...Possibly to be consistent with the second equation? You are right that $p_i^\star$ is a derministic price however observe that all other agents sample their prices $p_{-i}^t$ according to the probablity distribution $x_{-i}^t$ and that is why we use the expectation.