AI Paper Atlas

Research map / Learning theory and algorithms / Combinatorial and search optimization

Partial Verification as a Substitute for Money

Sofia Ceppi, Ian Kash, Rafael Frongillo

AAAI 2019 · Learning theory and algorithms › Combinatorial and search optimization · approach: Logic and answer set programming theory

Read the paperCheck your idea against 137,217 papers

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
Use truthful-in-expectation mechanisms instead of deterministic mechanismsSingle-agent mechanisms with no indifferences between assignments · General type spaceharmless-set sizeHurt
Allow universally truthful randomization over deterministic mechanismsSingle-agent mechanisms · General type spaceharmless setNo clear effect
Characterize verification using critical allocation hyperplanes for each pair of allocationsImplementable-with-payments allocation rules · More than two allocationsharmless-set characterizationImproved
Restrict reports to be close to the true typeVerification for implementable-with-payments allocation rules · Two allocationsprevention of profitable misreportsNo clear effect
Use asymmetric verification that rules out the half-space beyond the critical allocation hyperplaneVerification for implementable-with-payments allocation rules · Two allocationsprevention of profitable misreportsImproved
Add allocation-dependent verificationVerification for a fixed allocation rule · General mechanismsnumber of types requiring verificationImproved
Use no-underbidding and direction-imposing verificationFixed tie-breaking implementable-with-payments allocation rules · K-facility location on a linetruthfulnessImproved
Remove the requirement to verify when truthful allocation is already the agent's preferred allocationNo-underbidding and direction-imposing verification · K-facility location on a lineverification requiredImproved

Closest papers by meaning

Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy