English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider Vickrey-Clarke-Groves (VCG) auctions for a very generalcombinatorial structure, in an average-case setting where item costs areindependent, identically distributed uniform random variables. We prove thatthe expected VCG cost is at least double the expected nominal cost, and exactlydouble when the desired structure is a basis of a bridgeless matroid. In thematroid case we further show that, conditioned upon the VCG cost, theexpectation of the nominal cost is exactly half the VCG cost, and we showseveral results on variances and covariances among the nominal cost, the VCGcost, and related quantities. As an application, we find the asymptoticvariance of the VCG cost of the minimum spanning tree in a complete graph withrandom edge costs.

VCG Auction Mechanism Cost Expectations and Variances