Abstrakt. I den här artikeln studerar vi problemet med marknadsclearing online där det finns en vara på marknaden som köps och säljs av flera köpare och säljare vars bud kommer fram och går ut vid olika tidpunkter. Auktionsförrättaren står inför ett online clearing problem att besluta vilka köpa och sälja bud för att matcha utan att veta vilka bud kommer att komma i framtiden. För att maximera vinsten presenterar vi en (randomized) online-algoritm med ett konkurrensförhållande på ln( p max − p min )+1, när buden är i ett intervall [ p min, p max ], som vi visar är det bästa möjliga. En enklare algoritm har ett förhållande två gånger detta, och kan användas även om utgångsdatum inte är kända. För att maximera antalet affärer, presenterar vi en enkel girig algoritm som uppnår en faktor av 2 konkurrensförhållande om inga pengar förlorar affärer är tillåtna. Vi visar också att om online-algoritmen tillåts subventionera matcher-matcha pengar förlora par om det redan har samlat tillräckligt med pengar från tidigare par för att betala för dem-då kan det faktiskt vara 1-konkurrenskraftig med avseende på den optimala offline algoritm som inte är tillåten subvention. Det vill säga, för att maximera antalet affärer, förmågan att subventionera är minst lika värdefull som att känna till framtiden. Vi anser också att målen är att maximera köp- eller säljvolym och social välfärd. Vi presenterar alla dessa resultat som corollaries av teorem på online matchning i en ofullständig intervall diagram. Vi överväger också frågan om incitamentkompatibilitet, och utveckla en nästan optimal incitamentkompatibel algoritm för att maximera social välfärd. För att maximera vinsten visar vi att ingen incitamentskompatibel algoritm kan uppnå ett sublinjärt konkurrensförhållande, även om endast ett köpbud och ett säljbud lever åt gången. Vi tillhandahåller dock en algoritm som, under vissa milda antaganden på buden, utför nästan lika bra som det bästa fasta paret av köp- och säljpriser, en svagare tillstånd att göra digitala eller hårda kopior av delar eller hela detta arbete för personligt eller klassrum användning beviljas utan avgift, förutsatt att kopior inte görs eller distribueras för vinst eller direkt kommersiell fördel och att kopior visar detta meddelande på första sidan eller första skärmen av en display tillsammans med den fullständiga citering. Upphovsrätt till delar av detta verk som ägs av andra än ACM måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar, för att omfördela till listor, eller för att använda någon komponent i detta verk i andra verk krävs förhandsgodkännande och/eller avgift. Behörighet kan begäras från publikationsavdelningen., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701, USA, fax +1 (212) 869-0481, eller behörigheter@acm.org. men ändå naturliga prestandamått. Detta senare resultat använder inlärningsmetoder online, och vi visar också hur sådana metoder kan användas för att förbättra våra "optimala" algoritmer till en bredare uppfattning om optimalitet. Slutligen visar vi hur några av våra resultat kan generaliseras till miljöer där köparna och säljarna själva har online-budstrategier, snarare än bara var och en har enskilda bud.
I REF, författarna studerade online-marknaden clearing inställning för en allmän råvarumarknad utan tjänstebegränsningar och gav algoritmer med robusta lägre gränser.
Online algorithms for market clearing
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}