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

In most social choice settings, the participating agents express theirpreferences over the different alternatives in the form of linear orderings.While this clearly simplifies preference elicitation, it inevitably leads topoor performance with respect to optimizing a cardinal objective, such as thesocial welfare, since the values of the agents remain virtually unknown. Thisloss in performance because of lack of information is measured by the notion ofdistortion. A recent array of works put forward the agenda of designingmechanisms that learn the values of the agents for a small number ofalternatives via queries, and use this limited extra information to makebetter-informed decisions, thus improving distortion. Following this agenda, inthis work we focus on a class of combinatorial problems that includes mostwell-known matching problems and several of their generalizations, such asOne-Sided Matching, Two-Sided Matching, General Graph Matching, and$k$-Constrained Resource Allocation. We design two-query mechanisms thatachieve the best-possible worst-case distortion in terms of social welfare, andoutperform the best-possible expected distortion achieved by randomized ordinalmechanisms.

Don't Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond