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 truthful mechanisms for hiring a team of agents in three classes ofset systems: Vertex Cover auctions, k-flow auctions, and cut auctions. ForVertex Cover auctions, the vertices are owned by selfish and rational agents,and the auctioneer wants to purchase a vertex cover from them. For k-flowauctions, the edges are owned by the agents, and the auctioneer wants topurchase k edge-disjoint s-t paths, for given s and t. In the same setting, forcut auctions, the auctioneer wants to purchase an s-t cut. Only the agents knowtheir costs, and the auctioneer needs to select a feasible set and paymentsbased on bids made by the agents.  We present constant-competitive truthful mechanisms for all three setsystems. That is, the maximum overpayment of the mechanism is within a constantfactor of the maximum overpayment of any truthful mechanism, for every setsystem in the class. The mechanism for Vertex Cover is based on scaling eachbid by a multiplier derived from the dominant eigenvector of a certain matrix.The mechanism for k-flows prunes the graph to be minimally (k+1)-connected, andthen applies the Vertex Cover mechanism. Similarly, the mechanism for cutscontracts the graph until all s-t paths have length exactly 2, and then appliesthe Vertex Cover mechanism.

Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts