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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The secretary and the prophet inequality problems are central to the field ofStopping Theory. Recently, there has been a lot of work in generalizing thesemodels to multiple items because of their applications in mechanism design. Themost important of these generalizations are to matroids and to combinatorialauctions (extends bipartite matching). Kleinberg-Weinberg \cite{KW-STOC12} andFeldman et al. \cite{feldman2015combinatorial} show that for adversarialarrival order of random variables the optimal prophet inequalities give a$1/2$-approximation. For many settings, however, it's conceivable that thearrival order is chosen uniformly at random, akin to the secretary problem. Forsuch a random arrival model, we improve upon the $1/2$-approximation and obtain$(1-1/e)$-approximation prophet inequalities for both matroids andcombinatorial auctions. This also gives improvements to the results of Yan\cite{yan2011mechanism} and Esfandiari et al. \cite{esfandiari2015prophet} whoworked in the special cases where we can fully control the arrival order orwhen there is only a single item.  Our techniques are threshold based. We convert our discrete problem into acontinuous setting and then give a generic template on how to dynamicallyadjust these thresholds to lower bound the expected total welfare.

Prophet Secretary for Combinatorial Auctions and Matroids