When designing online marketplaces, dynamic pricing algorithms, or automated bidding agents, the ideal scenario is to have full information: knowing exactly how much a buyer values an item, or precisely what a competitor bid in an auction. In reality, however, market platforms usually operate under extreme information asymmetry.
Instead of observing continuous valuations, a platform typically observes only a single bit of data: binary feedback. A customer either buys an item or walks away; a trade is either successfully executed or it fails; an auction bid either wins or loses. This phenomenon, often formalized as censored feedback or bandit feedback, fundamentally changes how algorithms must explore and optimize markets.
The Information Bandwidth of a Sale
To understand why binary feedback is challenging, consider a seller setting a posted price $P$ for an item. If a buyer purchases the item, the seller learns only that the buyer's internal valuation $V$ was greater than or equal to $P$ ($V \ge P$). They do not learn how much more the buyer was willing to pay. Conversely, if the buyer rejects the price, the seller only learns that $V < P$.
As Ramesh Johari et al. point out in Semi-Parametric Dynamic Contextual Pricing, this censoring hides the exact threshold of demand. The seller cannot simply compute a gradient based on exact valuation errors; instead, they must treat pricing as a multi-armed bandit problem where each price point is an arm that yields a binary reward. To map out the underlying demand curve and locate the revenue-maximizing price, the algorithm must carefully balance exploiting known profitable prices with cautiously exploring new ones, as analyzed by Nicolò Cesa-Bianchi et al. in Dynamic Pricing with Finitely Many Unknown Valuations.
This representational challenge scales up when moving to multi-item or contextual settings. For instance, in Learning Optimal Posted Prices for a Unit-Demand Buyer, Yifan Wang demonstrates how binary queries can be extended to multi-parameter environments to estimate complex value distributions without ever directly observing private valuations.
The Bilateral Trade Bottleneck
The information bottleneck becomes significantly more severe in bilateral trade, where a platform acts as a broker between a single buyer (with private valuation $V_B$) and a single seller (with private valuation $V_S$).
If the broker proposes a single trade price $P$, a transaction occurs only if both parties accept—meaning $V_B \ge P \ge V_S$. If the trade fails, the broker receives a feedback bit of $0$. Crucially, this single bit does not reveal which party rejected the price. Did the buyer find it too high, or did the seller find it too low?
As Solenne Gaucher et al. explain in Feature-Based Online Bilateral Trade, this lack of granular data makes it incredibly difficult to isolate the parameters of the market participants. Without specialized exploration strategies, the broker can easily get stuck in a suboptimal pricing loop, unable to estimate the potential gain from trade or determine the margin by which a transaction failed (Nicolò Cesa-Bianchi et al. in Bilateral Trade: A Regret Minimization Perspective).
Decoupling Signals via Asymmetric Probing
To overcome the bilateral trade bottleneck, modern online learning algorithms rely on a core mechanism: decoupling the pricing signals.
Instead of forcing a single price on both participants, the broker can employ a dual-price mechanism, posting a buyer price $P_B$ and a seller price $P_S$. By systematically varying these prices independently, the algorithm can isolate the behavior of one side of the market at a time.
In No-Regret Learning in Bilateral Trade via Global Budget Balance, Martino Bernasconi et al. show that this asymmetric estimation procedure allows the learner to construct a mathematically sound proxy for the total market welfare. By holding one side's price constant while testing the other, the broker can deduce the underlying valuation distributions using nothing more than the binary success or failure signals of the resulting trades. Similarly, Yossi Azar et al. prove in An $\alpha$-regret analysis of Adversarial Bilateral Trade that randomized dual-price probing is powerful enough to achieve optimal competitive ratios against adversarial valuations, proving that full valuation transparency is never strictly required for effective market learning.
Trading Short-Term Deficits for Long-Term Knowledge
Isolating market responses via dual pricing introduces a new dilemma: if $P_B < P_S$, a trade might be mutually acceptable to the buyer and seller, but executing it would force the broker to subsidize the transaction, violating strict per-round budget constraints.
A foundational insight across recent literature is that Global Budget Balance is the key to unlocking efficient learning under binary feedback. If a platform is forced to balance its books at every single step, it cannot afford the costly exploration required to discover optimal prices. However, if it can reinvest profits over time—running a deficit in early rounds to "buy" information and recouping the costs during later exploitation phases—it can break through historical impossibility barriers.
The mathematical trade-offs of this approach are stark:
- With strict per-round budget balance: Learning is severely restricted because the broker cannot safely probe the boundaries of buyer and seller willingness.
- With global budget balance: The broker can tolerate temporary, controlled losses during explicit exploration rounds.
As demonstrated by Anna Lunghi et al. in A Stronger Benchmark for Online Bilateral Trade: From Fixed Prices to Distributions, relaxing this constraint allows algorithms to achieve optimal sublinear regret rates ($\tilde{\mathcal{O}}(T^{3/4})$) against highly sophisticated benchmarks, matching the performance of settings with far more granular feedback.
Action-Dependent Censoring in Auctions
A parallel manifestation of the binary feedback constraint occurs in automated auctions, where bidders face action-dependent censoring. In a repeated auction (such as digital advertising markets), a bidder only learns the true value of an item or the nature of the competitive landscape if their bid is high enough to win.
If an agent bids too low and loses, they receive a feedback bit of $0$. They remain entirely unaware of the winning bid or what the counterfactual utility would have been had they won (Arthur Flajolet et al. in Real-Time Bidding with Side Information).
To optimize in these opaque environments, algorithms must treat bidding as a strategic exploration problem. As Juliette Achddou et al. demonstrate in Efficient Algorithms for Stochastic Repeated Second-price Auctions, effective bidding under censoring requires modifying standard Upper Confidence Bound (UCB) strategies to account for the fact that losing provides zero information. Bidders must occasionally overbid purely as an information-gathering mechanism, treating the financial premium of a potential overpayment as the cost of illuminating the hidden valuation space.