Vi presenterar ett nytt konvext flödesprogram som beskriver jämviktslösningar till linjära Arrow-Debreu-marknader. Konvexa formuleringar var tidigare kända ([Nenakov och Primak 1983; Jain 2007; Cornet 1989] ), vårt program uppvisar flera nya funktioner. Det ger ett enkelt nödvändigt och tillräckligt villkor och ett koncist bevis på förekomsten och rationaliteten av jämvikt och löser en öppen fråga som väcktes av Vazirani [2012]. Som en följd av detta får vi också ett enkelt nytt bevis på resultatet i Mertens [2003] att jämviktspriserna utgör ett konvext polyhedral set. Specialfall, den linjära Fisher-modellen, som formulerades av Fisher 1891, som också studerade jämviktens beräkningsbarhet via en hydraulisk maskin, inte mindre! (Se Brainard och Scarf [2000] för en fascinerande skildring.) I denna modell är agenterna uppdelade i två typer, köpare och säljare; köpare anländer till marknaden med en viss mängd pengar som de vill spendera på varor som erbjuds av säljarna. Denna modell visade sig vara betydligt enklare ur ett beräkningsperspektiv än den linjära Arrow-Debreu-modellen. En konvex programmeringsformulering gavs av Eisenberg och Gale [1959]. Problemet med jämviktsberäkning introducerades till det teoretiska datavetenskapliga samfundet av Devanur et al. [2008], som presenterade en polynom tid combinatorial primal-dual algoritm. Detta initierade en intensiv forskning, mest anmärkningsvärd bland vilka är en starkt polynom tid algoritm av Orlin [2010], för en undersökning, se Nisan et al. [2007, kapitel 5] eller Vazirani [2012]. Dessutom presenterade Shmyrev [2009] en ny typ av konvext program (som upptäcktes självständigt av Birnbaum et al. [2011] ) Fånga jämvikten. Låt oss nu övergå till den linjära Arrow-Debreu-modellen. Det första viktiga algoritmiska resultatet var en ändlig Lemke-type path-följande algoritm för att hitta en jämviktslösning av Eaves [1976]. En anmärkningsvärd konsekvens av denna algoritm är att när verktygen ges av rationella tal, finns det också en jämvikt mellan rationella tal. Historien om konvexa programmering formuleringar för den linjära Arrow-Debreu modellen är något invecklad. Jain [2007] formulerade ett konvext program vars lösningar motsvarar marknadsjämvikt; detta kan användas för att erhålla en polynom-tidsalgoritm via Ellipsoidalgoritm. Det visade sig senare att samma konvexa program redan var formulerat av Nenakov och Primak [1983]. Det är intressant att lägga märke till att det datavetenskapliga samfundet hittills tycks ha varit ovetande om att Cornet [1989] lade fram ett liknande, men ännu bättre, konvext program. Detta nämns inte ens i undersökningsdokumentet av Codonotti et al. [2004] utforska bakgrunden till problemet. (Dessa konvexa program kommer att omfattas av avsnitt 3.) En otillfredsställande aspekt av programmet i Jain [2007] och Nenakov och Primak [1983] är att det misslyckas med att visa existensen av en jämvikt; det visar bara att om det finns en jämvikt, då någon genomförbar lösning på konvexa programmet är en. Däremot ger Cornets program ett bevis på existens om man antar att ett starkare tillfredsställande tillstånd i Gale [1957] föreligger. Den visar dock inte på det svagare nödvändiga och tillräckliga tillståndet i Gale [1976]. En effektiv inre punktalgoritm för beräkning av jämvikt gavs av Ye [2008] baserat på konvexa programmet i Jain [2007] och Nenakov och Primak [1983]. Ett viktigt resultat nyligen är en kombinatorisk primal-dual algoritm av Duan och Mehlhorn [2015]; detta bygger inte på konvex programmering formulering, utan anpassar snarare tekniker från algoritmen av Devanur et al. [2008] för linjära fiskerimarknader. Konvexa program av Nenakov och Primak [1983], Jain [2007] och Cornet [1989] för den linjära Arrow-Debreu modellen är av en helt annan karaktär än Eisenberg och Gale [1959], Shmyrev [2009] och Birnbaum et al. [2011 för den linjära Fisher-modellen. De sistnämnda har endast linjära begränsningar, med separata konvexa mål, i motsats till de icke-linjära begränsningarna i Nenakov och Primak [1983] och Jain [2007]. Medan Cornet [1989] endast är formulerat med mycket enkla linjära begränsningar, döljer målet max-min faktiskt liknande icke-linjära begränsningar. Den möjliga regionen för båda formuleringarna för den linjära Fisher modellen är klassisk polyhedra, Eisenberg och Gale [1959] en generaliserad flöde polyhedron, och Shmyrev [2009] och Birnbaum et al. [2011] en cirkulationspolyhedron. Detta förklarar också varför det för den linjära Fisher-modellen finns klassiska flödestekniker (se Végh [2013, 2012]) och starkt polynomiska tidsalgoritmer. Dessutom, intressant nog, konvexa program av Eisenberg och Gale [1959], Shmyrev [2009], och Birnbaum et al. Kommissionens genomförandeförordning (EU) nr 668/2014 av den 13 juni 2014 om tillämpningsföreskrifter för Europaparlamentets och rådets förordning (EU) nr 1151/2012 om kvalitetsordningar för jordbruksprodukter och livsmedel (EUT L 179, 19.6.2014, s. 1).
Devanur m.fl. REF formulerade ett rationellt konvext program för den linjära Arrow-Debreu-modellen för att karakterisera en marknadsjämvikt.
A Rational Convex Program for Linear Arrow-Debreu Markets
{'venue': 'TEAC', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Economics', 'Computer Science']}