論文の概要、ライセンス

# (参考訳) 移動目標に対する価格への学習 [全文訳有]

Learning to Price Against a Moving Target ( http://arxiv.org/abs/2106.04689v1 )

ライセンス: CC BY 4.0
Renato Paes Leme, Balasubramanian Sivan, Yifeng Teng, Pratik Worah(参考訳) 価格設定の学習において、売り手は、買い手のバリュエーションを学習しながら収益を最大化することを目的として、時間とともに価格を投稿する。 この問題は固定値(固定値またはiid)であるときに非常によく理解される。 ここでは、購入者の値が移動対象である場合、すなわち、確率過程によって、あるいは有界変動に逆らって、時間とともに変化する問題について検討する。 いずれの場合も、最適収益損失の上限は上下に一致します。 ターゲットが移動しているため、学習した情報はすぐに時代遅れになり、探索段階と悪用段階の間をアルゴリズムが切り替え続けることになる。

In the Learning to Price setting, a seller posts prices over time with the goal of maximizing revenue while learning the buyer's valuation. This problem is very well understood when values are stationary (fixed or iid). Here we study the problem where the buyer's value is a moving target, i.e., they change over time either by a stochastic process or adversarially with bounded variation. In either case, we provide matching upper and lower bounds on the optimal revenue loss. Since the target is moving, any information learned soon becomes out-dated, which forces the algorithms to keep switching between exploring and exploiting phases.
公開日: Tue, 8 Jun 2021 20:57:11 GMT

※ 翻訳結果を表に示しています。PDFがオリジナルの論文です。翻訳結果のライセンスはCC BY-SA 4.0です。詳細はトップページをご参照ください。

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
1 2 0 2 n u J 1 2 0 2 n u J 0.85
8 ] T G . s c [ 8 ]tg。 sc [ 0.60
1 v 9 8 6 4 0 1 v 9 8 6 4 0 0.85
. 6 0 1 2 : v i X r a . 6 0 1 2 : v i X r a 0.85
Learning to Price Against a Moving Target 移動目標に対する価格への学習 0.80
Renato Paes Leme Google Research Renato Paes Leme Google Research 0.85
Balasubramanian Sivan Balasubramanian属 0.58
Google Research Google Research 0.85
Yifeng Teng UW-Madison Yifeng (複数形 Yifengs) 0.36
renatoppl@google.com renatoppl@google.com 0.78
balusivan@google.com balusivan@google.com 0.78
yifengt@cs.wisc.edu yifengt@cs.wisc.edu 0.59
Pratik Worah Pratik Wáh 0.70
Google Research Google Research 0.85
pworah@google.com pworah@google.com 0.78
Abstract In the Learning to Price setting, a seller posts prices over time with the goal of maximizing revenue while learning the buyer’s valuation. 概要 Learning to Priceの設定では、売り手は買い手の評価額を学習しながら収益を最大化する目的で、時間とともに価格を公表する。 0.59
This problem is very well understood when values are stationary (fixed or iid). この問題は固定値(固定値またはiid)であるときに非常によく理解される。 0.67
Here we study the problem where the buyer’s value is a moving target, i.e., they change over time either by a stochastic process or adversarially with bounded variation. ここでは、購入者の値が移動対象である場合、すなわち、確率的プロセスによって時間とともに変化するか、境界変動に逆らうかという問題を考察する。 0.66
In either case, we provide matching upper and lower bounds on the optimal revenue loss. いずれの場合も、最適収益損失の上限は上下に一致します。 0.58
Since the target is moving, any information learned soon becomes out-dated, which forces the algorithms to keep switching between exploring and exploiting phases. ターゲットが移動しているため、学習した情報はすぐに時代遅れになり、探索段階と悪用段階の間をアルゴリズムが切り替え続けることになる。 0.64
1 Introduction Inspired by applications in electronic commerce, we study a problem where a seller repeatedly interacts with a buyer by setting prices for an item and observing whether the buyer purchases or not. 1 はじめに 電子商取引の応用に触発されて、売り手が商品の価格を設定し、買い手が購入するかどうかを観察することで、買い手と繰り返し対話する問題を研究する。 0.68
These problems are characterized by two salient features: (i) binary feedback: we only observe if the buyer purchased or not, at the price we posted; (ii) discontinuous loss function: pricing just below the buyer’s valuation incurs a small loss while pricing just above it incurs a large loss since it results in a no-sale. i) バイナリフィードバック: 掲載した価格で買い手が購入したかどうかのみ観察する(ii) 不連続損失関数: 買い手のバリュエーションのすぐ下の価格が小さな損失を伴いますが、価格のすぐ上には売り切れになるため大きな損失が発生します。
訳抜け防止モード: これらの問題は2つの有能な特徴によって特徴づけられる: (i)バイナリフィードバック 買い手が購入したかどうかだけを 掲載した価格で観察します ; (ii)不連続損失関数 : 買い手の評価額の直ぐ下にある価格は、わずかな損失をもたらす。 その上の価格で no- saleの結果、大きな損失が発生します。
0.79
This problem has been studied with many different assumptions on how the buyer valuation vt changes over time: fixed over time and i.i.d. この問題は、バイヤーのバリュエーションvtが時間とともにどのように変化するかについて多くの異なる仮定で研究されてきた。 0.57
draws each round were studied in [13, 7, 3], deterministic contextual [1, 5, 17, 15, 16], contextual with parametric noise [11] and contextual with non-parametric noise [22, 14]. 13, 7, 3],決定論的文脈[1, 5, 17, 15 16],パラメトリックノイズ[11],非パラメトリックノイズ[22, 14]における各ラウンドのドローについて検討した。 0.69
All those models are stationary in the sense that the buyer’s model is i.i.d. これらのモデルはすべて、購入者のモデルがi.i.dであるという意味で静止している。 0.60
across time. The exceptions to this are algorithms that consider valuations that are drawn adversarially [13], but that work still compares with the best single price in hindsight. 時間をかけて 例外は、[13]に逆らって描画されるバリュエーションを考慮するアルゴリズムだが、それでもその処理は、後向きの最高の単価と比較される。
訳抜け防止モード: 時間をかけて 例外は、逆向きに描画される評価を考慮に入れたアルゴリズムです [13 ]。 しかしその仕事は 後から見て 最高の単価と 比べられるでしょう
0.70
I.e., even though the buyer model is non-stationary, the benchmark still is. つまり、バイヤーモデルが非定常であるにもかかわらず、ベンチマークは依然として存在する。 0.49
Our main goal in this paper is to explore settings where both the buyer model and the benchmark are non-stationary. この論文の主な目標は、購入者モデルとベンチマークの両方が静止していない設定を検討することです。
訳抜け防止モード: この論文の主な目標は バイヤーモデルとベンチマークの両方が非定常であるような設定を探求する。
0.76
We will compare our revenue with the first-best benchmark, namely, the sum of the buyer’s value at every single step. 当社の収益を、第1位のベンチマーク、すなわち、購入者のすべてのステップでの価値の合計と比較する。 0.67
We will however assume that the buyer’s valuation moves slowly. しかし、バイヤーの評価額はゆっくりと推移していると仮定する。 0.55
Motivation Our main motivation for this study is online advertising. モチベーション この研究の主な動機はオンライン広告です。 0.67
Display ads are mostly sold through first price auctions with reserve prices [20]. ディスプレイ広告は、予約価格[20]で最初の価格オークションを通じて販売される。 0.67
In many market segments, the auctions are thin, i.e., there is just one buyer, who bids just above the reserve when his value exceeds the 多くの市場セグメントでは、オークションは薄い、すなわち1人の買い手しかおらず、その価値が価格を超えると準備額のすぐ上を入札する。 0.69
英語(論文から抽出)日本語訳スコア
reserve (to both pay as little as possible, and not reveal their true value) and doesn’t bid otherwise. reserve(可能な限り少額を支払うため、真の価値を明かさないため)は、別途入札しない。 0.60
This scenario effectively offers just binary feedback, and also makes reserve price the only pricing tool (i.e., not much auction competition). このシナリオは、バイナリフィードバックのみを効果的に提供し、予約価格を唯一の価格ツール(つまり、あまり競売の競争ではない)にする。
訳抜け防止モード: このシナリオはバイナリフィードバックのみを効果的に提供し 予約価格 唯一の価格設定ツール(つまり、あまり競売の競争ではない)。
0.79
To see why buyer value changes are typically slow, and unknown to the seller: the effective value of a buyer, even for two identical queries, is similar but not exactly the same due to factors such as remaining budget. 買い手の価値の変動が一般的に遅く、売り手にとって未知であることを確認するために、買い手の有効値は、2つの同じクエリであっても似ているが、残りの予算などの要因により全く同じではない。 0.65
A common scenario is that a buyer has a spend target stating a target θt of their daily budget to be spent by time t. Bids often become a function of the ratio between the actual spend and the target spend. 一般的なシナリオは、買い手が日々の予算の目標θtを時間によって消費する、という消費目標を持っていることである。
訳抜け防止モード: 一般的なシナリオは、買い手が日々の予算の目標θtを時間tで消費する、という目標を持つことである。 バイドはしばしば、実際の支出と目標支出の比率の関数となる。
0.70
The auction platform doesn’t know the targets/bidding formula, but it can use the fact that both target and actual spend, and hence the bids, will change smoothly over time. オークションプラットフォームは目標/入札の公式を知らないが、ターゲットと実際の支出の両方、つまり入札が時間とともにスムーズに変化するという事実を利用することができる。 0.73
Another important motivation is to effectively price buyers who are learning about their own valuation. もうひとつの重要な動機は、バリュエーションについて学習しているバリュエーションを効果的に価格付けすることだ。 0.47
This is a common setup in finance [23] where traders constantly acquire new information about the products they are trading, and update their valuations accordingly. これは金融[23]において共通の設定であり、トレーダは、取引している商品に関する新しい情報を常に取得し、それに応じてバリュエーションを更新する。 0.55
Our results and techniques are presented in Section 3 after we formally define our model in 私たちの結果とテクニックは、モデルを正式に定義した後に、セクション3で示されます。 0.56
Section 2. Related Work Our work is situated in the intersection of two lines of work in online learning: online learning for pricing (discussed earlier in the introduction) and online learning with stronger benchmarks, such as tracking regret [10, 18], adaptive regret [9], strongly adaptive online learning [6] and shifting bandits [8, 19]. 第2部。 私たちの仕事は、オンライン学習における2行の作業の交点にある: 価格設定のためのオンライン学習(導入に先立って議論されている)と、より強力なベンチマークによるオンライン学習、例えば、後悔の追跡 [10, 18]、適応的後悔[9]、強い適応的オンライン学習 [6]、変化するバンディット [8, 19]。 0.66
The difficulty in applying this line of work to pricing problems is that even when the valuation vt changes slightly, the loss function itself will change dramatically for certain prices. このラインを価格問題に適用することの難しさは、バリュエーション vt がわずかに変化しても、損失関数自体が一定の価格で劇的に変化することである。 0.73
Instead here, we exploit the special structure to the revenue loss to obtain better regret bounds. 代わりに、我々は特別な構造を収益損失に活用し、より良い後悔の限界を得る。 0.67
There is another line of work that studies revenue maximization in the presence of evolving buyer values [12, 21, 4]. 進化する買い手価値[12,21,4]の存在下で、収益の最大化を研究する別の作業がある。 0.66
While all these works consider the cumulative value over time as benchmark, there are important differences, the first two papers have full feedback: they design mechanisms that solicit buyer bids. これらの作業はすべて、時間とともに累積価値をベンチマークとして考えるが、重要な違いがある。最初の2つの論文には完全なフィードバックがある。 0.60
Chawla et al shoot for simple pricing schemes yielding constant factor approximations, while we seek to obtain much closer to the optimal. Chawla et al shoot for simple pricing schemes yields constant factor approximation, while we seek more closer to the optimal。 0.72
Moreover, in their model the values evolve only when the buyer purchases the good. さらに、モデルでは、買い手が良いものを買うときだけ価値が進化する。 0.70
2 Setting General setting. 2 設定 一般的な設定。 0.71
A seller repeatedly interacts with a buyer over T time steps, offering to sell an item at each step. 売り手はTタイムステップで買い手と繰り返し対話し、各ステップでアイテムを販売する。
訳抜け防止モード: 売り手は、Tタイムステップで買い手と繰り返し対話します。 それぞれのステップでアイテムを売ります。
0.64
The buyer’s value is vt ∈ [0, 1] at time step t ∈ [T ], and is changing across time. バイヤーの値は、時刻ステップ t ∈ [T ] における vt ∈ [0, 1] であり、時間とともに変化している。 0.84
The seller has no knowledge of the buyer’s value at any time, not even at t = 1. 売り手は買い手の価値をいつでも知ることができず、t = 1 にもならない。 0.61
At each time step t, the seller posts a price pt ∈ [0, 1] to the buyer, and the buyer purchases the item if and only if she can afford to buy it, i.e. 各ステップtにおいて、売り手は買い手に対して価格pt ∈ [0, 1]を投稿し、買い手は購入する余裕がある場合に限り購入する。
訳抜け防止モード: 各時間に t, 売り手は買い手に対して価格 pt ∈ [ 0, 1 ] を投稿する。 購入者が商品を購入するのは 購入する余裕がある場合に限る
0.60
pt ≤ vt. The binary signal pt ≤ vt。 二進法信号 0.76
σt = 1{vt ≥ pt} ∈ {0, 1} σt = 1{vt ≥ pt} ∈ {0, 1} 0.91
of whether the item is sold or not is the only feedback the seller obtains at each time step. 商品が売れているかどうかが、売り手が各時間ステップで得る唯一のフィードバックである。 0.60
The seller’s objective is to maximize his the total revenue, i.e. 売り手の目的は、収入を最大化することである。 0.46
Rev = PT from the buyer, which is the sum of her value across all time periods: Opt = PT Rev = PT from the buyer, which is the sum of her value across all time periods: Opt = PT 0.85
Loss metrics. The benchmark we are comparing to is the hindsight optimal revenue we can get t=1 vt. 損失メトリクス。 私たちが比較しているベンチマークは、t=1 vtで得られる最適な収益です。 0.62
The revenue t=1 ptσt. 収入は t=1 ptσt。 0.60
2 2 0.85
英語(論文から抽出)日本語訳スコア
loss at any time step t is defined by ℓR(pt, vt) = vt − ptσt, and the revenue loss of any price vector p = (p1,··· , pT ) for value profile v = (v1,··· , vT ) is defined by ステップtにおける損失は lr(pt, vt) = vt − ptσt で定義され、v = (v1,···· , vt ) に対する任意の価格ベクトル p = (p1,···· , pt ) の収益損失は、値プロファイル v = (v1,···· , vt ) で定義される。 0.78
ℓR(p, v) = lR(p, v) = 0.85
1 T (Opt − Rev) = 1T (Opt − Rev) = 0.81
1 T T Xt=1 (vt − ptσt). 1T T Xt=1 (vt − ptσt)。 0.76
The symmetric loss at any time step t is defined by ℓ1(pt, vt) = |vt − pt|, and the total symmetric loss of any price vector p = (p1,··· , pT ) for value profile v = (v1,··· , vT ) is defined by 任意の時間ステップ t における対称損失は l1(pt, vt) = |vt − pt| で定義され、値プロファイル v = (v1,···· , vt ) に対する任意の価格ベクトル p = (p1,···· , pt ) の完全対称損失は定義される。 0.91
ℓ1(p, v) = l1(p, v) = 0.96
1 T T Xt=1 |vt − pt|. 1T T Xt=1 |vt − pt|。 0.75
Intuitively, the revenue loss determines how much revenue we lose compared to a hindsight optimal selling strategy. 直感的には、収益損失は、後から見る最適な販売戦略に比べて、どれだけの収入を失うかを決定する。
訳抜け防止モード: 直感的には 収入損失は どれだけの収入を 後ろ向きの最適な販売戦略に 比較すると負けます
0.69
The symmetric loss determines how close our price guesses are from the correct value vector of the buyer. 対称損失は、購入者の正しい値ベクトルから価格がどれだけ近いかを決定する。 0.78
3 Our Results and Techniques Next we describe our main results in this model. 3 結果と技術 次に、このモデルの主な結果を述べます。 0.68
Our results will be given in terms of the changing rate, which we define as follows: consider a sequence of buyer valuations v1, v2, . 我々の結果は、変化率の観点で与えられ、次のように定義する: 買い手の評価の列を v1, v2, . 0.77
. . , vT and a sequence ǫ1, . . . , vT, シーケンスは 1 である。 0.81
. . , ǫT−1 (all ǫt ≤ 1). . . t ≤ 1 である。 0.69
We say that a sequence of buyer valuations {vt}t=1..T has changing rate {ǫt}t=1..T−1 whenever (1) a sequence of buyer valuations {vt}t=1..T have change rate {\t}t=1..T−1 when (1) 0.93
|vt+1 − vt| ≤ ǫt. |vt+1 − vt| ≤ t である。 0.60
The average changing rate is ¯ǫ = 1 t=1 ǫt. 平均変化率は t = 1 t=1 t である。 0.76
Our guarantees are a function of the average changing rate ¯ǫ but our algorithms are agnostic to both the changing rate sequence and its average (except in warmup section 4). 我々の保証は平均的な変化率の関数であり、我々のアルゴリズムは変化率列と平均の両方に依存しない(ウォームアップセクション4を除く)。 0.77
T−1 PT−1 We will consider the problem in two environments: T−1 PT−1 この問題は2つの環境で検討する。 0.61
1. Adversarial: an adaptive adversary chooses vt’s. 1. adversarial: アダプティブな敵はvtを選択します。 0.77
2. Stochastic: an adaptive adversary chooses a mean-zero distribution supported in [−ǫt, ǫt] from which vt+1 − vt is drawn so that vt is a bounded martingale. 2. 確率: アダプティブな敵は、vt+1 − vt が引き出される [−\t, \t] で支持される平均零分布を選択し、vt が有界なマーティンゲールとなる。
訳抜け防止モード: 2. 確率論 : アダプティブな敵は [ −t,,] でサポートされる平均-ゼロ分布を選択する そこから vt+1 − vt は vt が有界マルティンゲールとなるように描画される。
0.77
More generally, our results hold for any stochastic process satisfying Azuma’s inequality. より一般的には、この結果は吾妻の不等式を満たす任意の確率過程に当てはまる。 0.44
We analyze three settings in total: symmetric loss in the adversarial environment, and revenue loss in both the adversarial and stochastic environments. 対人環境における対称的損失と、対人環境と確率環境の両方における収益損失の合計3つの設定を分析した。 0.76
In each of the three settings, we design our algorithms gradually starting from the simple case where the changing rate is fixed and known (warmup, Section 4), then fixed and unknown (Section 5)), and finally dynamic and unknown (Section 6)). 3つの設定それぞれにおいて、変更率を固定し、既知の単純なケース(ウォームアップ、セクション4)から徐々にアルゴリズムを設計し、その後、固定して未知(セクション5)、最終的に動的で未知(セクション6)にします。 0.74
In Section 6, where we study dynamic and unknown Dynamic, non-increasing changing rates ǫt, we focus primarily on the case where the changing rates ǫt are non-increasing over time. 第6節では、動的で未知の動的、非増大的な変化率を研究し、主に時間とともに変化率が上昇しない場合に焦点を当てる。 0.78
This is motivated by situations where buyers use a learning algorithm with non-increasing learning rates (quite common) to determine their value, or using a controller to bid that stabilizes once the value approaches the ground truth. これは、購入者が非増加学習率(平均的)の学習アルゴリズムを使用して価値を決定する状況や、価値が基礎的な真実に近づくと安定化する入札にコントローラを使用する状況によって動機づけられる。 0.73
For symmetric loss alone (Theorem 6.4), we give guarantees for any sequence ǫt (i.e., not just non-increasing) but we get an additional log(T )-factor in loss. 対称損失のみ (theorem 6.4) に対して、任意のシーケンス st に対する保証を与える(つまり、非拡大だけでなく)が、追加の log(t )-ファクター損失を得る。 0.76
3 3 0.85
英語(論文から抽出)日本語訳スコア
Our results For symmetric loss, we develop an algorithm with average loss ˜O(¯ǫ) (Theorem 6.1) [and a slightly larger loss of ˜O(¯ǫ log T ) when the ǫt’s are not necessarily non-increasing (Theorem 6.4)]. 対称損失に対する結果として, 平均損失がo( ) (theorem 6.1) であるようなアルゴリズムを開発し, (theorem 6.4) が必ずしも増大しない場合の損失が少し大きい場合 (theorem 6.4) について検討した。 0.79
For revenue loss we show average loss of ˜O(¯ǫ1/2) in the adversarial setting (Theorem 6.2) and ˜O(¯ǫ2/3) in the stochastic setting (Theorem 6.3). 収益損失については、敵対的設定(theorem 6.2)における平均損失は、確率的設定(theorem 6.3)における平均損失である。 0.73
Throughout, we use ˜O(f ) to denote O(f )polylog(1/¯ǫ) + o(1) where the o(1) is with respect to T . 全体を通して、o(1) は T に関して O(f )polylog(1/ s) + o(1) と表すのに使われる。 0.68
Surprisingly, our loss bounds for none of the three settings in the general case of dynamic and unknown changing rates (Section 6) can be improved even if the changing rate is fixed and known (Section 4, Theorems 4.1, 4.2, 4.3). 驚くべきことに、動的な変化率と未知の変動率の一般的な場合(第6節)における3つの設定の損失限界は、変化率が固定されても改善することができる(第4節、定理4.1、定理4.2、第4.3)。 0.67
I.e., in our fairly general model, knowing the rate of change of valuation, or having the rate of change be fixed, don’t provide much help in learning the valuation function to profitably price against it! つまり、当社のかなり一般的なモデルでは、バリュエーションの変更率を知ること、あるいは変更率を固定することは、バリュエーション関数を学習してそれに対して利益のある価格を取る上で、あまり役に立たないのです!
訳抜け防止モード: すなわち、私たちのかなり一般的なモデルでは、バリュエーションの変化率を知ることです。 あるいは変化の度合いを 固定することです あまり役に立たない 評価関数を学習して 対価を稼げる!
0.72
Our techniques Step 1: fixed and known ǫ (Section 4): Here, the algorithm keeps in each period a confidence interval [ℓt, rt] containing vt. われわれの手法のステップ1:固定化・既知化(第4節): ここで、このアルゴリズムはvtを含む信頼区間 [lt, rt] を各周期に保持する。 0.79
If rt − ℓt is small, we price at the lower endpoint ℓt, resulting in a larger interval [ℓt+1, rt+1] = [ℓt − ǫ, rt + ǫ] in the next iteration. rt − lt が小さい場合、低いエンドポイント lt で価格を設定すれば、次のイテレーションでより大きな間隔 [lt+1, rt+1] = [lt − s, rt + s] が得られる。 0.85
Once the interval is large enough, we decrease its size by a binary search to decrease and re-start the process. 間隔が十分に大きくなると、二分探索によってそのサイズを小さくし、プロセスの縮小と再起動を行う。
訳抜け防止モード: 間隔が十分大きくなると、二分探索によりそのサイズを小さくする プロセスを縮小し、再起動する。
0.75
The algorithm thus keeps alternating between exploring and exploiting, where the length of the interval decides when we do what. したがって、アルゴリズムは探索と利用の交互性を維持し、間隔の長さがいつ何をするかを決定する。 0.73
Step 2: fixed and unknown ǫ (Section 5): Here, we start guessing a very small value of ǫ, say ˆǫ = 1/T and we behave as if we knew ǫ. ステップ2: 固定と未知の値(第5節): ここで、非常に小さな値 s = 1/t を推測し始めると、まるで s を知っていたかのように振る舞う。 0.71
If we detect any inconsistency with our assumption, we double our guess: ˆǫ ← 2ˆǫ. 仮定と矛盾を検知すると、推測を2倍にします。 0.41
It is easy to detect when the value is below our confidence interval (since we always price at the lower point) but not so easy to detect when it is above. 値が信頼区間より低いとき(常に低い地点で価格を下げているため)は容易に検出できますが、その上にあるときはあまり検出できません。 0.78
To address this issue, we randomly select certain rounds (with probability proportional to a power of our estimate ˆǫ) to be checking rounds. この問題に対処するために、あるラウンドをランダムに選び(確率は我々の推定値に比例する)、ラウンドをチェックする。 0.73
In those rounds, we price at the higher end of the interval. これらのラウンドでは、インターバルの上位で価格を付けます。 0.51
Step 3: dynamic, non-increasing and unknown ǫt (Section 6): We again keep an estimate ˆǫ like in Step 2, but now we adjust it in both directions. ステップ3: 動的、非増加的、未知のエット(ステップ6): ステップ2のように再度見積もりを保ちますが、今度はそれを両方の方向に調整します。 0.77
We increase ˆǫ as in the previous step if we observe anything inconsistent with the guess. 推測と矛盾するものを観察するならば、前段と同様に ... を増加させる。 0.51
For the other direction, we optimistically halve the guess (ˆǫ ← ˆǫ/2) after we spend 1/ˆǫ periods with the same guess. もう一方の方向については、同じ推測で1/1の期間を過ごした後、楽観的に推測を半分に減らします。 0.54
Comment on average versus total loss. 平均損失対総損失に関するコメント。 0.75
Our results are all framed in terms of the average loss instead of the total loss, thus suppressing the factor T . その結果, 平均損失は全体の損失ではなく, 平均損失で表され, 因子Tが抑制されることがわかった。 0.68
To see why, note that even if we knew vt−1 exactly for each t, and even if values evolved stochastically, we would already incur an O(ǫ) loss per step leading to a total regret of O(T ǫ). その理由を確かめるために、各 t に対して vt−1 を正確に知っていて、仮に値が確率論的に進化したとしても、ステップ毎に O( ) が失われ、O(T ) が完全に後悔される。 0.66
Consequently, the main question is not the dependence on T (which is necessarily linear and cannot become any worse), but how much worse does the dependence on ǫ get, per time step. したがって、主な問題は、T への依存(これは必ずしも線型であり、さらに悪いことにはならない)ではなく、時間が経過するごとに T への依存がどれだけ悪化するかである。 0.70
To see this in action, it is instructive to compare our algorithms with the algorithm in [13] which has sublinear loss with respect to a fixed price benchmark. これを実際に見るためには,[13] のアルゴリズムと,[13] の固定価格ベンチマークに対するサブ線形損失を持つアルゴリズムを比較することを指導する。 0.85
For a fixed ǫ consider the periodic sequence vt that starts at zero and increases by ǫ in each period reaching 1 and then decreases by ǫ in each period reaching 0 and starts climbing again. 固定された t に対して、周期列 vt は 0 から始まり、各周期が 1 に到達し、各周期が 0 に到達して再び登頂を開始する周期列 vt を考える。 0.68
4 + O(ǫ). 4 + o( ) である。 0.82
2 − O(√ǫ)), while Kleinberg and Leighton guarantee 2 − o ) であるのに対し、kleinberg と leighton は保証する。 0.65
Our algorithm guarantees total revenue T ( 1 a revenue of T 1 In the supplementary material we show that for this example their algorithm indeed suffers a total loss of Ω(T ) with respect to the first-best benchmark, while our algorithms suffer T ˜O(√ǫ), i.e., much better dependence on ǫ. 我々のアルゴリズムは総収入T(1はT1の収入)を保証します この例では、これらのアルゴリズムが第1のベンチマークに対してΩ(T)の総損失を被っているのに対して、我々のアルゴリズムはT(O)を被っているのです。 0.79
2 + O(ǫ) while the best fixed price benchmark is T 最高の固定価格ベンチマークがtであるのに対して、2 + o(\) 0.61
The first-best benchmark is Pt vt = T 最初のベンチマークは Pt vt = T である。 0.63
4 − O(√T ). 4 − o である。 0.48
4 4 0.85
英語(論文から抽出)日本語訳スコア
4 Warmup: Buyer’s Changing Rate is Fixed, Known 4月4日のウォームアップ:バイヤーの金利変動が修正 0.53
We begin by studying the symmetric loss in the adversarial environment. まず、敵対的環境における対称的損失の研究から始める。 0.65
The result is straightforward via a binary search algorithm that keeps track of a confidence interval [ℓt, rt] that contains the true value vt in each time step. 結果は、時間ステップ毎に真の値 vt を含む信頼区間 [lt, rt] を追跡するバイナリ検索アルゴリズム経由で簡単に得られる。 0.75
Theorem 4.1. If the buyer has adversarial values and a fixed changing rate ǫ that is known to the seller, there is an online pricing algorithm that achieves symmetric loss O(ǫ). 定理4.1。 買い手が反対の値と、売り手が知っている固定的な変動率 s を持つ場合、対称損失o(\) を達成するオンライン価格アルゴリズムが存在する。 0.64
Further, no online algorithm can obtain symmetric loss less than Ω(ǫ). さらに、オンラインアルゴリズムはΩ( ) 未満の対称損失を得ることができない。 0.80
Proof. Firstly, consider the value sequence to be an unbiased random walk with step size ǫ, and starting point v1 = 1 2 . 証明。 まず、値列をステップサイズ s の偏りのないランダムウォークとし、出発点 v1 = 1 2 とする。
訳抜け防止モード: 証明。 第一に、値列をステップサイズで偏りのないランダムウォークと考えてみよう。 開始点 v1 = 1 2 である。
0.67
The symmetric loss from each time step t is Ω(ǫ) even if vt−1 is known to the seller, since the seller does not know whether vt = vt−1 + ǫ or vt = vt−1 − ǫ. ステップ t の各時間における対称損失は、vt−1 が売り手に知られているとしても ω(\) であり、売り手は vt = vt−1 + s か vt = vt−1 − s かを知らないからである。
訳抜け防止モード: 各タイムステップ t からの対称的損失は、もしも Ω( ) である。 vt−1は売り手に知られている。 売り手は vt = vt−1 + . または vt = vt−1 − . を知らない。
0.82
Thus no online algorithm can obtain a symmetric loss o(ǫ) for this instance. したがって、この場合、オンラインアルゴリズムは対称損失o(\)を得ることができない。 0.72
Then we show that a naive binary search algorithm achieves symmetric loss O(ǫ). 次に、2進探索アルゴリズムが対称損失O(a)を達成することを示す。 0.77
The algorithm keeps track of a confidence interval [ℓt, rt] that contains the true value vt in each time step. アルゴリズムは 時間ステップ毎に真の値vtを含む信頼区間[lt, rt]を追跡する。 0.67
ALGORITHM 1: Symmetric loss minimizing algorithm for adversarial buyer with known changing rate ǫ ALGORITHM 1: 変化率が既知の逆購入者に対する対称性損失最小化アルゴリズム 0.83
ℓ1 ← 0 r1 ← 1 for each time step t do Price at pt ← rt+ℓt if the current value vt < pt then もし電流値 vt < pt が pt であるなら、l1 > 0 r1 > 1 は pt > rt+lt で値を取る。 0.69
2 else ℓt+1 ← max(0, ℓt − ǫ) rt+1 ← min(1, pt + ǫ) ℓt+1 ← max(0, pt − ǫ) rt+1 ← min(1, rt + ǫ) 2 その他 lt+1 は max(0, lt − ) rt+1 は min(1, pt + ) lt+1 は max(0, pt − ) rt+1 は min(1, rt + ) である。 0.77
end if end for At time t we have a confidence interval [ℓt, rt] ∋ vt that contains the true value of the buyer, since the buyer’s value only changes by at most ǫ. 終われば終われば t には、買い手の真の価値を含む信頼区間[lt, rt] > vt が存在します。
訳抜け防止モード: 終われば終われば t の時点では、バイヤーの真の価値を含む信頼区間 [lt, rt ] > vt が存在します。 買い手の価値は最大で 1 でしか変化しないからである。
0.62
If the buyer can afford to pay pt = ℓt+rt , i.e. もし買い手が pt = lt+rt を支払う余裕があるなら、つまり、 0.67
vt ≥ pt, it means that vt+1 ∈ [pt − ǫ, rt + ǫ]; otherwise, it means that vt+1 ∈ [ℓt − ǫ, pt + ǫ]. vt ≥ pt は vt+1 ∈ [pt − s, rt + s] を意味し、そうでなければ vt+1 ∈ [lt − s, pt + s] を意味する。 0.94
In both cases, we almost halve the length of the confidence interval. どちらの場合も、信頼区間の長さはほぼ半分になる。 0.63
Let at be the length of the confidence interval at time t. Since the price is always the middle point of the interval, the symmetric loss of each time step is at most at 2 . 時間tにおける信頼区間の長さとする。価格は常に区間の中間点であるため、各時間ステップの対称損失は少なくとも2 度である。 0.72
As at starts with 1 and almost halves in each step until at = O(ǫ), we have 1 2 Pt at = O(T ǫ), which upper bounds the total symmetric loss of all time steps in the algorithm. 1 とほぼ半分のステップで開始すると、O( ) = O(T ) となるまで、1 2 Pt at = O(T ) となり、これはアルゴリズムの全ての時間ステップの合計対称損失を上界とする。 0.81
2 Next, we extend the algorithm for symmetric loss to an optimal algorithm for revenue loss. 2 次に、対称損失のアルゴリズムを、収益損失の最適アルゴリズムに拡張する。 0.79
Theorem 4.2. If the buyer has adversarial values and a fixed changing rate ǫ that is known to the seller, there exists an online pricing algorithm with revenue loss ˜O(ǫ1/2). 理論4.2。 買い手が逆の値を持ち、売り手が知っている固定的な変動率である場合、収益損失が1/2であるオンライン価格アルゴリズムが存在する。 0.61
Further, no online algorithm can obtain a revenue loss less than Ω(ǫ1/2). さらに、オンラインアルゴリズムは ω(1/2) 未満の収益損失を得ることができない。 0.70
5 5 0.85
英語(論文から抽出)日本語訳スコア
Proof. We assume that ǫ ≥ 1 loss ˜O((ǫ′)1/2) = o(1) = ˜O(ǫ1/2). 証明。 ここでは、n ≥ 1 の損失は o(1) = oO((a)1/2) と仮定する。 0.70
T . Otherwise, we can run the algorithm with ǫ′ = 1 T。 さもないと、アルゴリズムは s′ = 1 で実行できる。 0.74
T and get revenue The idea of the algorithm is as follows. tと収入は アルゴリズムの考え方は以下の通りである。 0.70
The sale process starts with the seller not knowing the initial value v1 of the buyer. 販売プロセスは、売り手が買い手の初期値v1を知らずに開始する。 0.74
However, since the buyer’s value only changes by at most ǫ in each step, the seller can quickly locate the buyer’s value within O(ǫ) error by binary search. しかし、買い手の価値はステップごとに最大で1/1しか変化しないため、売り手はバイナリ検索によって、買い手の値がo(\)エラー内ですぐに見つけることができる。 0.65
Such a small confidence interval that contains the buyer’s current value extends by ǫ in both upper bound and lower bound after each step. 購入者の現在の値を含むこの小さな信頼区間は、各ステップの後に上限と下限の両方で s まで延びる。 0.63
We propose an algorithm that repeatedly prices at the bottom of the confidence interval and re-locates the buyer’s current value whenever the confidence interval becomes too wide. 本稿では,信頼区間の下部で繰り返し価格を値付けし,信頼区間が広すぎると買い手の現在の値を再配置するアルゴリズムを提案する。 0.79
Firstly, we have the following building-block algorithm that quickly returns the range of the buyer’s value with additive accuracy O(ǫ). まず、次のビルディングブロックアルゴリズムを用いて、購入者の値の範囲を迅速に加算精度O()で返す。 0.60
In the algorithm, timestamp t increases by one after any pricing query. アルゴリズムでは、タイムスタンプtは価格クエリの後に1つ増加する。 0.67
ALGORITHM 2: Locating the value of a buyer with changing rate ǫ to an interval of length a ≤ 6ǫ ALGORITHM 2: a ≤ 6 {\displaystyle 6} の長さの間隔に変化率 > で買い手の値を設定する 0.81
Input: current confidence interval [ℓt, rt] Run Algorithm 1 until confidence interval [ℓt, rt] satisfies rt − ℓt < 4ǫ Return [ℓt − ǫ, rt + ǫ] The algorithm repeatedly does binary search until the confidence interval has length O(ǫ). 入力:現在の信頼区間 [lt, rt] アルゴリズム 1 を信頼区間 [lt, rt] がrt − lt < 4 の返り [lt − ] を満たすまで実行します。
訳抜け防止モード: 入力 : 現在の信頼区間 [lt, rt ] 信頼区間 [lt, ] までアルゴリズム1を走らせる rt ] は rt − lt < 4 の戻りを満足する。 rt + t ] このアルゴリズムは、信頼区間が長さ O( ) になるまで二分探索を繰り返し行う。
0.88
If at the beginning we have a confidence interval of length b and finally we have a confidence interval of length a, thus the total number of steps needed is O(log b a ), and the total loss of the algorithm is O(log b 最初は長さ b の信頼区間を持ち、最後に長さ a の信頼区間を持つなら、必要なステップの総数は O(log b a ) であり、アルゴリズムの総損失は O(log b) である。 0.72
a ) since the loss of each step is at most 1. a)各ステップの損失は最大で1である。 0.73
Next, we present the entire pricing algorithm for an adversarial buyer with changing rate ǫ using 次に, 変動率 > を用いた逆購入者の価格設定アルゴリズムを提案する。 0.68
Algorithm 2 as a building block. ビルディングブロックとしてのアルゴリズム2。 0.76
ALGORITHM 3: Revenue loss minimizing algorithm for adversarial buyer with known changing rate ǫ ALGORITHM 3: 変動率が既知の逆購入者に対する収益損失最小化アルゴリズム 0.89
for each phase [t0 + 1, t0 + m] of length m = ǫ−1/2 do 長さ m の相 [t0 + 1, t0 + m] について、 0.77
Apply Algorithm 2 to locate the current value of the buyer in an interval [ℓt, rt] with length √ǫ for each step t in the phase do アルゴリズム2を適用して、段階 do の各ステップ t に対して長さ ~ の間隔 [lt, rt] で買い手の現在の値を見つける。 0.82
Price at pt ← ℓt [ℓt+1, rt+1] ← [ℓt − ǫ, rt + ǫ] pt > lt [lt+1, rt+1] > [lt − >, rt + >] 0.57
end for end for Now we analyze the revenue loss of the algorithm. 終止符 終止符 現在、アルゴリズムの収益損失を分析している。 0.66
In each phase of the algorithm with m time steps, we first initialize and locate the value of the buyer to a small range √ǫ. m の時間ステップを持つアルゴリズムの各フェーズにおいて、まずバイヤーの値を小範囲の ... に初期化し、配置する。 0.67
The revenue ǫ ) = ˜O(1) in each phase (actually O(1) after the first phase loss incurred by Algorithm 2 is O(log 1 since the length of confidence interval only needs to shrink by constant fraction). アルゴリズム2によって生じた第1の位相損失後の各フェーズ(実際にはo(1))の収入は、信頼区間の長さが一定分数で縮まる必要があるため、o(log 1)である。 0.81
Then we price at the bottom of the confidence interval for O(√ǫ) steps for m = √ǫ steps. すると、信頼区間の底辺で、m = 〜 step の o(\) ステップの価格が決まる。 0.54
Since the confidence interval [ℓt, rt] expands by 2ǫ each time, it is equivalent to say we wait until the confidence interval has length 3√ǫ. 信頼区間 [lt, rt] は毎回 2 度膨張するので、信頼区間の長さが 3 になるまで待つと言うのと同値である。 0.75
The revenue loss from each step is ≤ 3√ǫ since the item is bought by the buyer every time, thus O(√ǫ) · 3√ǫ = O(ǫ) in the entire phase; then we use binary search to narrow the confidence interval by 1 2 , which has revenue loss O(1) since it takes only O(1) steps in Algorithm 2. 各ステップからの収益損失は、そのアイテムが毎回買い手によって購入されるため、全フェーズでO( ) · O( ) = O( ) となり、次に二分探索を用いて信頼区間を1 2 に絞り込む。
訳抜け防止モード: 各ステップからの収益損失は 3 ≤ 3 である。 商品は毎回買い手によって買われます したがって、位相全体において O( ) · 3 ) = O( ) となると、二分探索を用いて信頼区間を 1 2 に絞り込み、O(1 ) の収益損失がある。 アルゴリズム2では O(1 ) ステップしかかからない。
0.81
Each phase takes Θ(√ǫ) steps with loss O(ǫ), therefore there are O(T ǫ−1/2) phases in total with loss O(T ǫ−1/2) · O(ǫ) = O(T ǫ1/2). 各位相は、損失 O(a) と損失 O(a) の段階を取るので、合計 O(T )−1/2) と損失 O(T )−1/2) = O(T )1/2) の段階が存在する。 0.72
Thus the total loss of the algorithm is ˜O(T ǫ1/2), with average revenue loss ˜O(ǫ1/2). したがって、アルゴリズムの損失の総和は、平均収益損失は、o(t)(1/2)である。 0.81
We show that such loss is tight, that no online algorithm can obtain a revenue loss o(ǫ1/2). このような損失は厳密であり,オンラインアルゴリズムでは収益損失o(1/2)が得られないことを示す。 0.73
By Yao’s minimax principle, to reason that there exists some adversarial buyer such that no random- ヤオのミニマックス原理により、無作為ではないような敵対的な買い手が存在することを推論する 0.57
6 6 0.85
英語(論文から抽出)日本語訳スコア
2 , vt0+j = vt0 + jǫ, ∀j ∈ [ǫ−1/2]; with probability 1 2 , vt0+j = vt0 + j であり、確率 1 である。 0.76
ized online algorithm can get revenue loss o(ǫ1/2), it suffices to show that there exists a random adversarial buyer such that no online deterministic algorithm can get such low revenue loss. オンラインアルゴリズムは収益損失o(1/2)を得ることができ、オンライン決定論的アルゴリズムがそのような低い収益損失を得ることができないような、無作為な敵対的な買い手が存在することを示すことは十分である。 0.58
The buyer’s value sequence is predetermined as follows. 購入者の値の順序は次のとおりである。 0.70
In the beginning, the buyer has value v0 = 1 2 . 当初、買い手は値 v0 = 1 2 を持つ。 0.65
The entire time horizon [T ] is partitioned to T√ǫ phases, each with length ǫ−1/2. 全時間水平線 [T ] は、長さ ~−1/2 の T 相に分割される。 0.73
In each phase starting with time t0 + 1 and ending with time t0 + ǫ−1/2, the values of the buyer form a monotone sequence: with probability 1 2 , vt0+j = vt0 − jǫ, ∀j ∈ [ǫ−1/2]. 時間 t0 + 1 から開始し、時間 t0 + s−1/2 で終わる各段階において、買い手の値は単調列を形成する: 確率 1 2 , vt0+j = vt0 − j である。 0.85
For any deterministic algorithm with price pt at each time, when any phase begins, the algorithm needs to decide the pricing strategy without knowing which value instance of the buyer will be realized. 価格のptがある決定論的アルゴリズムの場合、どのフェーズが始まっても、買い手のどの値インスタンスが実現されるかを知らずに価格戦略を決定する必要がある。 0.79
Let ˆt ∈ [t0 + 1, t0 + ǫ−1/2] be the first time step in the phase such that vt0 − (t − t0)ǫ < pt. t ∈ [t0 + 1, t0 + t−1/2] を vt0 − (t − t0) = < pt となるような位相の最初の段階とする。 0.86
If such ˆt exists, then the revenue loss at time ˆt is vt0 − (ˆt− t0)ǫ = vt0 − O(ǫ1/2) when the values of the buyer decrease in the phase, and this case happens with probability 1 2 . そのような t が存在する場合、時点 t における収益損失は、購入者の値が位相が減少するときに vt0 − ( t − t0) ) = vt0 − O(\1/2) となり、この場合の確率は 1 2 となる。 0.78
Then in expectation the revenue loss in this phase is Ω(vt0)− O(ǫ1/2). すると、この段階での収益損失はΩ(vt0)− O(...1/2)となる。 0.66
Notice that the starting value vt0 of each phase form a unbiased random walk sequence with step size ǫ1/2, since the buyer starts with v0 = 1 2 , therefore with constant probability vt0 ≥ 1 2 . 各相の開始値 vt0 は、v0 = 1 2 で始まり、したがって定数確率 vt0 ≥ 1 2 となるので、ステップサイズ 1/2 の偏りのないランダムウォーク列を形成することに注意する。 0.73
Thus we can also claim that the expected revenue loss in the phase is Ω(1). したがって、フェーズにおける期待される収益損失はΩ(1)であると主張することもできる。 0.73
If such ˆt does not exist, it means that the algorithm has identical information from both instances of the buyer in the entire phase, since the buyer can always afford to purchase the item. t が存在しない場合、購入者が常にアイテムを購入する余裕があるため、アルゴリズムが購入者の両方のインスタンスから同一の情報を持っていることを意味する。 0.73
As pt ≤ vt0 − (t− t0)ǫ for each time t, the revenue loss of the algorithm when the values of the buyer increase in the phase is at least Pt0<t≤t+ǫ−1/2(vt0 + (t− t0)ǫ− pt) ≥ Pt0<t≤t+ǫ−1/2 2(t− t0)ǫ = Ω(1). pt ≤ vt0 − (t− t0) = pt ≤ vt0 − (t− t0) とすると、位相におけるバイヤーの増大する値が少なくとも Pt0<t≤t + t−1/2(vt0 + (t− t0) ) ≥ Pt0<t≤t + t−1/2 2(t− t0) ) = Ω(1) となるときのアルゴリズムの収益損失は減少する。
訳抜け防止モード: pt ≤ vt0 − ( t− t0) である。 アルゴリズムの収益損失は 買い手の価値は 段階的に上昇し 最低でも Pt0 < t≤t + n −1/2(vt0 + ( t− t0) ) ≥ Pt0 < t≤t + n −1/2 2(t− t0) ) = Ω(1 ) である。
0.80
Therefore in both cases, the revenue loss in the phase is Ω(1) in this phase for any deterministic algorithm. したがって、どちらの場合も、この位相における収益損失は任意の決定論的アルゴリズムに対してΩ(1)である。 0.72
As there are T ǫ1/2 phases, the total revenue loss from all phases is at least Ω(T ǫ1/2). 任意の位相から得られる総収入損失は、少なくとも Ω(T は1/2) である。 0.65
Thus no randomized algorithm can get average revenue loss o(ǫ1/2). したがって、ランダム化アルゴリズムは平均収益損失o(1/2)を得ることができない。 0.62
If the buyer’s value evolves stochastically across time, the stochasticity helps us incur less revenue loss. 買い手の価値が時間とともに確率的に進化すれば、確率性は収益損失を減らすのに役立ちます。 0.50
To be more specific, when the buyer’s value is stochastic and forms a martingale, after every ǫ−2/3 steps, although the buyer’s value can change by as large as ǫ−2/3 · ǫ = ǫ1/3, with high probability the buyer’s value only changes by ǫ2/3. より具体的に言うと、購入者の値が確率的であり、かつマーチンゲールを形成する場合、各ステップの後に、購入者の値が シュ=2/3 · シュ = シュ1/3 になるが、高い確率で購入者の値が シュ=2/3 だけ変化する。
訳抜け防止モード: より具体的に言うと 買い手の価値は確率的であり、マーチンゲールを形成する。 2/3 ステップごとに値が変化するが、購入者の値が 3/3 · 3 で変わることもある。 高い確率で買い手の価値は2/3にしか変化しない。
0.68
Thus compared to Algorithm 3, we can extend each phase’s length while maintaining a shorter confidence interval. したがって、アルゴリズム3と比較して、信頼区間を短くしながら各フェーズの長さを延ばすことができる。 0.74
We state the algorithm and the revenue loss below. アルゴリズムと収益損失を以下に示す。 0.59
ALGORITHM 4: Revenue loss minimizing algorithm for stochastic buyer with known changing rate ǫ ALGORITHM 4: 変動率が既知の確率的買い手に対する収益損失最小化アルゴリズム 0.86
[ℓ, r] ← [0, 1] for each phase [t0 + 1, t0 + m] of length m = ǫ−2/3 do 長さ m の各相 [t0 + 1, t0 + m] について、[l, r] は、[0, 1] である。 0.82
Apply Algorithm 2 to narrow down the confidence interval [ℓ, r] to length 6ǫ for each step t in the phase do アルゴリズム2を適用して、位相 do の各ステップ t に対して、信頼区間 [l, r] を長さ 6 に狭める。 0.83
Price at pt ← ℓ − 4ǫ2/3qlog 1 pt での価格: l − 4/2/3qlog 1 0.51
ǫ end for end for Theorem 4.3. ǫ 終止符 終止符 定理4.3。 0.66
If the buyer has stochastic value and a fixed changing rate ǫ that is known to the seller, Algorithm 4 has revenue loss ˜O(ǫ2/3). 買い手が確率的価値と、売り手が知る固定的な変動率である場合、アルゴリズム4は収益損失をo(2/3)とする。 0.75
Furthermore, no online algorithm can obtain a revenue loss less than Ω(ǫ2/3). さらに、オンラインのアルゴリズムではΩ(2/3)未満の収益損失が得られない。 0.73
Proof. We assume that ǫ ≥ 1 ˜(ǫ′)2/3 = o(1) = ˜O(ǫ2/3). 証明。 次は 1 と 1 と 1 と o(1) = o(1) とすると仮定する。 0.49
loss When the buyer’s value is stochastic and forms a martingale, after every ǫ−2/3 steps, although the buyer’s value can change by as large as ǫ−2/3 · ǫ = ǫ1/3, with high probability the buyer’s value 買い手の値が確率的かつマルティンゲールである場合、その買い手の値が 1/3 ステップごとに変化するが、買い手の値が 1/2/3 · 1/1/3 に変化し、買い手の値が高い確率で変化する。
訳抜け防止モード: 買い手の価値が確率的であり、マーチンゲールを形成する場合の損失。 2/3 ステップごとに値が変化するが、購入者の値が 3/3 · 3 で変わることもある。 買い手の価値が高い確率で
0.70
T . Otherwise, we can run the algorithm with ǫ′ = 1 T。 さもないと、アルゴリズムは s′ = 1 で実行できる。 0.74
T and get revenue 7 tと収入は 7 0.73
英語(論文から抽出)日本語訳スコア
only changes by ǫ2/3. Thus compared to Algorithm 3, we can extend the length of each phase, while maintaining shorter confidence interval. 変更は2/3。 したがって、アルゴリズム3と比較して各位相の長さを延長できるが、信頼性間隔は短い。 0.73
The detailed algorithm is as follows. 詳細なアルゴリズムは以下の通りである。 0.74
ALGORITHM 5: Revenue loss minimizing algorithm for stochastic buyer with known changing rate ǫ ALGORITHM 5: 変動率が既知の確率的買い手に対する収益損失最小化アルゴリズム 0.84
ℓ ← 0 r ← 1 for each phase [t0 + 1, t0 + m] of length m = ǫ−2/3 do 長さ m の位相 [t0 + 1, t0 + m] 毎に l > 0 r > 1 となると、 0.85
Apply Algorithm 2 to narrow down the confidence interval [ℓ, r] to length 6ǫ for each step t in the phase do アルゴリズム2を適用して、位相 do の各ステップ t に対して、信頼区間 [l, r] を長さ 6 に狭める。 0.83
Price at pt ← ℓ − 4ǫ2/3qlog 1 pt での価格: l − 4/2/3qlog 1 0.51
ǫ end for end for Now we analyze the revenue loss of the algorithm. ǫ 終止符 終止符 現在、アルゴリズムの収益損失を分析している。 0.71
In each phase [t0 + 1, t0 + m] with m = ǫ−2/3, ǫ ) = ˜O(1). 各位相 [t0 + 1, t0 + m] において、m = t−2/3, t ) = tO(1) となる。 0.75
Suppose that firstly the binary search algorithm is called with a revenue loss of O(log 1 at time t1 the search algorithm ends, and we get an estimate of vt1 with additive accuracy 6ǫ. まず、二分探索アルゴリズムは、時間t1においてo(log 1)の損失で呼ばれ、探索アルゴリズムが終了すると、加算精度6 のvt1の推定値が得られるとする。 0.75
Let ǫ . In the remaining of the phase, the price is fixed to be ℓ−δ. としよう。 相の残りでは、価格は l−δ に固定される。 0.67
For any t ∈ [t1, t0 +m], 任意の t ∈ [t1, t0 +m] に対して 0.73
δ = 4ǫ2/3qlog 1 by Azuma’s inequality, the probability that vt 6∈ [vt1 − δ, vt1 + δ] is δ = 4/2/3qlog 1 は azuma の不等式により、vt 6 ∈ [vt1 − δ, vt1 + δ] が成り立つ確率である。 0.71
Pr[vt 6∈ [vt1 − δ, vt1 + δ]] ≤ 2 exp(cid:18)− Pr[vt 6∂ [vt1 − δ, vt1 + δ]] ≤ 2 exp(cid:18)− 0.95
δ2 2mǫ2(cid:19) < δ2 2m>2(cid:19) < 0.67
1 m2 . (2) By union bound, the probability that exists t ∈ [t1, t0 + m] such that vt 6∈ [vt1 − δ, vt1 + δ] is at most 1 m ; in this case, the revenue loss in the phase is at most 1 per step thus m in total, so the expected revenue loss contributed from the case is O(1). 1m2。 (2) t ∈ [t1, t0 + m] であり、vt 6 tasktop [vt1 − δ, vt1 + δ] が少なくとも 1 m である確率は、結合境界により、t ∈ [t1, t0 + m] が存在する。
訳抜け防止モード: 1m2。 (2) 結合境界により、 t ∈ [ t1, t0 + m ] が存在する確率は vt 6∂ [ vt1 − δ] となる。 vt1 + δ ] は少なくとも 1 m である。 フェーズの収益損失は 1ステップ当たり 1 以上なので 合計 m になります。 したがって、このケースから得られた収益損失は、O(1 )である。
0.81
If vt ∈ [vt1 − δ, vt1 + δ] for every t ∈ [t1, t0 + m], the revenue loss for setting price ℓ − δ ≥ vt − 6ǫ − δ is at most O(ǫ + δ) for each step, thus mO(ǫ + δ) = O(qlog 1 ǫ ) = ˜O(1) in total. 任意の t ∈ [t1, t0 + m] に対して vt ∈ [vt1 − δ, vt1 + δ] が成り立つと、価格 l − δ ≥ vt − 6n − δ を設定した場合の収益損失は、各ステップの最大 O(+ δ) であり、従って、mO(> + δ) = O(qlog 1 > ) = O(qlog 1 ) ) である。 0.86
Combine both cases above, we know that the expected revenue loss in each phase is ˜O(1), thus ˜O(T ǫ2/3) in total and ˜O(ǫ2/3) revenue loss on average since there are T 上記の2つのケースを組み合わせると、各フェーズにおける期待される収益損失が...O(1)であり、Tが存在するため、合計で...O(T)2/3)、平均で...O(2)/3)であることがわかる。
訳抜け防止モード: 上記の2つのケースを組み合わせて、私たちはそれを知っています。 各段階で予想される収益損失は >O(1 ) したがって、T が存在するため、合計で >O(T >2/3 ) と >O(>2/3 ) の収益損失は平均で減少する。
0.55
m = T ǫ2/3 phases. m = T × 2/3 相。 0.64
Now we show that such loss is tight, even when the buyer’s values form an unbiased random 購入者の値が偏りのないランダムであっても、このような損失は厳しいことを示します。 0.61
walk with step size ǫ and starting value 1 2 . ステップサイズ > と開始値 1 2 で歩きます。 0.70
Consider a game with multiple phases and the following more powerful seller. 複数のフェーズと以下の強力な売り手を持つゲームを考える。 0.68
Each phase has at most 2m = 2ǫ−2/3 time steps. 各フェーズは、少なくとも2m = 22/3の時間ステップを持つ。 0.53
At the beginning of each phase, the seller is told the exact value v0 of the buyer at the current time. 各フェーズの開始時に、売り手が購入者の正確な値v0を現在時刻に知らせる。 0.63
Then at each time step t ∈ [1, 2m], the current value vt increases or decreases by ǫ with equal probability, and the seller sets a price pt. すると、各時間ステップ t ∈ [1, 2m] において、現在の値 vt は、同じ確率で s で上昇または減少し、売り手は価格 pt を設定する。 0.79
Whenever pt > vt, the phase terminates and incurs a loss ℓ = vt. pt > vt になると位相は終了し、損失 l = vt が発生する。 0.80
If pt < vt for the entire phase, the loss ℓ of the phase is defined pt < vt が全位相の場合、その位相の損失 l が定義される 0.71
by Pt≤2m ℓt = Pt≤2m(vt − pt). Pt≤2m lt = Pt≤2m(vt − pt)。 0.76
Then the game goes to the next phase, with v0 reset to v2m ± ǫ. ゲームは次のフェーズに進み、v0 は v2m ± 0 にリセットされる。 0.72
The entire game ends when the total number of time steps in each phase sum up to T . ゲーム全体は、各フェーズにおける時間ステップの合計数が T となると終了する。 0.86
We notice that in the game, the seller is strictly more powerful, while the loss does not increase. ゲーム内では、売り手は厳密には強力であるが、損失は増加しない。 0.58
In each phase before the phase terminates, the seller learns no information from the pricing. フェーズ終了前の各フェーズにおいて、売り手は価格から情報を受け取らない。 0.69
Thus without loss of generality, assume that given initial value v0 of the buyer, the seller proposes a sequence of deterministic prices (randomness won’t help) p1, p2,··· , p2m, and then the values v1,··· , v2m are realized randomly. したがって、一般性を失うことなく、買い手の初期値 v0 が与えられた場合、売り手は決定論的価格 p1, p2,······ , p2m の列を提案し、その後 v1,···· , v2m がランダムに実現される。 0.74
We do not count the loss contributed from the first m steps. 最初のmステップから得られた損失はカウントしません。 0.73
Since Chernoff bound is tight up to constant factor for U{−1, 1} random variables, i.e. チャーノフ境界は、U{−1, 1} 確率変数の定数因子、すなわち、厳密である。
訳抜け防止モード: チャーノフ境界は U{−1 の定数因子に近くなるからである。 1 } 変数、すなわち確率変数。
0.64
Pr[vt < v0 − ǫ√t] ≥ Ω(1) for t ≥ m. Thus t ≥ m に対する Pr[vt < v0 − >t] ≥ Ω(1) である。 0.89
8 8 0.85
英語(論文から抽出)日本語訳スコア
probability 1 phase ends at step 2m. 確率1のフェーズは ステップ2mで終了。 0.70
for any t ≥ m if pt ≥ v0 − ǫ√m, with constant probability the phase stops at time t with loss vt, which is Ω(1) in expectation. 任意の t ≥ m に対して、pt ≥ v0 − sm であれば、一定確率で位相は時間 t で停止し、損失 vt は期待値 ω(1) となる。 0.77
If pt < v0 − ǫ√m, E[vt − pt|vt ≥ pt] = Ω(ǫ√m) = Ω(ǫ2/3) since with 2 , vt ≥ v0. 2 , vt ≥ v0 であるため、 pt < v0 − ym の場合、E[vt − pt|vt ≥ pt] = Ω(nm) = Ω(n2/3) となる。 0.81
Thus the loss of the phase is at least mΩ(ǫ2/3) = Ω(1) in expectation if the The above analysis shows that at each phase, the expected loss is Ω(1). したがって、位相の損失が少なくとも mΩ(\2/3) = Ω(1) であるとは、上記の解析が各位相において期待される損失が Ω(1) であることを示している。 0.81
Since there are at least T m = T ǫ2/3 phases, the total loss is at least Ω(T ǫ2/3) in expectation. 少なくとも T m = T > 2/3 相が存在するので、総損失は予想において少なくとも Ω(T > 2/3) である。 0.70
This finishes the proof of no randomized algorithm can get revenue loss o(ǫ2/3). これにより、ランダム化アルゴリズムが収益損失o(2/3)を得ることができないことが証明される。 0.56
5 Buyer’s Changing Rate is Fixed, Unknown 5人の買い手、金利変更の修正-関係者 0.63
In this section, we consider the case where the buyer’s value changes by fixed rate ǫt = ǫ that is unknown to the seller. 本節では,購入者の価値が,販売者にとって未知の固定レート st = s で変化する場合について考察する。 0.72
As a warm-up, we first study the symmetric loss obtained by online prices. ウォームアップとして,オンライン価格によって得られる対称損失を最初に検討する。 0.57
Such a problem lets us understand better how to deal with the unknown rate of value change, and the pricing algorithm can be extended to the case of revenue loss. このような問題は、未知の価値変化率にどのように対処するかをよりよく理解し、価格アルゴリズムを収益損失の場合に拡張することができる。 0.81
Theorem 5.1. If the buyer has adversarial values and a fixed changing rate ǫ unknown to the seller, there exists an online pricing algorithm with a symmetric loss ˜O(ǫ). 理論5.1。 買い手が逆の値を持ち、売り手が未知の固定的な変動率である場合、対称損失 s(o) を持つオンライン価格アルゴリズムが存在する。 0.67
Further, no online algorithm can obtain a symmetric loss less than Ω(ǫ). さらに、オンラインアルゴリズムはΩ( ) 未満の対称損失を得ることができない。 0.83
Proof. The Ω(ǫ) tightness result was shown in Theorem 4.1. 証明。 その結果は Theorem 4.1 で示された。 0.62
Here we propose a pricing algorithm with a symmetric loss ˜O(ǫ). 本稿では,対称損失が o( ) となる価格設定アルゴリズムを提案する。 0.79
Compared to the case where ǫ is known to the seller, the seller can use a guess ˆǫ to replace the true rate ǫ, and run the algorithms in the known ǫ setting. 売り手が s を知られている場合と比較すると、売り手は推測 s を使って真のレート s を置き換えることができ、既知の s の設定でアルゴリズムを実行することができる。 0.66
The algorithm starts with ˆǫ = 1 T , and doubles ˆǫ whenever the algorithm detects that the changing rate of the value exceeds ˆǫ. アルゴリズムは 1 t の値から始まり、その値の変化速度が 1 を超えるとアルゴリズムが検出すると、その値が 2 倍になる。 0.78
ALGORITHM 6: Symmetric loss minimizing algorithm for adversarial buyer with unknown changing rate ǫ ALGORITHM 6: 変動率未知の逆購入者に対する対称性損失最小化アルゴリズム 0.86
[ℓ1, r1] ← [0, 1] ˆǫ ← 1 while ˆǫ < 1 2 do [l1, r1] > [0, 1] > > 1 , > < 1 2 である。 0.80
T for each three consecutive time steps t, t + 1, t + 2 do T 3つの連続時間ステップ t, t + 1, t + 2 do に対して 0.87
Set price pt ← ℓt Set price pt+1 ← rt + ˆǫ Set price pt+2 ← ℓt+rt if the seller finds vt < ℓ or vt+1 ≥ rt + ˆǫ then vt < l または vt+1 ≥ rt + t とすると、売り手は vt < l または vt+1 ≥ rt + t となる。
訳抜け防止モード: 価格 pt + lt + t + t + t + t + t + t を設定すれば、売り手は vt < l となる。 あるいは vt+1 ≥ rt + >
0.76
2 ˆǫ ← ˆǫ · 2 break 2 ˆǫ ← ˆǫ · 2 break 0.88
end if if vt+2 < pt+2 then end if vt+2 < pt+2 ならば 0.77
else ℓt+3 ← ℓt − 3ˆǫ, rt+3 ← pt+2 + ˆǫ ℓt+3 ← pt+2 − ˆǫ, rt+3 ← r + 3ˆǫ その他 lt+3 と lt − 3 と rt+3 と pt+2 と lt+3 と pt+2 − 3 と rt+3 は r + 3 である。 0.59
end if end for end while 最後まで終われば終わりだ 0.63
The algorithm deal with three time steps t, t + 1, t + 2 at each time, and always maintain a confidence interval [ℓt, rt] of vt at the beginning of time step t, such that ˆǫ > ǫ, vt ∈ [ℓt, rt] always アルゴリズムは、3つの時間ステップ t, t + 1, t + 2 を各時間に処理し、常に時間ステップ t の開始時に vt の信頼区間 [lt, rt] を維持する。
訳抜け防止モード: このアルゴリズムは、t, t + 1の3つの時間ステップを扱う。 t + 2 は常に信頼区間 [lt, lt] を維持する。 時間ステップtの開始時のvtの[rt] vt ∈ [ lt , rt ] が常に成り立つような
0.81
9 9 0.85
英語(論文から抽出)日本語訳スコア
holds. Time steps t and t + 1 are “checking steps”, to check whether the current three steps vt , vt+1 and vt+2 incur too much loss. ホールド。 タイムステップ t と t + 1 は「チェックステップ」であり、現在の3つのステップ vt , vt+1 と vt+2 が過剰な損失をもたらすかどうかを確認する。 0.62
In particular, if ˆǫ > ǫ, then vt ≥ pt and vt+1 < pt+1 will always hold. 特に、 s > s のとき、vt ≥ pt と vt+1 < pt+1 は常に成り立つ。 0.84
On the other hand, if vt ≥ pt, then vt+1 ≥ pt − ǫ, vt+2 ≥ pt − 2ǫ since the value of the buyer only changes at most ǫ additively, although the seller does not know the value of ǫ. 一方、vt ≥ pt の場合、vt+1 ≥ pt − >, vt+2 ≥ pt − 2> は、買い手の値が > の値だけ加法的に変化するからである。
訳抜け防止モード: 一方、vt ≥ pt ならば、vt+1 ≥ pt − s である。 vt+2 ≥ pt − 2 は、バイヤーの値が少なくとも加法的にのみ変化するためである。 ただし、売り手は s の価値を知らない。
0.72
Thus vt, vt+1, vt+2 ≥ ℓt − 2ǫ. したがって vt, vt+1, vt+2 ≥ lt − 2 である。 0.70
Similarly, if vt+1 < pt+1 = rt + ˆǫ, then vt < pt+1 + ǫ, vt+2 < pt+1 + ǫ. 同様に、vt+1 < pt+1 = rt + > とすると、vt < pt+1 + >, vt+2 < pt+1 + > となる。 0.69
Thus vt, vt+1, vt+2 < rt + ǫ + ˆǫ. したがって、vt, vt+1, vt+2 < rt + s + s である。 0.66
Since pt, pt+1, pt+2 are all in range [ℓt − 2ǫ, rt + ǫ + ˆǫ], we have for any j ∈ {t, t + 1, t + 2}, |vj − pj| = O(rt − ℓt + ǫ + ˆǫ). pt, pt+1, pt+2 は、すべて範囲 [lt − 2 , rt + t + >] であるため、任意の j ∈ {t, t + 1, t + 2}, |vj − pj| = O(rt − lt + > + >) に対して成立する。 0.92
Thus in a round of three consecutive time steps t, t + 1, t + 2, if vt ≥ pt and vt+1 < pt+1, the symmetric loss from this round of three time steps is proportional to the length of confidence bound plus the true changing rate and the estimated changing rate, i.e. したがって、3つの連続時間ステップ t, t + 1, t + 2 のラウンドでは、vt ≥ pt と vt+1 < pt+1 のとき、3つの時間ステップのこのラウンドからの対称損失は、信頼限界の長さと真の変化率と推定変化率に比例する。 0.84
O(rt − ℓt + ǫ + ˆǫ). O(rt − lt + t + t) である。 0.85
To summarize, if in any three consecutive time steps the seller finds out pt > vt or pt+1 ≤ vt+1, then ˆǫ < ǫ and ˆǫ is doubled, and the symmetric loss obtained from time step t, t + 1, t + 2 is at most 1 each; if in any consecutive three time steps the seller observes pt ≤ vt and pt+1 > vt+1, then the symmetric loss obtained from time step t, t + 1, t + 2 is O(rt − ℓt + ǫ + ˆǫ) on average. まとめると、3つの連続時間ステップにおいて、売り手が pt > vt または pt+1 ≤ vt+1 を発見すれば、その時間ステップ t, t + 1, t + 2 から得られる対称損失は最大 1 であり、任意の連続時間ステップにおいて、売り手が pt ≤ vt および pt+1 > vt+1 を観測した場合、時間ステップ t, t + 1, t + 2 から得られる対称損失は平均 O(rt − lt + ) となる。 0.82
Since ˆǫ can only be doubled to at most 2ǫ, we know that there are O(log T ) iterations with fixed ˆǫ. 1 を 2 の倍数にしかできないので、O(log T ) の反復が固定されたようなことが分かる。 0.63
In each iteration, the time when ˆǫ is doubled, the symmetric loss obtained from the previous three time steps is O(1); in other cases, the symmetric loss obtained from the previous three time steps is constant times the length of the confidence interval plus O(ǫ + ˆǫ). それぞれのイテレーションにおいて、次の3つのタイムステップから得られる対称損失はO(1)であり、他の場合では、前の3つのタイムステップから得られる対称損失は信頼区間の長さの一定倍である。 0.68
Since in each phase of fixed ˆǫ the length of confidence interval starts with 1, and then decreases geometrically to O(ˆǫ), thus if the iteration contains a time steps, the total length of the confidence intervals is O(1 + ˆǫa) = O(1 + ǫa), and the total symmetric loss of the phase is also O(1 + ǫa). 固定区間の各々の位相において、信頼区間の長さは 1 から始まり、それから幾何的に o( ) へと減少するので、もし反復が時間ステップを含むならば、信頼区間の総長さは o(1 + ) = o(1 + ) であり、位相全体の対称損失も o(1 + ) である。 0.77
Thus the total symmetric loss of the algorithm is O(log T + T ǫ) = ˜O(T ǫ), which is ˜O(ǫ) on average. したがって、アルゴリズムの全体の対称損失は O(log T + T ) = シュオ(T )) であり、平均的には シュオ(T ) である。 0.76
Using a similar technique of checking steps as in the case of symmetric loss, we can obtain the same revenue loss as in the setting where the seller knows the changing rate, no matter whether the buyer has adversarial or stochastic value. 対称的損失の場合と同様のステップチェック手法を用いることで、買い手が逆か確率的な値であっても、売り手が変化率を知っている設定と同じ収益損失を得ることができる。 0.75
Theorem 5.2. If the buyer has adversarial values and a fixed changing rate ǫ unknown to the seller, there exists an online pricing algorithm with revenue loss ˜O(ǫ1/2). 理論5.2。 買い手が逆の値を持ち、販売者にとって未知の固定的な変動率である場合、収益損失 so(1/2) を持つオンライン価格アルゴリズムが存在する。 0.58
Further, no online algorithm can obtain a revenue loss less than Ω(ǫ1/2). さらに、オンラインアルゴリズムは ω(1/2) 未満の収益損失を得ることができない。 0.70
Proof. The tightness Ω(ǫ1/2) result is shown in Theorem 4.2, so we only need to construct an algorithm with revenue loss ˜O(ǫ1/2). 証明。 Theorem 4.2 では、厳密性 Ω(シュ1/2) の結果が示されるので、収入損失が O(シュ1/2) のアルゴリズムを構築する必要がある。 0.65
We want to apply the same technique of “checking steps” as in the pricing algorithm for symmetric loss. 対称損失に対する価格設定アルゴリズムと同じ手法を,“ステップチェック”と同じ方法で適用したいのです。 0.85
Recall that the checking steps in Algorithm 6 repeatedly price at the upper bound and the lower bound of the current confidence interval of the value of the buyer to make sure the buyer’s value is not too far away from the confidence bound. アルゴリズム6におけるチェックステップは、買い手の値の上限値と現在の信頼区間の下限の繰り返し価格で設定され、買い手の値が信頼範囲からそれほど遠くないかどうかを確認する。 0.67
However, when minimizing revenue loss, the seller cannot afford to frequently check the upper bound of the confidence interval, since each time the buyer is very likely to reject the item and incurs a huge revenue loss. しかし、売上損失を最小限に抑える場合には、買い手が商品を拒絶し、巨額の損失をもたらす可能性が非常に高いため、売り手は信頼区間の上限を頻繁にチェックすることができない。 0.69
The solution to such a problem is that we can add one checking step to each phase of Algorithm 3. このような問題の解決策は、アルゴリズム3の各フェーズに1つのチェックステップを追加できることです。 0.75
By pricing at the lower bound ℓt of the confidence interval at time t and the upper bound rt+1 of the confidence interval at time t + 1, the seller can know whether vt−1 is far away from our confidence interval [ℓt−1, rt−1] for it. 時間 t における信頼区間の下限lt と時間 t + 1 における信頼区間の上限 rt+1 の価格設定により、売り手は vt−1 が我々の信頼区間 [lt−1, rt−1] から遠く離れているかどうかを知ることができる。 0.77
Thus for a phase with m time steps and k “bad steps” when the buyer’s value is far away from the confidence interval, a random checking step can detect a bad step with probability k m . したがって、買い手の値が信頼区間から遠く離れているとき、mのタイムステップとkの“バッドステップ”を持つフェーズにおいて、ランダムチェックステップは、確率kmの悪いステップを検出することができる。 0.70
This means that after O(m) bad steps in expectation, a bad step will be detected and the algorithm will move to the next iteration with ˆǫ doubled. これは、O(m)悪いステップが期待された後、悪いステップが検出され、アルゴリズムが次のイテレーションに移動することを意味します。 0.74
The algorithm is stated as follows. アルゴリズムは次のように記述される。 0.68
10 10 0.85
英語(論文から抽出)日本語訳スコア
ALGORITHM 7: Revenue loss minimizing algorithm for adversarial buyer with unknown changing rate ǫ アルゴリズム7:未知の変動率を有する敵対的買い手の収益損失最小化アルゴリズム 0.84
ˆǫ ← 1 while ˆǫ < 1 ˆǫ ← 1 while ˆǫ < 1 0.94
T 2 do for each phase [t0 + 1, t0 + mˆǫ] of length mˆǫ = ˆǫ−1/2 do T 2度 長さ m の相 [t0 + 1, t0 + m ] に対して、n 1/2 do である。 0.71
Apply Algorithm 2 to locate the current value of the buyer in an interval [ℓt, rt] with length √ˆǫ Randomly select a t∗ ∈ [t0 + 1, t0 + mˆǫ] for each step t in the phase do アルゴリズム2を適用すれば、各ステップtの位相 do に対して、t∗ ∈ [t0 + 1, t0 + m] をランダムに選択する間隔 [lt, rt] で買い手の現在の値を見つけることができる。 0.80
if t 6= t∗ then t 6= t∗ ならば 0.79
Price at pt ← ℓt if vt < pt then vt < pt ならば pt > lt の価格。 0.63
ˆǫ ← 2ˆǫ and break (terminate the phase) 第2段階と第2段階(第2段階を終了) 0.50
end if else Price at pt ← rt if vt ≥ pt then end if 終われば その他 vt ≥ pt ならば pt > rt の価格で終了する。 0.68
ˆǫ ← 2ˆǫ and break (terminate the phase) 第2段階と第2段階(第2段階を終了) 0.50
end if [ℓt+1, rt+1] ← [ℓt − ǫ, rt + ǫ] t+1, rt+1] > [lt − s, rt + s] が終われば、 0.73
end for end for end while 終止符 終止符を打て 0.60
The algorithm first guesses ˆǫ = 1 アルゴリズムはまず は = 1 と推測する 0.75
T , and doubles ˆǫ whenever the algorithm detects a piece of evidence of ˆǫ being smaller than the true ǫ. T は、アルゴリズムが正の t よりも小さい t の証拠を検知するたびに t を倍増する。 0.65
In particular, the algorithm maintains confidence bound [ℓt, rt] that may contain the current value vt of the buyer. 特に、アルゴリズムはバイヤーの現在の値 vt を含む可能性のある信頼境界[lt, rt]を維持する。 0.70
When ˆǫ first becomes larger than ǫ (thus at most 2ǫ), the algorithm will run smoothly without triggering any break statement since 1 が 1 よりも大きくなったら(少なくとも 2 は)、アルゴリズムはブレークステートメントを発生させることなくスムーズに実行される。 0.65
vt ∈ [ℓt, rt] always holds. vt ∈ [lt, rt] は常に成り立つ。 0.91
The revenue loss is ˜O(√ˆǫ) = ˜O(√ǫ) as analyzed in Theorem 4.2. 収益損失は、Theorem 4.2で分析されたように、 .O( ) = .O( ) である。 0.69
In an iteration when ˆǫ < ǫ, firstly there is an additional O(log 1 1 の反復において、第一に O(log 1) が存在する。 0.64
ˆǫ ) = ˜O(1) loss for binary search initialization of the confidence interval compared to Algorithm 3 for the fixed ǫ setting. 二項探索による信頼区間の初期化は、固定された s 設定のアルゴリズム 3 と比較される。 0.64
Let bad event Et denote “vt ≥ rt + 2ǫ or vt < ℓt”. 悪い事象 et を "vt ≥ rt + 2 または vt < lt" と表現する。 0.76
If bad events never happen, the additional loss is at most 2ǫ per step (thus T ǫ in total), since in the analysis of Algorithm 3 it has confidence interval [ℓt, rt] rather than [ℓt, rt + 2ǫ] here. アルゴリズム3の解析では、[lt, rt + 2]ではなく信頼区間 [lt, rt] があるため、悪い事象が起こらない場合、追加損失はステップあたりの最大で2/2(合計でt )となる。 0.69
In a phase with time steps [t0 + 1, t0 + mˆǫ], if an event Et happens, then there are two cases. 時間ステップ [t0 + 1, t0 + m ] のフェーズでは、イベント Et が発生した場合、2つのケースがある。 0.85
If vt < ℓt, then it is detected when pt = ℓt, which almost surely happens. vt < lt であれば、pt = lt が検出されるが、これはほぼ確実に起こる。 0.75
If vt > rt + 2ǫ, then it is detected when pt+1 = rt+1 i.e. vt > rt + 2 であれば、pt+1 = rt+1 である。 0.75
t∗ = t, since vt+1 ≥ vt − ǫ > rt + ǫ = rt+1. t∗ = t であるため、vt+1 ≥ vt − s > rt + s = rt+1 となる。 0.75
Therefore, since t∗ is randomly selected from [t0 + 1, t0 + mˆǫ], if k events in Et0+1,··· ,Et0+mˆǫ happens, with probability k a bad event gets detected. したがって、t∗ は [t0 + 1, t0 + m ] からランダムに選択されるので、et0+1,····· ,et0+m で k の事象が起こると、確率 k では悪い事象が検出される。
訳抜け防止モード: したがって t∗ は [ t0 + 1, t0 + m ] からランダムに選択される。 Et0 + 1, · · ·, 確率 k のとき、悪い事象が検出される。
0.73
Thus, in an iteration with fixed ˆǫ < ǫ, mˆǫ when a bad event is detected, in expectation m bad events have occurred. したがって、固定された _< >, m の反復では、悪い事象が検出されると、期待された m の悪い事象が発生する。
訳抜け防止モード: したがって、悪い事象が検出されたとき、固定された > < > で m を繰り返す。 期待して 悪い事件が起きた。
0.63
Each bad event will result in additional revenue loss at most 1, thus ˜O(mˆǫ) = O(ˆǫ−1/2). 各悪い事象は、最大で1の収入損失をもたらすので、O(m)) = O(-1/2) となる。 0.66
The total contribution of revenue loss from bad events is at most Plog T = O(T 1/2) = T o(1). 悪い出来事による収益損失の合計は、Plog T = O(T 1/2) = T o(1) である。 0.77
To summarize, the total revenue loss of the algorithm is ˜O(T ǫ1/2) for Algorithm 3 with known ǫ, plus the binary search cost ˜O(1) for locating the position of vt in each iteration of different ˆǫ, plus the additional cost O(T ǫ) for having a slightly larger confidence interval in good events than Algorithm 3, plus a total revenue loss of T 1/2 from the bad events. 要約すると、アルゴリズムの総収益損失はアルゴリズム3の既知値 s と二分探索コスト so(1) であり、異なる繰り返しごとに vt の位置を特定するための二分探索コスト so(1) と、アルゴリズム3よりも良いイベントにおいてわずかに大きな信頼区間を持つ追加コスト o(t ) と、悪いイベントからのt 1/2 の合計損失である。 0.72
Sum up all the costs above we show that the total revenue loss of Algorithm 7 is T ˜O(ǫ1/2) for all time steps, thus ˜O(ǫ1/2) on average. 上述のコストをまとめると、アルゴリズム7の総収益損失は全時間ステップで T-O であり、従って平均 -O は T-O であることがわかる。 0.67
T (cid:17)−1/2 T (cid:17)-1/2 0.63
i=0 (cid:16) 2i i=0 (cid:16) 2i 0.64
11 11 0.85
英語(論文から抽出)日本語訳スコア
When the buyer has stochastic value, we can modify Algorithm 7 for an adversarial buyer such that in each phase is replaced by a phase in Algorithm 4, with the normal pricing step t 6= t∗ pricing at pt = ℓt0 − ˜O(ˆǫ−1/3), and each checking step t∗ at price pt∗ = rt0 + ˜O(ˆǫ−1/3). 購入者が確率値を持つ場合には、各フェーズにおいてアルゴリズム4の位相に置き換えられるようにアルゴリズム7を変更でき、通常の価格ステップt6=t∗をpt = lt0 − >O( >−1/3)で、各チェックステップt∗をpt∗ = rt0 + >O( >−1/3)で行う。 0.74
The analysis is almost identical to Theorem 5.2. この分析はTheorem 5.2とほぼ同一である。 0.72
Theorem 5.3. If the buyer has stochastic value and a fixed changing rate ǫ unknown to the seller, there exists an online pricing algorithm with revenue loss ˜O(ǫ2/3). 理論5.3。 買い手が確率的価値を持ち、販売者にとって未知の固定的な変動率である場合、収益損失がo(2/3)となるオンライン価格アルゴリズムが存在する。 0.60
Further, no online algorithm can obtain a revenue loss less than Ω(ǫ2/3). さらに、オンラインのアルゴリズムではΩ(2/3)未満の収益損失が得られない。 0.73
Proof. The Ω(ǫ2/3) tightness of the theorem follows from Theorem 4.3. 証明。 定理の Ω2/3) の厳密性は、Theorem 4.3 から従う。 0.67
Now we provide an algorithm with revenue loss ˜O(ǫ2/3). 現在,収益損失がo(2/3)のアルゴリズムを提供する。 0.73
The algorithm combines Algorithm 4 for stochastic buyer with known changing rate and Algorithm 7 for adversarial buyer with unknown changing rate as follows. このアルゴリズムは、確率的な買い手に対するアルゴリズム4と既知の変化率とを組み合わせ、敵の買い手に対するアルゴリズム7は以下のように変化する。
訳抜け防止モード: 確率的買い手のためのアルゴリズム4と既知の変化率を組み合わせたアルゴリズム and Algorithm 7 for adversarial buyer with unknown change rate as 。
0.88
For every iteration with guess ˆǫ in Algorithm 7, replace each phase of length ˆǫ−1/2 by a phase in Algorithm 4 with a random checking step that prices at the top of the confidence interval which tries to find the evidence of ˆǫ < ǫ. アルゴリズム7の推測値の全ての反復に対して、アルゴリズム4の位相によって長さのそれぞれの位相を置換し、信頼区間の最上部の値が s < 1/2 の証拠を見つけようとするランダムなチェックステップに置き換える。 0.81
The analysis is almost the same as the analysis for Algorithm 7. この分析は、アルゴリズム7の分析とほぼ同じである。 0.77
ALGORITHM 8: Revenue loss minimizing algorithm for stochastic buyer with unknown changing rate ǫ ALGORITHM 8: 変動率未知の確率的買い手に対する収益損失最小化アルゴリズム 0.84
ˆǫ ← 1 while ˆǫ < 1 ˆǫ ← 1 while ˆǫ < 1 0.94
T 2 do for each phase [t0 + 1, t0 + mˆǫ] of length mˆǫ = ˆǫ−2/3 do T 2度 長さ m の相 [t0 + 1, t0 + m ] に対して、n は、 0.73
Apply Algorithm 3 to locate the current value of the buyer in an interval [ℓ, r] with length √ˆǫ Randomly select a t∗ ∈ [t0 + 1, t0 + mˆǫ] for each step t in the phase do アルゴリズム3を適用すれば、位相 do の各ステップ t に対して、t∗ ∈ [t0 + 1, t0 + m] をランダムに選択する間隔 [l, r] で買い手の現在の値を見つけることができる。 0.80
if t 6= t∗ then Price at pt ← ℓ − 4ˆǫ−2/3√log T ˆǫ ← 2ˆǫ break (terminate the phase) t 6= t∗ ならば pt > l − 4 > −2/3 >log T > > 2 > の値打ち(位相を決定する)。 0.59
if vt < pt then vt < pt の場合 0.70
end if else Price at pt ← r + 4ˆǫ−2/3√log T if vt ≥ pt then ˆǫ ← 2ˆǫ break (terminate the phase) 終われば その他 vt ≥ pt ならば pt > r + 4 >−2/3 >log T の価格は > > 2 > である(位相の終了)。 0.62
end if end if end for 終われば 終われば終われば 0.63
end for end while Now we analyze the revenue loss of the algorithm. 終止符を打て 現在、アルゴリズムの収益損失を分析している。 0.67
In each iteration with changing rate estimate ˆǫ, let δ = 4ˆǫ−2/3√log T . 変化率を見積もる各反復において、δ = 4 〜 2/3 log T とする。 0.57
If ˆǫ ≥ ǫ, then the probability that vt 6∈ [ℓ − δ, r + δ] is at most 1 T 2 for each step t (as analyzed in (2)). vt 6∂ [l − δ, r + δ] の確率は、各ステップ t に対して少なくとも 1 T 2 である((2) で解析される)。 0.65
By union bound, the probability that the algorithm falsely doubles ˆǫ when ˆǫ ≥ ǫ is at most 1 T in all time steps. 結合境界によって、アルゴリズムがすべての時間ステップにおいて s ≥ s が最大 1 t であるとき、誤って s を倍にする確率は2倍になる。 0.60
Therefore the revenue loss contributed from this case is O(1), since the total revenue loss when this case happens is at most T . したがって、この場合の収益損失はO(1)であり、この場合の総収益損失は少なくともTである。
訳抜け防止モード: したがって、このケースから得られた収益損失はO(1 )である。 この場合の総売上損失は、少なくともTである。
0.75
12 12 0.85
英語(論文から抽出)日本語訳スコア
Then we assume that ˆǫ is always at most ǫ, and the rest of the analysis is identical to the analyze of Algorithm 7. すると、その解析の残りの部分は常にアルゴリズム7の解析と同一であると仮定する。
訳抜け防止モード: すると、常に > は > である、と仮定する。 そして残りの分析結果は、アルゴリズム7の分析と同一である。
0.74
In each iteration with fixed ˆǫ, when a bad event vt 6∈ [ℓ − δ, r + δ] is detected, in expectation mˆǫ = ˆǫ−2/3 bad events have occurred, thus the revenue loss contributed from bad events is ˆǫ−2/3 in an iteration with changing rate estimate ˆǫ, thus Pˆǫ ˆǫ−2/3 = O(T 2/3) in total. 固定値の反復において、悪い事象 vt 6∂ [l − δ, r + δ] が検出されたとき、予想される m で、悪事象から生じる収益損失は、変化率の推定値 t の反復で t−2/3 となるので、総じて Pt−2/3 = O(T2/3) となる。 0.77
The revenue loss for each time step with good event vt 6∈ [ℓ − δ, r + δ] is O(δ) = ˜O(ˆǫ2/3), thus ˜O(T ˆǫ2/3) = ˜O(T ǫ2/3) in total. 良い事象vt 6∂ [l − δ, r + δ] を持つ各タイムステップの収益損失は、O(δ) = >O(T >2/3) となるので、合計で >O(T >2/3) となる。 0.85
Combining the revenue loss of steps with good events, steps with bad events, and cases where ˆǫ > ǫ, we have the total revenue loss of the algorithm for all time steps is ˜O(T ǫ2/3) + O(T 2/3) + ˜O(1) = T ˜O(ǫ2/3). ステップの収益損失と良いイベントとのステップ、悪いイベントのステップと悪いイベントのケースを組み合わせることで、すべての時間ステップに対するアルゴリズムの総収益損失は、 >O(T >2/3) + O(T 2/3) + O(T 2/3) + >O(1) = T >O(>2/3) となる。
訳抜け防止モード: ステップの収益損失と良いイベント、悪いイベントのステップを組み合わせること。 とすると、全ての時間ステップにおけるアルゴリズムの総収益損失が > O(T > 2/3 ) となる。 + O(T 2/3 ) + > O(1 ) = T > O(t 2/3 ) である。
0.79
ǫ ), if the algorithm sets δ = 4ˆǫ2/3 log4 1 もしアルゴリズムが δ = 4/2/3 log4 1 とすると、 0.72
Note: The current revenue loss of the algorithm is actually O(ǫ2/3 log T ). 注:アルゴリズムの現在の収益損失はO(2/3 log T)である。 0.82
It can get improved to O(ǫ2/3polylog 1 ˆǫ , and doubles ˆǫ whenever the current total number of bad events detected for the current ˆǫ exceeds 1 m2 fraction of the current total number of time steps. o(2/3polylog 1 ) に改善でき、現在検出されている悪い事象の総数が現在の時間ステップの総数のうち1m2以上に達すると、その数を2倍にすることができる。 0.69
By Azuma’s inequality, we can argue that the probability that ˆǫ > ǫ is falsely doubled is less than 1 m2 = O(T ˆǫ2/3) in total. 吾妻の不等式により、虚に 2 倍になる確率は 1 m2 = O(T > 2/3) 以下であると主張することができる。 0.61
The revenue loss from good events is O(δ) = ˜O(ˆǫ2/3) per step. 良いイベントからの収益損失は、ステップ当たりのO(δ) = シュオ(2/3)である。 0.74
Thus the average revenue loss is ˜O(ǫ2/3) per step. したがって、平均的な収益損失は1ステップあたり /o (2/3) である。 0.58
m2t2 in step t, which will only in expectation contribute to revenue loss T m2t2 in step t, which will be contribute to revenue loss T 0.85
6 Buyer’s Changing Rate is Dynamic, Unknown 買い手6人の変動率、ダイナミックで未知 0.57
In this section, we study a more complicated setting where the buyer’s value changes in a more dynamic way. 本節では,バイヤーの価値がよりダイナミックに変化するような,より複雑な設定について検討する。 0.74
In particular, |vt+1 − vt| are upper bounded by possibly different non-increasing ǫt that are unknown to the seller. 特に、|vt+1 − vt| は、売り手にとって未知の、異なる非拡大性である。 0.70
For the symmetric-loss minimization problem with an adversarial buyer, we show that when ǫt 反対買い手による対称損失最小化問題に対して、 t のときを示す。 0.71
are non-increasing, the seller can still achieve a symmetric loss of ˜O(¯ǫ) as in the case of fixed ǫ. 増加しない場合、売り手は固定された s の場合と同様に、対称な so( ) の損失を達成することができる。 0.64
Theorem 6.1. If the buyer has adversarial values and non-increasing changing rates ǫt unknown to the seller, then there exists an online pricing algorithm with symmetric loss ˜O(¯ǫ). 理論6.1。 買い手が反対値を持ち、非増加率の変動率が売り手にとって未知である場合、対称損失 >O( ) を持つオンライン価格アルゴリズムが存在する。 0.66
Furthermore, no online algorithm can obtain a symmetric loss less than Ω(¯ǫ). さらに、オンラインアルゴリズムはΩ( ) 未満の対称損失を得ることができない。 0.82
Proof. The tightness result Ω(¯ǫ) was shown in Theorem 4.1. 証明。 厳密性の結果は Theorem 4.1 に示されている。 0.70
Now we propose an algorithm with symmetric loss ˜O(¯ǫ). 本稿では,対称損失 s(o) を持つアルゴリズムを提案する。 0.77
We propose the following algorithm for the seller that repeatedly guess the current level of changing rate at each time step. そこで, 販売者に対して, 時間ステップ毎に変化率の現在のレベルを繰り返し推測するアルゴリズムを提案する。 0.80
The algorithm starts with guessing ˆǫ = 1 2 being an estimate of ǫt, and reduce the value of the guess ˆǫ by a factor of 1 2 if in O(log T ) time steps the algorithm cannot find any evidence supporting ˆǫ < ǫt. o(log t ) の時間ステップにおいて、アルゴリズムは s = 1 2 を t の推定値として推定し、o(log t ) の時間ステップにおいて、推測 s の値を 1 2 の係数で減少させる。 0.69
Whenever the algorithm finds a piece of evidence that ˆǫ < ǫt, the algorithm repeatedly doubles ˆǫ and updates the confidence interval according to the new ˆǫ, until the evidence of ˆǫ < ǫt disappears. アルゴリズムが > < >t の証拠を見つけ出すと、アルゴリズムは > < >t の証拠が消えるまで > を何度も倍増し、新しい > に従って信頼区間を更新する。 0.60
Such a dynamic update of ˆǫ keeps the symmetric loss bounded. このような動的更新は対称損失を有界に保つ。 0.75
Below we show the algorithm in detail. 以下はそのアルゴリズムを詳細に示す。 0.73
The same as Algorithm 6 for unknown fixed changing rate, the algorithm takes a round of 3 time steps each time, and always keeps a confidence interval [ℓt, rt] for the true value of the buyer at each time step. 未知の固定変動率に対するアルゴリズム6と同様に、アルゴリズムは毎回3回のステップをとり、各時間ステップでバイヤーの真の値に対する信頼区間[lt, rt]を常に保持する。 0.74
The same as in Algorithm 1, for three consecutive time steps 3k + 1, 3k + 2, 3k + 3 in round k, the algorithm first prices at the bottom of the confidence interval, then at the top of If ˆǫ ≥ ǫ3k+1, this is going to be a the confidence interval, finally in the middle of the interval. アルゴリズム1の場合と同様に、3つの連続した時間ステップ3k + 1, 3k + 2, 3k + 3 をラウンドkで繰り返すと、アルゴリズムは最初に信頼区間の底で価格を出し、if ≥ 3k+1 の頂点で最後に信頼区間となる。 0.68
“good round” with v3k+1 ≥ p3k+1 and v3k+2 < p3k+2, so no bad evidence is found by the algorithm. v3k+1 ≥ p3k+1 と v3k+2 < p3k+2 の「良いラウンド」なので、アルゴリズムから悪い証拠は見つからない。
訳抜け防止モード: v3k+1 ≥ p3k+1 と v3k+2 < p3k+2, アルゴリズムから 悪い証拠は見つからない
0.78
If this holds for log3 T consecutive rounds, it means that the algorithm has been stable with the current ˆǫ, and the confidence interval has been O(ˆǫ3k+1) for Ω(log3 T ) steps. これがlog3 t の連続するラウンドに対して成り立つならば、アルゴリズムは現在の s で安定であり、信頼区間は ω(log3 t ) ステップに対して o(3k+1) である。 0.79
Then the algorithm decreases ˆǫ by a factor of 1 2 to try to explore the possibility that the true changing rate ǫ3k+1 is するとアルゴリズムは 1 2 の係数で t を減らし、真の変化速度が 3k+1 である可能性を探ろうとする。
訳抜け防止モード: するとアルゴリズムは 1 2 の係数で y を減少させる 3k+1 が真の変化率である可能性を探る
0.85
13 13 0.85
英語(論文から抽出)日本語訳スコア
ALGORITHM 9: Symmetric loss minimizing algorithm for adversarial buyer with unknown decreasing changing rate ǫt ALGORITHM 9: 変動率を未知とした対価購入者に対する対称性損失最小化アルゴリズム 0.77
Set confidence interval [ℓ1, r1] ← [0, 1] Set changing rate estimate ˆǫ ← 1 Let a ← 0 be the recent round without bad evidence Let s ← 0 be the number of rounds for the current ˆǫ for each round k with three consecutive time steps 3k + 1, 3k + 2, 3k + 3 do 信頼区間 [l1, r1] , [0, 1] をセットする 変化率推定値 s, 1 を悪い証拠のない最近のラウンドとし、s , 0 を3つの連続した時間ステップ 3k + 1, 3k + 2, 3k + 3 do を持つ各ラウンド k に対して現在の s のラウンド数とする。 0.77
2 s ← s + 1 Set price p3k+1 ← ℓ3k+1 Set price p3k+2 ← r3k+2 = r3k+1 + ˆǫ Set price p3k+3 ← ℓ3k+1+r3k+1 if the seller finds v3k+1 ≥ ℓ3k+1 and v3k+2 < r3k+2 then 2 もし売り手が v3k+1 ≥ l3k+1 と v3k+2 < r3k+2 を見つけたら、 設定価格 p3k+2 = r3k+1 を設定。 0.85
2 a ← k if v3k+3 < p3k+3 then 2 もし v3k+3 < p3k+3 なら 0.76
else [ℓ3k+4, r3k+4] ← [ℓ3k+1 − 3ˆǫ, p3k+3 + ˆǫ] [ℓ3k+4, r3k+4] ← [p3k+3 − ˆǫ, r3k+1 + 3ˆǫ] その他 [l3k+4, r3k+4] > [l3k+1 − 3 , p3k+3 + 3 ] [l3k+4, r3k+4] > [p3k+3 − , r3k+1 + 3 ] 0.58
ˆǫ ← ˆǫ/2 end if ˆǫ ← ˆǫ/2 終われば 0.62
else end if if s > log3 T and ˆǫ > 1 その他 終端 if s > log3 t かつ s > 1 である。 0.70
T then ˆǫ ← 2ˆǫ [ℓ3k+4, r3k+4] ← [ℓ3a+1 − (3k + 3 − 3a)ˆǫ, r3a+1 + (3k + 3 − 3a)ˆǫ] それなら r3k+4, r3k+4] ] [l3a+1 − (3k + 3 − 3a) ], r3a+1 + (3k + 3 − 3a) ] 0.63
end if end for currently much smaller than ˆǫ. 終われば終われば 現在よりはるかに小さい。 0.64
However, when ˆǫ < ǫ3k+1, the confidence interval may expand not enough to contain the true value of the buyer, so there is possibility that this round becomes a “bad round” with v3k+1 < p3k+1 or v3k+2 ≥ p3k+2. しかし、 > < > 3k+1 の場合、信頼区間は買い手の真価を含まないほど拡大するので、このラウンドは v3k+1 < p3k+1 または v3k+2 ≥ p3k+2 の「バッドラウンド」となる可能性がある。 0.67
In this case, the algorithm doubles ˆǫ. この場合、このアルゴリズムは2倍になる。 0.76
The confidence bound is not accurate as ˆǫ < ǫ3k+1 previously. 信頼境界は以前のように正確ではない。 0.48
However, if the new ˆǫ ≥ ǫ3k+1, the algorithm gets the correct confidence bound [ℓ3a+1, r3a+1] in the previous good round a, and calculates a correct confidence bound [ℓ3k+4, r3k+4] ← [ℓ3a+1 − (3k + 3− 3a)ˆǫ, r3a+1 + (3k + 3− 3a)ˆǫ] for time step 3k + 4, since the buyer’s value cannot change more than (3k + 3− 3a)ǫ3a+1 < (3k + 3− 3a)ˆǫ in 3k + 3− 3a steps. しかし、このアルゴリズムは前回のグッドラウンド a において正しい信頼境界 [l3a+1, r3a+1] を取得し、時間ステップ 3k + 4 に対して正しい信頼境界 [l3k+4, r3k+4] を計算し、その値が 3k + 3- 3a の 3k + 3- 3a の 3k + 3- 3a の 3k + 3- 3a の 3k + 3- 3a の 3k + 3- 3a の 3k + 3- 3a のステップでは変化しない。 0.78
Now we analyze the performance of the algorithm. そこで,本アルゴリズムの性能を解析する。 0.81
Partition time horizon [T ] to log T intervals I1, I2,··· , Ilog T , such that for each time interval Ii and time t ∈ Ii, ǫt ∈ (2−i, 2−i+1]. 分割時間地平線 [T] からログT間隔 I1, I2,··· , Ilog T へ、各時間間隔 Ii と時刻 t ∈ Ii に対して、t ∈ (2−i, 2−i+1] が成立する。 0.82
In other words, each time interval contains time steps with similar changing rate. 言い換えれば、各時間間隔は、同じ変化率の時間ステップを含む。 0.74
For any time interval Ii, let ǫ∗i = 2−i+1. 任意の時間区間 ii に対して、s∗i = 2−i+1 とする。 0.56
We argue that in time interval Ii the symmetric loss is O(log4 T + |Ii|ǫ∗i = O(log4 T +Pt∈Ii ǫt), and the theorem follows immediately by taking the average of the symmetric loss in all time intervals. 時間区間 ii において対称損失は o(log4 t + |ii| ∗i = o(log4 t +ptسii ) であり、定理はすべての時間区間における対称損失の平均を取ることによって直ちに従う。 0.78
Notice that in Ii, the algorithm may start with ˆǫ > ǫ∗i , then decrease gradually to reach ˆǫ = ǫ∗i . なお、Ii では、アルゴリズムは > > > > > > から始まり、その後徐々に減少して > = > となる。 0.64
The symmetric loss in this process is O(log4 T ), since there will be no bad rounds, and ˆǫ will stay at each ˆǫ > ǫ∗i for at most O(log3 T ) steps, thus reduce to ǫ∗i in O(log4 T ) steps. この過程における対称的損失は o(log4 t ) である、なぜならば、悪ラウンドは存在せず、全ての o(log3 t ) ステップに対して s は各 s > ∗i に留まり、したがって o(log4 t ) ステップでは s∗i に減少するからである。 0.70
Now we analyze what happens when ˆǫ ≤ ǫ∗i . では、このとき何が起こるかを分析する。 0.68
For any bad round k, since it is at most b rounds from the closest good round a = k − b with confidence interval [ℓ3a+1, r3a+1], all of the values and prices in the round are bounded by interval 悪いラウンド k に対して、最も近い良ラウンド a = k − b から最も近い b ラウンドであり、信頼区間 [l3a+1, r3a+1] を持つため、ラウンドのすべての値と価格は間隔で境界づけられる。
訳抜け防止モード: 悪い円 k に対して、それは最も近い良い円 a = k − b から、信頼区間 [l3a+1, r3a+1] の b ラウンドである。 ラウンドのすべての値と価格は 間隔で区切られている
0.77
14 14 0.85
英語(論文から抽出)日本語訳スコア
[ℓ3a+1 − 3bǫ∗i , r3a+1 + 3bǫ∗i ] ⊆ [ℓ3a+1 − 3 log T ǫ∗i , r3a+1 + 3 log T ǫ∗i ], since in round a all of the values and confidence boundaries are bounded by [ℓ3a+1−O(1)ǫ∗i , r3a+1 +O(1)ǫ∗i ]. ラウンドにおいて、すべての値と信頼境界は [l3a+1−o(1)〜∗i , r3a+1 +o(1)*i , r3a+1 +o(1)*i ] で区切られるからである。 0.70
Thus the symmetric loss for any bad round that is b rounds away from a good round is O(r3a+1− ℓ3a+1)+ O(ǫ∗i )+ 6 log T ǫ∗i = O(log T ǫ∗i ). したがって、b が良いラウンドから遠ざかる悪ラウンドの対称損失は o(r3a+1−l3a+1)+ o(*i )+ 6 log t ∗∗i = o(log t )∗i である。 0.77
As analyzed in Algorithm 6 for static changing rate, in a good round k without bad evidence, the symmetric loss in the round is proportional the length of the confidence interval plus the true changing rate ǫ3k+1 and the estimated changing rate ˆǫk for the round, i.e. 静的な変化率を求めるアルゴリズム6で分析されたように、悪い証拠のない良い円 k において、ラウンドの対称損失は信頼区間の長さと真の変化率 ^3k+1 と、ラウンドに対する推定変化率 ^k に比例する。 0.82
O(r3k+1 − ℓ3k+1 + ˆǫk + ǫ3k+1). o(r3k+1 − l3k+1 + s3k+1) である。 0.55
In such a good round, since ˆǫk, ǫ3k+1 and the length of confidence interval r3k+1 − ℓ3k+1 are all O(ǫ∗i ), the good round has symmetric loss O(ǫ∗i ) ≤ cǫ∗i for some constant c. The same as in the analysis of Algorithm 10 for the revenue loss setting, we can use the loss of good rounds to compensate the loss of the bad rounds. そのような良いラウンドでは、 シュク, シュ3k+1 と信頼区間 r3k+1 − l3k+1 の長さがすべて O(シュンチイ) であるため、ある定数 c に対して良いラウンドは対称損失 O(シュンチイ) ≤ c ∗i を持つ。
訳抜け防止モード: そのような良いラウンドでは、 シュク, シュ3k+1 と信頼区間 r3k+1 − l3k+1 の長さがすべて O(シュ∗i ) であるからである。 良いラウンドは、ある定数 c に対して対称的な損失 O(*i ) ≤ c ∗i を持つ。 良いラウンドの損失を 悪いラウンドの損失を補うためです
0.68
We argue that the per-step symmetric loss in Ii is ≤ 2cǫ∗i . Ii のステップごとの対称損失は ≤ 2c ∗i であると主張する。 0.65
Between two blocks of consecutive bad rounds, there are at least O(log3 T ) good rounds. 2ブロック連続する悪いラウンドの間には、少なくともO(log3 T )良いラウンドがある。 0.72
In a block of bad rounds, the symmetric loss is O(log T ǫ∗i ) more than the expected 2cǫ∗i loss per step, thus O(log2 T ǫ∗i ) more in total in the block of bad rounds. 悪い丸のブロックでは、対称的損失はステップ当たりの予想2c\∗i損失よりも O(log T >∗i ) であり、したがって、悪い丸のブロック全体で O(log2 T >∗i ) はより大きい。 0.73
At the same time, In the O(log3 T ) consecutive good rounds, the symmetric loss is cǫ∗i less than the expected 2cǫ∗i loss per step, thus O(log3 T ǫ∗i ) less in total in the block of good rounds. 同時に、O(log3 T ) の連続した良いラウンドでは、対称的な損失はステップ当たりの 2c-*i の損失よりも c-∗i が小さいので、良いラウンドのブロック全体で O(log3 T ) が小さくなる。 0.78
Combine the cases above for good rounds and bad rounds, we know that in time interval Ii with ˆǫ ≤ ǫ∗i , the symmetric loss is ≤ cǫ∗i in each round on average. 上述した良い円と悪い円のケースを組み合わせると、Ii の時間区間において、対称的な損失は各ラウンドの平均で ≤ c ∗i となることが分かる。 0.73
This finishes the proof of the total symmetric loss in the time interval being O(log4 T + |Ii|ǫ∗i = O(log4 T +Pt∈Ii Thus the total symmetric loss of the algorithm is Pi≤log T O(log4 T + Pt∈Ii O(1)Pt∈Ii これにより、時間間隔における全対称損失の証明が o(log4 t + |ii|\∗i = o(log4 t +ptftpii) となるので、アルゴリズム全体の対称損失は piftplog t o(log4 t + ptسii o(1)ptftpii となる。 0.70
ǫt). ǫt) = T o(1) + の意)。 t) = t o(1) + である。 0.72
ǫt = T ˜O(¯ǫ). t(t) は t(t) である。 0.56
For the revenue loss minimization problem for an adversarial buyer, we can also recover the results in previous sections, even when ǫt are unknown to the seller. 広告購入者に対する収益損失の最小化問題に対して,販売者に対して不確かである場合であっても,先行部での結果を回収することができる。 0.62
We describe the result and the algorithm in detail here. 本稿では,結果とアルゴリズムについて詳述する。 0.82
Theorem 6.2. If the buyer has adversarial values and non-increasing changing rates ǫt unknown to the seller, there exists an online pricing algorithm with revenue loss ˜O(¯ǫ1/2), here ¯ǫ = 1 t=1 ǫt. 理論6.2。 買い手が相手の値を持ち、非増加率の変動率が売り手にとって未知である場合、収益損失を減らしたオンライン価格アルゴリズムが存在している。 0.61
Further, no online algorithm can obtain a revenue loss less than Ω(¯ǫ1/2). さらに、オンラインのアルゴリズムではΩ(~1/2)未満の収益損失が得られない。 0.69
T PT Proof. The Ω(¯ǫ1/2) tightness result has been shown in Theorem 4.2 with all ǫt being identical. TPT 証明。 Ω( s1/2) の厳密性の結果は Theorem 4.2 で示され、すべての t は同一である。 0.56
Now we show that there exists an algorithm with revenue loss ˜O(¯ǫ1/2). ここでは,収益損失がゼロとなるアルゴリズムが存在することを示す。 0.63
When ǫt decreases, the seller needs to detect such a trend timely, otherwise the loss of each t が減少すると、売り手はそのような傾向をタイムリーに検出する必要がある。 0.66
time step is going to be not comparable to Pt ǫt. time stepはpt stに匹敵するものではない。 0.67
We propose the following algorithm for the seller, that repeatedly guesses the current level of changing rate at each time step. 本稿では,販売者に対して,各段階における現在の変化率を繰り返し推定するアルゴリズムを提案する。 0.80
The algorithm starts with guessing ˆǫ = 1 2 being an estimate of ǫt, and reduces the value of the guess ˆǫ by a factor of 1 2 if in several time steps the algorithm cannot find any evidence supporting ˆǫ < ǫt. アルゴリズムは、推測 s = 1 2 を t の推定値とすることから始まり、数回のステップにおいて、アルゴリズムが s = 1 2 を裏付ける証拠を見つけることができない場合、1 2 の係数で推測 s の値を減少させる。 0.77
Whenever the algorithm finds evidence that supports ˆǫ < ǫt, the algorithm repeatedly doubles ˆǫ and updates the confidence interval according to the new ˆǫ, until the evidence of ˆǫ < ǫt disappears. アルゴリズムが > < >t を支持する証拠を見つけると、アルゴリズムは > < >t の証拠が消えるまで、新しい > < < >t を満たす信頼区間を何度も倍増し、更新する。 0.56
Such a dynamic update of ˆǫ keeps the revenue loss bounded. このような動的更新は、収益損失を束縛する。 0.70
To be more specific, ˆǫ decreases by a factor of 1 より具体的に言うと s は 1 の因子で減少します 0.81
2 if the seller has not observed any evidence of ˆǫ < ǫt for long enough time. 2) 売り手が十分な時間の間,<>t の証拠を観測していない場合。 0.73
In particular, the algorithm tries to run ˆǫ−1/2 identical phases in Algorithm 7, and will halve ˆǫ when the buyer passes all checking steps. 特にアルゴリズムはアルゴリズム7で1/2の同一のフェーズを実行し、買い手が全てのチェックステップをパスしたとき、 を半分にしようとする。 0.69
The algorithm is described in Algorithm 10. アルゴリズムはアルゴリズム10に記述されている。 0.70
15 15 0.85
英語(論文から抽出)日本語訳スコア
ALGORITHM 10: Revenue loss minimizing algorithm for adversarial buyer with unknown decreasing changing rate ǫt ALGORITHM 10: 変動率の未知な対価購入者に対する収益損失最小化アルゴリズム 0.84
ˆǫ ← 1 while true do 2 1 は真である。 2 0.63
for ˆǫ−1/2 phases of length mˆǫ = ˆǫ−1/2 do 長さ m の-1/2 相に対して、m は-1/2 である。 0.38
At the beginning of phase [t0 + 1, t0 + mˆǫ], apply Algorithm 2 to locate the current value of the buyer in an interval [ℓt, rt] with length √ˆǫ Randomly select a t∗ ∈ [t0 + 1, t0 + mˆǫ] for each step t in the phase do 位相 (t0 + 1, t0 + m)] の開始時にアルゴリズム2を適用して、位相 t の各ステップ t に対して t∗ ∈ [t0 + 1, t0 + m)] をランダムに選択した間隔 [lt, rt] でバイヤーの現在の値を求める。 0.84
if t 6= t∗ then t 6= t∗ ならば 0.79
Price at pt ← ℓt if vt < pt then vt < pt ならば pt > lt の価格。 0.63
end if ˆǫ ← 2ˆǫ and go back to the beginning of the while loop (terminate the ˆǫ−1/2 phases) 終われば そして、時間ループの始まりに戻ります(-1/2 相を終了します) 0.63
else Price at pt ← rt if vt ≥ pt then end if その他 vt ≥ pt ならば pt > rt の価格で終了する。 0.69
ˆǫ ← 2ˆǫ and go back to the beginning of the while loop (terminate the ˆǫ−1/2 phases) そして、時間ループの始まりに戻ります(-1/2 相を終了します) 0.60
end if [ℓt+1, rt+1] ← [ℓt − ǫ, rt + ǫ] t+1, rt+1] > [lt − s, rt + s] が終われば、 0.73
end for end for ˆǫ ← ˆǫ/2 if ˆǫ > 1 終止符 終止符 ˆǫ ← ˆǫ/2 if ˆǫ > 1 0.65
T end while i later. T 最後まで 私は 後で 0.67
˜O(ˆǫ−1/2) = ˜O((ǫ∗i )−1/2) in total. 総和は O(n-1/2) = O(n-1/2) である。 0.61
Now we analyze the performance of the algorithm. そこで,本アルゴリズムの性能を解析する。 0.81
Partition the time horizon [T ] to log T intervals I1,··· , Ilog T , such that for each time interval Ii and time t ∈ Ii, ǫt ∈ (2−i, 2−i+1]. T 間隔 I1,··· , Ilog T に時間水平線 [T ] を分割し、時間間隔 Ii と時間 t ∈ Ii に対して、t ∈ (2−i, 2−i+1] を割る。 0.86
Let ǫ∗i = 2−i+1. 2-i+1 とする。 0.56
We argue that in time interval Ii the total revenue loss is ˜O((ǫ∗i )−1/2 + |Ii|(ǫ∗i )1/2). 時間区間 ii において、総収益損失は、o((*i )−1/2 + |ii|(*i )1/2 である。 0.69
In interval Ii the algorithm may start with ˆǫ > ǫ∗i , and then gradually decreases to reach ˆǫ = ǫ∗i In this process, the revenue loss is ˜O(1) in each phase and never become larger than ǫ∗i as shown in the proof of Theorem 5.2, thus ˜O(ˆǫ−1/2) loss for every value ˆǫ > ǫ∗i and at most Pˆǫ>ǫ∗ Now we show that after ˆǫ reaches ǫ∗i , the revenue loss is ˜O((ǫ∗i )1/2) per step on average. 区間 ii において、この過程において、アルゴリズムは次から次へと減少し、次の過程では、各段階において、収入損失は、o(1) となり、定理 5.2 の証明で示されるように、*i よりも大きくなることはない。
訳抜け防止モード: 区間 Ii において、アルゴリズムは s > s*i から始めることができる。 徐々に減少し この過程において、次の点に到達する。 収益損失は各段階において ^O(1 ) であり、定理 5.2 の証明に示されるように ^∗i よりも大きくなることはない。 したがって、すべての値 t > t と P > t の t の t を t から t に減らす。 1ステップあたりの収入損失は、平均して1/2O(()∗i )である。
0.68
First we study the revenue loss from each ˆǫ−1/2 phases with changing rate ˆǫ. まず,各段階毎の収益損失について,その変動率で検討する。 0.65
The same as in previous proofs, a piece of “bad evidence”, or a piece of evidence of ˆǫ < ǫ is the event of vt < pt in a non-checking step t 6= t∗ or vt ≥ pt in a checking step t = t∗. 以前の証明と同様に、「悪い証拠」あるいは「悪い証拠」の断片は、チェックしないステップ t 6= t∗ における vt < pt またはチェックしないステップ t = t∗ における vt < pt の事象である。 0.75
If no evidence of ˆǫ < ǫ is detected, then the revenue loss is at most some constant c = ˜O(1) in each phase, thus cˆǫ−1/2 for the ˆǫ−1/2 phases with ˆǫ−1 time steps. もし証拠が検出されないならば、収益損失は各々のフェーズにおいて定数 c = so(1) であり、従って s−1 の時間ステップを持つ s −1/2 の位相に対して cs−1/2 となる。 0.66
We also observe that if we run the algorithm with changing rate ǫ∗i , the revenue loss of such ˆǫ−1 time steps is going to be c(ǫ∗i )1/2 per step thus cˆǫ−1(ǫ∗i )1/2 in total. また、このアルゴリズムを変化速度で実行すれば、そのような ^−1 の時間ステップの収益損失は1ステップ当たり c( ^*i )1/2 となるので、合計 c ^−1( ^∗i )1/2 となる。 0.67
We argue that the per-step revenue loss in Ii is at most 2c(ǫ∗i )1/2. Ii のステップごとの収益損失は、少なくとも 2c(*i )1/2 であると主張する。 0.58
In ˆǫ−1/2 phases where no bad evidence is found, the algorithm actually gets c(ˆǫ−1(2ǫ∗i )1/2 − ˆǫ1/2) > cˆǫ−1(ǫ∗i )1/2 > cˆǫ−1/2 less revenue loss than the expected benchmark (2c(ǫ∗i )1/2 per step). 悪質な証拠が見出されない半半期において、アルゴリズムは実際に期待される平均値(2c(\∗i )1/2)よりも小さい収益損失 (2c(\∗i )1/2) となる。 0.65
In any phase with estimated changing rate ˆǫ where a piece of bad evidence is found, as shown in the analysis of Algorithm 7, in expectation mˆǫ = ˆǫ−1/2 steps with value out of confidence bound has occurred, and contributes at most ˆǫ−1/2 total additional revenue loss more than the normal 2c(ǫ∗i )1/2 loss per step. アルゴリズム7の解析で示されるように、推定された変動率のいずれの段階でも、アルゴリズム7の分析で示されるような悪質な証拠が見つかると、期待値が信頼度に満たないステップが発生し、平均的な2c(*i)1/2の損失よりも多く、−1/2の合計的な収入損失が寄与する。 0.61
Therefore, every time the algorithm goes through ˆǫ−1/2 phases without bad evidence, the algorithm has at したがって、アルゴリズムが悪証拠を伴わずに シュ=1/2 段階を経るたびに、アルゴリズムは、 0.71
16 16 0.85
英語(論文から抽出)日本語訳スコア
least cˆǫ−1/2 less revenue loss than expected; every time the algorithm with estimated changing rate ˆǫ finds a phase with a piece of bad evidence, the algorithm has at most cˆǫ−1/2 more revenue loss than expected. 推定された変化率のアルゴリズムが、悪質な証拠の1つでフェーズを見つけるたびに、アルゴリズムは、予想よりも最大でc-1/2以上の収益損失を発生させる。 0.73
Observe that in each iteration with ˆǫ decreases by 1 2 no bad evidence is detected, and bad evidence is found in each iteration with ˆǫ getting doubled. 1 が 1 2 に減少する各イテレーションでは、悪い証拠は検出されず、各イテレーションで悪い証拠が発見され、 は 2 倍になる。 0.69
Thus the number of iterations with no bad evidence being detected is at least the number of iterations with bad evidence found, which means that the algorithm has no more revenue loss than the expected 2c(ǫ∗i )1/2 per step. したがって、悪い証拠が検出されない反復の数は、少なくとも悪い証拠が見つかった反復の数であり、これはアルゴリズムが予想される2c( ∗i )1/2ステップよりも収益損失がほとんどないことを意味する。 0.76
To summarize, in Ii after ˆǫ reaches ǫ∗i , the revenue loss is ˜O((ǫ∗i )1/2) per step. 要約すると、Ii の > の後の収入損失は、ステップ当たりの収入損失は >O((>*i )1/2) となる。
訳抜け防止モード: まとめると ii が s∗i に達した後、収益損失はステップ 1/2 に対して so((\∗i ) 1/2 ) となる。
0.65
Above reasoning shows that in each time interval Ii, the total revenue loss is ˜O((ǫ∗i )−1/2 + 上述の推論は、各時間間隔 ii において、総収益損失が o((*i )−1/2 + であることを示している。
訳抜け防止モード: 以上の推論が示す。 Ii の各時間間隔で、総収入損失は ^O((\∗i ) −1/2 +
0.79
|Ii|(ǫ∗i )1/2). i|(i)1/2 である。 0.67
Sum up over all i, the total revenue loss of all time steps is 合計すると、すべての時間ステップの合計収益損失は 0.62
Xi≤log T ˜O((ǫ∗i )−1/2 + |Ii|(ǫ∗i )1/2) |Ii|(ǫ∗i )1/2 Xi≤log T i(i)-1/2) |ii|(i)1/2) |ii|(i)1/2 0.70
= ˜O(T 1/2) + ˜O(1)Xi ≤ T o(1) + ˜O(1)Xi = >O(T 1/2) + >O(1)Xi ≤ T o(1) + >O(1)Xi 0.93
|Ii|¯ǫ1/2 = ˜O(T ¯ǫ1/2), |Ii| ^1/2 = ^O(T ^1/2) 0.50
Here the inequality is by Cauchy-Schwarz. ここでの不等式はコーシー=シュワルツ(Cauchy-Schwarz)による。 0.33
Thus the average revenue loss of each time step is ˜O(¯ǫ1/2). したがって、各時間ステップの平均収益損失は、o( 1/2) である。 0.70
Such a result can also be extended for a stochastic buyer. このような結果は確率的購入者にも拡張できる。 0.73
Theorem 6.3. If the buyer has stochastic value and non-increasing changing rate ǫt unknown to the seller, then there exists an online pricing algorithm with revenue loss ˜O(¯ǫ2/3), here ¯ǫ = 1 t=1 ǫt. 理論6.3。 買い手が確率的価値を持ち、非増加率の変動率が売り手にとって未知である場合、収益損失がゼロとなるオンライン価格アルゴリズムが存在する。
訳抜け防止モード: 理論6.3。 買い手が確率的価値と非-増加率を持つ場合、売り手は不詳である。 オンラインの料金アルゴリズムでは、収益損失がゼロになる。 t = 1 t = 1 t である。
0.64
Furthermore, no online algorithm can obtain a revenue loss less than Ω(¯ǫ2/3). さらに、オンラインのアルゴリズムでは、Ω(2/3)未満の収益損失が得られない。 0.68
Proof. The Ω(¯ǫ2/3) tightness follows from Theorem 4.3. 証明。 Ω2/3) の強みは Theorem 4.3 から従う。 0.66
The algorithm for ˜O(¯ǫ2/3) revenue loss can be obtained by combining Algorithm 8 for stochastic buyer with unknown fixed changing rate, and Algorithm 10 for adversarial buyer with unknown decreasing changing rate. 確率的購入者に対するアルゴリズム8を未知の一定変化率で組み合わせ、対向的購入者に対するアルゴリズム10を未知の変動率で組み合わせることにより、収益損失に対するアルゴリズムを得ることができる。 0.79
In particular, we replace each iteration of fixed ˆǫ with ˆǫ−1/2 phases of length ˆǫ−1/2, by ˆǫ−2/3 phases of length ˆǫ−2/3 in Algorithm 8. 特に、アルゴリズム8では、固定された各々の反復を長さの−1/2相、長さの−−1/2相、長さの−−2/3相に置き換える。 0.53
T PT The analysis of the algorithm is identical to the analysis of Algorithm 10. TPT アルゴリズムの分析は、アルゴリズム10の分析と同一である。 0.54
Partition the time horizon [T ] to intervals I1,··· , Ilog T /2, each with ǫt ∈ (2−i, 2−i+1 = ǫ∗i ] for any t ∈ Ii. 時間地平線 [T ] を区間 I1,··· , Ilog T /2 に分割し、任意の t ∈ Ii に対して t ∈ (2−i, 2−i+1 = s∗i ) とする。 0.76
We can prove that the total revenue loss in each time interval is ˜O((ǫ∗i )−2/3 + |Ii|(ǫ∗i )2/3). 各時間間隔における総収益損失は、o((*i )−2/3 + |ii|(*i )2/3) であることが証明できる。 0.66
The total revenue loss of the algorithm is アルゴリズムの総収入損失は 0.59
Xi≤log T ˜O((ǫ∗i )−2/3 + |Ii|(ǫ∗i )2/3) |Ii|(ǫ∗i )2/3 |Ii|(cid:18)Pi |Ii|ǫ∗i Xi≤log T 2/3 |Ii|(→*i )2/3 |Ii|(→∗i )2/3 |Ii|(→*i )2/3 |Ii|(→18)Pi |Ii|\∗i 0.65
= ˜O(T 2/3) + ˜O(1)Xi ≤ T o(1) + ˜O(1)Xi = ˜O(T ¯ǫ2/3), o(t2/3) + (o(1)xi ≤ t o(1) + (o(1)xi) = (t2/3)) である。 0.82
Pi |Ii| (cid:19)2/3 Pi |Ii| (cid:19)2/3 0.63
Here the inequality follows from H¨older’s inequality and ¯ǫ = 1 loss of each time step is ˜O(¯ǫ2/3). ここでの不等式は、H シュルダーの不等式から導かれるもので、各時間ステップの損失は ^O( ^2/3) である。 0.47
T Pt ǫt. Thus the average revenue 略称はT。 平均的な収入は 0.63
17 17 0.85
英語(論文から抽出)日本語訳スコア
For the revenue loss minimization problem, it is hard to obtain positive results when the changing rates ǫt are arbitrary, since setting a price slightly higher than the true value in a step can result in a huge revenue loss. 収益損失最小化問題では、ステップの真の価値より少し高い価格を設定すると、大きな収益損失につながるため、変更率 t が任意である場合には、肯定的な結果を得ることができない。 0.73
Surprisingly, even if ǫt for each time step can change arbitrarily, we can still achieve the ˜O(¯ǫ) loss in previous sections, only losing a tiny O(log T ) factor. 驚くべきことに、各時間ステップに対する st が任意に変化しても、前のセクションで so( ) の損失を達成でき、小さな o(log t ) 因子を失うだけである。 0.68
Theorem 6.4. If the buyer has adversarial values and dynamic changing rate ǫt unknown to the seller, there exists an online pricing algorithm with symmetric loss ˜O(¯ǫ log T ) for ¯ǫ = 1 Further, no online algorithm can obtain a symmetric loss less than Ω(¯ǫ). 理論6.4。 買い手が売り手に対して未知な対向値と動的変化率を持つとすると、a = 1 に対して対称的損失 >O( > log T ) を持つオンライン価格アルゴリズムが存在し、さらに、オンラインアルゴリズムは Ω( > log T ) 未満の対称的損失を得ることができない。 0.65
T Pt∈[T ] ǫt. t pt pt[t ] である。 0.55
Proof. Suppose for a moment that the algorithm is allowed to set multiple pricing queries for a single time step. 証明。 アルゴリズムが1回のステップで複数の価格設定クエリを設定できることを少し考えてみましょう。 0.66
The algorithm maintains a correct confidence interval [ℓt, rt] that contains the value vt of the buyer at each time step. アルゴリズムは、各時間ステップでバイヤーの値vtを含む正しい信頼区間[lt, rt]を維持する。 0.67
At time t + 1, the seller does not know the exact value change vt+1 − vt. 時刻 t + 1 において、売り手は正確な値変化 vt+1 − vt を知らない。 0.85
Furthermore, she also does not know a bound of the value change ǫt ≥ |vt+1 − vt|. さらに、彼女は値の値変化の束縛が |vt+1 − vt| であることも知らない。 0.70
However, the seller can try to price at ℓt − δj and rt + δj repeatedly for every j and δj = 2jT −1. しかし、売り手はすべての j に対して lt − δj と rt + δj を繰り返し値付けし、δj = 2jT −1 となる。 0.77
When j has increased such that the algorithm finds that ℓt − δj < vt+1 < rt + δj, the seller can then price at ℓt+rt , rt + δj]. j が増加して lt − δj < vt+1 < rt + δj となると、売り手は lt+rt , rt + δj] で価格を設定できる。 0.81
Let at = rt − ℓt be the length of the confidence interval at time t, then at+1 = 1 2 at + δj. t = rt − lt を t における信頼区間の長さとし、 + δj において +1 = 1 2 とする。 0.83
Since vt+1 and all prices at this time step are in [ℓt − δj, rt + δj], thus the symmetric loss of each query is at most 2at + 2δj = 4at+1. vt+1 とこの時点での全ての価格は [lt − δj, rt + δj] であるため、各クエリの対称損失は最大 2at + 2δj = 4at+1 である。 0.80
Also notice that vt+1 6∈ [ℓt − δj/2, rt + δj/2] since the algorithm does 2 as the buyer’s value must has changed by δj not stop at j − 1 at time t, thus ǫt > δj 2 at this step. また、アルゴリズムが 2 となると、買い手の値が δj が t のとき j − 1 で止まらなければならず、したがって δj > δj 2 であるから、vt+1 6∂ [lt − δj/2, rt + δj/2] が変化する。 0.76
Therefore the symmetric loss of each time step t + 1 is at most 4at+1, while at+1 ≤ 1 2 at + ǫt. したがって、ステップ t + 1 の各時間の対称損失は最大 4at+1 であり、一方 at+1 ≤ 1 2 at + st である。 0.78
Then the total symmetric loss of the algorithm is ≤ 4Pt∈[T ] at ≤ 8Pt∈[T ] ǫt, which implies the average symmetric loss is O(¯ǫ). するとアルゴリズムの全対称損失は ≤ 8Pt~[T ] で ≤ 4Pt~[T ] であり、これは平均対称損失が O( ) であることを意味する。 0.87
to get a new correct confidence interval [ℓt+1, rt+1] ← [ℓt − δj, ℓt+rt to get a new correct confidence interval [lt+1, rt+1] > [lt − δj, lt+rt 0.83
] or [ ℓt+rt ]または[lt+rt] 0.56
2 2 2 However, we are not allowed to have multiple pricing queries for the same value. 2 2 2 しかし、同じ値に対して複数の価格クエリを持つことは許されません。 0.81
The key observation to be proved in this section is that when we serialize the pricing queries in such an algorithm with at most k queries per step, the symmetric loss only increases by a factor of O(k). この節で証明すべき重要な観察は、1ステップあたりの最大kクエリでそのようなアルゴリズムで価格クエリをシリアライズする場合、対称損失はO(k)因子によってのみ増加することである。 0.82
Since the above algorithm has at most O(log T ) = ˜O(1) pricing queries in each step, the serialized algorithm’s symmetric loss only increases by ˜O(1). 上記のアルゴリズムは、各ステップでo(log t ) = so(1) の値付けクエリを持つため、直列化されたアルゴリズムの対称損失は so(1) でのみ増加する。 0.82
The serialized algorithm runs as follows. 直列化アルゴリズムは次のように実行される。 0.57
The algorithm runs in phases, with each phase i having time steps [ti+1, ti+1] for a to-be-determined stopping time ti+1. アルゴリズムはフェーズiで動作し、各フェーズiは停止時間ti+1の時間ステップ[ti+1, ti+1]を有する。 0.76
In each phase, the algorithm starts with an estimated confidence interval [ℓti+1, rti+1], and repeatedly set prices ℓti+1− δj and rti+1 + δj for every two time steps. 各フェーズにおいて、アルゴリズムは推定信頼区間 [lti+1, rti+1] から始まり、2段階ごとにlti+1− δj と rti+1 + δj を繰り返し設定する。 0.75
If the algorithm observes vti+2j+1 ≥ ℓti+1 − δj and vti+2j+2 < rti+1 + δj, trying to halve the length the phase stops at time ti+1 = ti + 2j + 3 with price pti+1 = of the confidence interval. アルゴリズムが vti+2j+1 ≥ lti+1 − δj と vti+2j+2 < rti+1 + δj を観測すると、ti+1 = ti + 2j + 3 で位相が停止する。 0.89
ℓti+1+rti+1 lti+1+rti+1 0.29
2 Now we analyze the symmetric loss of each phase Ii = [ti + 1, ti+1]. 2 さて、各位相 ii = [ti + 1, ti+1] の対称損失を解析する。 0.82
The first observation is that at each time step, the true value may not be in the confidence interval, due to the delay of prices. 第一の観察は、各段階において、真の価値は、価格の遅れのため、信頼区間にないかもしれないということである。 0.68
The confidence interval at time ti + 1 is [ℓti+1, rti+1] in the algorithm, but since the value of ℓti+1 and rti+1 are determined in the previous three time steps, thus the “true” confidence interval can be defined by vti+1 ∈ [ℓti+1 − ǫti−2 − ǫti−1 − ǫti, rti+1 + ǫti−2 + ǫti−1 + ǫti]. 時間ti + 1 の信頼区間はアルゴリズムにおいて [lti+1, rti+1] となるが、lti+1 と rti+1 の値は前の3つの時間ステップで決定されるので、「真の」信頼区間は vti+1 ∈ [lti+1 − シュティ−2 − シュティ−1 − シュティ, rti+1 + シュティ−2 + シュティ−1 + シュティ] で定義される。 0.69
Furthermore, for any time t′ ∈ Ii, vt′ ∈ [ℓti+1 −Pti−2≤t<ti+1 Observe that the algorithm in phase i breaks at j, thus vti+2j+1 ≥ pti+2j+1 = ℓti+1 − δj and vti+2j+2 < pti+2j+2 = rti+1 + δj. さらに、任意の時間 t′ ∈ Ii に対して、vt′ ∈ [lti+1 −Pti−2≤t<ti+1 は相 i のアルゴリズムが j で破れることを観測し、したがって vti+2j+1 ≥ pti+2j+1 = lti+1 − δj および vti+2j+2 < pti+2j+2 = rti+1 + δj となる。 0.57
Thus any price in the phase is in range [ℓti+1 − δj, ℓti+1 + δj], while any value vt in the phase is in range [vti+2j+1 −Pt∈Ii ǫt] ⊆ [ℓti+1 − δj − ǫt, rti+1 + δj + Pt∈Ii Pt∈Ii ǫt], so the symmetric loss at any time step in the phase is at most rti+1 − ℓti+1 + 2δj +Pt∈Ii ǫt. したがって、相中の任意の価は [lti+1 − δj, lti+1 + δj] の範囲であり、相中の任意の値 vt は [vti+2j+1 −pthtmlii ,t] の範囲内であり、[lti+1 − δj − st, rti+1 + δj + pthtmlii pthtmlii st] であり、相内の任意の時間ステップにおける対称損失は、最大 rti+1 − lti+1 + 2δj + 2δj +pthtmlii st である。
訳抜け防止モード: したがって、相の任意の価格は [ lti+1 − δj, lti+1 + δj ] の範囲である。 相中の任意の値 vt は [vti+2j+1] の範囲にあるが lti+1 − δj − st, rti+1 である。 したがって、相の任意の段階での対称損失は、少なくとも rti+1 − lti+1 + 2δj + ptسii である。
0.71
ǫt, rti+1 +Pti−2≤t<ti+1 t, rti+1 +Pti−2≤t<ti+1 0.50
ǫt, vti+2j+2 +Pt∈Ii t, vti+2j+2 +pthtmlii 0.40
ǫt]. 18 という。 18 0.63
英語(論文から抽出)日本語訳スコア
ALGORITHM 11: Symmetric loss minimizing algorithm for adversarial buyer with unknown dynamic changing rate ǫt [ℓ1, r1] ← [0, 1] Let t1 + 1 = 1 be the starting time of the first phase for each phase i of time interval [ti + 1, ti+1] with to-be-determined stopping time ti+1 do ALGORITHM 11: 未知の動的変化率を持つ逆購入者に対する対称損失最小化アルゴリズム t1 + 1 = 1 を時間間隔 [ti + 1, ti+1] で決定された停止時間 ti+1 do の各フェーズ i の開始時刻とする。
訳抜け防止モード: アルゴリズム11 : 未知の動的変動率<t[l1, r1 ]<0,>を有する敵対的買い手に対する対称損失最小化アルゴリズム 1 ] t1 + 1 = 1 を時間間隔 [ti + 1] の各位相 i の第一相の開始時間とする。 ti+1 ] with to - be - determined stop time ti+1 do
0.85
Let ti + 1 be the starting time step of the phase for each two consecutive time steps ti + 2j + 1, ti + 2j + 2 with j ≥ 0 do ti + 1 を相の開始時間ステップとし、2つの連続時間ステップ ti + 2j + 1, ti + 2j + 2 を j ≥ 0 とする。 0.88
break (from this for loop) break (複数形 breaks) 0.62
ˆǫ ← δj = 2jT −1 Set price pti+2j+1 ← ℓti+1 − δj Set price pti+2j+2 ← rti+1 + δj if the seller finds vti+2j+1 ≥ pti+2j+1 and vti+2j+2 < pti+2j+2 then end if end for ti+1 ← ti + 2j + 3 Set pti+1 ← if vti+1 < pti+1 then pti+2j+1 ≥ pti+2j+1 ≥ pti+2j+1 と vti+2j+2 < pti+2j+2 であれば、ti+1 と ti + 2j + 3 set pti+1 で終わる。 0.83
ℓti +1+rti+1 lti +1+rti+1 0.44
2 else [ℓti+1+1, rti+1+1] ← [ℓti+1 − δj, pti+1] [ℓti+1+1, rti+1+1] ← [pti+1, rti+1 + δj] 2 その他 [lti+1+1, rti+1+1] ] [lti+1 − δj, pti+1] [lti+1+1, rti+1+1] ] [pti+1, rti+1 + δj] 0.67
end if end for Also since the algorithm does not break at j−1 in the for loop, thus either vti+2j−1 < pti+2j−1 = Let ai = rti+1 − ℓti+1 be the length of the confidence interval at the beginning of phase i, ǫt be the total changing rate of the value in phase i. 終われば終われば また、このアルゴリズムはforループのj−1でブレークしないので、vti+2j−1 < pti+2j−1 = let ai = rti+1 − lti+1 を位相 i の開始時の信頼区間の長さとする。 0.70
Then according to the 2 ai + δji where ji is the value of j at the end of phase i. すると 2 ai + δji に従って ji は相 i の終点 j の値である。 0.70
Since ℓti+1 − δj−1, or vti+2j > pti+2j = rti+1 + δj−1. 以来 lti+1 − δj−1 または vti+2j > pti+2j = rti+1 + δj−1。 0.61
In either case, Pti−2≤t<ti+1 and bi = Pt∈Ii binary search step, ai+1 = 1 δji = 2δji−1 < Pti−2≤t<ti+1 いずれの場合も、Pti−2≤t<ti+1 と bi = Ptが表示され、ai+1 = 1 δji = 2δji−1 < Pti−2≤t<ti+1 0.60
ǫt < bi−1 + bi, we have t < bi−1 + bi, 0.73
ǫt > δj−1 = 1 t > δj−1 = 1 0.75
2 δj. 1 2 ai+1 < 2δj。 1 2 ai+1 < 0.81
ai + 2(bi + bi−1). ai + 2(bi + bi−1)。 0.92
Then ai+1 can be represented using only bi’s as follows: すると、ai+1 は bi のみを使って表現できる。 0.76
ai+1 < 2(bi + bi−1) + (bi−1 + bi−2) + ai+1 < 2(bi + bi−1) + (bi−1 + bi−2) + 0.78
1 2 (bi−2 + bi−3) + ··· 1 2 (bi−2+bi−3) + ···· 0.73
(3) Since the total symmetric loss in phase i is upper bounded by ai+1 + Pt∈Ii (3) 位相 i における全対称損失は ai+1 + pthtmlii で上限されるからである。 0.74
ǫt per step thus |Ii|(ai+1 + bi) ≤ (2 log T + 1)(ai+1 + bi) in total, summing over all phases we get the total symmetric loss of the algorithm for all phases is L := (2 log T + 1)Pi(ai+1 + bi). したがって、ステップごとに |Ii|(ai+1 + bi) ≤ (2 log T + 1)(ai+1 + bi) を合計すると、全ての位相に対してアルゴリズムの全対称損失が L := (2 log T + 1)Pi(ai+1 + bi) となる。 0.92
L can be represented with only bi by applying (3) to L. Since the coefficient of bi in L is O(log T ) for each bi, thus L = O(log T )Pi bi = O(log T )Pt∈[T ] ǫt. L における bi の係数は、各 bi に対して O(log T ) であるため、L = O(log T )Pi bi = O(log T )Pt∂[T ] >t となる。
訳抜け防止モード: l の bi の係数は各 bi に対して o(log t ) であるので、l は (3 ) を l に当てて (3 ) だけ bi で表すことができる。 したがって、l = o(log t ) pi bi = o(log t ) ptftp[t ] である。
0.75
Therefore the average symmetric loss of the algorithm is ˜O(¯ǫ). したがって、アルゴリズムの平均対称損失は、o( ) である。 0.84
19 19 0.85
英語(論文から抽出)日本語訳スコア
References [1] Kareem Amin, Afshin Rostamizadeh, and Umar Syed. 参考文献 [1] kareem amin, afshin rostamizadeh, umar syed。 0.61
Repeated contextual auctions with strategic buyers. 戦略的買い手による繰り返しコンテキストオークション。 0.71
In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 622–630, 2014. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014 December 8-13 2014, Montreal, Canada, pages 622–630, 2014 0.82
1 [2] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. 1 [2] peter auer、nicolo cesa-bianchi、yoav freund、robert e schapire。 0.75
Gambling in a rigged In Proceedings of IEEE 36th Annual IEEE第36回年次論文集に見るギャンブル 0.59
casino: The adversarial multi-armed bandit problem. Casino: 敵のマルチアームバンディット問題です。 0.68
Foundations of Computer Science, pages 322–331. コンピュータ科学専攻、322-331頁。 0.71
IEEE, 1995. 1995年、IEEE。 0.71
22 [3] Nicolo Cesa-Bianchi, Tommaso Cesari, and Vianney Perchet. 22 [3]Nicolo Cesa-Bianchi,Tommaso Cesari,Vianney Perchet。 0.76
Dynamic pricing with finitely 有限値による動的価格設定 0.57
many unknown valuations. 多くの未知の評価です 0.63
In Algorithmic Learning Theory, pages 247–273. アルゴリズム学習理論』247-273頁。 0.76
PMLR, 2019. 2019年、PMLR。 0.72
1 [4] Shuchi Chawla, Nikhil R. Devanur, Anna R. Karlin, and Balasubramanian Sivan. 1 [4]Shuchi Chawla、Nikhil R. Devanur、Anna R. Karlin、Balasubramanian Sivan。 0.78
Simple pricing schemes for consumers with evolving values. 進化する価値を持つ消費者のためのシンプルな価格体系。 0.51
In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1476–1490. Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016 page 1476–1490。 0.93
SIAM, 2016. 2016年、SIAM。 0.73
2 [5] Maxime C Cohen, Ilan Lobel, and Renato Paes Leme. 2 5] Maxime C Cohen, Ilan Lobel, Renato Paes Leme 0.74
Feature-based dynamic pricing. 機能ベースの動的価格設定。 0.54
In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 817–817. 2016 acm conference on economics and computationの論文817-817頁。 0.68
ACM, 2016. 2016年、ACM。 0.87
1 [6] Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz. 1 Amit Daniely氏、Alon Gonen氏、Shai Shalev-Shwartz氏。 0.78
Strongly adaptive online learning. オンライン学習の強化。 0.71
In International Conference on Machine Learning, pages 1405–1411. 院 国際機械学習会議、1405-1411頁。 0.60
PMLR, 2015. 2015年、PMLR。 0.70
2 [7] Nikhil R. Devanur, Yuval Peres, and Balasubramanian Sivan. 2 7]ニクヒル・r・デバヌール、ユーヴァル・ペレス、バラスプラマニア・シヴァン。 0.60
Perfect bayesian equilibria in repeated sales. 完全ベイズ平衡 反復販売。 0.57
Games Econ. Behav., 118:570–588, 2019. ゲームecon。 118:570–588, 2019年。 0.64
1 [8] Dylan J Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Sridharan, and ´Eva Tardos. 1 8]Dylan J Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Sridharan, そしてEva Tardos。 0.79
Learning in games: robustness of fast convergence. ゲームでの学習: 迅速な収束の堅牢性。 0.78
In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 4734–4742, 2016. The 30th International Conference on Neural Information Processing Systems, page 4734–4742, 2016 0.76
2 [9] Elad Hazan and Comandur Seshadhri. 2 9]Elad HazanとComandur Seshadhri。 0.73
Adaptive algorithms for online decision problems. オンライン意思決定問題に対する適応アルゴリズム 0.83
In Electronic colloquium on computational complexity (ECCC), volume 14, 2007. 院 Electronic colloquium on computational complexity (ECCC) Volume 14, 2007 (英語) 0.61
2 [10] Mark Herbster and Manfred K Warmuth. 2 10]マーク・ハーブスターと マンフレッド・k・ウォーマス 0.69
Tracking the best linear predictor. 最良の線形予測器を追跡する。 0.66
Journal of Machine Learning Research, 1(281-309):10–1162, 2001. 日誌 機械学習研究 1(281-309):10-1162, 2001。 0.62
2 [11] Adel Javanmard 2 [11]アデル Javanmard 0.81
and Hamid Nazerzadeh. そしてHamid Nazerzadeh。 0.68
Dynamic pricing ダイナミック pricing 0.80
in dimensions. http://jmlr.org/pape rs/v20/17-357.html. イン 寸法。 http://jmlr.org/pape rs/v20/17-357.html 0.50
1 Journal of Machine Learning Research, 1 Journal of Machine Learning Research(英語) 0.79
20(9):1–49, 20(9):1–49, 0.82
2019. highURL 2019. 高URL 0.78
[12] Sham M. Kakade, Ilan Lobel, and Hamid Nazerzadeh. [12]Sham M. Kakade、Ilan Lobel、Hamid Nazerzadeh。 0.66
Optimal dynamic mechanism design and the virtual-pivot mechanism. 最適動的機構設計 そして仮想ピボット機構。 0.66
Oper. Res., 61(4):837–854, 2013. Oper 2013年、61(4):837–854。 0.62
2 [13] Robert Kleinberg and Tom Leighton. 2 13] ロバート・クラインバーグと トム・リートン 0.75
The value of knowing a demand curve: Bounds on regret for online posted-price auctions. 需要曲線を知る価値:オンライン公開価格オークションに対する後悔に縛られる。 0.68
In Foundations of Computer Science, 2003. 2003年、計算機科学研究所設立。 0.69
Proceedings. 44th Annual IEEE Symposium on, pages 594–605. 手続きだ 第44回IEEE Symposium on, page 594–605. 0.60
IEEE, 2003. 2003年、IEEE。 0.71
1, 4, 21, 22 1, 4, 21, 22 0.85
20 20 0.85
英語(論文から抽出)日本語訳スコア
[14] Akshay Krishnamurthy, Thodoris Lykouris, Chara Podimata, and Robert Schapire. 14] Akshay Krishnamurthy, Thodoris Lykouris, Chara Podimata, Robert Schapire 0.63
Contextual search in the presence of irrational agents. 文脈 不合理なエージェントの前で検索する。 0.61
arXiv preprint arXiv:2002.11650, 2020. arXiv preprint arXiv:2002.11650, 2020 0.81
1 [15] Renato Paes Leme and Jon Schneider. 1 [15]Renato Paes LemeとJon Schneider。 0.76
Contextual search via intrinsic volumes. 固有ボリュームによる文脈探索。 0.61
In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 268–282, 2018. doi: 10.1109/FOCS.2018.00 034. 第59回IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, Paris, October 7-9, 2018, page 268–282, 2018. doi: 10.1109/FOCS.2018.00 034 0.77
URL https://doi.org/10.1 109/FOCS.2018.00034. URL https://doi.org/10.1 109/FOCS.2018.00034 0.36
1 [16] Allen Liu, Renato Paes Leme, 1 [16]アレン・リュー、ルナート・パス・レム、 0.68
and Jon Schneider. ジョン・シュナイダーも。 0.54
and extensions. https://epubs.siam.o rg/doi/abs/10.1137/1 .9781611976465.66. 拡張も。 https://epubs.siam.o rg/doi/abs/10.1137/1 .978161 1976465.66 0.39
1 pages 1059–1078, 2021. 1 1059-1078, 2021頁。 0.75
doi: 10.1137/1.9781611976 465.66. Doi: 10.1137/1.9781611976 465.66. 0.44
Optimal contextual pricing URL 最適コンテキスト価格URL 0.69
[17] Ilan Lobel, Renato Paes Leme, and Adrian Vladu. Ilan Lobel氏、Renato Paes Leme氏、Adrian Vladu氏。 0.56
Multidimensional binary search for contex- 頂点の多次元二元探索- 0.55
tual decision-making. Operations Research, 2017. チュア意思決定。 2017年、経営調査。 0.58
1 [18] Haipeng Luo and Robert E Schapire. 1 18]Hipeng LuoとRobert E Schapire。 0.73
Achieving all with no parameters: Adanormalhedge. パラメータなしですべてを達成する: Adanormalhedge。 0.77
In Conference on Learning Theory, pages 1286–1304. 院 学習理論講座 1286-1304頁。 0.52
PMLR, 2015. 2015年、PMLR。 0.70
2 [19] Thodoris Lykouris, Karthik Sridharan, and ´Eva Tardos. 2 [19]Thodoris Lykouris, Karthik Sridharan, ́Eva Tardos。 0.79
Small-loss bounds for online learning with partial information. 部分的情報を用いたオンライン学習のための小損失境界 0.61
In Conference on Learning Theory, pages 979–986. PMLR, 2018. 979-986頁。 2018年、PMLR。 0.43
2 [20] Renato Paes Leme, Balasubramanian Sivan, and Yifeng Teng. 2 20]renato paes leme、balasubramanian sivan、yifeng teng。 0.66
Why do competitive markets converge to first-price auctions? 競争市場はなぜファーストプライスオークションに収束するのか? 0.64
In Proceedings of The Web Conference 2020, pages 596–605, 2020. Proceedings of The Web Conference 2020, page 596–605, 2020。 0.84
1 [21] Alessandro Pavan, Ilya Segal, and Juuso Toikka. 1 [21]Alessandro Pavan、Ilya Segal、Juuso Toikka。 0.74
Dynamic mechanism design: A myersonian approach. 動的機構設計:ミアソン的アプローチ。 0.80
Econometrica, 82(2):601–653, 2014. doi: https://doi.org/10.3 982/ECTA10269. Econometrica, 82(2):601–653, 2014 doi: https://doi.org/10.3 982/ECTA10269。 0.61
URL https://onlinelibrar y.wiley.com/doi/abs/ 10.3982/ECTA10269. URL https://onlinelibrar y.wiley.com/doi/abs/ 10.3982/ECTA10269。 0.30
2 [22] Virag 2 [22]ヴィラグ 0.80
Shah, Shah, Shah 0.77
Ramesh Johari, ラーメシュ ジョハリ 0.42
and parametric https://proceedings. neurips.cc/paper/201 9/file/363763e5c3dc3 a68b399058c34aecf2c- Paper.pdf. そして parametric https://proceedings. neurips.cc/paper/201 9/file/363763e5c3dc3 a68b399058c34aecf2c- Paper.pdf 0.45
1 contextual dynamic 1 文脈 dynamic~ 0.75
pricing. Jose 32:2363–2373, 価格。 ホセ32:2363–2373 0.58
Blanchet. 2019. Blanchet 2019. 0.69
SemiURL [23] Steven E Shreve. セミURL 23] スティーブン・e・シュリーブ 0.56
Stochastic calculus for finance II: Continuous-time models, volume 11. 金融のための確率計算 II: 連続時間モデル、巻11。 0.76
Springer Science & Business Media, 2004. 専門は2004年出版の『Springer Science & Business Media』。 0.51
2 A Comparison to Fixed Price Benchmark 2 固定価格ベンチマークとの比較 0.85
Theorem A.1. The no-regret algorithm for an adversarial buyer in [13] can have Ω(1) revenue loss. A.1。 13] の逆買い手に対する非回帰アルゴリズムは、Ω(1) の収益損失をもたらすことができる。 0.69
Proof. Consider the following sequence of buyer values v = (v1,··· , vT ) with changing rate ǫ. 証明。 バイヤー値 v = (v1,··· , vT , vT ) の次の列を、変化率 s で考える。 0.66
Let m = 1 ǫ . m = 1 である。 0.65
For any integer k ≥ 0 and 1 ≤ j ≤ m, let v2km+j = jǫ, and v2km+m+j = 1 − (j − 1)ǫ. 任意の整数 k ≥ 0 と 1 ≤ j ≤ m に対して、v2km+j = j とし、v2km+m+j = 1 − (j − 1) とする。 0.76
In other words, the value sequence is periodic with period 2m; in each phase of repetition, vt starts with ǫ and increases by ǫ for each step until it reaches 1, then starts with 1 and decreases by ǫ for each step. 言い換えれば、値列は周期 2m で周期的であり、反復の各段階では、vt は 1 に到達するまで、各ステップで s から始まり、次に 1 から始まり、各ステップで s から減少する。 0.65
21 21 0.85
英語(論文から抽出)日本語訳スコア
1 We show that the zero-regret pricing algorithm in [13] gives Ω(T ) revenue loss, if T > m3 ln m = ǫ3 ln 1 ǫ . 1 また,[13] におけるゼロレグレット価格アルゴリズムは,T > m3 ln m = .3 ln 1 . の場合に Ω(T ) の収益損失を与えることを示した。 0.82
The algorithm applies the seminal bandit algorithm EXP3 [2] with each arm 1 ≤ i ≤ m corresponding to a price pi = iǫ which is a multiple of ǫ. このアルゴリズムは、各アームが 1 ≤ i ≤ m で π の倍数である値 pi = i に対応するセミナルバンディットアルゴリズム EXP3 [2] を適用する。 0.66
We describe the algorithm in detail as follows. アルゴリズムの詳細は以下の通りである。 0.68
ALGORITHM 12: No-regret pricing algorithm in [13] ALGORITHM 12:No-regret pricing algorithm in [13] 0.99
T m η ← q ln m w1(i) ← 1 for each arm 1 ≤ i ≤ m for each time step t do qt(i) ← (1 − η) wt(i) Draw it from qt, i.e. Tm 各アーム1 ≤ i ≤ m に対し、ステップt が qt(i) となると、ステップt が qt(i) となる(1 − η) wt(i) が qt から引き出す。 0.58
Pr[it = i] = qt(i) for each 1 ≤ i ≤ m Price at pt ← itǫ, and observe revenue gain rt ← pt1{vt ≥ pt} Update wt+1(i) ← wt(i) for i 6= it, and wt+1(it) ← wt(it) exp(cid:16)η Pr[it = i] = qt(i) for each 1 ≤ i ≤ m Price at pt > it , and observed revenue gain rt > pt1{vt ≥ pt} Update wt+1(i) ^ wt(i) for i 6= it, and wt+1(it) ^ wt(it) ^ wt(it) exp(cid:16)η 0.90
+ η m Wt end for +ηm Wt 終止符 0.74
rt mqt(it)(cid:17) rt mqt(it)(cid:17) 0.90
It suffices to show that the revenue loss in each time interval I = [2mk + 1, 2mk + m] is Ω(m) 2 + 1,··· , m}. 各時間間隔 I = [2mk + 1, 2mk + m] における収益損失が Ω(m) 2 + 1,··· , m} であることを示すのに十分である。 0.90
in expectation. Partition the arms to two groups S1 = {1, 2,··· , m Then we have the following observations. 期待して 腕を2つの群 s1 = {1, 2,··· , m に分割すると、次の観察が得られる。 0.64
2 } and S2 = { m 2 } および S2 = { m 0.94
rt 1 T m m2 )m > 1 e . rt 1 Tm m2)m>1e。 0.75
m2 for each t ∈ I is at least (1 − m−1 各 t ∈ I に対する m2 は (1 − m−1) である。 0.74
m2 for each time step t ∈ I. m2 の各時間ステップ t ∈ I について。 0.69
This is because m2 is at most m−1 m2 since there are at most m − 1 これは、m2 が最も m−1 m2 であるからである。 0.80
Observation 1: with probability > 1 e , qt(it) ≥ 1 the probability of selecting an arm i with qt(i) < 1 such arms, thus the probability of qt(it) ≥ 1 Observation 2: with probability > 1 e , wt(i) increases to a factor of e in the entire time interval I for every arm 1 ≤ i ≤ m. This is because if qt(it) ≥ 1 m2 , wt+1(it) increases to a m·m−2(cid:19) < e1/m compared to wt(it) for each time step t mqt(it)(cid:17) ≤ exp(cid:18)q ln m fraction of exp(cid:16)η since T > m3 ln m. Thus if qt(it) ≥ 1 m2 for each time step t ∈ I, then for any arm 1 ≤ i ≤ m and time step t ∈ I, wt(i) < ew2mk+1(i) as there are only m steps in I. Observation 1: with probability > 1 e , qt(it) ≥ 1 the probability of selecting an arm i with qt(i) < 1 such arms, thus the probability of qt(it) ≥ 1 Observation 2: with probability > 1 e , wt(i) increases to a factor of e in the entire time interval I for every arm 1 ≤ i ≤ m. This is because if qt(it) ≥ 1 m2 , wt+1(it) increases to a m·m−2(cid:19) < e1/m compared to wt(it) for each time step t mqt(it)(cid:17) ≤ exp(cid:18)q ln m fraction of exp(cid:16)η since T > m3 ln m. Thus if qt(it) ≥ 1 m2 for each time step t ∈ I, then for any arm 1 ≤ i ≤ m and time step t ∈ I, wt(i) < ew2mk+1(i) as there are only m steps in I. 0.97
Then Observation 2 follows from Observation 1. 次に、観測2が観測1から続く。 0.67
Then we are ready to argue that in time interval I, the total revenue loss of Algorithm 12 is Ω(m). そして、時間間隔Iにおいて、アルゴリズム12の総収益損失がΩ(m)であることについて議論する準備ができています。 0.68
We prove a stronger result, that the algorithm has Ω(m) revenue loss in either time interval I1 = [2mk + m 4 + 1, 2mk + m]. I1 = [2mk + m 4 + 1, 2mk + m] のいずれかの時間間隔で Ω(m) の収益損失があることを示す。 0.70
Let Wt,1 = Pi∈S1 wt(i) be the total weight of arms in S1 = {1, 2,··· , m 2 } at time step t ∈ I, and similarly define Wt,2 = Pi∈S2 wt(i) for arms S2. wt,1 = piبs1 wt(i) を s1 = {1, 2,··· , m 2 } の時間ステップ t ∈ i におけるアームの総重量とし、同様に wt,2 = piبs2 wt(i) をarms s2 に対して定義する。 0.76
If W2mk+1,1 ≥ W2mk+1,2 at the beginning of I, by Observation 2 Wt,1 ≥ 1 e Wt,2 for any time step t ∈ I. I の初めの W2mk+1,1 ≥ W2mk+1,2 であれば、任意の時間ステップ t ∈ I に対して 2 Wt,1 ≥ 1 e Wt,2 となる。 0.63
By definition of qt(i), with constant probability > 1/e 1+1/e = 1 e+1 , the algorithm selects an arm i ∈ S1 at any time step t ∈ I. 定数確率 > 1/e 1+1/e = 1 e+1 の qt(i) の定義により、アルゴリズムは任意の時間ステップ t ∈ I でアーム i ∈ S1 を選択する。 0.83
In particular, with probability 1 e+1 , an arm it ∈ S1 (which corresponds a price pt < 1 2 ) is selected in time step t ∈ I2. 特に、確率 1 e+1 では、時間ステップ t ∈ I2 において、アーム it ∈ S1 (価格 pt < 1 2 ) が選択される。 0.81
Since in time step t ∈ I2 we always have vt > 3 4 for each time step t ∈ I2 with constant probability, thus Ω(m) in expectation in total. 時間ステップ t ∈ i2 において、常に一定確率の時間ステップ t ∈ i2 に対して vt > 3 4 が成り立つので、ω(m) は全体の期待値となる。 0.80
Similarly, if W2mk+1,1 < W2mk+1,2 at the beginning of I, then at each time step t ∈ I1 we have 1 2 , but with constant probability an arm in S2 is selected and results in pt > 1 4 , thus Ω(m) in expectation in total. 同様に、I の初めの W2mk+1,1 < W2mk+1,2 の場合、各ステップ t ∈ I1 では 1 2 となるが、一定の確率で S2 の腕が選択され、結果として pt > 1 4 となる。 0.83
To summarize, in either I1 = [2mk + m 4 + 1, 2mk + m], the total revenue loss is Ω(m) in expectation. 要約すると、i1 = [2mk + m 4 + 1, 2mk + m] において、総収益損失は期待値 ω(m) である。 0.83
Summing up the revenue loss for all phases, the total revenue loss for Algorithm 12 is Ω(T ) for all time steps, thus Ω(1) on average. 全段階での収益損失を補うため、アルゴリズム12の総収益損失は全時間ステップでΩ(T)であり、平均してΩ(1)となる。 0.81
4 , thus the revenue loss is at least 1 4 以上であり,収益損失は少なくとも1。 0.80
2 and revenue loss vt > 1 2および収益損失vt > 1。 0.78
4 + 1, 2mk + m 4 + 1, 2mk + m 0.96
2 ] or I2 = [2mk + 3m 2 ] または I2 = [2mk + 3m 0.83
4 + 1, 2mk + m 4 + 1, 2mk + m 0.96
2 ] or I2 = [2mk + 3m 2 ] または I2 = [2mk + 3m 0.83
4 < vt ≤ 1 4 < vt ≤ 1 0.85
22 22 0.85
英語(論文から抽出)日本語訳スコア
B Buyer’s Changing Rate is Dynamic, Known bバイヤーの変動レートは動的、知られている 0.72
In this section, we study the problem where ǫt are publicly known by the seller. 本稿では,販売者によって公に知られている問題について考察する。 0.64
In this case, the algorithms are much simpler than the case in the main body where ǫt are unknown to the seller, and we are able to handle the case where ǫt are not decreasing for the revenue loss. この場合、アルゴリズムは、売り手が未知である本体の場合よりもずっと単純であり、売上損失に対して、 st が減少していない場合を処理できる。 0.53
Theorem B.1. If the buyer has adversarial values and changing rates ǫt known to the seller, then there exists an online pricing algorithm with symmetric loss O(¯ǫ) = O( 1 t=1 ǫt). B.1。 買い手が逆の値を持ち、売り手が知っている変動レートが t であれば、対称損失 o(s) = o(1 t=1 st) を持つオンライン価格アルゴリズムが存在する。 0.69
Furthermore, no online algorithm can obtain a symmetric loss less than Ω(¯ǫ). さらに、オンラインアルゴリズムはΩ( ) 未満の対称損失を得ることができない。 0.82
T PT Proof. The tightness result Ω(¯ǫ) was shown in Theorem 4.1 even when ǫt are identical. TPT 証明。 厳密性の結果 Ω( ) は t が同一である場合でも Theorem 4.1 で示される。 0.59
Now we show that a binary search algorithm that tracks the confidence bound gets symmetric loss O(¯ǫ). ここでは、信頼境界を追跡する二項探索アルゴリズムが対称損失O(s)を得ることを示す。 0.76
We only slightly modify Algorithm 1 as follows. アルゴリズム1を少しだけ修正します。 0.60
The algorithm maintains confidence bound [ℓt, rt] at each time step, and price at pt = ℓt+rt . アルゴリズムは各時間ステップで[lt, rt] の信頼を保ち、pt = lt+rt の価格を保っている。 0.72
If vt < pt, then [ℓt+1, rt+1] = [ℓt − ǫt, pt + ǫt]; if vt ≥ pt, then [ℓt+1, rt+1] = [pt − ǫt, rt + ǫt]. vt < pt ならば、[lt+1, rt+1] = [lt − st, pt + st]; vt ≥ pt ならば [lt+1, rt+1] = [pt − st, rt + st] である。 0.96
Let at = rt − ℓt be the length of the confidence interval at each time. at = rt − lt を各時間における信頼区間の長さとする。 0.81
The symmetric loss at time t is upper bounded by at 時間 t における対称損失は at によって上限される 0.79
2 2 + 2ǫt, we have 2 2 + 2 である。 0.76
2 . Observe that at+1 ≤ at 2 . +1 ≤ で観測する 0.83
at+1 ≤ 2ǫt + ǫt−1 + 2−1ǫt−2 + ··· + 2−(t−1)ǫ1 + 2−(t−1)a1. 1 ≤ 2 t + 2−1 t−1 + 2−1 t−2 + ··· + 2−(t−1) =1 + 2−(t−1)a1 である。 0.54
(4) Notice that the total symmetric loss is upper bounded by PT 1 2 at. (4) 合計対称損失は pt 1 2 at で上限されていることに注意。 0.82
When we apply (4) to the formula, the coefficient of any ǫt is at most 2 + 1 + 2−1 + ··· ≤ 4. 式に (4) を適用すると、任意の t の係数は少なくとも 2 + 1 + 2−1 + ··· ≤ 4 である。 0.80
Thus the symmetric loss is O(¯ǫ). したがって、対称損失は O( ) である。 0.86
t=1 Theorem B.2. If the buyer has adversarial values and changing rates ǫt known to the seller, then there exists an online pricing algorithm with revenue loss ˜O(¯ǫ1/2), here ¯ǫ = 1 t=1 ǫt. t=1。 B.2。 買い手が相手の値と変更率を持つ場合、販売者には知られないが、収益損失がゼロとなるオンライン価格アルゴリズムが存在し、ここでは1 t=1 tである。 0.59
Furthermore, no online algorithm can obtain a revenue loss less than Ω(¯ǫ1/2). さらに、オンラインのアルゴリズムではΩ(~1/2)未満の収益損失が得られない。 0.69
T PT t=t0+1 TPT t=t0+1 0.37
Proof. The tightness result has been shown in Theorem 4.2. 証明。 厳密性の結果はTheorem 4.2で示されている。 0.64
Now we construct an online pricing algorithm with revenue loss ˜O(¯ǫ1/2). そこで我々は,収益損失が半減したオンライン価格アルゴリズムを構築した。 0.65
The algorithm is obtained by slightly modifying Algorithm 3. このアルゴリズムはアルゴリズム3を少し修正して得られる。 0.73
Firstly, the update rule of confidence interval is changed to [ℓt+1, rt+1] ← [ℓt − ǫt, rt + ǫt]. 第一に、信頼区間の更新規則を[lt+1, rt+1], [lt − st, rt + st] に変更する。 0.80
Secondly, the length of each phase is no longer a fixed length. 第二に、各位相の長さはもはや固定長ではない。 0.78
A phase starting at time step t0 + 1 has length m such that Pt=t0+m−1 t=t0+1 ǫt. 時間ステップ t0 + 1 で始まる位相は、pt=t0+m−1 t=t0+1 であるような長さ m を持つ。 0.57
In other words, the total possible value change in each phase is Θ(√¯ǫ), so the revenue loss of each step is O(√¯ǫ). 言い換えれば、各位相における総可能な値の変化は s であるので、各ステップの収益損失は O ( s ) である。 0.76
Thirdly, in the initialization step of each phase, the algorithm uses binary search algorithm to narrow down the length of the confidence interval to O(¯ǫ1/2). 第三に、各位相の初期化ステップにおいて、アルゴリズムは二項探索アルゴリズムを用いて信頼区間の長さを o( 1/2) に狭める。 0.83
The number of phases is O(T ¯ǫ−1/2) since Pt ǫt = T ¯ǫ. 位相の数は O(T-1/2) である。 0.60
Then the revenue loss of all phases is contributed by the loss of binary search for locating the value to a confidence interval of length √¯ǫ ) = ˜O(1) per phase and ˜O(T ¯ǫ−1/2) in total; plus the revenue loss in each phase, which is O(log 1√¯ǫ of each step in the phase, which is at most O(√¯ǫ) each step thus O(T√¯ǫ) in total. すると、すべてのフェーズの収益損失は、各フェーズにおける各ステップのo(log 1)とo(t)とo(t-1/2)の合計の信頼区間に値を置く二分探索の損失と、各ステップがo(t) となる各フェーズの収益損失によって引き起こされる。
訳抜け防止モード: すると、すべてのフェーズの収益損失は、各フェーズ毎の信頼区間(英語版)に値を見つけるための二分探索の損失によって引き起こされる。 そして、総じて、o(t)(t)−1/2) であり、さらに各段階での収益損失も大きい。 相の各ステップの o(log 1 ) は、相の各ステップの o(log 1 ) である。
0.74
Thus the total revenue loss of the algorithm is ˜O(T ¯ǫ−1/2) for all time steps, thus ˜O(¯ǫ−1/2) on average. したがって、アルゴリズムの総収益損失は全ての時間ステップで so(t ) であり、したがって平均で so(t-1/2) となる。 0.72
ǫt ≤ √¯ǫ < Pt=t0+m t = t=t0+m である。 0.43
Theorem B.3. If the buyer has stochastic value and changing rates ǫt known to the seller, then t . B.3。 買い手が確率的価値を持ち、売り手が知らない変化率がある場合、t。 0.55
Further- there exists an online pricing algorithm with revenue loss ˜O(˜ǫ2/3), here ˜ǫ = q 1 さらに オンライン価格アルゴリズムが存在し、収益損失が o( ]2/3) である。 0.69
more, no online algorithm can obtain a revenue loss less than Ω(˜ǫ2/3). さらに、オンラインのアルゴリズムでは、Ω(2/3)未満の収益損失が得られない。 0.68
T PT t=1 ǫ2 23 TPT t=1~2 23 0.60
英語(論文から抽出)日本語訳スコア
Proof. The tightness result has been shown in Theorem 4.3. 証明。 厳密性の結果はTheorem 4.3で示されている。 0.64
Now we construct an online pricing algorithm with revenue loss ˜O(˜ǫ2/3). そこで我々は,収益損失が2/3のオンライン価格アルゴリズムを構築した。 0.66
The algorithm is obtained by slightly modifying Algorithm 4. アルゴリズムはアルゴリズム4を少し修正して得られる。 0.80
Firstly, the update rule of confidence interval is changed to [ℓt+1, rt+1] ← [ℓt − ǫt, rt + ǫt]. 第一に、信頼区間の更新規則を[lt+1, rt+1], [lt − st, rt + st] に変更する。 0.80
Secondly, the length of each phase is no longer a fixed length. 第二に、各位相の長さはもはや固定長ではない。 0.78
A phase starting at time step t0 + 1 has length m such that Pt=t0+m−1 t . 時間ステップ t0 + 1 で始まる位相は、pt=t0+m−1 t となる長さ m を持つ。 0.64
Thirdly, let δ = 4 ˜O(˜ǫ−2/3), then the fixed price in the phase is pt = ℓt0 − δ. 第三に、δ = 4 {\displaystyle δ=4} とすると、位相の固定価格は pt = lt0 − δ となる。 0.80
Finally, in the initialization step of each phase, the algorithm uses binary search algorithm to narrow down the length of the confidence interval to O(4˜ǫ2/3). 最後に、各位相の初期化段階において、アルゴリズムは二分探索アルゴリズムを用いて信頼区間の長さをO(4 ×2/3)に絞り込む。 0.83
This is achievable since for any t in the phase ǫt ≤ ˜ǫ2/3, as Pt=t0+m−1 Pt=t0+m−1 の位相 t ≤ >2/3 の任意の t に対して、これは達成可能である。 0.57
t ≤ ˜ǫ4/3 < Pt=t0+m t=t0+1 ǫ2 t ≤ 4/3 < pt=t0+m t=t0+1 0.47
ǫ2 t ≤ ˜ǫ4/3. 4/3 で表される。 0.61
Ω(˜ǫ4/3) The parameters are selected to match the analysis of Algorithm 4. Ω(˜ǫ4/3) パラメータはアルゴリズム4の分析に一致するように選択される。 0.79
Since Pt ǫ2 t = T ˜ǫ2, there = O(T ˜ǫ2/3) phases. Pt2以降。 t = t (2/3) 位相は o(t) である。 0.76
In each phase, the binary search incurs ˜O(1) loss, thus ˜O(T ˜ǫ2/3) are in all phases. 各フェーズにおいて、二項探索は、o(1) の損失を伴い、したがって、o(t) はすべてのフェーズに含まれる。 0.57
Suppose that at time t1 the search algorithm ends, and we get an estimate of vt1 with additive accuracy 4˜ǫ2/3. 時間t1で探索アルゴリズムが終了し、加法精度4/2/3のvt1の推定値が得られると仮定する。 0.67
In the remaining of the phase, the price is fixed to be ℓ − δ. 相の残りの部分では、価格は l − δ に固定される。 0.70
For any t ∈ [t1, t0 + m], by Azuma’s inequality, the probability that vt 6∈ [vt1 − δ, vt1 + δ] is 任意の t ∈ [t1, t0 + m] に対して、吾妻の不等式により、vt 6 ≤ [vt1 − δ, vt1 + δ] が成り立つ確率 0.73
t=t0+1 t=t0+1 t=t0+1 t=t0+1 0.34
ǫ2 T ˜ǫ2 Pr[vt 6∈ [vt1 − δ, vt1 + δ]] ≤ 2 exp(cid:18)− = 2 exp(cid:18)− ǫ2 T2 Pr[vt 6∂ [vt1 − δ, vt1 + δ]] ≤ 2 exp(cid:18)− = 2 exp(cid:18)− 0.81
δ2 t (cid:19) 2Pt ǫ2 2˜ǫ4/3(cid:19) < δ2 t (cid:19) 2Pt >2 2 >4/3 (cid:19) < 0.69
δ2 1 m2 . By union bound, the probability that exists t ∈ [t1, t0 + m] such that vt 6∈ [vt1 − δ, vt1 + δ] is at most 1 m ; in this case, the revenue loss in the phase is at most 1 per step thus m in total, so the expected revenue loss contributed from the case is O(1). δ2 1m2。 t ∈ [t1, t0 + m] であり、vt 6 tasktop [vt1 − δ, vt1 + δ] が少なくとも 1 m である確率は、結合境界により、t ∈ [t1, t0 + m] が存在する。
訳抜け防止モード: δ2 1m2。 結合境界により、 t ∈ [ t1, t0 + m ] が存在する確率は vt 6∂ [ vt1 − δ] となる。 vt1 + δ ] は少なくとも 1 m である。 フェーズの収益損失は 1ステップ当たり 1 以上なので 合計 m になります。 したがって、このケースから得られた収益損失は、O(1 )である。
0.79
Since there are O(T ˜ǫ2/3) phases, the revenue loss of this case in all phases is ˜O(T ˜ǫ2/3) in total. o(t ]2/3) のフェーズがあるので、すべてのフェーズにおけるこのケースの収益損失は、合計で o(t ]2/3) である。 0.62
If vt ∈ [vt1 − δ, vt1 + δ] for every t ∈ [t1, t0 + m], the revenue loss for setting price ℓ− δ ≥ vt − 4˜ǫ2/3 − δ is at most O(˜ǫ2/3 + δ) = O(δ) for each step, thus O(T δ) in total for all phases with ℓ− δ ≥ vt − 4˜ǫ2/3 − δ in each time step. vt ∈ [vt1 − δ, vt1 + δ] が任意の t ∈ [t1, t0 + m] に対して、価格 l− δ ≥ vt − 4 s2/3 − δ の収益損失は、各ステップで最大 o(s2/3 + δ) = o(δ) となるので、各ステップで l− δ ≥ vt − 4 s2/3 − δ となるすべての相に対して o(t δ) は総じて o(t δ) となる。
訳抜け防止モード: vt ∈ [ vt1 − δ, vt1 + δ ] が任意の t ∈ [ t1, t0 + m ],価格 l− δ ≥ vt − 4 >2/3 − δ の収益損失は,各ステップ毎に最大 O( >2/3 + δ ) = O(δ ) となる。 したがって、全位相で O(T δ ) は l− δ ≥ vt − 4 × 2/3 − δ である。
0.92
Combine all cases above, the expected revenue loss is ˜O(T ˜ǫ2/3) in total, thus ˜O(˜ǫ2/3) on average. 上述のすべてのケースを合わせると、予想収益損失は平均で平均で平均2O(T)/3)となる。 0.71
24 24 0.85
                                                 ページの最初に戻る

翻訳にはFugu-Machine Translatorを利用しています。