Vi föreslår definitioner av substitut och komplement för information ("signaler") i samband med beslut eller optimeringsproblem, med spelteoretiska och algoritmiska tillämpningar. I ett spelteoretiskt sammanhang, ersätter fånga minskande marginellt värde av information till en rationell beslutsfattare. Där tar vi itu med det största öppna problemet i en grundläggande strategisk-information-revelation inställning, förutsägelse marknader. Vi visar att substitut karakteriserar "bästa möjliga" jämvikt med omedelbar informationsaggregation, medan komplement karakteriserar "sämsta möjliga", fördröjd aggregering. Spel-teoretiska program inkluderar också inställningar såsom crowdsourcing tävlingar och fråge-och svarsforum. I ett algoritmiskt sammanhang, där substitut fångar minskande marginell förbättring av information till ett optimeringsproblem, innebär substitut effektiva approximationsalgoritmer för en mycket allmän klass av (adaptiva) informationsinhämtningsproblem. Tillsammans med dessa breda tillämpningar undersöker vi strukturen och utformningen av informationssubstitut och komplement. De har motsvarande intuitiva definitioner ur olika perspektiv: submodularitet, geometri och informationsteori. Vi överväger också utformningen av poängsättningsregler eller optimeringsproblem för att uppmuntra utbytbarhet eller komplementaritet, med positiva och negativa resultat. Som helhet ger resultaten vissa belägg för att informationssubstitut parallellt med utbytbara objekt spelar en naturlig konceptuell och formell roll i spelteori och algoritmer.
En annan typ av arbete har studerat problemet med att dela information när indata är substitut eller komplement till REF, som definierade värdet av information (och av en marginell enhet av information) och omedelbar det i samband med förutsägelser marknader.
Informational Substitutes
{'venue': '2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Computer Science']}