Double Auctions with Two-sided Bandit Feedback

Summary

This paper studies double auctions, where a set of $N$ buyers interacts with a set of $M$ sellers to trade some goods. This is a fundamental problem in economics that has been studied extensively. The specific mechanism that is studied in this paper is the average mechanism; it sorts the bids of the sellers and the buyers, identifies the best $k$ so that exactly $k$ trades can happen, and then posts as price the average of the bids of the kth seller and the kth buyer. Formally, the authors study the following repeated setting: at each time $t$, each agent submits a bid, the average mechanism is implemented, and all the agents participating in a trade are revealed a noisy sample of their valuation. This paper aims to design a learning protocol that exhibits a sublinear regret with respect to the outcome of the average mechanism when all the agents declare their actual valuations. Note that in the model studied, the agents do not know their valuations but only learn it by participating in the auction and receiving bandit feedback. The learning protocol proposed by the authors is simple: each agent maintains a (scaled) confidence interval of their valuation, the sellers bid according to LCB, and the buyers to UCB. This protocol yields $O(\log T /\Delta)$ regret regarding social welfare, which is tight. From the agent's perspective, the protocol exhibits an $O(\sqrt T)$ regret for agents belonging to the optimal solution and an $O(\log T/\Delta) $ regret for the others. These results are shown to be tight up to poly-log T terms.

Strengths

- The study of economic problems from an online learning perspective is an active and fruitful line of research, and many works have appeared at NeuriPS and ICML - The regret results are tight, and the algorithm is natural and elegant. - The fact that the authors studied social welfare (i.e., total happiness) and individual utility (i.e., individual happiness) offers a compelling argument for implementing this mechanism in real life. - Given the space constraints, the authors did a good job in presenting and motivating the problem and highlighting the crucial steps of the analysis

Weaknesses

Minor comments: - I do not find that surprising the fact that sellers want to bid according to their LCB - Please spend some extra words on the definition of social welfare used in the paper. In the economic literature, social welfare is defined as the sum of the agents' utilities at the end of the trade. Thus, it also contains the sellers' valuations that retain their goods. The authors call social welfare the gain from trade, i.e., the variation in social welfare after and before the trade. As pointed out by [10], these two notions are equivalent when minimizing regret (due to its additive nature). Please clarify this point. - It makes little sense to have an experimental paragraph in the main body and all the experimental results in the appendix. Either add some plots in the main body or defer everything to the appendix. - The feedback in [10] is not bandit-like: they receive only ordinal information about the price posted and the agents' valuations. This is not enough to reconstruct the gain from trade (so it is strongly less informative than bandit feedback).

Questions

None

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See above

Summary

This paper studies double auction markets where both buyers and sellers receive bandit feedback. There are $N$ buyers and $M$ sellers trading a single type of item in the market during a time horizon $T$. They don't know their own valuations so they need to learn through repeated interactions. The auctioneer implements the average price mechanism at each round. All buyers use UCB algorithms while all seller use LCB algorithms. The benchmark is defined to be the ideal market where true valuations are known and all players bid truthfully. The authors derive regret upper bounds for social welfare and individual utility. They also give regret lower bounds in the minimax sense.

Strengths

1. To the best of my knowledge, this is the first paper that considers repeated double auctions with unknown valuations. Unlike in the standard repeated-auction setting, one need to deal with two-sided uncertainty in repeated double auctions. The regret analysis requires non-trivial techniques. 2. The analysis in the paper is limited to a specific variant of double auction mechanism, but the authors have discussed incentives and deviations, and have complemented the theoretical results with simulation study for completeness. I believe these results can inspire future work on a more general setting. 3. The paper is well written and organized. I particularly like the comments after the main results, which contribute to helping readers better perceive the regret bounds in theorems. The proof flow in the appendix is also very good.

Weaknesses

1. The proof techniques may not be easily applied to more general settings, i.e., when agents don't follow UCB-type algorithms, when the auctioneer don't use the average price mechanism, or where true valuations are time-variant, sampled from some distribution.

Questions

1. Line 148, $n_{s,j}(t)$ -> $n_{b,i}(t)$. 2. How to understand these regret bounds if there are ties. For instance, if $B_{K^*} = B_{K^*+1}$, will the regret on social welfare be arbitrarily bad? What if $\Delta=0$? 3. I personally suggest making the proof outline more concise, so that the main body of the paper can have space to put some results of simulation experiments. 4. Line 615. Does it mean $\beta\geq 2$ is enough for proving Regret=$O(\log T)$?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

The authors acknowledge that the study of incentive compatibility is out of scope for this paper. However, they have given enough discussion on incentives in Appendix C.

Summary

The paper studies an online learning problem related to double auctions. In particular, the paper assumes that the auctioneer uses a average price mechanism. The goal is to study the online learning problem faced by sellers and buyers that do not know they own valuations. The authors design a algorithm based on upper confidence bounds that if applied by all the sellers and buyers guarantees low regret both for each individual and socially. In particular, they show that the social regret is upperbounded by $O(log T/\Delta)$, where $\Delta$ is the minimum price gap, while the individual regret is at most $O(\sqrt T)$.

Strengths

The setting is interesting and of practical relevance. The proposed algorithm is easy to implement and guarantees good regret bounds.

Weaknesses

The algorithmic approach is straghtforward and does not introduce substantial new ideas. I am confused by your choice to use instance dependent regret bound in some cases (depending on $\Delta$) and some instance independent regret bounds $\sqrt T$. I don’t see any conceptual difference between the case in which you apply instance dependent and instance independent bound. For instance, your Lemma 21 (that proves the instance dependent bound) employs arbitrary small difference between the buyer and seller valuations. Hence, it does not rule out logarithm instance dependent bound depending on $\Delta$.

Questions

Please clarify why your are using both instance dependent and instance independent regret bounds. Why do you handle individual regret and social regret in different ways?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Yes

Summary

This work considers learning in a two-sided double auction setting in which both sides must confront uncertainty over their valuations (which are realized upon winning in the auction) and choose to adhere to the same protocol in order to perform that learning. The work shows that buyers and sellers bidding less aggressively - e.g., buyers bidding higher than they otherwise might, and sellers bidding lower than they otherwise might - leads to faster learning than the usual alternative (Optimism in the Face of Uncertainty). One note is that strategic behavior and any Nash equilibrium will be a change in the other direction, and involve bidders bidding more aggressively (buyers lower / sellers higher). Using this strategy, the paper develops bounds on social welfare and individual participant regret. It is mentioned in the appendix that individuals may have incentives to deviate, but in the context of robustness of results, strategic behavior is not considered.

Strengths

The work makes an interesting connection between double auctions and bandit learning, and would seem to be the first to tackle learning on both sides of the market.

Weaknesses

The recommended strategy is quite simple - bidding higher for buyers or lower for sellers, which results in more trade happening than e.g. bidding at expectation or bidding more aggressively, and it is this encouragement of trade that drives results. The authors note that if both sides bid too aggressively then it can slow down trade and hence slow down learning. Incentives from best responding however will push buyers and sellers in the other direction. The protocol model assumes coordination between buyers and sellers on the algorithm to use in order to bid, which could in a real world setting encourage collusion among participants and/or platform disintermediation.

Questions

Double auctions are ubiquitous as mentioned in the discussion. Which many-to-many double auction bandit settings do you view as the right motivation for this work?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

No - discussions of collusion or platform disintermediation would be beneficial for the work.