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 the random assignment problem, objects are randomly assigned to agentskeeping in view the agents' preferences over objects. A random assignmentspecifies the probability of an agent getting an object. We examine thestructural and computational aspects of ex post efficiency of randomassignments. We first show that whereas an ex post efficient assignment can becomputed easily, checking whether a given random assignment is ex postefficient is NP-complete. Hence implementing a given random assignment viadeterministic Pareto optimal assignments is NP-hard. We then formalize anotherconcept of efficiency called robust ex post efficiency that is weaker thanstochastic dominance efficiency but stronger than ex post efficiency. Wepresent a characterization of robust ex post efficiency and show that it can betested in polynomial time if there are a constant number of agent types. It isshown that the well-known random serial dictatorship rule is not robust ex postefficient. Finally, we show that whereas robust ex post efficiency dependssolely on which entries of the assignment matrix are zero/non-zero, ex postefficiency of an assignment depends on the actual values.

Structure and complexity of ex post efficient random assignments