Rationalizing collective revealed preferences with an application in fair resource allocation

Chuwen Zhang; Yinyu Ye; Zhiyun Guo; Zizhuo Wang

arxiv: 2606.23985 · v1 · pith:5H6SPFLCnew · submitted 2026-06-22 · 💻 cs.GT · math.OC

Rationalizing collective revealed preferences with an application in fair resource allocation

Chuwen Zhang , Zhiyun Guo , Zizhuo Wang , Yinyu Ye This is my paper

Pith reviewed 2026-06-26 05:44 UTC · model grok-4.3

classification 💻 cs.GT math.OC

keywords revealed preferencecollective consumptionrationalizationfair resource allocationempirical risk minimizationgeneralization boundsprivacy preservationsurrogate market

0 comments

The pith

The Constructive Rationalization Method rationalizes collective revealed preferences by building a surrogate market of artificial consumers that matches aggregate demand.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper introduces the Constructive Rationalization Method (CRM) to rationalize collective consumption behavior from observed aggregate demand data alone. CRM constructs a surrogate market by adding artificial consumers, called androids, with easy-to-compute demand functions on the fly while redistributing wealth according to empirical risk minimization. The method supplies generalization risk guarantees for learning the aggregate demand function and preserves the privacy of the underlying real consumers. As an application, CRM approximates proportionally fair allocations without requiring knowledge of individual utility functions.

Core claim

By approximating the real market with a surrogate market consisting of artificial consumers (androids) with computable demand functions, added on the fly while redistributing wealth under empirical risk minimization, the Constructive Rationalization Method (CRM) rationalizes collective revealed preferences and provides guarantees on the generalization risk for learning the aggregate demand function.

What carries the argument

The Constructive Rationalization Method (CRM), which builds a surrogate market by adding artificial consumers (androids) on the fly under empirical risk minimization to match observed aggregate demand.

If this is right

Reliable predictions of collective consumption behavior become possible from aggregate observations.
Proportionally fair resource allocations can be approximated without access to individual utilities.
Generalization risk bounds apply to the learned aggregate demand function.
Privacy of the original consumers is maintained throughout the rationalization process.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The on-the-fly addition of androids could extend to sequential or dynamic settings where demand evolves over time.
Similar surrogate constructions might apply to other multi-agent revealed-preference problems that supply only aggregate data.
Testing the method on real market datasets would reveal whether the approximation error remains small enough to preserve fairness guarantees in practice.

Load-bearing premise

That a surrogate market formed by adding artificial consumers under empirical risk minimization can faithfully approximate the real collective demand without introducing bias that invalidates the generalization bounds or fairness properties.

What would settle it

A controlled experiment in which the CRM-derived proportionally fair allocation deviates substantially from the allocation computed directly from known individual utilities in the same market setting.

Figures

Figures reproduced from arXiv: 2606.23985 by Chuwen Zhang, Yinyu Ye, Zhiyun Guo, Zizhuo Wang.

**Figure 1.** Figure 1: Expenditure share of Example 2. Four different random mixtures of CES agents are presented for comparison. Example 2 (A homothetic “oscillating” agent). Let 𝑟𝑥 (𝜏) := exp −𝜏 + 2 sin( 𝜏 2 ) . Then it can be rationalized by the utility 𝑢(𝑥1, 𝑥2) := 𝑥2𝜙 𝑥1 𝑥2 , where log 𝜙(𝜌) := ∫ 𝜌 1 d𝑠 𝑠 + exp(−𝑟 −1 𝑥 (𝑠)) < ∞. (80) Furthermore, it holds that (1) 𝑢 is homogeneous of degree one, increasing, and concave… view at source ↗

read the original abstract

This paper presents a revealed preference approach for rationalizing collective consumption behavior. We introduce the Constructive Rationalization Method (CRM), which approximates the real market via a surrogate market of artificial consumers, called androids, with easy-to-compute demand functions. CRM uses observed aggregate demand and adds artificial consumers on the fly, while redistributing wealth under an empirical risk minimization principle. Unlike classical revealed preference approaches, CRM provides guarantees on the generalization risk for learning the aggregate demand function, while respecting the privacy of the underlying consumers in the real market. As an application, CRM can be used to provide reliable predictions for collective consumption behavior. Specifically, we show how to apply CRM to approximate allocations that are proportionally fair without requiring the knowledge of individual utilities.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

CRM gives a constructive way to rationalize collective demand with androids under ERM and claims generalization plus privacy, but the approximation error between surrogate and real aggregate needs explicit bounds or the guarantees do not transfer.

read the letter

The main point on this paper is that it introduces the Constructive Rationalization Method (CRM), which builds a surrogate market by adding artificial consumers (androids) on the fly while redistributing wealth via empirical risk minimization. This is meant to rationalize observed aggregate demand, deliver generalization risk bounds for learning that demand, keep individual data private, and then use the same construction to approximate proportionally fair allocations without knowing individual utilities.

What the work does is move revealed preference rationalization from mostly existence results toward something algorithmic and predictive. The privacy angle and the direct link to fair allocation are practical additions that classical approaches often lack.

The soft spot is the approximation step itself. The stress-test note flags that if the error between the android surrogate and the true collective demand is not controlled independently of the number of androids or the function class, then both the generalization bounds and the fairness approximation fail to carry over. The abstract states the claims but does not display the derivations or error controls, so it is not possible to tell whether the paper actually closes this gap or treats the surrogate as sufficiently close by construction.

This is aimed at researchers working on revealed preference, collective choice, and fair division mechanisms. Someone looking for computational methods that stay within the revealed-preference framework would find the construction useful if the bounds are solid.

It deserves a serious referee because the method is distinct from the classical literature cited and the application is concrete, even though the central approximation issue will need checking in review.

Referee Report

2 major / 0 minor

Summary. The paper introduces the Constructive Rationalization Method (CRM) for rationalizing collective revealed preferences. CRM approximates the observed aggregate demand by constructing a surrogate market of artificial consumers ('androids') whose demand functions are easy to compute; androids are added on the fly while wealth is redistributed according to an empirical risk minimization principle. The central claims are that this construction yields generalization-risk bounds for learning the aggregate demand function, respects consumer privacy, and can be used to approximate proportionally fair allocations without knowledge of individual utilities.

Significance. If the approximation error between the android-augmented surrogate demand and the true collective demand is rigorously bounded independently of the number of androids, and if the resulting generalization bounds are non-vacuous, the method would supply a privacy-preserving route from observed aggregates to both predictive guarantees and fairness approximations in resource allocation. No machine-checked proofs, reproducible code, or parameter-free derivations are referenced in the abstract.

major comments (2)

[Abstract] Abstract: the claim that CRM 'provides guarantees on the generalization risk for learning the aggregate demand function' is load-bearing for both the predictive and fairness applications, yet the abstract supplies no derivation, no explicit bound on the approximation error between the ERM-redistributed android surrogate and the observed aggregate demand, and no statement that this error is controlled independently of the number of androids or the demand class. Without such control the claimed transfer of generalization bounds to the true collective behavior does not follow.
[Abstract] Abstract: the downstream claim that CRM 'can be used to approximate allocations that are proportionally fair without requiring the knowledge of individual utilities' inherits the same gap; if the surrogate demand deviates from the true aggregate by an uncontrolled amount, the fairness approximation property cannot be guaranteed to hold for the real market.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying the need to strengthen the abstract's presentation of the key claims. We respond to each major comment below.

read point-by-point responses

Referee: [Abstract] Abstract: the claim that CRM 'provides guarantees on the generalization risk for learning the aggregate demand function' is load-bearing for both the predictive and fairness applications, yet the abstract supplies no derivation, no explicit bound on the approximation error between the ERM-redistributed android surrogate and the observed aggregate demand, and no statement that this error is controlled independently of the number of androids or the demand class. Without such control the claimed transfer of generalization bounds to the true collective behavior does not follow.

Authors: The abstract serves as a concise overview; the full derivations, explicit approximation-error bounds, and their independence from the number of androids (via the ERM wealth-redistribution step) appear in the body of the paper. Nevertheless, we agree that the abstract would benefit from a brief clarifying clause on this independence to make the load-bearing claim more transparent on first reading. We will revise the abstract accordingly. revision: yes
Referee: [Abstract] Abstract: the downstream claim that CRM 'can be used to approximate allocations that are proportionally fair without requiring the knowledge of individual utilities' inherits the same gap; if the surrogate demand deviates from the true aggregate by an uncontrolled amount, the fairness approximation property cannot be guaranteed to hold for the real market.

Authors: The fairness guarantee is derived from the same controlled approximation error between surrogate and aggregate demand that is established in the main text. We concur that the abstract should explicitly link the two claims by noting the error bound's independence from the number of androids. A revised abstract will include this clarification. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained against external benchmarks

full rationale

The abstract and reader's assessment describe CRM as constructing a surrogate android market from observed aggregate demand under ERM to derive generalization bounds and fair allocation approximations. No quoted equations or steps show a prediction reducing by construction to a fitted input, self-definition of key quantities, or load-bearing self-citation chains. The central claims rest on the surrogate construction and ERM principle providing independent approximation and risk guarantees, which are presented as externally verifiable rather than tautological. This matches the default expectation of no circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The approach rests on the domain assumption that a surrogate market of artificial consumers can approximate real collective behavior with generalization guarantees. No explicit free parameters or invented entities beyond the androids are stated in the abstract.

axioms (1)

domain assumption A surrogate market of artificial consumers (androids) can approximate real collective demand under empirical risk minimization
Invoked as the foundation for both the rationalization procedure and the generalization guarantees.

invented entities (1)

androids (artificial consumers) no independent evidence
purpose: Form a surrogate market with easy-to-compute demand functions that rationalizes observed aggregate demand
New entities introduced to enable the constructive rationalization while preserving privacy.

pith-pipeline@v0.9.1-grok · 5659 in / 1221 out tokens · 31317 ms · 2026-06-26T05:44:15.603945+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

15 extracted references · 4 canonical work pages · 2 internal anchors

[1]

Learning Economic Parameters from Revealed Preferences

URLhttp://arxiv.org/abs/1407.7937. Peter Bartlett, Yoav Freund, Wee Sun Lee, and Robert E. Schapire. Boosting the margin: a new explanation for the effectiveness of voting methods.The Annals of Statistics, 26(5):1651–1686,

work page internal anchor Pith review Pith/arXiv arXiv
[2]

DynamicsofdistributedupdatinginFishermarkets

YunKuenCheung,RichardCole,andYixinTao. DynamicsofdistributedupdatinginFishermarkets. InProceedings ofthe2018ACMConferenceonEconomicsandComputation,EC’18,pages351–368,NewYork,NY,USA,2018. Association for Computing Machinery. Yun Kuen Cheung, Richard Cole, and Nikhil R. Devanur. Tatonnement beyond gross substitutes? Gradient descent to the rescue.Games and ...

2018
[3]

Federico Echenique, Sangmok Lee, and Matthew Shum

URLhttps://web.stanford.edu/ class/cs229t/2017/homework.html. Federico Echenique, Sangmok Lee, and Matthew Shum. The money pump as a measure of revealed preference violations.Journal of Political Economy, 119(6):1201–1223,

2017
[4]

Regulation (EU) 2016/679 of the European Parliament and of the Council.Official Journal of the European Union,

EU. Regulation (EU) 2016/679 of the European Parliament and of the Council.Official Journal of the European Union,

2016
[5]

URLhttp://arxiv.org/abs/2208.14314. J. D. Geanakoplos and H. M. Polemarchakis. On the disaggregation of excess demand functions.Econometrica, 48 (2):315–331,

work page arXiv
[6]

Efficiently Learning from Revealed Preference

URLhttp:// arxiv.org/abs/1211.4150. Chuwen Zhang, Chang He, Bo Jiang, and Yinyu Ye. The second-order tâtonnement: decentralized interior-point methods for market equilibrium,

work page internal anchor Pith review Pith/arXiv arXiv
[7]

URLhttp://arxiv.org/abs/2508.04822. 19 Appendix A Derivation of demand functions and the expenditure shares.......................................................................................20 A.1 CES consumer..........................................................................................................................20 A.2 Leontief consum...

work page arXiv 1995
[8]

sup γ∈ℋ 𝐾 ∑ 𝑘=1 𝜀𝑘Φ𝑘 (γ(ω𝑘)) # ≤ √ 2𝑀0 𝐾 𝔼ξ

Fact 6.For anyc∈ℝ 𝑛 >0, set the reparameterizationy=log(c) ∈ℝ 𝑛. Then the expenditure share of a linear consumer at pricepisγ(p)=e 𝑗∗ where𝑗 ∗ ∈arg max 𝑗∈ [𝑛] {𝑦 𝑗 −log𝑝 𝑗 }. Strictly speaking, there could be multiple𝑗∗ for a givenp. We force the concentration of expenditure, which means to select one𝑗∗ by a tie-breaking rule. Similar to the CES case,ℋLin...

1995
[9]

This completes the proof

Thus, ∥softmax(x ′) −softmax(x) ∥ 2 = ∫ 1 0 ∇softmax(x+𝑡(x ′ −x)) (x ′ −x)d𝑡 ≤ ∫ 1 0 ∥∇softmax(x+𝑡(x ′ −x)) ∥ ∥x′ −x∥d𝑡= 1 2 ∥x−x ′ ∥2. This completes the proof. ■ We will need the following comparison lemma for Rademacher and Gaussian averages. Lemma C.5(Comparison lemma).Letξ∈ {±1}𝑛 be a Rademacher vector with i.i.d. coordinates andζ∼N(0,I𝑛) a standard ...

1991
[10]

Writing the Rademacher vectors intoξ:=[ξ1;· · ·;ξ𝐾 ] ∈ {±1} 𝑛𝐾, we can associate each labelingJ∈ Jwith the vector e(J):=[e 𝑗1;· · ·;e 𝑗𝐾 ] ∈ℝ 𝑛𝐾 ,∥e(J) ∥ 2 = √ 𝐾

(see, also Matousek [2002, 6.1.1]), we can bound the number of possible regions generated by these hyperplanes, since there are at most 𝑛 2 𝐾of them in all: |J | ≤ 𝑛 ∑ 𝑖=0 𝑛 2 𝐾 𝑖 ≤ 𝑒𝑛 2 𝐾 𝑛 ! 𝑛 = 𝑒𝑛 2 𝐾 𝑛 ! 𝑛 = 𝑒(𝑛−1)𝐾 2 𝑛 ,(43) where the second inequality is due to Shalev-Shwartz and Ben-David [2014, Lemma A.5]. Writing the Rademacher vectors intoξ:=[ξ1...

2002
[11]

It is not strongly NP-hard, and there is an FPTAS provided in Depetrini and Locatelli

(2)If𝐾≥2, LFP is NP-hard [Matsui, 1996, Freund and Jarre, 2001] due to the reduction from set partitioning problem. It is not strongly NP-hard, and there is an FPTAS provided in Depetrini and Locatelli

1996
[12]

For𝐾≥2and𝜎≠0, we establish NP-hardness by reducing LFP to SEP, i.e., by inverting the map of Lemma D.1

For𝐾≥2and𝜎=0, the expenditure sharesoftmax(y)is independent of the price, so SEP is the Cobb-Douglas problem treated above, which is globally solvable in polynomial time. For𝐾≥2and𝜎≠0, we establish NP-hardness by reducing LFP to SEP, i.e., by inverting the map of Lemma D.1. Given an instance of LFP with coefficientsθ𝑘,f 𝑘 ∈ℝ 𝑛 + and feasible boxQ, set p𝑘 ...

2011
[13]

AppLFMP”, that returnsa“relatively

considers the linear fractional minimization problem (we are solving a maximization problem). They provided a FPTAS, called “AppLFMP”, that returnsa“relatively”approximateoptimalsolutioniftheproblemdataisintegral. TouseAppLFMPhere,weneedto justify that the methods finds an approximate optimal solution measured inabsolute errorforreal-valued data. We first...

2011
[14]

Then, there exists𝜎′ ∗ ∈Σ ℎ with|𝜎 ∗ −𝜎 ′ ∗| ≤ℎ; this𝜎 ′ ∗ need not equalˆ𝜎

By Corollary D.1, in˜O (𝜖−𝐾 )operations, 𝜋( ˜y(𝜎 ′), 𝜎 ′) ≥𝜋 ∗(𝜎 ′) − 𝜖 2 .(76) Let(y ∗, 𝜎∗)be a joint maximizer. Then, there exists𝜎′ ∗ ∈Σ ℎ with|𝜎 ∗ −𝜎 ′ ∗| ≤ℎ; this𝜎 ′ ∗ need not equalˆ𝜎. So we 36 have, 𝜋( ˆy,ˆ𝜎) ≥𝜋( ˜y(𝜎 ′ ∗), 𝜎 ′ ∗) ≥ (76) 𝜋∗(𝜎 ′ ∗) − 𝜖 2 ≥ (75) 𝜋∗(𝜎 ∗) − 𝐾 𝐷p 2 ℎ− 𝜖 2 =𝜋(y ∗, 𝜎∗) −𝜖 . The total cost is|Σℎ| · ˜O (𝜖−𝐾 )= ˜O (𝜖− (𝐾+1) ...

2015
[15]

=−𝜎(𝜏),1+𝜎(𝜏) ≥0, where the logistic factor uses𝛾1 =ℓ(log𝑟 𝛾). For a function𝑓:I ↦→ℝon an intervalI ⊆ℝ, letTV I (𝑓)be the total variation of𝑓onI, defined as the supremum of the sum of the absolute differences of the function over all possible partitions of the interval. Namely, for a finite subset𝑆𝑚 ={𝜏 0,· · ·, 𝜏𝑚} ⊆ Iwith𝜏 0 <· · ·< 𝜏 𝑚 ∈ I, TVI (𝑓)=sup...

1999

[1] [1]

Learning Economic Parameters from Revealed Preferences

URLhttp://arxiv.org/abs/1407.7937. Peter Bartlett, Yoav Freund, Wee Sun Lee, and Robert E. Schapire. Boosting the margin: a new explanation for the effectiveness of voting methods.The Annals of Statistics, 26(5):1651–1686,

work page internal anchor Pith review Pith/arXiv arXiv

[2] [2]

DynamicsofdistributedupdatinginFishermarkets

YunKuenCheung,RichardCole,andYixinTao. DynamicsofdistributedupdatinginFishermarkets. InProceedings ofthe2018ACMConferenceonEconomicsandComputation,EC’18,pages351–368,NewYork,NY,USA,2018. Association for Computing Machinery. Yun Kuen Cheung, Richard Cole, and Nikhil R. Devanur. Tatonnement beyond gross substitutes? Gradient descent to the rescue.Games and ...

2018

[3] [3]

Federico Echenique, Sangmok Lee, and Matthew Shum

URLhttps://web.stanford.edu/ class/cs229t/2017/homework.html. Federico Echenique, Sangmok Lee, and Matthew Shum. The money pump as a measure of revealed preference violations.Journal of Political Economy, 119(6):1201–1223,

2017

[4] [4]

Regulation (EU) 2016/679 of the European Parliament and of the Council.Official Journal of the European Union,

EU. Regulation (EU) 2016/679 of the European Parliament and of the Council.Official Journal of the European Union,

2016

[5] [5]

URLhttp://arxiv.org/abs/2208.14314. J. D. Geanakoplos and H. M. Polemarchakis. On the disaggregation of excess demand functions.Econometrica, 48 (2):315–331,

work page arXiv

[6] [6]

Efficiently Learning from Revealed Preference

URLhttp:// arxiv.org/abs/1211.4150. Chuwen Zhang, Chang He, Bo Jiang, and Yinyu Ye. The second-order tâtonnement: decentralized interior-point methods for market equilibrium,

work page internal anchor Pith review Pith/arXiv arXiv

[7] [7]

URLhttp://arxiv.org/abs/2508.04822. 19 Appendix A Derivation of demand functions and the expenditure shares.......................................................................................20 A.1 CES consumer..........................................................................................................................20 A.2 Leontief consum...

work page arXiv 1995

[8] [8]

sup γ∈ℋ 𝐾 ∑ 𝑘=1 𝜀𝑘Φ𝑘 (γ(ω𝑘)) # ≤ √ 2𝑀0 𝐾 𝔼ξ

Fact 6.For anyc∈ℝ 𝑛 >0, set the reparameterizationy=log(c) ∈ℝ 𝑛. Then the expenditure share of a linear consumer at pricepisγ(p)=e 𝑗∗ where𝑗 ∗ ∈arg max 𝑗∈ [𝑛] {𝑦 𝑗 −log𝑝 𝑗 }. Strictly speaking, there could be multiple𝑗∗ for a givenp. We force the concentration of expenditure, which means to select one𝑗∗ by a tie-breaking rule. Similar to the CES case,ℋLin...

1995

[9] [9]

This completes the proof

Thus, ∥softmax(x ′) −softmax(x) ∥ 2 = ∫ 1 0 ∇softmax(x+𝑡(x ′ −x)) (x ′ −x)d𝑡 ≤ ∫ 1 0 ∥∇softmax(x+𝑡(x ′ −x)) ∥ ∥x′ −x∥d𝑡= 1 2 ∥x−x ′ ∥2. This completes the proof. ■ We will need the following comparison lemma for Rademacher and Gaussian averages. Lemma C.5(Comparison lemma).Letξ∈ {±1}𝑛 be a Rademacher vector with i.i.d. coordinates andζ∼N(0,I𝑛) a standard ...

1991

[10] [10]

Writing the Rademacher vectors intoξ:=[ξ1;· · ·;ξ𝐾 ] ∈ {±1} 𝑛𝐾, we can associate each labelingJ∈ Jwith the vector e(J):=[e 𝑗1;· · ·;e 𝑗𝐾 ] ∈ℝ 𝑛𝐾 ,∥e(J) ∥ 2 = √ 𝐾

(see, also Matousek [2002, 6.1.1]), we can bound the number of possible regions generated by these hyperplanes, since there are at most 𝑛 2 𝐾of them in all: |J | ≤ 𝑛 ∑ 𝑖=0 𝑛 2 𝐾 𝑖 ≤ 𝑒𝑛 2 𝐾 𝑛 ! 𝑛 = 𝑒𝑛 2 𝐾 𝑛 ! 𝑛 = 𝑒(𝑛−1)𝐾 2 𝑛 ,(43) where the second inequality is due to Shalev-Shwartz and Ben-David [2014, Lemma A.5]. Writing the Rademacher vectors intoξ:=[ξ1...

2002

[11] [11]

It is not strongly NP-hard, and there is an FPTAS provided in Depetrini and Locatelli

(2)If𝐾≥2, LFP is NP-hard [Matsui, 1996, Freund and Jarre, 2001] due to the reduction from set partitioning problem. It is not strongly NP-hard, and there is an FPTAS provided in Depetrini and Locatelli

1996

[12] [12]

For𝐾≥2and𝜎≠0, we establish NP-hardness by reducing LFP to SEP, i.e., by inverting the map of Lemma D.1

For𝐾≥2and𝜎=0, the expenditure sharesoftmax(y)is independent of the price, so SEP is the Cobb-Douglas problem treated above, which is globally solvable in polynomial time. For𝐾≥2and𝜎≠0, we establish NP-hardness by reducing LFP to SEP, i.e., by inverting the map of Lemma D.1. Given an instance of LFP with coefficientsθ𝑘,f 𝑘 ∈ℝ 𝑛 + and feasible boxQ, set p𝑘 ...

2011

[13] [13]

AppLFMP”, that returnsa“relatively

considers the linear fractional minimization problem (we are solving a maximization problem). They provided a FPTAS, called “AppLFMP”, that returnsa“relatively”approximateoptimalsolutioniftheproblemdataisintegral. TouseAppLFMPhere,weneedto justify that the methods finds an approximate optimal solution measured inabsolute errorforreal-valued data. We first...

2011

[14] [14]

Then, there exists𝜎′ ∗ ∈Σ ℎ with|𝜎 ∗ −𝜎 ′ ∗| ≤ℎ; this𝜎 ′ ∗ need not equalˆ𝜎

By Corollary D.1, in˜O (𝜖−𝐾 )operations, 𝜋( ˜y(𝜎 ′), 𝜎 ′) ≥𝜋 ∗(𝜎 ′) − 𝜖 2 .(76) Let(y ∗, 𝜎∗)be a joint maximizer. Then, there exists𝜎′ ∗ ∈Σ ℎ with|𝜎 ∗ −𝜎 ′ ∗| ≤ℎ; this𝜎 ′ ∗ need not equalˆ𝜎. So we 36 have, 𝜋( ˆy,ˆ𝜎) ≥𝜋( ˜y(𝜎 ′ ∗), 𝜎 ′ ∗) ≥ (76) 𝜋∗(𝜎 ′ ∗) − 𝜖 2 ≥ (75) 𝜋∗(𝜎 ∗) − 𝐾 𝐷p 2 ℎ− 𝜖 2 =𝜋(y ∗, 𝜎∗) −𝜖 . The total cost is|Σℎ| · ˜O (𝜖−𝐾 )= ˜O (𝜖− (𝐾+1) ...

2015

[15] [15]

=−𝜎(𝜏),1+𝜎(𝜏) ≥0, where the logistic factor uses𝛾1 =ℓ(log𝑟 𝛾). For a function𝑓:I ↦→ℝon an intervalI ⊆ℝ, letTV I (𝑓)be the total variation of𝑓onI, defined as the supremum of the sum of the absolute differences of the function over all possible partitions of the interval. Namely, for a finite subset𝑆𝑚 ={𝜏 0,· · ·, 𝜏𝑚} ⊆ Iwith𝜏 0 <· · ·< 𝜏 𝑚 ∈ I, TVI (𝑓)=sup...

1999