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 an online matching problem with concave returns. This problem isa significant generalization of the Adwords allocation problem and has vastapplications in online advertising. In this problem, a sequence of items arrivesequentially and each has to be allocated to one of the bidders, who bid acertain value for each item. At each time, the decision maker has to allocatethe current item to one of the bidders without knowing the future bids and theobjective is to maximize the sum of some concave functions of each bidder'saggregate value. In this work, we propose an algorithm that achievesnear-optimal performance for this problem when the bids arrive in a randomorder and the input data satisfies certain conditions. The key idea of ouralgorithm is to learn the input data pattern dynamically: we solve a sequenceof carefully chosen partial allocation problems and use their optimal solutionsto assist with the future decision. Our analysis belongs to the primal-dualparadigm, however, the absence of linearity of the objective function and thedynamic feature of the algorithm makes our analysis quite unique.

A Near-Optimal Dynamic Learning Algorithm for Online Matching Problems with Concave Returns