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 efficiency and budget balance for designing mechanisms in generalquasi-linear domains. Green and Laffont (1979) proved that one cannotgenerically achieve both. We consider strategyproof budget-balanced mechanismsthat are approximately efficient. For deterministic mechanisms, we show that astrategyproof and budget-balanced mechanism must have a sink agent whosevaluation function is ignored in selecting an alternative, and she iscompensated with the payments made by the other agents. We assume thevaluations of the agents come from a bounded open interval. Using this result,we find a tight lower bound on the inefficiencies of strategyproof,budget-balanced mechanisms in this domain. The bound shows that theinefficiency asymptotically disappears when the number of agents is large---aresult close in spirit to Green and Laffont (1979, Theorem 9.4). However, ourresults provide worst-case bounds and the best possible rate of convergence.  Next, we consider minimizing any convex combination of inefficiency andbudget imbalance. We show that if the valuations are unrestricted, nodeterministic mechanism can do asymptotically better than minimizinginefficiency alone.  Finally, we investigate randomized mechanisms and provide improved lowerbounds on expected inefficiency. We give a tight lower bound for an interestingclass of strategyproof, budget-balanced, randomized mechanisms. We also use anoptimization-based approach---in the spirit of automated mechanism design---toprovide a lower bound on the minimum achievable inefficiency of any randomizedmechanism.  Experiments with real data from two applications show that the inefficiencyfor a simple randomized mechanism is 5--100 times smaller than the worst case.This relative difference increases with the number of agents.

Efficiency and Budget Balance in General Quasi-linear Domains