PaperlayerView exact revision on arXiv

Source-linked AI summary

Pricing Information in Search with Nonobligatory Inspection

Shuo Zhang, Boyu Liu, Zihe Wang

arXiv:2610.34369v1cs.GT

TL;DR

The paper asks how platforms can price information for sequential search when buyers may select alternatives without purchasing their reports. It analyzes static and adaptive fees, showing that common pricing has strong guarantees and that an adaptive access fee can extract the full information surplus.

  • Problem

    Agent-assisted search can weaken the link between sponsored placement, user clicks, and product discovery, motivating information sales that improve an agent’s choice.

    Source: §1 · p. 1

  • Method

    The paper analyzes static and adaptive report pricing for search among alternatives, including common fees and simple static pricing schemes.

    Source: §1.1 · pp. 2–3, §5 · p. 12

  • Results

    Common fees are optimal for identical priors; heterogeneous binary pricing is NP-hard, yet a polynomial algorithm earns at least ∆/3, and uniform fees secure 1/(1 + ln n) of optimal adaptive revenue.

    Source: §1.1 · pp. 2–3, §6 · p. 14

  • Takeaways & Limitations

    These guarantees provide a basis for monetizing agent-mediated search through information sales and quantify the revenue cost of keeping report fees fixed.

    Source: §6 · p. 14

    Whether static prices can capture more than one third of binary-prior surplus and the best polynomial-time approximation to optimal static revenue remain open.

    Source: §4.3 · p. 12, §6 · p. 14

Abstract

from arXiv · show

As AI agents reshape Web search and advertising, platforms can monetize information that improves decisions. We study information pricing for sequential search among independent alternatives with nonobligatory inspection: the buyer may select any alternative without buying its report. We show that a common fee maximizes static revenue for identical priors, resolving a uniform-pricing conjecture. Our results also establish that exact optimization is NP-hard for heterogeneous binary priors. Despite this hardness, our polynomial-time static pricing algorithm achieves a $3$-approximation to the information surplus. More generally, a common static fee approximates optimal adaptive revenue within a logarithmic factor in the number of alternatives. This guarantee is asymptotically tight.

1 Introduction

The paper studies selling information for sequential search as agents change how people discover products. It establishes pricing guarantees for identical and heterogeneous priors, then compares static fees with adaptive pricing.

1 Introduction

  • Agent-assisted search can evaluate more alternatives without requiring users to browse each one, potentially weakening the link between sponsored placement, clicks, and product discovery.This motivates selling information that improves an agent’s choice.Source: §1 · p. 1
  • The model lets buyers purchase reports sequentially but select any alternative without buying its report, making the buyer’s fallback part of the pricing problem.An uninspected alternative offers its prior mean, while an unfavorable inspection can replace that prospect with a low realized value.Source: §1 · pp. 1–2

1.1 Results and approach

  • A common fee maximizes static revenue for identical priors, while heterogeneous binary priors make exact static-price optimization NP-hard.For heterogeneous priors, a polynomial-time algorithm nevertheless earns at least ∆/3 of the information surplus.Source: §1.1 · pp. 2–3
  • For general priors, a common static fee earns at least 1/(1 + ln n) of optimal adaptive revenue, and this bound is asymptotically tight.An adaptive access fee of ∆ followed by free reports extracts the full information surplus.Source: §1.1 · p. 3

1.2 Related work

  • For general i.i.d. priors, the paper’s uniform-optimality result removes Chawla et al.’s [15] (1 −1/n) loss while keeping every report available, and establishes computational difficulty and revenue guarantees with fees fixed before disclosure.Chawla et al. obtain a (1 −1/n) share of optimal static revenue for general i.i.d. priors by withholding one report and posting a common fee for the rest.Source: §1.2 · p. 3

2 Model and benchmarks

The model has a risk-neutral buyer who sequentially buys reports at fixed fees and may retain uninspected alternatives as blind choices. The information surplus and individual information caps bound what pricing can earn and charge.

2 Model and benchmarks

  • The seller posts separate fixed fees before search; buying a report reveals that alternative’s value, and reports have no production costs.An infinite fee withholds a report while leaving the alternative available for selection.Source: §2 · pp. 3–4
  • At each step, the buyer may stop and choose a revealed value, a blind alternative worth its prior mean, or a payoff of zero.The buyer maximizes expected selected value less expected payments, accounting for how each report outcome affects later search.Source: §2 · p. 4
  • The information surplus ∆ is the gain in expected choice value from learning all values rather than choosing without inspection, and it bounds static revenue.The buyer can decline every report and retain the best prior mean as the blind payoff.Source: §2 · p. 4
  • No utility-optimal continuation buys report i above its information cap ci = E[(Xi −µi)+]; lowering such a fee to ci preserves buyer utility and weakly increases seller-favorable revenue.The cap measures potential gains above the prior mean; a deterministic alternative has no information to sell.Source: §2 · p. 4

3 Uniform pricing

With identical priors, a common static fee is revenue-optimal even though willingness to pay changes during search. Cheapest-first inspection and a price-merging argument reduce the seller’s problem to choosing one common fee.

3 Uniform pricing

  • For any number of independent copies of a nonnegative finite-mean value, every static fee vector is weakly revenue-dominated by an attained optimal common fee.Even when an intermediate observation sustains demand for the final report, identical priors permit a common fee to match or exceed differentiated fees.Source: §3 · p. 5, Figure 1 · p. 5

3.1 Buyer response and revenue

  • At every history, a revenue-maximizing utility-optimal buyer continuation can inspect a cheapest remaining report whenever it continues.Interchanging two reports with identical priors preserves selected-value distributions and purchase probabilities while avoiding higher payments if search ends early.Source: §3.1 · p. 6
  • For sorted capped fees, revenue sums each fee times its purchase probability, with a final-report correction for histories where the buyer selects the remaining alternative blindly.The correction depends only on the largest fee, linking the stopping rule to the price-merging argument.Source: §3.1 · pp. 6–7

3.2 Merging prices without losing revenue

  • Merging adjacent fee groups by raising the earlier fee or lowering the later one can preserve or improve revenue; repeating this leaves one common fee with revenue at least as high as before.Neither merge raises the largest fee, so the correction for blind selection cannot increase.Source: §3.2 · pp. 7–8

4 Static pricing for binary priors

With heterogeneous binary priors, exact static pricing is NP-hard, but a polynomial-time algorithm selects among at most three static fee vectors to capture at least one third of the information surplus. The schemes preserve blind fallback options while pricing information that can improve the buyer’s choice.

4 Static pricing for binary priors

  • Exact revenue-optimal static pricing is NP-hard even for independent nonnegative two-point values.The reduction encodes Product Partition through low-outcome probabilities and the prices that determine which reports are inspected before or after the best blind alternative.Source: §4 · p. 8
  • A polynomial-time static fee vector earns at least ∆/3 for independent nonnegative two-point values, regardless of the number of alternatives or their heterogeneity.The algorithm selects among at most three candidate vectors using their revenue guarantees.Source: §4 · pp. 8–9

4.1 Surplus and the reserve scheme

  • The reserve scheme preserves the best blind choice and prices other reports at expected improvements over it, collecting the search gain B while keeping buyer utility at m.At these prices, an optimal response inspects in decreasing order of high values and stops at the first value above the reserve.Source: §4.1 · pp. 9–10

4.2 Two further pricing schemes

  • The early-report scheme keeps alternative 2 blind as a reserve, sells report 1 first, and prices remaining reports against the reserve; the optimal response stops after a high first outcome.After a low outcome, the buyer searches remaining reports in decreasing order of high values; the guarantee combines the initial payment with continuation revenue.Source: §4.2 · p. 10
  • The free-report scheme gives report 2 away and charges for report 1, using the free disclosure to make the paid comparison worthwhile.When the free report reveals h2, report 1 is worth exactly its fee, yielding guarantee D = θ2v1(h2).Source: §4.2 · pp. 10–11
  • The three schemes target distinct sources of information value: searching around the best blind choice, inspecting that choice, and selling an early report or a paid comparison after free disclosure.When t > s, Table 2 lists the schemes’ fixed fees and expected-revenue lower bounds.Source: Table 2 · p. 9, §4.1 · p. 9, §4.3 · p. 11

4.3 The approximation guarantee

  • The seller computes bounds before search and posts one selected fee vector; the largest of three guarantees captures at least one third of the surplus.For t ≤ s, the reserve and free-report-1 vectors give a bound of ∆/2; for t > s, ∆=A+B≤B+C+D.Source: §4.3 · pp. 11–12
  • The algorithm computes its bounds and fees in polynomial time for rational input, while whether static prices can always capture more than one third of surplus remains open.The best polynomial-time approximation to optimal static revenue also remains open.Source: §4.3 · p. 12

5 The static–adaptive revenue gap

A common static fee has a logarithmic worst-case revenue gap from adaptive pricing, and the bound is asymptotically tight. A committed access fee followed by free reports extracts the full information surplus; identical mean-one exponential priors show the tight separation.

5 The static–adaptive revenue gap

  • The adaptivity gap compares optimal adaptive revenue with the worst-case static revenue across n-alternative instances with positive surplus.Adaptive fees may respond to public inspection history under a rule announced before search.Source: §5 · p. 12

5.1 A uniform-price revenue bound

  • The worst-case adaptivity gap is at most 1 + ln n, and G_n/ln n approaches 1 as n grows.The analysis bounds revenue through aggregate demand: information surplus is the area under the demand curve, while uniform-fee revenue is a rectangle beneath it.Source: §5 · p. 12, §5.1 · p. 13

5.2 Full extraction with a single initial payment

  • Charging Δ for the first report and making later reports free lets a committed adaptive seller extract the full information surplus.The buyer can inspect all remaining reports at no further cost and choose the highest revealed value; the initial fee leaves utility equal to the blind payoff.Source: §5.2 · pp. 13–14

5.3 A matching exponential instance

  • As n grows, optimal static revenue approaches 1 while adaptive revenue grows as H_n − 1 under mean-one exponential priors, yielding a tight logarithmic gap.The lower and upper bounds on G_n/ln n both approach 1.Source: Figure 2 · p. 13, §5.3 · p. 14

6 Discussion and conclusion

The paper combines static-pricing guarantees with a tight logarithmic comparison to adaptive revenue and full surplus extraction under a committed access fee. It also identifies unresolved approximation questions and bounds revenue by the information surplus.

6 Discussion and conclusion

  • For identical priors, a common fee maximizes static revenue; for heterogeneous binary priors, exact optimization is NP-hard, while a polynomial-time algorithm gives a 3-approximation to information surplus.For general priors, uniform pricing gives a tight logarithmic approximation to optimal adaptive revenue, and a committed access fee followed by free reports extracts the full surplus.Source: §6 · p. 14
  • Whether static prices can capture more than one third of surplus for binary priors remains open, as do stronger approximation guarantees for heterogeneous priors.For general heterogeneous finite-support priors, even a constant-factor approximation to optimal static revenue is unknown; correlated values and partial disclosure are also unaddressed extensions.Source: §6 · p. 14

A.1 The information-surplus bound

  • Any voluntary-payment mechanism that lets the buyer stop initially for μ* has expected revenue at most Δ.The bound follows because expected selected value is at most M and voluntary participation gives the buyer utility of at least μ*.Source: §A.1 · p. 19

A.2 Individual information caps

  • A report priced above its individual information cap c_i is not worth inspecting, so lowering such a fee to c_i cannot reduce revenue.The buyer can replace inspection with a no-inspection continuation; backward induction preserves utility and the original optimal policy remains feasible.Source: §A.2 · p. 19

B.1 Proof of the exact revenue formula

The appendix derives the exact revenue expression by characterizing when reports are reached and purchased as search unfolds. It also establishes that an optimal uniform price is attained.

B.1 Proof of the exact revenue formula

  • The last report’s value after best inspected value b is w(b) = E[max{b, X}] − max{b, μ}.Its maximum is w(μ) = c.Source: §B.1 · p. 19
  • With at least two alternatives remaining, the cheapest remaining report is weakly worth inspecting when b ≤ μ.Inspecting it and retaining one alternative blind yields utility μ + c − p ≥ μ.Source: §B.1 · p. 19
  • When b ≥ μ, inspecting the cheapest remaining report is worthwhile exactly when b ≤ g(p).The utility improvement from inspection and stopping is E[(X − b)+] − p; equality can still generate revenue under seller-favorable tie-breaking.Source: §B.1 · p. 20
  • If b > g(p), the observed value dominates blind choices and stopping is strictly optimal.The expected gain from any positive-probability inspection is less than its price.Source: §B.1 · p. 20
  • Among the first n − 1 reports, report j is reached exactly when all earlier realized values are at most g(p_j), an event with probability q(p_j)^(j−1).Source: §B.1 · p. 20
  • The final report is inspected exactly when ℓ(p_n) ≤ b ≤ g(p_n), with probability q(p_n)^(n−1) − z(p_n)^(n−1).Summing the resulting payments gives the exact revenue expression.Source: §B.1 · p. 20
  • Zero-priced reports can be inspected first without restricting continuation policies, and they contribute no revenue.If the final report also has zero price, both sides of the revenue expression are zero.Source: §B.1 · p. 20

B.2 Attainment of the optimal uniform price

  • The uniform-price revenue expression is upper semicontinuous on (0, c] and tends to zero at p = 0, so it attains a maximum on [0, c].Source: §B.2 · p. 20

C Proofs for binary priors

This passage only states that the section uses notation defined in Section 4.

C Proofs for binary priors

C.1 Hardness of exact static pricing

The appendix proves exact static pricing hard through a product-partition reduction, then develops bounds used to analyze binary reports and search with a permanent fallback.

C.1 Hardness of exact static pricing

  • For a fee vector using the mandatory-search branch, revenue is bounded by ∆−a(u+v−2Q), and a constructed cap vector attains this bound for each subset.The construction sets caps by whether alternatives lie in S or its complement.Source: §C.1 · p. 21
  • Exact static pricing is value- and threshold-hard via a reduction from product partition, with binary-prior instances encoding the source problem.An exact optimal fee vector can also be used to recover a balanced subset.Source: §C.1 · pp. 20–22

C.2 The shape of a binary report’s value

  • A binary report's value curve is piecewise linear, with every segment having slope at most 1−θ_i.The stated formula also covers coincident endpoints.Source: §C.2 · p. 22

C.3 A capped-value bound for a permanent reserve

  • With a permanent fallback b and only inspected alternatives selectable against it, search utility is bounded by the expected maximum of b and the alternatives' capped values.For caps g_i, the capped value for alternative i is min(X_i, g_i).Source: §C.3 · p. 22

C.4 Three static constructions

Three static constructions give revenue guarantees by keeping a highest-mean alternative blind, charging for the highest-mean report first, or making the second-highest-mean report free.

C.4 Three static constructions

  • Keeping the highest-mean alternative blind and pricing other reports at their expected excess over its mean earns at least B.The blind alternative supplies a permanent reserve, and the resulting selected value is max{m,Y}.Source: §C.4 · p. 22
  • When t≤s, making report 1 free and pricing the others at their expected excess over s earns at least A; when t>s, the second vector earns at least C.For t≤s, the guarantee follows on the event that report 1 realizes s; for t>s, the construction uses a blind reserve t and continuation revenue from the remaining reports.Source: §C.4 · pp. 22–23
  • Making the second-highest-mean report free, charging the first report v1(h2), and excluding later reports earns at least D=θ2v1(h2).The construction's stated revenue guarantee is the probability-weighted value of report 1 at h2.Source: §C.4 · p. 23

D Proof of the revenue gap

A demand-integral argument lower-bounds common-fee revenue by a logarithmic share of information surplus, while charging the full surplus for the first adaptive purchase extracts optimal adaptive revenue.

D.1 The demand-integral bound

  • For n≥2, optimal common-fee revenue is at least ∆/(1+ln n).The proof relates inspection demand under fee t to the derivative of buyer utility and integrates demand over fees.Source: §D.1 · p. 23

D.2 Extraction through the first purchase

  • Charging ∆ for the first report and making subsequent reports free yields adaptive revenue ∆, matching the upper bound.Complete inspection after the first purchase leaves utility equal to the blind payoff; discounting the first fee slightly makes every optimal response purchase.Source: §D.2 · p. 24

D.3 The exponential lower bound

The proof bounds adaptive revenue relative to static revenue by a logarithmic factor and shows that this factor is asymptotically tight for independent exponential values.

D.3 The exponential lower bound

  • The cited result states OPTdyn = ∆ and OPTst ≥ OPTunif ≥ ∆/(1 + ln n), yielding an adaptive-to-static revenue ratio of at most 1 + ln n.Source: §D.3 · p. 24
  • For independent Exp(1) values, OPTst=1−(1−e^-1)^(n−1) and OPTdyn=Hn−1, yielding a logarithmic revenue gap asymptotically.The static optimum occurs at p=e^-1, while Hn/ln n tends to 1.Source: §D.3 · p. 24
Loading 2610.34369v1…