先验独立算法的下界_LowerBoundsforPriorIndependentAlgorithms资源-CSDN文库

版权申诉

81 浏览量 2022-01-22 08:31:35 上传评论收藏 740KB PDF 举报

资源详情

资源评论

arXiv:2107.04754v1 [cs.GT] 10 Jul 2021

Lower Bounds for Prior Independent Algorithms

Jason Hartline

∗

Aleck Johnsen

†

July 13, 2021

The prior independent framework for algorithm design considers how well an algorithm that

does not know the distribution of its inputs approximates the expected performance of the optimal

algorithm for this distribution. This paper gives a method that is agnostic to problem setting

for proving lower bounds on the prior independent approximation factor of any algorithm. The

method constructs a correlated distribution over inputs that can be generated both as a distribu -

tion over i.i.d. go od-for-algorithms distributions and as a distribution over i.i.d. bad-for-algorithms

distributions. Prior independent algorithms are upper-boun ded by the optimal algorithm for the

latter distrib ution even when the true distribution is the former. Thus, the ratio of the expected

performances of the Bayesian optimal algorithms for these two decompositions is a lower bound on

the prior independent approximation ratio. The techniques of the paper connect prior independent

algorithm design, Yao’s Minimax Principle, an d information design. We apply this f ramework to

give new lower bounds on several canonical prior independent mechanism design problems.

∗

Northwestern U., Evanston IL. Work done in part while supported by NSF CCF 1618502.

Email: h artline@northwestern.edu

†

Northwestern U., Evanston IL. Work done in part while supported by NSF CCF 1618502.

Email: aleckjohnsen@u.northwestern.edu

1 Introduction

This paper develops a novel method for establishing lower bounds on prior independent approxi-

mation algorithms.

Stochastic models are enablin g theoretical understanding of algorithms beyond those provided

by classical worst-case treatments (see Rou gh gard en, 2019). These models are especially interesting

for algorithm design problems with information theoretic constraints such as online algorithms,

mechanism design, streaming algorithms, etc. The Bayesian algorithm design problem can be

viewed as a two stage process. In the ﬁrst s tage the input is the prior distribution and an algorithm

is constructed for the distribution. In the second stage the constructed algorithm is run on the

realized input. The Bayesian optimal algorithm is the one w ith the highest expected performance.

The prior independent f ramework evaluates algorithms, which are not privy to the (ﬁrst stage)

prior distribution of inputs, against a benchmark deﬁned as the performance of the Bayesian op-

timal algorithm that is constructed for this prior. With no constraints on the prior distribu tion,

this problem is equivalent to classical worst-case algorithm design. Alternatively, prior indepen-

dent analyses in mechanism design (e.g., Dhangwatnotai et al., 2015) and online learning (e.g.,

Auer et al., 2002) r estrict th e distributions to be in dependent and identically distributed (i.i.d.),

respectively over values of agents in a mechanism and rounds of online inputs.

This paper develops a method f or establishing lower bounds on the performance of prior in-

dependent algorithms (for classes of i.i.d. distributions). The method is based on Yao’s Minimax

Principle (Yao, 1977). The prior independent framework asks for th e designer to p ick one algorithm

that is good on an adversary’s chosen worst-case distribution. Yao’s minimax principle allows the

order of moves of the designer and adversary to be swapped. Thus, the prior independent op -

timal approximation ratio can be equ ivalently identiﬁed by an adversary choosing a distribution

over prior distributions and then the designer choosing a best algorithm. Note that the class of

i.i.d. distributions is not closed under convex combination, thus, the adversary’s distr ibution over

distributions generally gives a symmetric, correlated distribution over inputs.

The m ain object of study of this paper is dual blends, w hich are pairs of distinct distributions

over i.i.d. distributions of inputs that ind uce the same correlated d istribution. To establish a

prior independent lower bound, we will be considering dual blends where one s ide of the dual

blend mixes over good-for-algorithms distributions and the other side mixes over bad-for-algorithms

distributions. The adversary can choose the mix over good-for-algorithms distributions in which

case the expectation over Bayesian optimal performances for this mix deﬁnes the ben chmark of the

prior independent framework. On the other hand, the algorithm cannot tell the two blends apart

and thus its expected performan ce is upper bounded by the expectation over performances of the

Bayesian optimal algorithms for the bad-for-algorithms mix.

As a s im ple example, consider the mechanism design problem of posting a price to a single

agent with value on [1, h]. (Here the restriction to i.i.d. distributions is trivial as there is only

one agent.) A class of good-for-algorithms distributions is given by point masses. Note that the

Bayesian optimal pricing mechanism for a point mass is to post identically the same price as the

value (at which the agent always buys). A class of bad-for-algorithms distributions is given by

the equal revenue distribution with cumulative distribution F (x) = 1 −

/x and a point mass of

/h at h. The equal revenue d istribution has the property that the expected revenue from any

posted price is 1 (the agent bu y s if her value is at least the price). Now consider the dual blend

where on the good-for-algorithms side we have the equal revenue distribution over point masses

and on the bad-for-algorithms side we have a point mass on the equal r evenue distr ibution. Th e

expected revenue over Bayesian optimal algorithms (in response to point mass distributions) from

the good-for-algorithms side is the expected value of the equal revenue distr ibution on [1, h], i.e.,

1 + ln h. The expected revenue from the bad-for-algorithms side is 1. Thus, we have established a

lower bound of 1 + ln h on the approximation factor of single-agent posted pricing. (In fact, this

example analysis is tight due to a matching upper bound f rom Hartline an d Rou gh gard en, 2014.)

There are two challenges in establishing lower bounds for prior independent algorithms via the

blends metho d. The ﬁrst challenge is in suﬃciently understand ing the Bayesian optimal algorithm

for the class of distributions under consideration. In several of the central studied areas of Bayesian

algorithms, this ﬁ rst challenge is s olved in closed form . Bayesian optimal mechanisms are identiﬁed

broadly by Myerson (1981). For online learning with payoﬀs that are i.i.d. across rounds, the

Bayesian optimal algorithm is trivial, it selects the action w ith the highest expected payoﬀ (which

is the same in each round). Of course, when closed forms are not available, boun ds on th e Bayesian

optimal performance can be employed instead. An im portant observation of the method of dual

blends is th at not only are Bayesian optimal algorithms used to deﬁne the benchmark, but they can

also be used to get non-trivial bounds on any algorithm’s prior independent approximation ratio.

The second challenge of the blends method is in identifying dual blends where the expected

Bayesian-optimal performances for good-for-algorithms and bad-for-algorithms distributions are

signiﬁcantly sep arated. In pursuit of this challenge we give two general appr oaches for constructing

dual blends for inputs of size two. (Many of the challenge problems in prior ind ependent mechanism

design are for inputs of size two, e.g., Hartline et al., 2020.) The ﬁrst approach is based on the

observation that when the density function of a correlated distribution on inputs of size two can

be written as a separable product of independent functions per order statistic of th e inputs, then

it can be decomposed into two distinct distributions over i.i.d. distributions. The second approach

considers one side of the dual blend constructed from any s caled class of distributions with the

other side given by the inverse-distributions of these (for which, as a class, the roles of values and

scales are reversed in comparison to the original class).

We apply the blends method to two canonical problems in mechanism design. Both are two-

agent single-item environments. One consider s the objective of revenue maximization under a

standard regularity assumption on the distribution. The other considers the objective of residual

surplu s maximization (i.e., maximizing the value of the winner minus any p ayments made). Under

the restriction to scale invariant mechanisms , Hartline et al. (2020) identiﬁed the prior independent

optimal mechanism for revenue (and its approximation factor of about 1.907). It is unknown

whether the restriction to scale-invariant mechanisms is with loss. We use the blends method to

establish an unconditional lower bound of

/18 ≈ 1.2777. For the residual surplus objective, an

upper bound of

/3 exists as a corollary of Hartline and Roughgarden (2014). We establish a lower

bound of 1.00623 (no previous lower bound was known).

There are a number of signiﬁcant open questions pertaining to lower bound s for prior inde-

pendent algorithm design from the method of dual blends. First, determine whether there are

non-trivial settings where the m ethod from dual blends is tight. Second, develop methods for op ti-

mizing the lower bound over classes of dual b lends. Third, generalize the method beyond two-input

models. O n this last point, while there are important problems in mechanism design with inputs of

size two, other settings would beneﬁ t from generalization to larger inputs, such as online algorithms.

Related Work The prior independent model was introduced in mechanism design by Hartline and Roughgarden

(2008) and further reﬁned by Dhangwatnotai et al. (2015). At the time it was conjectured that

the second-price auction was the prior independent revenue-optimal mechanism for selling a single

item to one of two agents with i.i.d. values from a regular distribution (Dhangwatnotai et al. (2015)

had shown that it guaranteed an upper bound of 2-approximation). Fu et al. (2015) disp roved this

conjecture by identifying a mechanism with an improved upper bound. Allouah an d Besbes (2018)

– with an additional restriction to scale-invariant mechanisms – proved a weaker version of the con-

jecture (restriction to monotone hazard rate distr ibutions); and for r egular distributions: improved

the upper bound and gave th e ﬁrst non-trivial lower bound for prior independent approximation

(by establishing a gap for speciﬁc distributions). Hartline et al. (2020) proved the tight result for

regular distributions under the scale-invariance restriction.

Hartline et al. (2020) connected the prior ind ependent model from mechanism design with the

standard model for online learning. Most relevantly in relation to our work on prior independent

lower bou nds, th ey showed that the simple follow-the-leader algorithm is optimal for expert learning

in prior independent settings (by direct analysis rather than by showing a matching lower bound).

Main Paper Outline Section 2 gives formal preliminaries of the prior independent setting and

proves lower bounds of the Blends Technique. Section 3 gives an explicit example of dual blends

and applies it to two distinct settings within mechanism design to show novel prior independent

lower bounds. Section 4 identiﬁes two large classes of blends solutions, each distinctively motivated

as a generalization of the example of Section 3. Section 5 connects blends to information design

and considers the structure of blends’ information as it relates to Blackwell ordering. A secondary

outline for the appendix sections is included at the beginning of Appendix A.

2 Prior Independent Setup and Lower Bound Technique

Let F be a class of probability distributions with known ﬁxed sup port V (e.g., [0, ∞)). In the prior

independent algorithm design setting (PI), there is a distribution F which is known to come from

the class F and n inputs are drawn i.i.d. from F (thus input space is V

). Critically, the algorithm

designer does not know the speciﬁc F ∈ F. The notation F is overloaded to be the cumulative

distribution function (CDF), and its probability density function (PDF) is f .

Fix an algorithm design prob lem that takes n i.i.d. inputs. Denote a class of feasible algorithms

by A and an algorithm in this class by A with expected performance A(v) for inputs v. Wh en

evaluating the performance in expectation over inputs drawn from a distribution F , we adopt the

notation A(F ) = E

v∼F

[A(v)]. An algorithm’s performance for an unknown distribution F is mea-

sured against the performance of the optimal algorithm which knows F . With these abstractions,

we formally deﬁne the Bayesian and prior independent (PI) optimization problems.

Deﬁnition 1. The Bayesian optimal algorithm design problem is given by a distribution F and

class of algorithms A; and solves for the algorithm O PT

with the maximum expected performance:

OPT

= argmax

A∈A

A(F ). (OPT

)

Note that OPT

is an algorithm. Given a distr ibution F , the expected performan ce of the optimal

algorithm is OPT

(F ) and is the benchmark that we use for prior independent algorithms:

Deﬁnition 2. The prior indepen dent algorithm design problem is given by a class of algorithms

A and a class of distributions F; and searches for the algorithm that minimizes its worst-case

approximation:

= min

A∈A



max

F ∈F

OPT

(F )

A(F )



(α

)

where the value of the program α

is the optimal prior independent approximation factor for class

F and class A (which we leave implicit).

2.1 Theoretical Lower Bounds from Minimax

Yao’s Minimax Principle (Theorem 1) illustr ates the role of the adversary through a direct con-

nection to a 2-player zero-sum game. First we deﬁne additional terms for use in Theorem 1 and

throughout the paper. Given a space Ω, denote the set of all possible distributions by ∆(Ω) – i.e.,

the probability simplex. Denote a distribution over elements ω ∈ Ω by γ ∈ ∆(Ω). Given a function

f : Ω

× Ω

→ R where Ω

and Ω

have arbitrary dimensions, we denote the expectation of f over

arguments ω

∈ Ω

according to γ

∈ ∆(Ω

) as f (γ

, ω

j6= i

) = E

∼γ

[f(ω

, ω

)], e.g., in Theorem 1.

Theorem 1 (Yao, 1977). [Yao’s Minimax Principle] Given a 2-player zero-sum game G in which

sequentially player 1 chooses mixed action γ

∈ ∆(Ω

), then player 2 chooses action ω

∈ Ω

. The

players are cost minimizers and the cost functions on pure actions are (any real-valued function)

(ω

, ω

) ≥ 0 and C

= −C

. Then the value of game G (the left-hand side) satisﬁes:

inf

∈∆(Ω

)

sup

∈Ω

(γ

, ω

) ≥ sup

∈∆(Ω

)

inf

∈Ω

(ω

, γ

) (1)

2.2 A Technique for Prior Independent Lower Bounds: Blends

There is a detailed explanation of the high-level technique of lower bounds from Yao’s Min im ax

Principle in the textbook by Borodin and El-Yaniv (1998). T his section gives a min im ax approach

that is speciﬁc to prior in dependent design. To outline, we: (a) ﬁx a ran domization over adversary

strategies in advance; (b) prove an upper bound on the performance of the best-response algorithm

from an alternative description of the adversary’s induced correlated distribution over inputs; and

on the expected performance of any algorithm. The key idea is the correlation in (b):

Deﬁnition 3. A blend is a distribution-over-distributions

δ ∈ ∆(F). (Thus, δ(F ) is the density at

F .) A blended distribution δ

∈ ∆(V

) is the induced density function of the correlated distribution

resulting f rom n i.i.d. draws f rom a common distribution

F , with

F drawn from δ.

Two blends δ

, δ

are called dual blends if there exists correlated density function g such that:

(v) = g(v) = δ

(v) ∀ v

Each of δ

, δ

are a side of the dual blend. Finally, deﬁne opt

n,i

= E

F ∼δ

[OPT

(F )] to be the

expected performance of an optimal algorithm which knows F over a blend δ

The point is: an arb itrary blend δ can be “ﬂ attened” to describe a speciﬁc (symmetric) correlated

distribution δ

= g over input space V

. Now suppose in fact two distinct blends δ

and δ

as choices

of the PI adversary induce the same correlated distribution, i.e., they satisfy Deﬁnition 3. Because

both induce the same description of input proﬁles, every algorithm is limited by th e structure of

剩余65页未读，继续阅读

评论收藏

内容反馈

版权申诉

先验独立算法的下界_Lower Bounds for Prior Independent Algorithms

评论0

最新资源

先验独立算法的下界_Lower Bounds for Prior Independent Algorithms

评论0

最新资源

相关推荐

Blum、Floyd、Pratt、Rivest、Tarjan__Time bounds for selection.pdf

插入和删除的局部可解码和可纠正码的指数下界_Exponential Lower Bounds for Locally Decod

所有光滑度阶凸优化的近似最优下界_Near-Optimal Lower Bounds For Convex Optimizati

加性噪声信道下学习通信的泛化界和算法_Generalization Bounds and Algorithms for Lear

DevPartner_Visual_C++_Boundschecker_11.0000.part4.rar

DevPartner_Visual_C++_Boundschecker_11.0000.part3.rar

DevPartner_Visual_C++_Boundschecker_11.0000.part2.rar

平面波电子结构计算中性质的实用误差界_Practical error bounds for properties in plan

DevPartner_Visual_C++_Boundschecker_11.0000

Conditional Cramer-Rao Lower Bounds for DOA Estimation and Array Calibration

Fast Exponentiation with Precomputation: Algorithms and Lower Bounds

算法导论_英文第三版

Time Bounds For Selection

Using Confidence Bounds for Exploitation-Exploration Trade-offs

gems of theoretical computer science

算法导论--Introduction.to.Algorithms

通俗易懂讲解Cramer-Rao下界

expected time bounds for selection

计算机编程艺术(The Art of Computer Programming)四卷全.part4

Cobalt Strike下载

北京邮电大学计算机考研复试笔试资料

计算机系统-笔记-HUN2021级

cs1.6老版本供下载

合成孔径雷达的经典成像算法cs(matlab)仿真代码（吐血整理，内容全，注释全）

港大CS（MSC）面试整理

合成孔径雷达RD CS OmegaK算法点目标仿真.rar

计算机科学导论原书第二版答案.zip

Cobalt-Strike-4.5

cobaltstrike4.3.zip