Benefits of Permutation-Equivariance in Auction Mechanisms
- URL: http://arxiv.org/abs/2210.05579v1
- Date: Tue, 11 Oct 2022 16:13:25 GMT
- Title: Benefits of Permutation-Equivariance in Auction Mechanisms
- Authors: Tian Qin, Fengxiang He, Dingfeng Shi, Wenbing Huang, Dacheng Tao
- Abstract summary: An auction mechanism that maximizes the auctioneer's revenue while minimizes 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.
- Score: 90.42990121652956
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Designing an incentive-compatible auction mechanism that maximizes the
auctioneer'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 defined 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 significant 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 theoretically
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 first work towards
understanding the benefits of permutation-equivariance in auction mechanisms.
Related papers
- Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
We consider a problem where an auctioneer sells an indivisible good to groups of buyers in every round, for a total of $T$ rounds.
The auctioneer aims to maximize their discounted overall revenue while adhering to a fairness constraint that guarantees a minimum average allocation for each group.
arXiv Detail & Related papers (2024-05-31T19:26:05Z) - Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions [18.086061048484616]
We study finite-sum monotone inclusion problems, which model broad classes of equilibrium problems.
Our main contributions are variants of the classical Halpern iteration that employ variance reduction to obtain improved complexity guarantees.
We argue that, up to poly-logarithmic factors, this complexity is unimprovable in the monotone Lipschitz setting.
arXiv Detail & Related papers (2023-10-04T17:24:45Z) - No Bidding, No Regret: Pairwise-Feedback Mechanisms for Digital Goods
and Data Auctions [14.87136964827431]
This study presents a novel mechanism design addressing a general repeated-auction setting.
The mechanism's novelty lies in using pairwise comparisons for eliciting information from the bidder.
Our focus on human factors contributes to the development of more human-aware and efficient mechanism design.
arXiv Detail & Related papers (2023-06-02T18:29:07Z) - Optimal-er Auctions through Attention [3.1423836318272773]
We propose two independent modifications of RegretNet, namely a new neural architecture based on the attention mechanism, denoted as TransRegret, and an alternative loss function that is interpretable.
In all experiments, we find that TransRegret consistently outperforms existing architectures in revenue.
arXiv Detail & Related papers (2022-02-26T10:47:12Z) - A Context-Integrated Transformer-Based Neural Network for Auction Design [25.763612577196124]
One of the central problems in auction design is developing an incentive-compatible mechanism that maximizes the auctioneer's expected revenue.
We propose $mathttCITransNet$, a context-integrated transformer-based neural network for optimal auction design.
We show by extensive experiments that $mathttCITransNet$ can recover the known optimal solutions in single-item settings, outperform strong baselines in multi-item auctions, and generalize well to cases other than those in training.
arXiv Detail & Related papers (2022-01-29T03:47:00Z) - A Game-Theoretic Analysis of the Empirical Revenue Maximization
Algorithm with Endogenous Sampling [19.453243313852557]
Empirical Revenue Maximization (ERM) is one of the most important price learning algorithms in auction design.
We generalize the definition of an incentive-awareness measure proposed by Lavi et al to quantify the reduction of ERM's outputted price due to a change of $mge 1$ out of $N$ input samples.
We construct an efficient, approximately incentive-compatible, and revenue-optimal learning algorithm using ERM in repeated auctions against non-myopic bidders, and show approximate group incentive-compatibility in uniform-price auctions.
arXiv Detail & Related papers (2020-10-12T08:20:35Z) - VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit
Feedback [104.06766271716774]
We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values.
We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism.
Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
arXiv Detail & Related papers (2020-04-19T18:00:58Z) - A Permutation-Equivariant Neural Network Architecture For Auction Design [49.41561446069114]
Design of an incentive compatible auction that maximizes expected revenue is a central problem in Auction Design.
In this work, we consider auction design problems that have permutationequivariant symmetry and construct a neural architecture that is capable of perfectly recovering the permutationequi optimal mechanism.
arXiv Detail & Related papers (2020-03-02T00:37:36Z) - SetRank: A Setwise Bayesian Approach for Collaborative Ranking from
Implicit Feedback [50.13745601531148]
We propose a novel setwise Bayesian approach for collaborative ranking, namely SetRank, to accommodate the characteristics of implicit feedback in recommender system.
Specifically, SetRank aims at maximizing the posterior probability of novel setwise preference comparisons.
We also present the theoretical analysis of SetRank to show that the bound of excess risk can be proportional to $sqrtM/N$.
arXiv Detail & Related papers (2020-02-23T06:40:48Z) - Generalization Guarantees for Multi-item Profit Maximization: Pricing,
Auctions, and Randomized Mechanisms [86.81403511861788]
We study multi-item profit when there is an underlying distribution over buyers' values.
For any set of buyers' values, profit is piecewise linear in the mechanism's parameters.
We prove new bounds for mechanism classes not yet in the sample-based mechanism design literature.
arXiv Detail & Related papers (2017-04-29T22:02:14Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.