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

Budget-feasible procurement has been a major paradigm in mechanism designsince its introduction by Singer (2010). An auctioneer (buyer) with a strictbudget constraint is interested in buying goods or services from a group ofstrategic agents (sellers). In many scenarios it makes sense to allow theauctioneer to only partially buy what an agent offers, e.g., an agent mighthave multiple copies of an item to sell, they might offer multiple levels of aservice, or they may be available to perform a task for any fraction of aspecified time interval. Nevertheless, the focus of the related literature hasbeen on settings where each agent's services are either fully acquired or notat all. The main reason for this, is that in settings with partial allocationslike the ones mentioned, there are strong inapproximability results. Under themild assumption of being able to afford each agent entirely, we are able tocircumvent such results in this work. We design a polynomial-time,deterministic, truthful, budget-feasible $(2+\sqrt{3})$-approximation mechanismfor the setting where each agent offers multiple levels of service and theauctioneer has a discrete separable concave valuation function. We then usethis result to design a deterministic, truthful and budget-feasible mechanismfor the setting where any fraction of a service can be acquired and theauctioneer's valuation function is separable concave (i.e., the sum of concavefunctions). The approximation ratio of this mechanism depends on how `nice' theconcave functions are, and is $O(1)$ for valuation functions that are sums of$O(1)$-regular functions (e.g., functions like $\log(1+x)$). For the specialcase of a linear valuation function, we improve the best known approximationratio for the problem from $1+\phi$ (by Klumper & Sch\"afer (2022)) to $2$.This establishes a separation between this setting and its indivisiblecounterpart.

Partial Allocations in Budget-Feasible Mechanism Design: Bridging Multiple Levels of Service and Divisible Agents