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 study the measure of order-competitive ratio introduced by Ezra et al.[2023] for online algorithms in Bayesian combinatorial settings. In oursetting, a decision-maker observes a sequence of elements that are associatedwith stochastic rewards that are drawn from known priors, but revealed one byone in an online fashion. The decision-maker needs to decide upon the arrivalof each element whether to select it or discard it (according to somefeasibility constraint), and receives the associated rewards of the selectedelements. The order-competitive ratio is defined as the worst-case ratio (overall distribution sequences) between the performance of the best order-unawareand order-aware algorithms, and quantifies the loss incurred due to the lack ofknowledge of the arrival order.  Ezra et al. [2023] showed how to design algorithms that achieve betterapproximations with respect to the new benchmark (order-competitive ratio) inthe single-choice setting, which raises the natural question of whether thesame can be achieved in combinatorial settings. In particular, whether it ispossible to achieve a constant approximation with respect to the best onlinealgorithm for downward-closed feasibility constraints, whether$\omega(1/n)$-approximation is achievable for general (non-downward-closed)feasibility constraints, or whether a convergence rate to $1$ of$o(1/\sqrt{k})$ is achievable for the multi-unit setting. We show, by devisingnovel constructions that may be of independent interest, that for all threescenarios, the asymptotic lower bounds with respect to the old benchmark, alsohold with respect to the new benchmark.

The Importance of Knowing the Arrival Order in Combinatorial Bayesian Settings