När man donerar pengar till en (säg, välgörenhet) orsak, är det möjligt att använda den planerade donationen som ett förhandlingschip för att få andra parter som är intresserade av välgörenhet att donera mer. Sådana förhandlingar görs vanligtvis i form av matchande erbjudanden, där en part lovar att betala ett visst belopp om andra betalar ett visst belopp. I sin nuvarande form tillåter dock matchningserbjudanden endast begränsade förhandlingar. För en, är det inte omedelbart klart hur flera parter kan göra matchande erbjudanden på samma gång utan att skapa cirkulära beroenden. Det är inte heller omedelbart klart hur man gör en donation villkorad av andra donationer till flera välgörenhetsorganisationer när donatorn har olika nivåer av uppskattning för de olika välgörenhetsorganisationerna. I båda dessa fall orsakar den begränsade expressiviteten i matchningserbjudanden ekonomisk förlust: det kan hända att ett arrangemang som alla parter (givare och välgörenhetsorganisationer) skulle ha föredragit inte kan uttryckas i form av matchningserbjudanden och därför inte kommer att förekomma. I detta dokument introducerar vi ett budspråk för att uttrycka mycket allmänna typer av matchande erbjudanden över flera välgörenhetsorganisationer. Vi formulerar motsvarande clearing problem (besluta hur mycket varje budgivare betalar, och hur mycket varje välgörenhet får), och visa att det inte kan approximeras till något förhållande i polynom tid om inte P = NP, även i mycket begränsade inställningar. Vi ger ett blandat heltal program formulering av clearing problem, och visa att för konkava bud, programmet minskar till ett linjärt program. Vi visar sedan att clearingproblemet för en underklass konkava bud är minst lika svårt som beslutsvarianten för linjär programmering. Vi överväger också fallet där varje välgörenhet har ett målbelopp, och budgivarnas villighet att betala funktioner är konkava. Här visar vi att det optimala överskottet kan uppskattas till ett förhållande m, antalet välgörenhetsorganisationer, i polynom tid (och ingen signifikant bättre approximation är möjlig i polynom tid om inte P = NP); inget polynom-tids approximationsförhållande är möjligt för maximering av den totala donerade, såvida inte P = NP. Därefter visar vi att clearingproblemet är mycket lättare när bud är kvasilinear-för maximering överskott, problemet bryts ner över välgörenhet, och för att maximera den totala donerade, en girig strategi är optimal om buden är konkava (även om detta senare problem är svagt NP-hård när buden inte konkava). För den kvasilinjära inställningen studerar vi frågan om mekanismens utformning. Vi visar att en effektiv mekanism i efterhand är omöjlig även med endast en välgörenhet och en mycket begränsad grupp av bud. Vi visar också att det kan finnas fördelar med att koppla samman välgörenhetsorganisationerna ur ett mekanismutformningsperspektiv. Slutligen diskuterar vi ett experiment där vi använde denna metod för att samla in pengar till offren för Tsunami i Indiska oceanen 2004.
Ett annat konkret exempel är arbetet av REF, som övervägde problemet med att uttrycka matchande erbjudanden, det vill säga erbjuder att donera när andra parter donerar också, i samband med välgörenhet.
Expressive markets for donating to charities
{'venue': 'ARTIFICIAL INTELLIGENCE', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}