Beneﬁts of Permutation-Equivariance in Auction Mechanisms Tian Qin1 2Fengxiang He2Dingfeng Shi2Wenbing Huang3 4Dacheng Tao2

2025-04-24 0 0 1.13MB 31 页 10玖币

侵权投诉

Beneﬁts of Permutation-Equivariance in

Auction Mechanisms

Tian Qin1, 2∗Fengxiang He2∗Dingfeng Shi2Wenbing Huang3, 4 Dacheng Tao2

1University of Science and Technology of China 2JD Explore Academy, JD.com Inc.

3Gaoling School of Artiﬁcial Intelligence, Renmin University of China

4Beijing Key Laboratory of Big Data Management and Analysis Methods

tqin@mail.ustc.edu.cn, fengxiang.f.he@gmail.com,

shidingfeng@buaa.edu.cn, hwenbing@126.com, dacheng.tao@gmail.com

Abstract

Designing an incentive-compatible auction mechanism that maximizes the auc-

tioneer’s revenue while minimizes the bidders’ ex-post regret is an important yet

intricate problem in economics. Remarkable progress has been achieved through

learning the optimal auction mechanism by neural networks. In this paper, we

consider the popular additive valuation and symmetric valuation setting; i.e., the

valuation for a set of items is deﬁned as the sum of all items’ valuations in the

set, and the valuation distribution is invariant when the bidders and/or the items

are permutated. We prove that permutation-equivariant neural networks have sig-

niﬁcant advantages: the permutation-equivariance decreases the expected ex-post

regret, improves the model generalizability, while maintains the expected revenue

invariant. This implies that the permutation-equivariance helps approach the theo-

retically optimal dominant strategy incentive compatible condition, and reduces

the required sample complexity for desired generalization. Extensive experiments

fully support our theory. To our best knowledge, this is the ﬁrst work towards

understanding the beneﬁts of permutation-equivariance in auction mechanisms.

1 Introduction

Optimal auction design [

] has wide applications in economics, including computational advertising

[

], resource allocation [

], and supply chain [

]. In an auction, every bidder has a private valuation

proﬁle over all items, and accordingly, submits her bid proﬁle. An auctioneer collects the bids from

all bidders, and determines a feasible item allocation to the bidders as well as the prices the bidders

need to pay. Consequently, every bidder receives her utility. From the auctioneer’s perspective, the

optimal auction mechanism is required to maximize her revenue, deﬁned as the sum of all bidders’

payments. From the aspect of the bidders, the optimal auction mechanism needs to incentivize every

bidder to bid their truthful valuation proﬁles (truthful bidding). This is summarized as the dominant

strategy incentive compatible (DSIC) condition; i.e., truthful bidding is always the dominant strategy

for every bidder [25].

The optimal auction mechanism can be approximated via neural networks [

]. The “approx-

imation error”, or the “distance” to the DSIC condition, is usually measured by the ex-post regret,

deﬁned as the gap between the bidder’s utility of truthful bidding and the utility when her bid proﬁle

is only the best to herself (selﬁsh bidding), while the bid proﬁles of all other bidders are ﬁxed in both

cases [

]. When a bidder’s ex-post regret is

, truthful bidding is her dominant strategy. Therefore,

the optimal auction design can be modeled as a linear programming problem, where the object is to

maximize the expected revenue subject to the expected ex-post regret being

for all bidders [

∗Both authors contributed equally.

36th Conference on Neural Information Processing Systems (NeurIPS 2022).

arXiv:2210.05579v1 [cs.GT] 11 Oct 2022

Another major consideration in learning the optimal mechanism is the generalizability to unseen data,

usually measured by the generalization bound,i.e., the upper bound of the gap between the expected

revenue/ex-post regret and their empirical counterparts on the training data [12].

In this paper, we consider the popular setting of additive valuation and symmetric valuation [

]. The additive valuation condition deﬁnes the valuation for a set of items as the sum of the

valuations for all items in this set. The symmetric valuation condition assumes the joint distribution

of all bidders’ valuation proﬁles to be invariant when bidders and/or items are permutated. This

setting covers many applications in practice. For example, when items are independent, the additive

valuation condition holds. Moreover, if the auction is anonymous or the order of the items is not

prior-known, the symmetric valuation condition holds.

We demonstrate that permutation-equivariant models have signiﬁcant advantages in learning the

optimal auction mechanism as follows.

(1)

We prove that the permutation-equivariance in auction

mechanisms decreases the expected ex-post regret while maintaining the expected revenue invariant.

Conversely, and equivalently, the permutation-equivariance promises a larger expected revenue,

when the expected ex-post regret is ﬁxed.

(2)

We show that the permutation-equivariance of auction

mechanisms reduces the required sample complexity for desirable generalizability. We prove that

the

l∞,1

-distance between any two mechanisms in the mechanism space decreases when they are

projected to the permutation-equivariant mechanism (sub-)space. This smaller distance implies a

smaller covering number of the permutation-equivariant mechanism space, which further leads to a

small generalization bound [12].

We further provide an explanation for the learning process of non-permutation-equivariant neural

networks (NPE-NNs). In learning the optimal auction mechanism by an NPE-NN, we show that

an extra positive term exists in the quadratic penalty of the ex-post regret based on the result

(1)

This term serves as a regularizer to penalize the “non-permutation-equivariance”. Moreover, this

regularizer also interferes the revenue maximization, and thus affects the learning performance of

NPE-NNs. This further explains the advantages of permutation-equivariance in auction design.

Experiments in extensive auction settings are conducted to verify our theory. We design permutation-

equivariant versions of RegretNet (RegretNet-PE and RegretNet-test) by projecting the RegretNet

[

] to the permutation-equivariant mechanism space in the training and test stage respectively. The

empirical results show that permutation-equivariance helps: (1) signiﬁcantly improve the revenue

while maintain the same ex-post regret; (2) record the same revenue with a signiﬁcantly lower

ex-post regret; and (3) narrow the generalization gaps between the training ex-post regret and its test

counterpart. These results fully support our theory.

Related works.

Myerson completely solves the optimal auction design problem in one-item auctions

[

]. However, solutions are not clear when the number of bidders/items exceeds one [

]. Initial

attempts have been presented on the characterization of optimal auction mechanisms [

]

and algorithmic solutions [

]. Remarkable advances have been made in the required sample

complexity for learning the optimal auction mechanism in various settings, including single-item

auctions [

], multi-item single-bidder auctions [

], combinatorial auctions [

], and

allocation mechanisms [

]. Machine learning-based auction design (automated auction design)

have obtained considerable progress [

]. The optimal auction design is modeled as a linear

programming problem [

]. However, early works suffer from the scalability issues that the

number of the constraints grows exponentially when the bidder number and the item numbers

increase. To address this issue, recent works propose to learn the optimal auction mechanism by deep

learning. RegretNet is designed for multi-bidder and multi-item settings [

]. Then, RegretNet is

developed to meet more restrictive constraints, such as the budget condition [

] and the certifying

strategyproof condition [

]. Rahme et al. [

] propose the ﬁrst equivariant neural network-based

auction mechanism design method with signiﬁcant empirical advantages. Ivanov et al. [

] propose

a RegretFormer which (1) introduces attention layers to RegretNet to learn permutation-equivariant

auction mechanisms, and (2) adopts a new interpretable loss function to control the revenue-regret

trade-off. Duan et al. [

] extend the applicable domain to contextual settings. All these works

make remarkable contributions in designing new algorithms from the empirical aspect only. However,

the theoretical foundations are still elusive. To our best knowledge, our paper is the ﬁrst work on

theoretically studying the beneﬁts of permutation equivariance in auction design via deep learning.

2 Notations and Preliminaries

Auction.

Suppose

bidders are bidding

items in an auction. Every bidder

has her bidder-

context (feature)

xi∈ X

, while every item

is associated with its item-context (feature)

yj∈ Y

The bidder

has a private valuation

vij ∈ V ⊂ R≥0

for the item

, which is sampled from

a conditioned distribution

P(·|xi, yj)

. The value proﬁle

vi= (vi1, . . . , vim)

is unknown to the

auctioneer. For the simplicity, we deﬁne

x= (xT

1, . . . , xT

n)T

y= (y1, . . . , ym)

v= (vT

1, . . . , vT

n)T

v−i= (vT

1, . . . , vT

i−1, vT

i+1, . . . , vT

n)T, and (v0

i, v−i)=(vT

1,...,(v0

i)T...,vT

n)T.

Every bidder submits a bid proﬁle

to the auctioneer according to her valuation proﬁle. Then, the

auctioneer determines a feasible item allocation

g(b, x, y)

and corresponding payments

p(b, x, y)

per an auction mechanism (g, p). Consequently, every bidder receives her utility as

ui(vi, b, x, y) =

j=1

gij (b, x, y)·vij −pi(b, x, y).

The auction mechanism

(g, p)

consists of an allocation rule

g:Rn×m× X n× Ym→Rn×m

and a payment rule

p:Rn×m× X n× Ym→Rn×m

, where

gij

is the probability of allocating

item

to the bidder

, and

pi=Pm

j=1 pij

is the price that the bidder

should pay. To avoid

allocating an item over once, the allocation rule is constrained such that

i=1 gij (b, x, y)≤1

for all

j∈[m]

. Every

in our notations can be replaced by

. Thus, we can deﬁne the

similar notations:

b−i= (bT

1, . . . , bT

i−1, bT

i+1, . . . , bT

n)T

(bi, v−i)=(vT

1,...,(bi)T...,vT

n)T

and

(vi, b−i) = (bT

1,...,(vi)T...,bT

n)T.

Optimal auction mechanism.

An auction mechanism

(g, p)

is deﬁned to be dominant strategy

incentive compatible (DSIC), if truthful bidding is always a dominant strategy of every bidder; i.e.,

ui(vi,(vi, b−i), x, y)≥ui(vi, b, x, y),

for all

i∈[n]

v, b ∈ Vn×m

x∈ X n

and

y∈ Ym

. In addition, an auction mechanism

(g, p)

is called

individually rational (IR), if for any bidder-contexts

x∈ X n

, any item-contexts

y∈ Ym

, any bidder

i∈[n]x∈ X n

, valuation proﬁle and bid proﬁle

v, b ∈ Vn×m

, truthful bidding always leads to a

non-negative utility, i.e.,

ui(vi,(vi, b−i), x, y)≥0.

If an auction mechanism is DSIC and IR, a rational bidder with an obvious dominant strategy will

play it (bidding truthfully). Moreover, an optimal auction mechanism is required to maximize the

auctioneer’s expected revenue rev =E(v,x,y)Pn

i=1 pi(v, x, y).

Auction design. The ex-post regret regi(v, x, y)for the bidder iis deﬁned as

max

i∈Vmui(vi,(b0

i, v−i), x, y)−ui(vi, v, x, y).

An auction mechanism

(g, p)

is DSIC, if and only if

i=1 regi(v, x, y) = 0

for any value pro-

ﬁle

v∈ Vn×m

, bidder-context

x∈ X n

, and item-context

y∈ Ym

. Suppose the payment

rule

satisﬁes

pi(b, x, y)≤Pm

j=1 gij (b, x, y)bij

, which implies that each bidder has a non-

negative utility. Then, the auction design can be modeled as a linear programming problem that

maximizes the expected revenue

E(v,x,y)[Pn

i=1 pi(v, x, y)]

subject to the expected ex-post regret

E(v,x,y)[Pn

i=1 regi(v, x, y)] = 0

. Without loss of generality, the ex-post regret may refer to the

average of all bidders’ ex-post regrets.

Deﬁnition 2.1.

Suppose the network’s parameter is

, and the bidder

’s empirical payment and ex-

post regret are deﬁned as

LPL

l=1 pω

i(v(l), x(l), y(l)),

and

dregi(ω) = 1

LPL

l=1 regω

i(v(l), x(l), y(l))

where the sample set

{(v(l), x(l), y(l))}L

l=1

is i.i.d. sampled from the following prior distribution,

P(v, x, y) = Qn,m

i,j=1 P(vij |xi, yj)PXi(xi)PYj(yj).

Equivariant mapping.

We deﬁne a mapping

-equivariant if

ψg◦f=f◦ρg

for two chosen

group linear representations ρand ψand any gin group G.

Deﬁnition 2.2

(Permutation-Equivariant Mapping)

A permutation-equivariant mapping is deﬁned

to be

f:Rn×m→Rn×m

that for any instance

x∈Rn×m

, and permutation matrices

σn∈Rn×n

and σm∈Rm×m, we have f(σnxσm) = σnf(x)σm.

In this paper, we consider the bidder-permutation

σn∈Rn×n

and item-permutation

σm∈Rm×m

Speciﬁcally, we deﬁne a mapping

is bidder-symmetric or item-symmetric, if

f(σnx) = σnf(x)

f(xσm) = f(x)σm

, respectively. Moreover, we deﬁne an auction mechanism

(g, p)

as bidder-

symmetric or item-symmetric, if the allocation rule

and the payment rule

are both bidder-

symmetric or item-symmetric.

Orbit averaging.

For any feature mapping

f:F → G

, the orbit averaging

is deﬁned as

Qf=1

|G|Pg∈Gψ−1

g◦f◦ρg,

where

and

are two chosen group representations acting on the

feature spaces Fand G, respectively. Orbit averaging can project any mapping to be equivariant:

Proposition 2.3.

Orbit averaging

is a projection to the equivariant mapping space

{f:ψ◦f=

f◦ρ}

, i.e.,

ψ◦ Qf=Qf◦ρ

and

Q2=Q

. In particular, if

is already equivariant, then

Qf=f

Moreover,

and

Qreg

refer to the utility and the ex-post regret induced by

and

. For

the simplicity, we denote the orbit averagings that modify the auction mechanism to be bidder-

symmetric, item-symmetric, and bidder/item-symmetric by bidder averaging

, item averaging

and bidder-item aggregated averaging

. Besides, a detailed proof of the feasibility of the projected

mechanisms can be found in Appendix A.1.

Hypothesis complexity.

The generalizatbility to unseen data is usually measured by the generaliza-

tion bound, which depends on the hypothesis set’s complexity. To characterize the complexity of the

hypothesis set, we introduce the following deﬁnitions of covering number

N∞,1

and its corresponding

distance

l∞,1

. Based on the covering number, we can obtain a generalization bound in Theorem 3.6.

Deﬁnition 2.4

(

l∞,1

-distance)

Let

be a feature space and

a space of functions from

The l∞,1-distance on the space Fis deﬁned as l∞,1(f, g) = maxx∈X (Pn

i=1 |fi(x)−gi(x)|).

Deﬁnition 2.5

(Covering number)

Covering number

N∞,1(F, r)

is the minimum number of balls

with radius rthat can cover Funder l∞,1-distance.

3 Theoretical Results

This section presents the theoretical results. For simplicity, we view

p= (p1, . . . , pn)T

as a

n×1

matrix to present the prices the bidders should pay. We ﬁrst prove that the permutation-equivariance

induces the same expected revenue and a smaller expected ex-post regret in Section 3.1. Next in

Section 3.2, we prove that the permutation-equivariant mechanism space has a smaller covering

number, which promises a smaller required sample complexity and a better generalization. Detailed

proofs are omitted from the main text and given in supplementary materials due to space limitation.

3.1 Beneﬁts for Revenue and Ex-Post Regret

In this section, we discuss the beneﬁts for the revenue and the ex-post regret in the conditions of

bidder-symmetry and item-symmetry separately, and then discuss the beneﬁts when both of them

hold. Based on these results, we also study the learning process of non-permutation-equivariant

neural networks for auction design.

3.1.1 Beneﬁts in the Bidder/Item-Symmetry Condition

When the bidders come from the same distribution, the joint valuation distribution

is invariant

under bidder-permutation, i.e.

f(σnv, σnx, y) = f(v, x, y)

for any

σn∈Sn

. Meanwhile, when

the items are indistinguishable, the joint distribution

is invariant under item-permutation, i.e.,

f(vσm, x, yσm) = f(v, x, y)

for any

σm∈Sm

. Both conditions do not always hold simultaneously.

In this section, we study them separately.

To measure the “non-permutation-equivariance” of the mechanism, we introduce the conception of

regret gap between the projected mechanism and the original mechanism as below,

∆·(g, p;v, x, y) = max

v0∈Vn×m

i=1

ui(vi,(v0

i, v−i), x, y)−max

v0∈Vn×m

i=1

[Q·u]i(vi,(v0

i, v−i), x, y),

where

is the valuation proﬁles,

is the valuation proﬁle of bidder

is the bidder-context,

is the

item-context, and the orbit averaging Q·can be the bidder averaging Q1or the item averaging Q2.

The bidder averaging

and the item averaging

acting on the allocation rule

and the payment

rule p, respectively, are as below,

Q1g(v, x, y) = 1

n!X

σn∈Sn

σ−1

ng(σnv, σnx, y),Q1p(v, x, y) = 1

n!X

σn∈Sn

σ−1

np(σnv, σnx, y),

Q2g(v, x, y) = 1

m!X

σm∈Sm

g(vσm, x, yσm)σ−1

m,and Q2p(v, x, y) = 1

m!X

σm∈Sm

p(vσm, x, yσm).

We thus can prove the following theorem that characterizes the beneﬁts of permutation-equivariance

for revenue and ex-post regret in the condition of bidder/item-symmetry.

Theorem 3.1

(Beneﬁts for revenue and ex-post regret in the condition of bidder/item-symmetry)

When the valuation distribution is invariant under permutations of bidders/items, the projected

mechanism has the same expected revenue and a smaller expected ex-post regret, that is,

E(v,x,y)n

i=1

[Q·p]i(v, x, y)=E(v,x,y)n

i=1

pi(v, x, y),and (1)

E(v,x,y)n

i=1

regi(v, x, y)−E(v,x,y)n

i=1

[Q·reg]i(v, x, y)=E(v,x,y)h∆·(g, p;v, x, y)i≥0,

(2)

where pis the payment rule, reg is the ex-post regret, and Q·is the bidder/item averaging.

A smaller expected ex-post regret implies this mechanism is closer to the dominant strategy incentive

compatible condition. Conversely, and equivalently, when the expected ex-post regrets are ﬁxed,

the projected auction mechanism has a larger expected revenue. For any auction mechanism, in the

bidder/item-symmetry condition, we can project it through the bidder/item averaging.

Remark 3.2.

The mechanism space can be decomposed into the direct sum of the permutation-

equivariant mechanism space

{M :QM =M}

and the complementary space

{N :QN = 0}

[

]. Thus, a mechanism

has a unique decomposition:

M=QM +N

. The pure permutation-

equivariant part

contains all and only the “permutation-equivariance” of the mechanism

The pure non-permutation-equivariant part

is independent from the permutation-equivairance. In

this way, we may study the inﬂuence of permutation-equivariance by comparing the mechanism

and its permutation equivariant part QM.

3.1.2 Interplay between Bidder-Symmetry and Item-Symmetry.

If the valuation distribution is invariant under both bidder-permutation and item-permutation, we

can project the mechanism to be permutation-equivariant with respect to both bidder and item in

two steps (by mapping

Q1◦ Q2

or mapping

Q2◦ Q1

). Consequently, the projected mechanism has

the same expected revenue and a smaller expected ex-post regret. Equivalently, we can also project

an auction mechanism to be bidder-symmetric and item-symmetric immediately by the bidder-item

aggregated averaging Q3as below,

Q3g(v, x, y) = 1

n!m!X

σn∈SnX

σm∈Sm

σ−1

ng(σnvσm, σnx, yσm)σ−1

m,and

Q3p(v, x, y) = 1

n!m!X

σn∈SnX

σm∈Sm

σ−1

np(σnvσm, σnx, yσm).

We can prove that the bidder-item aggregated averaging

is the composition of the orbit averaging

operators

and

, as shown in the following lemma. This lemma shows that the order of

and

Q2would not inﬂuence their composition.

Lemma 3.3.

The bidder-item aggregated averaging is the composition of bidder averaging and item

averaging: Q3=Q1◦ Q2=Q2◦ Q1.

Based on this lemma, we can prove the following theorem on the beneﬁts of permutation-equivariance

for revenue and ex-post regret in the condition of both bidder-symmetry and item-symmetry.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

BenetsofPermutation-EquivarianceinAuctionMechanismsTianQin1,2FengxiangHe2DingfengShi2WenbingHuang3,4DachengTao21UniversityofScienceandTechnologyofChina2JDExploreAcademy,JD.comInc.3GaolingSchoolofArticialIntelligence,RenminUniversityofChina4BeijingKeyLaboratoryofBigDataManagementandAnalysisMethod...

展开>> 收起<<

Beneﬁts of Permutation-Equivariance in Auction Mechanisms Tian Qin1 2Fengxiang He2Dingfeng Shi2Wenbing Huang3 4Dacheng Tao2.pdf

共31页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Beneﬁts of Permutation-Equivariance in Auction Mechanisms Tian Qin1 2Fengxiang He2Dingfeng Shi2Wenbing Huang3 4Dacheng Tao2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: