Eftersom distribuerade datorsystem spelar en allt viktigare roll i samhället kommer det att bli nödvändigt att överväga hur dessa maskiner kan fås att interagera effektivt. Särskilt när de interagerande maskinerna har designats självständigt är det viktigt att interaktionsmiljön främjar sina designers mål. Dessa designers kan till exempel önska att deras maskiner beter sig effektivt, och med ett minimum av overhead som krävs av själva samordningsmekanismen. Reglerna för samverkan bör tillgodose dessa behov, och andra. Formella verktyg och analyser kan bidra till en lämplig utformning av dessa regler. Vi överväger här hur koncept från spelteori kan ge standarder som ska användas vid utformningen av lämpliga förhandlings- och interaktionsmiljöer. Denna design är mycket känslig för den domän där interaktionen äger rum. Olika interaktionsmekanismer är lämpliga för olika områden, om attribut som effektivitet och stabilitet ska upprätthållas. Vi presenterar en allmän teori som fångar förhållandet mellan vissa områden och förhandlingsmekanismer. Analysen gör det möjligt att exakt kategorisera de typer av områden där agenter befinner sig, och att använda kategorin för att välja lämpliga förhandlingsmekanismer. Den teori som presenteras här både generaliserar tidigare resultat, och tillåter agentdesigners att karakterisera nya domäner korrekt. Analysen tjänar därmed som ett kritiskt steg i att använda förhandlingsteorin i verkliga tillämpningar. Vi visar att det inom vissa uppgiftsorienterade områden finns distribuerade samförståndsmekanismer med enkla och stabila strategier som leder till effektiva resultat, även när agenter har ofullständig information om sin miljö. Vi presenterar också ytterligare nya resultat, i synnerhet att *Detta är en reviderad och utvidgad version av tidningarna "En domänteori för uppgiftsorienterad förhandling" och "Konsentagenter: förhandlingsmekanismer för multiagentsystem" som publicerades i Proceedings Chambery, Frankrike, respektive. * Motsvarande författare. E-post: jeff@cs.huji.ac.il. ' E-post: gilad@mit.edu. 0004-3702/96/$15.00 Copyright @ 1996 Elsevier Science B.V. Alla rättigheter reserverade. ssD10004-3702(95)00104-2 111 konkava domäner som använder all- eller nothin g-affärer. Ingen lögn av en agent kan vara till nytta, och det i subadditiva domäner. Det finns ofta nyttiga lockbete lögner som inte kräver information om den andra agentens mål. Datorer fattar allt fler beslut på ett relativt självständigt sätt. Telekommunikationsnäten styrs av datorer som beslutar om telefon- och datapaketen 01. Elektriska nät har beslut som fattas av datorn om hur deras laster kommer att bc balanseras vid tider av toppefterfrågan. På liknande sätt görs forskning om hur datorer kan reagera på dem. och kontroll, bil- och flygplanstrafik i realtid. Några av de beslut som dessa computcra skapar båge görs i samförstånd med andra maskiner. Ofta. Detta samråd mellan maskinerna är av avgörande betydelse för den aktuella uppgiften. FOI-exempel. Med personliga digitala assistenter (PDA) kommer personens handdator att bc förväntas samordna scheman med andras PDA (c.g., min programvaruagent avgör om min bil har fixats i tid i garaget; om inte, den kontaktar taxibolaget, schemalägger om min beställning lor;I cub. och uppdaterar min dags schema). Ingen schemaläggning kommer att äga rum utan kommunikation mellan maskiner. Sällan kommer det att äga rum utan lösning av inter-maskin konflikt (eftersom de människor som dessa maskiner representerar har motstridiga mål). På samma sätt. Konceptet 01' intelligenta databaser bygger på sofistikerade interaktioner mellan autonoma programvaruagenter. En användares begäran om information kan kräva insamling och synthesizin, 0 information från flera distribuerade databaser. Maskiner behöver li)rmulera den nccssary insamlingen av förfrågningar, ordna tillgång till data (som kan vara delvis begränsad), och samarbeta för att få informationen där den behövs. Även när en dator uppgifter inte lzcl~ att involvera andra maskiner, kan det vara fördelaktigt att involvera dem. Ibland. Till exempel. Vi hittar automatiserade system som kontrollerar resurser (som det telenät som nämns ovan). Det är ofta till fördel för separata resurskontrollerande system att dela med sig av sina resurser (t.ex. fiberoptiska linjer, lagring på kort och lång sikt. switchin, ~7 noder) med varandra. All denna inter-maskin samordning kommer att äga rum inom något slag 01' irlternctiorr miljörannwrzt. Det kommer oundvikligen att finnas "protokoll" för hur maskiner hanterar varandra. Vad som oroar oss här är inte detaljerna om hur man stoppar information i ett paket på nätverket; det är inte ens frågan på högre nivå om hur agenter kommer att kommunicera med varandra (på ett gemensamt språk, eller kanske med hjälp av översättningsfilter) Snarare, när WC antar att agenter cm kommunicerar och förstår varandra, hur kommer de att komma fram till avtal? Dessa "interaktionsregler" kommer att utgöra grunden för förhandlingar mellan maskiner, överenskommelser, samordning och samarbete. Om inter-maskin protokollen är primitiva och oförmögna att fånga subtilis 01 "kooperativa möjligheter, maskinerna kommer att agera ineffektivt. De kommer att fatta fel beslut. De människor som är beroende av dessa beslut kommer att lida. Intelligence 86 (1996) 195-244 Denna artikel är organiserad i tre delar: (1) (2) (3) I den första delen (avsnitt 1.2-9) diskuterar vi det allmänna synsättet i vår ram för automatiserade förhandlingar, tillsammans med dess motivation och relaterad forskning. Vi ger också en mycket kort och informell översikt över våra resultat. I den andra delen (avsnitt lo-14) presenterar vi de formella detaljerna i vår tillämpning av ramverket på uppgiftsorienterade områden. Denna andra del innehåller också en mer formell diskussion om några av de viktigaste frågor som tas upp i den första delen av artikeln. I bilaga A presenterar vi bevisen för alla teorem som finns i den andra delen av artikeln.  Inom området distribuerad artificiell intelligens (DAI) utforskar forskare metoder som möjliggör koherent (t.ex. samordnad och effektiv) interaktion mellan datorer i distribuerade system. En av de viktigaste skillnaderna i DA1 är mellan forskning i distribuerad problemlösning (DPS) [4, 8, 13,63], där det distribuerade systemet har utformats centralt, och multiagentsystem (MA) [18,38,40,68], där det distribuerade systemet består av självständigt utformade medel. I DPS, det finns någon global uppgift som systemet utför, och det finns (åtminstone implicit) en global uppfattning om nytta som kan begränsa eller direkt agent aktivitet. I DPS antas det finnas en enda kropp som vid designtid kan direkt påverka alla agenters preferenser i systemet. I multiagentsystem antas det inte finnas någon enda kropp som vid konstruktionstidpunkten direkt kan påverka alla agenters preferenser i systemet. Agenternas preferenser kommer från olika designers. I MA-system är varje agent endast intresserad av sina egna mål (även om olika agenters mål kan överlappa), och det finns ingen global uppfattning om nytta. MA-systemagenten, som sysslar med sin egen välfärd (dvs. sin designers välfärd [ 12]), agerar följaktligen för att öka denna välfärd. Skillnaden mellan distribuerade problemlösningssystem och multiagentsystem bör i första hand ses som en distinktion mellan forskningsagendor. 2 Visst kommer det inte alltid att vara uppenbart för en utomstående observatör om ett givet distribuerat system faller i en eller annan kategori. En enda designer kan ha byggt sina agenter för att agera konkurrenskraftigt och tro att det förbättrar den totala systemeffektiviteten. På liknande sätt kan man se personer som är individuellt motiverade dela med sig av information och hjälpa varandra, eftersom de har bestämt sig för att det ligger i deras eget intresse att handla på det sättet. De forskningsfrågor som en forskare i DPS ställer skiljer sig dock ibland från de som ställs av en MAS-forskare (trots en hel del överlappning). I synnerhet, om en DPS-forskare kan visa att det är bra för systemet som helhet att agera på ett visst sätt, så är det faktiskt så att användningen av dessa termer själv genomgår en förändring. "Multiagentsystem" används nu ibland för att hänvisa till hela området distribuerad artificiell intelligens. För mer av en diskussion om DPS/MAS Intelligence 86 (1996) 195-244 199 En annan viktig fråga är den relation som agenter har till varandra, t.ex. i vilken utsträckning de är villiga att kompromissa med sina mål för varandra (förutsatt att en sådan kompromiss är nödvändig). Välvilliga agenter [ 581 är sådana som genom formgivning är villiga att ta emot varandra; de har byggts för att vara samarbetsvilliga, dela med sig av information och samordna i jakten på någon (åtminstone implicit) uppfattning om global nytta. I motsats till detta kommer agenter för multiagentsystem att samarbeta endast när det ligger i deras intresse att göra detta. Ytterligare ett annat potentiellt förhållande mellan agenter är ett modifierat förhållande mellan mästare och slav, som kallas ett "övervakare-övervakat" förhållande, där icke-absolut kontroll utövas av en agent över en annan [19, 201. Synkroniserings-, synkroniserings- eller justeringsprocessen för flera agentplaner utgör således en del av den (varierade) foci av DA1-planeringsforskningen. Synkronisering genom konfliktundvikande [ 28,29,66], fördelning av en enkelagent planerare bland flera agenter [ 91, användningen av en centraliserad multiagent planerare [ 551, och användningen av samförståndsmekanismer för att aggregera delplaner som produceras av flera agenter [ 231, har alla undersökts. Andra arbeten som nyligen utförts omfattar [17,24,34,36,40, 11. Det finns en stor och växande kropp av arbete inom artificiell intelligens som försöker fånga föreställningar om rationellt beteende genom logisk axiomatisering [6, 7,30,3 1,37,46,47,54]. Metoden fokuserar vanligen på en formaliserad modell av agentens övertygelser, önskningar och avsikter (den så kallade "BDI-modellen"). Syftet med den formella modellen är att exakt karakterisera vad som utgör rationellt beteende, i syfte att påtvinga ett sådant rationellt beteende på en automatiserad agent. De formella axiomen kan användas i körtid för att direkt begränsa en agents beslutsprocess, eller (mer sannolikt) de kan användas vid kompilering-tid för att producera en mer effektiv körbar modul. Fokus för denna forskning, kommer som det gör från en enda-agent artificiell intelligens perspektiv, är på arkitekturen av en enda automatiserad agent. Till exempel Cohen och Levesque [5, 6] har utforskat förhållandet mellan val, engagemang, och intention-en agent bör förbinda sig till vissa handlingsplaner, och förbli lojala mot dessa planer så länge det är lämpligt (till exempel, när agenten upptäcker en plan är ogenomförbar, bör planen överges). Även när man tittar på multiagentsystem har dessa forskare undersökt hur en medlem i en grupp bör utformas igen, och tittat på hur man utformar en enskild agent så att det är en produktiv gruppmedlem. I [ 361 axioms föreslås till exempel att en agent, när han upptäcker att han kommer att misslyckas med att fullgöra sin roll i en gemensam plan, att meddela de andra medlemmarna i sin grupp. Axiomatiseringar kan dock behöva ta itu med hur grupper av agenter kan ha ett gemensamt åtagande att uppnå ett visst mål [7], eller hur varje agent kan göra interpersonella åtaganden utan att använda sådana begrepp [ 3 11. En annan användning för BDI abstraktioner är att låta en agent att resonera om andra agenter, och relativisera ens intentioner i termer av övertygelser om andra agenters avsikter eller övertygelser. Olika forskare i distribuerad artificiell intelligens har föreslagit att det skulle vara värt att isolera "aspekter av kooperativt beteende", allmänna regler som skulle få agenter att agera på sätt som främjar samarbete. Hypotesen är att när agenter agerar på vissa sätt (t.ex. dela information. agera på förutsägbara sätt, skjuta upp gfobally begränsa val). Det kommer att bli lättare för dem att genomföra effektiva gemensamma åtgärder [3,45,6:5]. Moses, Shoham och Tenn ~nh~ltz [48.49.6 I.62]. har till exempel föreslagit att man tillämpar sociepmetaforen på artificiella system för att förbättra prestandan hos de agenter som verkar i detta samhälle. De frågor som ska behandlas är synkronisering, samordning av agenternas verksamhet, samarbetsmetoder för att utföra uppgifter och hur säkerhets- och rättvisebegränsningar i systemet kan garanteras. De föreslår samordning av agentverksamhet för att undvika konflikter; systemet kommer att struktureras så att agenterna inte kommer fram till potentiella konfliktsituationer. Således ses dessa sociala lagar som en metod för att undvika behovet av kostsamma samordningstekniker, som planering eller förhandlingar. Med agenter som följer lämpliga sociala lagar kommer behovet av löpande samordning att minska. Detta är viktigt, eftersom även agent designers kan bc willin, (7 att investera en stor insats vid designtid i att bygga effektiva distribuerade system, är det viktigt att drifttiden overhead vara så låg som möjligt. Det finns en likhet mellan detta USC av förkompilerade, högt strukturerade sociala lagar, och vår utveckling av fördefinierade interaktion protokoll. De sociala lagarna förutsätter emellertid att den som utformar lagarna har full kontroll över agenterna; agenter antas följa de sociala lagarna helt enkelt därför att de är utformade för att, och inte därför att de individuellt drar nytta av de sociala lagarna. Att lyda de sociala lagarna får inte vara "stabilt", förutsatt att alla andra lyder lagarna kan en agent göra bättre ifrån sig genom att bryta mot dem. Vår strategi handlar om sociala konventioner som är stabila, som kommer att vara lämpliga för individuellt motiverade agenter. Det har gjorts flera försök att betrakta marknadsmekanismer som ett effektivt sätt att fördela resurser i ett distribuerat system. Bland AI arbete är den av Smith kontrakt netto [ 63.641, Malone företagssystem 144J, och Wellmans WAL-RAS system f 72.73 1. Kontraktsnätet är ett kommunikationsprotokoll på hög nivå för ett distribuerat problemlösningssystem. Det gör det möjligt att fördela uppgifterna bland de noder som fungerar i systemet. Ett kontrakt mellan två noder upprättas så att uppgifter kan utföras; varje nod i nätet kan fungera som en mmager och / eller som en contracmr. En uppgift som har tilldelats en nod kan ytterligare brytas ned av entreprenören. Ett avtal upprättas genom ett anbudsförfarande som omfattar förvaltarens tillkännagivande av uppdraget och anbud som skickas in av de potentiella entreprenörerna. Enterprise 144 J är ett system som byggdes med hjälp av en variant av avtalets nätprotokoll. Den distribuerade schemaläggning pmtocnl lokaliserar den bästa tillgängliga maskinen för att utföra en uppgift. Detta protokoll liknar avtalsnätet. Men använder sig av ett mer välavvägt tilldelningskriterium. Intelligens 86 (1996) 195-244 201 Ett annat system som tar ett ekonomiskt grepp för att lösa ett distribuerat problem genom att använda en prismekanism har utforskats av Wellman i [ 72 1. Wellman använder konsument/producentmetaforen för att inrätta en prisbaserad mekanism för omfördelning av uppgifter som säkerställer stabilitet och effektivitet. Alla agenter fungerar som både konsumenter och producenter. Varje distinkt vara har en auktion i samband med den, och agenter kan få varan genom att lämna bud i auktionen för den varan. Det system som utvecklats av Wellman, WALRAS, beräknar jämviktspriset för varje marknad. Förhandlingar har varit en fråga av centralt intresse för DAI. Ordet har använts på många olika sätt, även om det i allmänhet hänvisar till kommunikationsprocesser som ytterligare samordning [ 8, 40.41.63]. Dessa förhandlingsförfaranden har innefattat utbyte av partiella globala planer [131, överföring av information som syftar till att ändra andra aktörers mål [67,681] och användning av stegvisa förslag som leder till gemensamma handlingsplaner [381. Interagentsamarbete i distribuerade problemlösningssystem har utforskats i den pågående forskningen av Lesser, Durfee och kollegor. Mycket av detta arbete har fokuserat på implementering och analys av datafusionsexperiment, där system av distribuerade sensorer absorberar och tolkar data och slutligen kommer fram till en gruppslutsats [1114,42]. Agenter utbyter partiella lösningar på olika detaljnivåer för att konstruera globala lösningar; en stor del av arbetet har undersökt effektiva strategier för kommunikation av data och hypoteser bland agenter, och i synnerhet de typer av relationer mellan noder som kan hjälpa effektiv gruppanalys. Till exempel kan olika organisationer, och olika metoder för att fokusera nodaktivitet, hjälpa systemet som helhet att bli mycket effektivare. Sycara har undersökt en förhandlingsmodell som kombinerar case-baserat resonemang och optimering av multi-attribute verktyg. I synnerhet, medan vi i vår forskning utgår från att agenternas mål är fastställda under förhandlingarna, är Sycara särskilt intresserad av hur agenter kan påverka varandra för att ändra sina mål genom en förhandlingsprocess (informationsöverföring, etc.). Kraus och hennes kollegor har utforskat förhandlingar där själva förhandlingstiden är en fråga [38,391. Agenter kan förlora värde på en förhandling som drar ut på tiden, och olika agenter är asymmetriska när det gäller kostnaden för förhandlingstiden. Agenternas inställning till förhandlingstid påverkar direkt vilken typ av avtal de kommer att nå. Det är emellertid intressant att lägga märke till att dessa avtal kan nås utan dröjsmål. Det finns en oundviklig ineffektivitet när det gäller att fördröja avtalet. Gasser [27] har utforskat de sociala aspekterna av agentkunskap och åtgärder i multiagentsystem ("programgemenskaper"). Sociala mekanismer kan utvecklas dynamiskt; programgemenskaper kan generera, modifiera och kodifiera sina egna lokala språk för interaktion. Gassers tillvägagångssätt kan vara mest effektivt när agenter interagerar inom ostrukturerade domäner, eller inom områden där deras struktur ständigt förändras. Den forskning vi presenterar utnyttjar å andra sidan ett på förhand utformat socialt skikt för multiagentsystem. Underrättelse 86 (1996) 195-244 203 åtgärder. Till exempel, semi-kooperativa affärer visade sig kunna lösa verkliga konflikter mellan agenter, medan blandade affärer inte. På samma sätt, multi-plan erbjudanden kan fånga mål avkoppling som en del av ett avtal. Det visades också att vissa andra egenskaper gällde för vissa typer av avtal men inte för andra. I synnerhet var olika agentstrategier lämpliga ("rationella") för olika typer av affärer och domäner. Agenter visade sig inte ha något incitament att ljuga när vissa typer av affärer användes inom vissa områden, men hade ett incitament att ligga med andra deal typ / domänkombinationer. Granskningen av detta förhållande mellan förhandlingsmekanismen och domänen använde sig av två prototypiska exempel: postmendomänen (införd i [75]) och de slitsade blocken i världen (presenterad i [771). Det stod klart att dessa två domäner exemplifierade allmänna klasser av multiagentiska interaktioner (t.ex. postmen domänen var till sin natur samarbetsvillig, slitsade block världen inte). Det var dock inte klart vilka egenskaper som gjorde vissa förhandlingsmekanismer lämpliga för dem. Det stod inte heller klart hur andra domäner skulle kunna jämföras med dessa prototyper. När presenteras med en ny domän (såsom agenter som frågar en gemensam databas), vilka tidigare resultat var tillämpliga, och vilka var inte? Forskningen saknade en allmän teori som förklarade förhållandet mellan domäner och förhandlingsmekanismer. I den här artikeln presenterar vi början på en sådan allmän teori. Analysen gör det möjligt att både förstå tidigare resultat på postmenområdet mer allmänt och att exakt karakterisera nya områden (dvs. vilka förhandlingsmekanismer som är lämpliga). Analysen tjänar därmed som ett kritiskt steg i att använda förhandlingsteorin i verkliga tillämpningar. Syftet med den forskning som beskrivs i den här artikeln är att undersöka hur vi kan bygga maskiner som kan göra konstruktiva avtal. Vi vill att våra maskiner ska interagera flexibelt. Vi vill att de ska företräda våra intressen och kompromissa när det är till vår fördel. Vi kanske ibland vill att de skall vara hemlighetsfulla och inte avslöja all sin information, och vi vill troligen att de skall känna igen dubbeltydighet från andras sida, när det är möjligt. Kort sagt, vi vill att våra agenter troget ska agera som våra surrogater i möten med andra agenter. När människor interagerar, gör de inte det i ett vakuum. Det finns sociala konventioner och lagar som begränsar deras beteende; syftet med sociala konventioner och lagar är att göra exakt det. En skatt som tas ut på ett företag som förorenar luften är avsedd att avskräcka från ett visst beteende. Positiv publicitet på ett filantropiskt företag ger den nytta för sitt beteende. Man kan tänka sig ett komplicerat system av lagar och konventioner som ett slags social ingenjörskonst, som är avsedd att frambringa ett visst beteende bland människor. Vi är intresserade av social ingenjörskonst för maskiner. Vi vill förstå vilka typer av förhandlingsprotokoll, och straff- och incitamentsmekanismer, som skulle motivera enskilda designers att bygga maskiner som agerar på ett sätt som alla dessa designers finner fördelaktigt. Som nämnts ovan har utvecklingen av "sociala lagar" paralleller med arbetet [621. Där finns dock de sociala lagarna för centralt utformade system av agenter (DPS). och kommer inte nödvändigtvis att vara meningsfullt för självständigt utformade agenter. Till exempel, en regel kan uppmuntra ett effektivt beteende om alla följde den, men om någon enskild agent kan gynna mot-c genom att inte följa regeln. systemet som helhet inte kommer att vara stabilt. Eftersom var och en av våra agenter kommer att göra vad som är nödvändigt för att maximera sin nytta, stabilitet är en kritisk fråga-vi behöver regler som agenter kommer att självständigt hitta i deras bästa intresse att följa. Vi kommer att återkomma till denna fråga om stabilitet nedan. Det scenario vi tänker på är följande. Föreställ dig att företrädare för olika företag (agentdesigners) samlas för att komma överens om interaktionsprotokoll för sina automatiserade agenter. Med tanke på ett visst område (t.ex. balansering av telekommunikationstrafiken mellan stora nät eller mötesschema) presenteras de med olika interaktionsmekanismer och visar att varje mekanism har vissa påvisbara egenskaper. Till exempel, en mekanism kan komma fram till garanterat globalt optimala lösningar, men till priset av en agent möjligen mycket dåligt. En annan mekanism kan se till att klyftan mellan agenters fördelar minimeras, men till priset av att alla gör lite värre. Dessutom visas det för dessa företagsrepresentanter att protokoll A är immunt mot bedrägeri: det kommer inte att ligga i någons intresse att utforma en fuskagent som avviker från protokollet på något sätt (t.ex. genom reportin g högre, eller lägre, nätverkstrafik än vad som faktiskt är närvarande) Företrädarna anser de olika alternativen, och beslutar sinsemellan vilket protokoll att bygga in i sina agenter. Mötet ajournerar, agenter arc byggt. och där man bland dem har kommit fram till nyttiga överenskommelser. Det visar sig att attributen för en viss mekanism är mycket känsliga för den domän där agenterna är verksamma. De regler för interaktion som kan vara lämpliga på ett område kan vara ganska olämpliga på ett annat. När dessa representanter för företaget sätter sig ner på mötet, måste de få veta "På detta område, protokoll A har egenskaper I, 2. och 3, och är immun mot bedrägeri. Protokoll B har egenskaper 2, 4, och 5, och är inte immun mot bedrägeri." Vår forskning utforskar möjligheternas utrymme och analyserar förhandlingsmekanismer inom olika områden. När konstruktörerna av automatiserade agenter möts, är detta den typ av information de kommer att behöva. Alternativet till att ha denna analys är att vandra i mörkret, och att bygga förhandlingsmoduler utan att förstå deras egenskaper. Kommer de att leda till bra avtal? Kan våra maskiner göra bättre ifrån sig? Kommer någon att bygga en falsk agent som utnyttjar min? Ska jag själv designa min agent för att vara hemlighetsfull eller bedräglig? Kommer detta att främja mina egna mål? Vår forskning är avsedd att besvara denna typ av frågor. Byggarna av komplexa distribuerade system, som sammankopplade nätverk, delade databaser, övervakning av monteringslinjer och tillverkning, och distribuerad bearbetning, kan bredda de verktyg som de för med sig i frågor om interagentsamordning. Intelligens 86 (1996) 195-244 20.5 Befintliga tekniker är i allmänhet beroende av enskilda agenters goda vilja och tar inte hänsyn till komplexa interaktioner mellan konkurrerande mål. Nya verktyg kan användas för att utforma heterogena, distribuerade system på hög nivå genom att upprätta lämpliga förhandlingsprotokoll. Hur kan maskiner bestämma hur man delar resurser, eller vilken maskin kommer att ge vika medan den andra fortsätter? Förhandlingar och kompromisser är nödvändiga, men hur bygger vi våra maskiner för att göra dessa saker? Hur kan formgivarna av dessa separata maskiner besluta om metoder för överenskommelse som möjliggör ömsesidigt fördelaktigt beteende? Vilka tekniker är lämpliga? Kan vi göra bestämda uttalanden om teknikernas egenskaper? Det sätt vi har börjat ta itu med dessa frågor är att syntetisera idéer från artificiell intelligens (t.ex. begreppet resonemang, rationell dator) med verktygen för spelteori (t.ex. studiet av rationellt beteende i ett möte mellan egenintresserade agenter). Om vi antar att automatiserade agenter, byggda av separata, egenintresserade designers, kommer att interagera, är vi intresserade av att utforma protokoll för specifika domäner som kommer att få dessa agenter att interagera på användbara sätt. Ordet "protokoll" betyder olika saker för olika människor. Som används för att beskriva nätverk, ett protokoll är strukturen av meddelanden som tillåter datorer att vidarebefordra information till varandra. När vi använder ordet protokoll, menar vi reglerna med vilka agenter kommer att komma överens. Den anger vilka typer av avtal de kan göra, liksom sekvensen av erbjudanden och moterbjudanden som är tillåtna. Detta är protokoll på hög nivå, som inte handlar om kommunikationsmekanismerna utan om dess innehåll. Protokollen är nära förbundna med domäner, med vilka vi menar den miljö i vilken våra agenter verkar. Automatiserade agenter som kontrollerar telenät är verksamma inom en annan domän (i formell mening) än robotar som flyttar lådor. Mycket av vår forskning är fokuserad på relationen mellan olika typer av domäner, och de protokoll som lämpar sig för var och en. Med tanke på ett protokoll måste vi överväga vilken agentstrategi som är lämplig. En strategi är hur en agent beter sig i en interaktion. Protokollet anger reglerna för interaktionen, men de exakta överenskommelser som en agent föreslår är ett resultat av den strategi som hans designer har satt in i honom. Som en analogi, ett protokoll är som reglerna för rörelse av pjäser i schackspelet. En strategi är det sätt på vilket en schackspelare beslutar om sitt nästa drag. Spelteori är rätt verktyg på rätt plats för utformningen av automatiserade interaktioner. Spelteoriverktyg har främst använts för att analysera mänskligt beteende, men på vissa sätt är de olämpliga: människor är inte alltid rationella varelser, inte heller har de nödvändigtvis konsekventa preferenser framför alternativ. Automatiserade samhällen däremot är särskilt lämpade för formell analys och utformning. Automatiserade medel kan uppvisa förutsägbarhet, konsekvens, snävhet i syfte (t.ex., inga känslor, ingen humor, inga rädslor, tydligt definierade och konsekvent risk attityd), och en explicit mätning av nytta (där detta kan ha en operativ betydelse inne i programmet kontrollera agenten ) Även begreppet "strategi" (en specifikation av vad man ska göra i varje alternativ under en interaktion), en klassisk spelteori term, tar på en tydlig och entydig mening när det blir helt enkelt ett program som placeras i en dator. Föreställningen att en människa skulle välja en fast strategi före en interaktion, och följa den utan förändring, leder till ointuitiva resultat för en person. Dessutom. Verkar det vara mer en formell konstruktion än en realistisk krav-beror människor eve? alternativ i förväg och bestämma vad du ska göra? Å andra sidan är uppfattningen att en dator programmeras med en fast strategi innan en interaktion, och följer den utan förändring, en enkel beskrivning av den nuvarande verkligheten. Naturligtvis är varken människor eller datorprogram idealiska spelteoriagenter. Viktigast av allt, de är inte kapabla till obegränsad tankekraft, som spelteori ofta antar. Ändå verkar det som om på vissa sätt automatiserade agenter är närmare spelet teorin idealisering av en agent än människor är. Det arbete som beskrivs här, utformningen av interaktionsmiljöer för maskiner. är närmast relaterat till området mekanismdesign i spelteorin [ 25]. Jämförelse med spelrheog Metoden som används i denna artikel är starkt baserad på tidigare arbete i spelteori, främst på vad som kallas "Nashs förhandlingsproblem" [43] eller "Nashs förhandlingsmodell" [601. Klassisk spelteori [ 32, 43, 50, 60.74] talar om agenter som når "deals", som definieras som vektorer för verktyg (en för varje agent). Ett förhandlingsspel kan hamna i något möjligt resultat (d.v.s. en "affär"). Varje spelare har en full preferensordning över uppsättningen möjliga resultat; denna preferensordning uttrycks av dess allmännyttiga funktion. För varje affär, det finns en verktygsvektorn som är listan över verktygen för denna affär för varje deltagare. Det finns en särskild verktyg vektor som kallas "konflikt" (eller ibland "status quo punkt") som är verktyget varje spelare tilldelar en konflikt (brist på slutlig överenskommelse). Spelteorin förutsätter att uppsättningen möjliga erbjudanden är en simplex, dvs. om ~1 och u2 är två allmännyttiga vektorer för två möjliga erbjudanden, då varje vektor på linjen ansluter NI till ~2 är en användbar vektor av någon möjlig affär (vilket innebär att domänen för erbjudanden är kontinuerlig). Klassisk spelteori behandlar följande fråga: med tanke på en uppsättning allmännyttiga vektorer (en simplex), vad kommer att vara nyttan vektor som spelarna kommer överens om (under särskilda antaganden)? Med andra ord fokuserar den klassiska förhandlingsteorin på förutsägelser av resultat, under vissa antaganden om spelarna och själva resultaten. Nash [50] visade att under vissa rationella beteende och symmetri antaganden, kommer spelarna att nå en överenskommelse om en affär som kommer att vara individuell rationell, pareto optimal, och kommer att maximera produkten av spelarnas nytta (se avsnitt 13 för en mer fullständig diskussion). Zeuthen [ 741 ansåg att två spelares förhandlingsproblem var ett beslutsförfarande för en spelare (beslut om att medge eller inte), enligt antagandet att om ingen av spelarna medger i ett visst steg kommer de att nå en konflikt. Zeuthen utvärderade hur stor risk varje spelare skulle vara villig att ta när han beslutar att inte medge (och därmed riskerar konflikt). Spelaren som är minst. Den som är villig att riskera kommer att göra nästa eftergift. Harsanyi [ 323 visade att de två tillvägagångssätten är likvärdiga i den meningen att två spelare som använder Zeuthens kriterier kommer att nå Nash-lösningen. Ovanstående tillvägagångssätt ger oss verktyg för vår egen design och utvärdering av förhandlingsmekanismer, vilket är vår främsta angelägenhet. Spelteoretiker är vanligtvis intresserade av hur spel kommer att spelas, ur både beskrivande och normativ synvinkel. Spellösningar består av strategier i jämvikt; om på något sätt ett socialt beteende når en likvibrium, har ingen agent något incitament att avvika från denna jämvikt beteende. Denna jämvikt anses vara en lösning på spelet. Det kan finnas en eller flera (eller inga) strategier i jämvikt, och det finns också olika uppfattningar om jämvikt (t.ex. Nash [ 501, perfekt jämvikt, dominerande strategijämvikt). Det finns också grupper av spelteoretiker som överväger problemet med hur man designar spel som har vissa attribut. Det är detta område av mekanismen design som är närmast vår egen oro för automatiserade agenter. ~~hanism design är också känt i spelet teori litteratur som impleme~ta-tion problem. Den impfeme~tation frågan [2,25j frågar om det finns en mekanism, eller spelform, med en särskiljande jämvikt punkt (dominant strategi, eller stark, eller bara Nash) sådan att varje social profil (dvs. grupp beteende) är associerad, när spelarna följer sin balans strategier, med önskat resultat. Med andra ord antas det finnas en grupp agenter, var och en med sin egen bruksfunktion och preferenser framför möjliga sociala resultat. Det finns också en social välfärdsfunktion som värderar alla möjliga sociala resultat (t.ex. kan en socialt effektiv överenskommelse värderas högre än en icke-effektiv). Frågan är då, kan man utforma ett spel så att det har en unik lösning (~uilib~um strategier), och sådan att när varje enskild agent beter sig enligt denna ~uilibrium strategi, det sociala beteendet kommer att maximera den sociala välfärdsfunktionen. Om ett sådant spel kan utformas, då sägs det att spelet implementerar den sociala välfärdsfunktionen. Som ett exempel på en social välfärdsfunktion bör man överväga att minimera föroreningarna. Även om alla kanske är intresserade av att minska föroreningarna, är alla intresserade av att andra bär de kostnader som är förknippade med detta. En m~h~ism att genomföra denna sociala välfärd funktion kan till exempel omfatta skatter på förorenande industrier och skattelättnader ges för inköp av elbilar. Detta är just den typ av mekanism som skulle leda till att agenser, efter en jämviktsstrategi, minimerar föroreningarna. Designern av en mekanism måste hantera varje konfiguration av agent verktygsfunktioner (vilket är just därför han utformar en mekanism, eller "spelform", och inte ett specifikt spel). Agenterna själva kan eller kanske inte har fullständig information om varandras allmännyttiga funktioner, och därmed kan eller kanske inte vet vilket konkret spel de spelar. Detta komplicerar problemet med mekanismens utformning. Vanligtvis. Det finns ett antagande om att agenterna har vissa begränsningar i form av sina allmännyttiga funktioner. Således finns det en känd cct av alla möjliga allmännyttiga funktioner. Varje agent kan sedan tilldelas en "typ" baserad på vilken av de allmännyttiga funktioner som den för närvarande använder. En mekanism kallas en direkt mekanism om agenterna arc frågade rakt ut vad deras typ är. Sedan, baserat på agenternas deklarerade typer, ger mekanismen ett visst resultat. Om agenterna inte tillfrågas deras typ, kallas mekanismen en indirekt mekanism. Uppenbarelseprincipen säger att vad som än kan göras med en indirekt mekanism också kan göras med en direkt mekanism. Med andra ord kan varje social funktion som är genomförbar genom en indirekt mekanism också genomföras genom en direkt mekanism, där agenter kommer att ha ett incitament att deklarera sin sanna typ. Detta kallas en incitamentskompatibel mekanism. Fördelen med en direkt mekanism där agenterna har ett incitament att förklara sin sanna typ framför en indirekt mekanism är enkelheten i agenternas strategier. Agenternas enkelhet kan dock uppvägas av behovet av en komplicerad mekanism. Även om vi föredrar en direkt mekanism, är det också viktigt för oss att det blir en enkel helhet. Man kan titta på det arbete som beskrivs i denna artikel som en typ av mekanism design, där den sociala välfärd funktion som genomförs är "effektivitet", dvs summan av agenter' verktyg. Kräver att summan maximeras c1 priori utesluter många sociala beteenden, men fortfarande kan tillåta flera summa maximization beteenden. Med andra ord, även när summan maximeras, det sätt på vilket nyttan är uppdelad mellan agenter kan skilja sig. Eftersom varje agent vill ha en större andel av denna grupp nytta, har vi ett typiskt förhandlingsscenario. Antingen kommer agenterna överens om en division, eller så kommer de fram till en konflikt. Eftersom vi pratar om automatiserade agenter. Vi är beroende av deras designers för att nå samförstånd om mekanismen och dess tillhörande strategier. Därför är vår mekanism design enklare än spelet teori. I motsats till den klassiska mekanismens utformning är vi inte intresserade av jämviktsstrategiernas unika karaktär. Det som är viktigt för oss är existensen OT en jämviktsstrategi som maximerar den sociala välfärdsfunktionen. Vi är nöjda med existensen av även en sådan maximerande jämvikt socialt beteende, även om det kan finnas andra sociala beteenden i jämvikt som inte maximerar den sociala välfärden funktion. Designerna av våra automatiserade agenter kan välja en mekanism som har många jämviktspunkter (en del av dem maximerar den sociala välfärdsfunktionen och en del av dem inte). men sedan samordna sig (genom att gemensamt välja en strategi) så att deras agenter når en särskild jämviktspunkt som maximerar den sociala välfärdsfunktionen. Genom att lätta på vårt krav på mekanismen kan vi upptäcka sociala välfärdsfunktioner som kan implementeras med vårt tillvägagångssätt, men som inte kan implementeras med hjälp av spelteorins (begränsar) appreach.  Vilka är de attribut som kan intressera dessa företagsrepresentanter när de träffas för att diskutera interaktionsmiljön för sina maskiner? Denna uppsättning attribut, och deras relativa betydelse, kommer i slutändan att påverka deras val av interaktionsregler. Vi har övervägt flera attribut som kan vara viktiga för systemdesigners. 1) Effektivitet: Agenterna bör inte slösa bort resurser när de kommer fram till ett avtal; det får inte slösas bort på nytta när ett avtal har nåtts. Till exempel är det rimligt att avtalen uppfyller kravet på pareto-optimalitet (ingen agent skulle kunna härledas mer från ett annat avtal, utan någon annan agent som härrör mindre från det alternativa avtalet). Ett annat övervägande kan vara global optimalitet, vilket uppnås när summan av agenternas fördelar maximeras. Ingen av dessa typer av optimalitet innebär nödvändigtvis den andra. Eftersom vi talar om självmotiverade agenter (som bryr sig om sina egna verktyg, inte summan av system-omfattande verktyg-ingen agent i allmänhet skulle vara villiga att acceptera lägre nytta bara för att öka systemets summa), Pareto optimalitet spelar en primär roll i vår effektivitet utvärdering. Bland Pareto optimala lösningar, men vi kan också överväga som ett sekundärt kriterium de lösningar som ökar summan av system-wide verktyg. (2) Stabilitet: Ingen formgivare bör ha incitament att avvika från överenskomna strategier. Den strategi som agenter programmeras med kan föreslås som en del av interaktionsmiljödesignen. När dessa strategier väl har föreslagits vill vi dock inte att enskilda designers (t.ex. företag) ska ha incitament att gå tillbaka och bygga sina agenter med olika, manipulativa strategier. (3) Enkelhet: Det kommer att vara önskvärt för den övergripande interaktionsmiljön att ställa låga beräkningskrav på agenterna och att kräva lite kommunikation overhead. Detta gäller både effektivitet och stabilitet: om interaktionsmekanismen är enkel ökar den effektiviteten i systemet, med färre resurser som förbrukas vid genomförandet av själva förhandlingarna. På liknande sätt, med stabila mekanismer, behöver få resurser spenderas på att ifrågasätta din motståndare, eller försöka upptäcka hans optimala val. Det optimala beteendet har avslöjats offentligt, och det finns inget bättre att göra än att bara utföra det. (4) Distribution: Företrädesvis kommer samverkansreglerna inte att kräva någon central beslutsfattare, av alla uppenbara skäl. Vi vill inte att vårt distribuerade system ska ha en prestanda flaskhals, eller kollaps på grund av ett enda misslyckande av en speciell nod. (5) Symmetri: Ingen formgivare vill att förhandlingsprocessen ska vara godtyckligt partisk mot hans agent. Därför bör ingen mekanism behandla agenser annorlunda på grund av olämpliga kriterier. Exakt vad som utgör olämpliga kriterier beror på det specifika området, Även om mekanismen kan vara asymmetrisk, till exempel eftersom en agent har många fler uppgifter att utföra än den andra, bör den upprätthålla strikt opartiskhet när irrelevanta aspekter av agenterna skiljer sig (t.ex. agenternas tillverkare). Dessa attribut behöver inte vara allmänt accepterade. I själva verket kommer det ibland att finnas kompromisser mellan ett attribut och ett annat (t.ex. är effektivitet och stabilitet ibland i konflikt med varandra [83]. Men våra protokoll är utformade, för specifika klasser av domäner, så att de uppfyller vissa eller alla av dessa attribut. Slutligen, dessa är de typer av kriterier som graderar acceptansen av en interaktionsmekanism över en annan. Som ett exempel, egenskapen stabilitet antar särskild betydelse när vi överväger öppna system, där nya agenter ständigt kommer in och lämnar gemenskapen av interagerande maskiner. Här kanske vi vill behålla stabiliteten inför nya agenter som för med sig nya mål och potentiellt nya strategier också. Om mekanismen är "självförstärkande", i det att det inte bara är till nytta för samhället som helhet att följa reglerna, utan också till förmån för varje enskild medlem, då förblir det sociala beteendet stabilt även när samhällets medlemmar förändras dynamiskt. När interaktionsreglerna skapar en miljö där en viss strategi är optimal, är ett fördelaktigt socialt beteende motståndskraftigt mot invasion utifrån [I]. Vi har flera gånger anspelat på kopplingen mellan protokoll och domäner för en viss klass av interaktioner, vissa protokoll kan vara lämpliga medan andra båge inte. Vi har funnit det användbart att kategorisera domäner i en trestegshierarki av uppgiftsorienterade domäner, statsorienterade domäner och värda orienterade domäner. Denna hierarki är på intet sätt fullständig, men täcker en stor del av de slag av interaktioner i verkligheten som vi är intresserade av. Denna artikel är inriktad på uppgiftsorienterade domäner. För behandling av statsorienterade domäner. Se [76-78,82-841; för behandling av värdeorienterade domäner, se [59,79,85]. Detta är områden där en agents verksamhet kan definieras i termer av en uppsättning uppgifter som den måste utföra. Dessa uppgifter kan utföras utan oro för inblandning från andra agenter; alla resurser som krävs för att utföra uppgifterna är tillgängliga för agenten. Å andra sidan. Det är möjligt att agenter kan nå överenskommelser där de omfördelar vissa uppgifter, till allas fördel (till exempel, om en agent gör någon uppgift, han kan, till liten eller ingen kostnad. kunna utföra en annan agents uppgift). Områdena är till sin natur samarbetsvilliga. Förhandlingar syftar till att upptäcka omfördelningen av uppgifter som är till nytta för båda parter. Den centrala frågan här är begreppet betar, ett odelbart arbete som måste utföras. Naturligtvis kommer det som utgör en uppgift att vara specifikt för området. Många typer av verksamhet kan dock uppfattas på detta sätt, som utförandet av odelbara uppgifter. Tänk dig till exempel att du har tre barn, som var och en måste levereras till en annan skola varje morgon. Din granne har fyra barn och behöver också ta dem till skolan. Leverans av varje barn kan modelleras som en odelbar uppgift. Även om både du och din granne kanske är intresserade av att sätta upp en samåkning, är det ingen tvekan om att du kommer att kunna utföra dina uppgifter själv, om det är nödvändigt. Det värsta som kan hända är att du och din granne inte kommer att komma överens om att inrätta en samåkning, i vilket fall du är inte sämre än om du var ensam. Du kan bara dra nytta (eller inte göra värre) av din nästas existens. Intelligens 86 (1996) 195-244 21 Jag antar dock att ett av mina barn och ett av min grannes barn båda går i samma skola (dvs. kostnaden för att utföra dessa två leveranser, eller två uppgifter, är samma som kostnaden för att utföra en av dem). Det är uppenbart att det är vettigt att båda barnen tas tillsammans, och bara min granne eller jag kommer att behöva göra resan för att utföra båda uppgifterna. Vilka slags överenskommelser kan vi komma överens om? Vi kan besluta att jag ska ta barnen på jämna dagar varje månad, och min granne kommer att ta dem på udda dagar; kanske, om det finns andra barn inblandade, kanske vi har min granne alltid ta dessa två specifika barn, medan jag är ansvarig för resten av barnen (hans och mitt). En annan möjlighet skulle vara att vi varje morgon slår mynt för att avgöra vem som skall ta barnen. En viktig fråga, utöver vilka avtal som kan nås, är hur man kommer att komma överens om ett specifikt avtal (se avsnitt 7.2 nedan). Som ytterligare exempel kan nämnas postmendomänen, databasdomänen och faxdomänen (dessa områden beskrivs närmare och mer formellt nedan). I postmen domänen, varje agent ges en uppsättning bokstäver för att leverera till olika noder på en graf; börjar och slutar på postkontoret, agenterna ska passera grafen och göra sina leveranser. Det finns ingen kostnad i samband med att bära bokstäver (de kan bära vilket nummer som helst), men det finns en kostnad i samband med graf traversal. Agenterna är intresserade av att göra korta resor. Agenter kan komma överens om att bära varandras brev och spara på sina resor. Databasdomänen tilldelar på liknande sätt varje agent en uppsättning uppgifter och möjliggör en fördelaktig omfördelning av uppgifter. Här, varje agent ges en fråga som det kommer att göra mot en gemensam databas (för att extrahera en uppsättning poster). En fråga kan i sin tur bestå av subqueries (dvs. agentens uppgifter). Till exempel, en agent kan vilja register över "Alla kvinnliga anställda som tjänar över $ 50000 per år", medan en annan agent kan vilja register över "Alla kvinnliga anställda med mer än tre barn". Båda agenterna delar en deluppgift, den fråga som innebär att extrahera register över alla kvinnliga anställda (före att extrahera en delmängd av dessa register). Genom att bara ha en agent får de kvinnliga anställdas register, kan en annan agent sänka sina kostnader. Det tredje exemplet är faxdomänen. Det verkar mycket lik postmen domänen, men är subtilt annorlunda. I faxdomänen får varje agent en uppsättning fax som skickas till olika platser runt om i världen (varje fax är en uppgift). Den enda kostnaden är att upprätta en förbindelse. När anslutningen är gjord kan ett obegränsat antal fax skickas. Naturligtvis, om två agenter båda har fax för att skicka till Paris och London, kan de omfördela sina fax, med en skicka alla fax till Paris och den andra skicka alla fax till London. Trots de till synes mindre skillnaderna inom dessa områden, attributen för lämpliga protokoll är mycket olika för varje, som vi kommer att se nedan. Den statsorienterade domänen (SOD) är den typ av domän med vilken de flesta AI-forskningar har handlat. Blockvärlden är till exempel en klassisk statsorienterad domän. SOD är en superuppsättning av TOD (dvs. varje TOD kan gjutas i form av en SOD). I en SOD, varje agent är intresserad av att flytta världen från en initial stat till en av en uppsättning av måltillstånd. Det finns naturligtvis en möjlighet till verklig konflikt här. På grund av till exempel konkurrens om resurser kan agenter ha fundamentalt olika mål. Det kanske inte finns några måltillstånd som tillfredsställer alla agenter. Vid andra tillfällen kan det finnas måltillstånd som tillfredsställer alla agenter. Men det är dyrt att nå och som kräver att agenterna gör mer arbete än de skulle ha behövt göra isolerat. Mekanismer för att hantera statsorienterade domäner granskas i [76][77][78]83,84]. Förhandlingsmekanismer som har vissa attribut inom uppgiftsorienterade områden (t.ex. effektivitet och stabilitet) behöver inte nödvändigtvis ha samma attribut inom statsorienterade områden. Värt orienterade domäner (WODs) är en generalisering av statsorienterade domäner, där agenter tilldela ett värde till varje potentiellt tillstånd, som etablerar sin önskvärdhet för agenten (i motsats till en SOD, där värdefunktionen är i huvudsak binära alla icke-mål stater har noll värde). Detta etablerar ett beslut teoretisk smak för interaktioner i en WOD. Ett exempel på en WOD är TileWorld, som beskrivs i [ 521. Den viktigaste fördelen med en värdeorienterad domän är att värdefunktionen gör det möjligt för agenter att kompromissa med sina mål, ibland öka den övergripande effektiviteten i avtalet. Varje SOD kan kastas i termer av en WOD. Naturligtvis (med binärt värde funktion). Förhandlingsmekanismer som lämpar sig för en SOD behöver inte vara lämpliga för en WOD (dvs. attributen för samma mekanism kan ändras vid förflyttning från en SOD till en WOD). Mekanismer för att hantera värdefulla områden undersöks i [79]. 851. Vad är det för fel på dig? Att utforma en förhandlingsmekanism, de övergripande "interaktionsreglerna", är en process i tre steg. För det första måste de som utformar agenten enas om en definition av domänen, sedan komma överens om ett förhandlingsprotokoll och slutligen föreslå en förhandlingsstrategi. Den fullständiga definitionen av en domän bör ge en exakt specificering av begreppet mål och av de tillgängliga agentverksamheten. Till exempel, i postmen domän, målet för en agent är den uppsättning bokstäver som agenten måste leverera (som i alla TOD, målet är den uppsättning uppgifter som måste utföras), tillsammans med kravet att agenten börjar och slutar på postkontoret. I specifikationen av den tillgängliga agentverksamheten definieras exakt vad en agent kan göra och arten av dessa åtgärders kostnader. I postmen domänen, återigen, är det en del av domändefinitionen att en agent kan bära ett obegränsat antal bokstäver, och att kostnaden för en graf traversal är det totala avståndet rest. Intelligence 86 (1996) 195-244 213 Denna formella domändefinition är det nödvändiga första steget för att analysera alla nya domäner. Om agenter förhandlar om överdelning av meddelandetrafik i telenät är det nödvändigt att helt specificera vad som utgör ett mål och vilka agentverksamheter som är tillgängliga. På samma sätt behöver PDA som deltar i förhandlingar om tidtabeller sina mål och operatörer exakt definieras. När domänen väl har specificerats måste vi specificera förhandlingsprotokollet, som fastställer reglerna för interaktion mellan agenter. Här måste vi bry oss både om utrymmet för möjliga överenskommelser och om förhandlingsprocessen. l Utrymme för möjliga avtal: För det första måste vi specificera uppsättningen av kandidatavtal. Vilka typer av överenskommelser kan agenterna komma fram till? Till exempel kan vi begränsa våra agenter till att bara diskutera avtal som inte innebär överflödigt arbete (t.ex. i samåkning exempel, föräldrarna kommer inte att överväga erbjudanden som har två föräldrar som besöker samma skola). På liknande sätt skulle vi kunna specificera att affärer inte kan innebära att man kastar ett mynt. l Förhandlingsprocess: Med tanke på en rad möjliga avtal, vad är den process som agenter kan använda för att konvergera till en överenskommelse om en enda affär? Med andra ord, vilka är de regler som specificerar hur samförstånd kommer att uppnås? Hur kommer en överenskommen överenskommelse att skiljas från de andra kandidaterna? I exemplet samåkning kan vi ange att varje förälder i sin tur kommer att erbjuda ett leveransschema och uppgifter; nästa förälder kan antingen acceptera erbjudandet, eller förkasta det och göra sin egen moterbjudande. Vi skulle också kunna tillåta, som en del av förhandlingsprocessen, att varje förälder när som helst kan lägga fram ett "take-it-or-leave-it"-förslag, som antingen kommer att accepteras eller avslutas utan överenskommelse. Ett annat exempel på en förhandlingsprocess var det monotona koncessionsprotokollet som beskrivs i avsnitt 2.5.1 ovan. Med tanke på ett antal möjliga avtal och en förhandlingsprocess, vilken strategi bör en enskild agent anta när han deltar i processen? Till exempel är en strategi för en förälder i samåkningsscenariot att beräkna en viss leveranstidtabell och presentera den som en "take-it-or-leave-it". En annan strategi är att börja med det avtal som är bäst för dig, och om den andra föräldern förkastar det, minimalt ändra det som en eftergift till den andra föräldern. Specifikationen av en förhandlingsstrategi är inte strikt en del av de interaktionsregler som beslutas av automatiserade agenters konstruktörer. Med andra ord, formgivarna är verkligen fria att bygga sina agenter som de tycker passar. Ingen kan tvinga dem att bygga sina agenter på ett visst sätt (med en viss strategi), och ett sådant tvång skulle förmodligen inte vara effektivt om man försökte. Men vi kan ge strategier med kända egenskaper, och tillåta designers att införliva dem. Mer specifikt kan vi kanske få fram en viss strategi och visa att den är påfallande optimal (för agenten själv). Det kommer inte att finnas något incitament för någon designer att använda någon annan strategi. Och när alla agenter använder den strategin, kommer det att finnas vissa (nyttiga) globala egenskaper i interaktionen. Så en förhandlingsstrategi ges till formgivarna som en tjänst; om ett övertygande fall görs, formgivarna kommer i själva verket att införliva denna strategi i sina agenter. Vi är i allmänhet intresserade av förhandlingsprotokoll/strategikombinationer. Som nämnts ovan är de domänexempel som ges i avsnitt 6.1 alla TOD och verkar ha en hel del gemensamt med varandra. Det finns dock kritiska skillnader mellan dem, alla fokuserade på domänernas kostnadsfunktioner. För att visa dessa skillnader kategoriserar vi TOD baserat på tre möjliga attribut för kostnadsfunktionen: subadditionalitet, konkavitet och modularitet. Detta är en hierarki; modularitet innebär konkavitet, vilket i sin tur innebär subadditionalitet. Protokoll och strategier som är stabila i en typ av TOD är inte nödvändigtvis stabila i andra typer. Dessa frågor diskuteras mer ingående nedan. På vissa områden, genom att kombinera uppsättningar av uppgifter kan vi minska (och kan aldrig öka) den totala kostnaden, jämfört med summan av kostnaderna för att uppnå uppsättningarna separat. Postmendomänen, till exempel, är subadditiv. Om X och Y är två uppsättningar adresser, och vi måste besöka dem alla (X U Y), då i värsta fall kommer vi att kunna göra den minimala cykel besöka X-adresser, sedan gör minima1 cykel besöka Y-adresser. Detta kan vara vår bästa plan om adresserna är osammanhängande och frikopplade (grafens topologi är emot oss). I så fall. kostnaden för att besöka alla adresser är lika med att besöka en uppsättning plus kostnaden för att besöka den andra uppsättningen. Men i vissa fall kanske vi kan göra bättre ifrån oss och besöka några adresser på vägen till andra. Det är vad subadditionalitet betyder. Ett annat exempel är databasens frågedomän. För att utvärdera två uppsättningar av frågor, X och Y, kan vi naturligtvis utvärdera alla frågor i X, sedan självständigt utvärdera alla frågor i Y. Detta, återigen, kan vara vår bästa åtgärd om frågorna är åtskilda och frikopplade; den totala kostnaden kommer att vara kostnaden för X plus kostnaden för Y. Men ibland kommer vi att kunna göra bättre, genom att dela resultaten av frågor eller subqueries, och utvärdera X U Y till lägre totalkostnad. En relativt liten förändring av en domändefinition kan dock eliminera subadditionalitet. Om agenterna inte var tvungna att återvända till postkontoret i slutet av sina leveranser, då skulle domänen inte vara subadditive. I en konkava domän, den kostnad som godtyckliga uppsättning av uppgifter Z lägger till en uppsättning uppgifter Y kan inte vara större än kostnaden Z skulle lägga till en delmängd av Y. Faxdomänen och databasens frågedomän är konkava, medan postmendomänen inte är det. Intuitivt är en konkav domän mer "förutsägbar" än en subadditiv domän som inte är konkav. Det finns ett element av monotonitet att kombinera uppgifter i en konkava domän G. Z&kin, J.S. Rosenschein/Artij?cial Intelligence 86 (1996) 195-244 215 som saknas från icke-konkav domäner. Du vet till exempel att om du har en ursprunglig uppsättning uppgifter (X), och står inför att få en extra utanför uppsättning (Z), kommer du inte att lida särskilt mycket om du förstorar den ursprungliga uppsättningen-det extra arbete som 2 lägger till kommer antingen påverkas eller minskas av utvidgningen av den ursprungliga uppsättningen. I en icke-konkav domän, även om den är subadditiv, kan du finna att det extra arbete som Z lägger till är mycket större än det skulle ha varit före utvidgningen. Inom ett modulärt område är kostnaden för kombinationen av två uppsättningar uppgifter exakt summan av deras individuella kostnader minus kostnaden för deras skärningspunkt. Detta är intuitivt den mest väluppfostrade subadditiva domänkategorin av alla. När uppgiftsuppsättningar kombineras är det bara deras överlappning som spelar roll-alla andra uppgifter är främmande för förhandlingarna. Endast faxdomänen från ovanstående TOD-exempel är modulär. En stor del av den forskning som vi har bedrivit enligt denna förhandlingsmodell tar upp frågor som rör agenter som har ofullständig information om sina möten [781. De kanske till exempel är medvetna om sitt eget mål utan att känna till målet för den agent de förhandlar med. De kan därför behöva anpassa sin förhandlingsstrategi för att hantera denna osäkerhet. Ett uppenbart sätt på vilket osäkerhet kan utnyttjas kan vara att förvränga en agents verkliga mål. Inom ett uppgiftsinriktat område kan sådan förvrängning innebära att man döljer uppgifter eller skapar falska uppgifter (fantomer eller lockbeten), allt i syfte att förbättra sin förhandlingsposition. Processen för att nå en överenskommelse är i allmänhet beroende av att agenter deklarerar sina individuella uppgifter, och sedan förhandlar om den globala uppsättningen av deklarerade uppgifter. Genom att förklara sin uppgift felaktigt inställd kan man i princip (under vissa omständigheter) ändra förhandlingsresultatet till förmån för en. Mycket av vår forskning har fokuserats på förhandlingsmekanismer som inte uppmuntrar till bedrägeri. Dessa typer av förhandlingsmekanismer kallas "incitamentkompatibla" mekanismer i spelteorilitteraturen. När en mekanism är incitamentskompatibel, ingen agent designer kommer att ha någon anledning att göra något annat än att få sin agent förklara sitt verkliga mål i en förhandling. Även om designern är fri att bygga sin agent på vilket sätt han vill, kommer sanningen att visas vara den optimala strategin. Denna strävan efter ärlighet bland agenter, och för att uppmuntra ärlighet genom själva förhandlingsmiljöns struktur, är en absolut nödvändig aspekt av arbetet med mutagenta system. Situationer där agenter har incitament att ljuga är i allmänhet inte stabila. Även om agent designers kan diskutera en strategi, de kommer då att vara motiverade att gå tillbaka och bygga sina agenter på ett annat sätt. Detta kommer i slutändan att resultera i mindre effektiva system (och utfall som är sämre för de enskilda agenserna). För det första kan agenter rimligtvis lägga ner mycket energi på att upptäcka den andra förhandlarens verkliga mål, och allt detta minskar systemets enkelhet och effektivitet. För det andra kommer de att frestas att riskera strategier som kan leda till sämre resultat. Två agenter, som kommer tillsammans, var och en försöker ifrågasätta varandra, kommer ibland att göra val som inte gagnar någon. På så sätt är effektivitet och stabilitet nära förbundna med varandra. Det är ingen idé, i multiagentsystem, att överväga effektivitet utan att ta hänsyn till stabilitet. Utan stabilitet kan effektivitet inte garanteras, eftersom agenter frestas att avvika från den globalt effektiva strategin. En tusk orienterad domän (TOD) beskriver en viss klass av scenarier för multiagent möten. Intuitivt är det en domän som är samarbetsvillig, utan negativa interaktioner mellan agenternas mål. Varje agent välkomnar förekomsten av andra agenter, för de kan bara dra nytta av varandra (om de kan nå en överenskommelse om att dela uppgifter). I) 7 är uppsättningen av alla möjliga uppgifter. så att för alla k t {I,. , II}, TX är en fin uppsättning uppgifter från 7 som Ak måste uppnå. Tk kommer också att kallas Aks Leoai. Enligt definitionen ovan. Kostnadsfunktionen c tar inga andra parametrar än aktivitetsuppsättningen. I allmänhet kan c definieras som att ha andra, globala, parametrar (som det ursprungliga tillståndet i världen). Kostnaden för en uppsättning uppgifter är dock oberoende av andras uppgifter som måste utföras. En agent i en TOD är säker på att kunna uppnå sitt mål till den kostnaden. Här ger vi flera exempel på TOD. som täcker en mängd olika situationer när det gäller läkemedelsinteraktion. Därefter kommer vi att ytterligare klassificera vart och ett av dessa TOD-exempel med avseende på de kostnadsegenskaper som nämns ovan i avsnitt 8. Beskrivning: Agenter måste leverera containrar till lager, som är ordnade på en viktad graf G = G( v E). Det finns ingen gräns för antalet behållare G. Uotkin, J.S. Rosenschein/Artificial Intelligence 86 (1996) 195-244 217 som får plats i ett lager. Agenterna börjar från en central distributionspunkt. Agenter kan byta containrar utan kostnad medan de är på distributionsstället, före leverans. Setet av alla adresser i grafen, nämligen V. Om adressen x finns i en agents uppgift, betyder det att han har minst en behållare att leverera till x. Kostnadsfunktion: Kostnaden för en delmängd av adresser X G V, dvs. c(X), är längden på den minimala sökvägen som börjar vid distributionspunkten och besöker alla X-medlemmar. Beskrivning: Agenter måste leverera uppsättningar av bokstäver till brevlådor, som är ordnade på en viktad graf G = G (YE). Det finns ingen gräns för antalet bokstäver som får plats i en brevlåda. Efter att ha levererat alla brev måste ombuden återvända till utgångspunkten (postkontoret). Agenter kan byta brev utan kostnad när de är på postkontoret, innan leverans. Uppgiftsuppsättning: Mängden av alla adresser i grafen, nämligen V. Om adressen x finns i en agents uppgiftsuppsättning, betyder det att han har minst ett brev att leverera till x. Kostnadsfunktion: Kostnaden för en delmängd av adresser X C V, dvs. c(X), är längden på den minimala vägen som börjar på postkontoret, besöker alla medlemmar av X, och slutar på postkontoret. Beskrivning: Agenter har tillgång till en gemensam databas, och var och en måste utföra en uppsättning frågor. Resultatet av varje fråga är en uppsättning poster. Till exempel, agent At kan vilja att register som uppfyller villkoret "Alla kvinnliga anställda i företag X tjänar över $ 50.000 per år", och agent A2 kan vilja att register som uppfyller villkoret "Alla kvinnliga anställda i företag X med mer än 10 års tjänstgöringstid". Agenter kan utbyta resultat av frågor och subqueries utan kostnad. Uppgiftsuppsättning: Alla möjliga frågor, uttryckta i primitiva av relationell databas teori, inklusive operatörer som gå, projektion, union, skärningspunkt, och skillnad. Kostnadsfunktion: Kostnaden för en uppsättning frågor är det minsta antalet databasoperationer som behövs för att generera alla poster. Det är möjligt att använda resultatet av en fråga som indata till andra frågor, dvs. operationer är inte destruktiva. Beskrivning: Agenter skickar fax till platser på ett telefonnät (en viktad graf) För att skicka ett fax måste en agent upprätta en förbindelse med den mottagande noden. När anslutningen är etablerad kan flera fax skickas utan extra kostnad. Agenterna kan utan kostnad utbyta meddelanden som skall faxas. Tusk set: Den uppsättning av alla möjliga mottagande noder i nätverket. Om nod x finns i en agents uppgift, betyder det att han har minst ett fax att skicka till n. Kostnadsfunktion: Det finns en kostnad i samband med att upprätta en enda anslutning till någon nod x. Kostnaden för en uppsättning uppgifter är summan av kostnaderna för att upprätta förbindelser 218 G. Zlorkin, J.S. Rosens~hein/Art~ciuI lntelli~mc~e 86 (I 996) 195-244 till alla noder i uppsättningen. Således, kostnaden för en uppringd anslutning till en given nod är oberoende av andra noder i uppgiften som. Beskrivning: Det finns en uppsättning identiska pinnar, en korg, och en uppsättning hål. En pinne kan vara i ett hål, i korgen eller i en agents hand. Varje hål är märkt som antingen svart eller vitt, och kan hålla som mest en pinne. En agent är endast intresserad av konfigurationen av pinnar i svarta hål, och den andra handlar endast om konfigurationen av pinnar i vita hål. Varje agent har en lista över (sin egen färg) hål att fylla eller tom. Det finns tillräckligt med pinnar för att tillfredsställa båda agenternas mål. Det finns två operationer i denna värld: Pickup (plocka upp pinnen från ett icke-tomma hål eller någon pinne från korgen), och PutDown (lägg ner pinnen som för närvarande hålls i ett tomt hål eller korgen). En agent kan inte hålla mer än en pinne åt gången. Tusk set: En enda uppgift (s, h) är att ha hål s innehåller h pinnar, där h är 0 eller 1 (dvs, gör hål är tomma eller har det endast innehåller en peg). 7 = (s, h): s är ett hål, h E (0, I}. I varje möte världen är i något initialt tillstånd (detta är en mötesspecifik parameter som påverkar kostnadsfunktionen, men kostnadsfunktionen är fortfarande identisk för alla agenter). En agent har en konsekvent uppgift som innehåller endast vita hål, medan den andra agenten har en konsekvent uppgift som endast innehåller svarta hål. Kostnadsfunktion: Kostnaden för en konsekvent uppsättning uppgifter X är den minimala uppsättningen av Pickup, PutDown operationer som måste göras för att flytta världen från sitt ursprungliga tillstånd till ett sluttillstånd som uppnår alla uppgifter i X. Det finns åtminstone en minimal kostnad plan som inte involverar den andra agentens hål (antingen tar eller placerar pinnar i dessa hål). Efter att ha infört TOD ovan, vänder vi nu vår uppmärksamhet till attribut som dessa domäner uppvisar. Dessa attribut påverkar i hög grad deras relationer till förhandlingsmekanismerna. Vi kommer att fokusera på attributen subadditionalitet, konkavitet och modularitet. Motiveringen till dessa definitioner presenteras mer i detalj nedan. Med andra ord, genom att kombinera uppsättningar av uppgifter kan vi minska (och kan aldrig öka) den totala kostnaden, jämfört med kostnaden för att uppnå uppsättningarna ensam. Alla TOD-exempel ovan är subadditiva, utom leveransdomänen. För att se varför leveransdomänen inte är subadditiv, tänk på mötet som visas i Bild. Jag. Kostnaden för uppgiften a (dvs. kostnaden för att leverera något att nodera en från distributionspunkten) är 1, vilket också är kostnaden för uppgift 6. Kostnaden för föreningen av a och b är dock 3 (leveranten, efter att ha levererat till den ena, måste gå tillbaka till distributionspunkten innan han fortsätter att leverera till den andra). Kostnaden för att förena uppgifterna (3) är således större än summan av kostnaderna för de enskilda uppgifterna (2). I leveransdomänen kan det finnas icke-subadditiva möten. I den här artikeln är vi främst intresserade av två-agent subadditiva domäner. Definition 4 (konkavitet). TOD (7, A, c) kommer att kallas konkava om för alla ändliga uppsättningar av Med andra ord, kostnaden att en godtycklig uppsättning uppgifter Z lägger till en uppsättning uppgifter Y inte kan vara större än kostnaden Z skulle lägga till en delmängd av Y. Beviset på detta teorem och alla andra teorem, liksom ytterligare lemmas, finns i bilaga A. Den allmänna postmen-domänen, och den svarta/vita håldomänen, är inte konkava. De andra TOD-exempelen (faxdomänen och databasens frågedomän) är konkava. Postmen domänen är inte konkava eftersom det kan finnas fall sådana att en uppgift (eller en uppsättning uppgifter) kan lägga mer till någon annan uppsättning uppgifter än det lägger till en delmängd av det. Ett sådant exempel kan man se i bild. 2............................................................... Varje kant mellan noderna har kostat 1. LetX= {d,e,f,g} CY={b,c,d,e,f,g} och Z=(h). Därför har vi ett brott mot konkaviteten: Ett exempel på det svarta/vita hålets icke-konkavitet kan ses i bild. 3............................................................... I det ursprungliga tillståndet (som kan ses i toppen av Bild. 3 ) slits Jag är tom medan slots 2 och 3 är fyllda. X inkluderar uppgiften (I. I ) (dvs., slot I är fylld). Kostnaden för att uppnå X från det ursprungliga tillståndet (c(X) ) är 2. Allt vi behöver göra är att plocka upp ett block från korgen eller från andra slots och sedan att PutDown blocket i slot I. Y innehåller X och en ytterligare uppgift till tom plats 2 (dvs, Y = { (1, 1). )............................................................................................................................ För att uppnå Y behöver vi också bara göra en pickup (den här gången kommer vi att plocka blocket i slot 2 upp) och en PutDown (dvs.. c.(Y) = 2). Z omfattar en uppgift: att tömma slot 3 (dvs. Z = ((3,O))). Av denna anledning c( X L Z) = 2, som uppnås genom att plocka upp blocket i slot 3 och lägga ner det i den tomma slot I. Hur som helst. C( Y li Z) = 4. eftersom vi måste flytta ett block (från slot 2 till slot I) för att uppnå Y, och sedan måste vi flytta ett annat block (från slot 3 till korgen) för att uppnå Z. Återigen har vi en överträdelse av konkavitet villkoret: Theorem 6 Med andra ord, kostnaden för kombinationen av två uppsättningar uppgifter är exakt summan av deras individuella kostnader minus kostnaden för deras korsning. Endast faxdomänen från ovanstående TOD-exempel är modulär. Som det sägs i Theorem 6 är postmendomänen begränsad till en trädtopologi konkava. En graf har en stjärna topologi om det inte finns mer än en nod med grad större än en (en stjärna topologi är en subcase av en träd topologi). Noden med grad större än en kallas grafens mittpunkt. Om vi ytterligare begränsar postmen domän till träd som har stjärntopologier (där postkontoret är i centrum), då har vi en modulär TOD. Ett stjärnexempel kan ses på vänster sida av Fig. 4, där postkontoret är på nod a. I en stjärntopologi kostnaden för att besöka två olika noder u, w E 7 är lika med summan av att besöka varje nod separat, dvs u # w --+ c( {u} U {w}) = c( {u}) + c <(w)). Detta innebär modulärt tillstånd. Postmen domän begränsad till fullt ansluten (det finns en båge mellan två noder) och homogena (alla bågar har samma längd) grafer, är också modulär. Ett exempel på en helansluten och homogen graf kan ses på höger sida av bild. 4........................................... Om längden på alla noder är 1 så kostnaden för att besöka en uppsättning noder X i en helt ansluten och homogen graf är: c(X) = 1x1 + 1. Detta innebär helt enkelt modulärt tillstånd: c(X U Y) = IX U YI + 1 = 1x1 + IYI -IX f? Y( + 1 = (~x~+1)+(~Y~+1)-(~xnY~+1)=c(X)+c(Y)-c(XnY). Icke-homogena fullt anslutna grafer är inte ens konkava. Ett exempel på detta är exemplet ovan i Bild. 3, Med ytterligare tillräckligt långa ytterligare bågar för att göra grafen fullt ansluten. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. Det är Zlotkin. J.S. Hosensc.lzeln/Art~frctur Intelli, I detta avsnitt utvecklar vi ramverket för att formalisera tvåagentiska förhandlingsmekanismer inom subadditiva uppgiftsorienterade områden. Liknande definitioner finns i vårt tidigare arbete [ 75.77.78 1. I denna förordning gäller följande definitioner: "Ej tillämpligt": "Ej tillämpligt" eller "Ej tillämpligt" eller "Ej tillämpligt": "Ej tillämpligt" eller "Ej tillämpligt" eller "Ej tillämpligt". Eftersom ett möte ( TI, 7'2 ) inom en två-agent TOD (7. {Al, AZ}, c) vi har följande: ( I ) En ren deul är en omfördelning 01 uppgifter bland agenter. Det är en beställd lista ( DI, 02) sådan att Dr, D? C 7. och Dl &.J 02 = Tl U Tz. Det semantiska i ett sådant avtal är att varje agent An åtar sig att utföra alla uppgifter i Dk. Kostnaden för en sådan affär till Ak definieras för honom Costk( D1,02) = c( Dk). (2) En blandad affär är en ren affär ( DI, D2) och en sannolikhet p, 0 < 11 < I. En blandad affär kommer han betecknad som (D1 1 Dl): p. Semantiken i denna affär är att agenterna kommer att utföra ett lotteri så att, med sannolikhet p, DI kommer att tilldelas Al och 02 kommer att tilldelas A?. Sannolikt kommer I-p. DI att tilldelas A2 medan D? kommer att tilldelas A 1. Kostnaden för en sådan affär till Ak definieras som Costk ((Dr, D2): Al har en p chans att utföra alla uppgifter Tl U T, och har en I ~ p chans att göra ingenting. Med ovanstående definitioner av tre transaktionstyper. Vi anser nu nytta, förhandlingssättet, optimala protokoll och stabila förhandlingsstrategier. ( I ) För alla erbjudanden 6 (rent, allt-eller-ingenting, eller blandat) kommer vi att definiera Utilityk( 6) E c(Tk) -Costk(8). (2) (ren) affär 0 E (TI, Tz ) kommer att kallas konjict affären. (9 är en konflikt eftersom ingen agent går med på att utföra andra uppgifter än sina egna. Observera att för alla k, Verktyg,!(O) = 0. När agenterna misslyckas med att komma överens, dvs., stöter på en konflikt, de som standard utföra konflikten affären 0. Vårt antagande är att rationella agenter är nytta maximerare; eftersom de kan garantera sig själv nytta 0, kommer de inte att gå med på någon affär som ger dem negativ nytta. För erbjudanden 6 och 8' (ren, allt-eller-ingenting, eller blandad), kommer vi att säga att 6 dominerar 8, och skriva 8 + 8, om och endast om (Utilityt (a), Utilityz (S)) t (Utility, (6), Utilityz ( 8) ). Vi kommer att säga att 6 svagt dominerar 8, och skriva 6 k 8, om och endast om (Utility, (6), Utilityz( 6) ) k (Utility, (a), Utility2 (8) ). Vi kommer att säga att 8 är lika med 8, och skriva 6 z 6 "om Jk (Utilityk(S) = Utilityk (8)). G. Zlotkin, J.S. RosenscheidArtifcial Intelligence 86 (1996) 195-244 223 Om S t 6' innebär det att affären S är bättre för minst en agent och inte sämre för den andra. En pareto optimal affär kan inte förbättras för en agent utan att sänka den andra agentens nytta från affären. Eftersom agenter per definition är likgiltiga mellan två erbjudanden som ger dem samma verktyg, är vi intresserade av förhandlingsmekanismer som producerar pareto optimala erbjudanden (dvs., om agent Al får samma verktyg från erbjudanden x och y, men A:! föredrar y, vi vill inte att de ska nöja sig med x). Just nu överväger vi bara förhandlingsmekanismer som resulterar i ett avtal från NS. Dessa mekanismer är på sätt och vis effektiva. Teorem 16. För varje möte i en TOD, NS över rena avtal är inte tomt. Teorem 17. För varje möte inom någon TOD, NS över blandade erbjudanden är inte tom. Efter att ha infört de två mekanismerna ovan (kom ihåg att en mekanism innehåller både ett protokoll och en strategi), kommer vi att flytta vår uppmärksamhet till hela klassen av mekanismer som uppfyller följande villkor: l Protokollet är symmetriskt fördelat. l Strategin är i balans med sig själv. l Med tanke på protokollet, om två agenter spelar strategin de kommer överens om en affär som maximerar produkten av sina verktyg. Om det finns mer än en produkt maximera affären, kommer de överens om en affär (bland dessa produkt maximerare) som maximerar summan av verktyg. Om det finns mer än en sådan summa maximera produkten maximerar, protokollet kommer att välja bland dessa handlar med någon godtycklig sannolikhet. Denna definition innebär både individuell rationalitet och pareto-optimalitet för de avtalade avtalen. Vi kommer att kalla denna klass av mekanismer den produkt nmximizing mekanismer, eller PMMs. Alla PMM är effektiva. Under resten av denna artikel kommer vi inte att bry oss om exakt vilka förhandlingsmekanismagenter som använder sig av: så länge den tillhör PMM-klassen. De är ett antal befintliga metoder för att lösa förhandlingsproblemet i spelteorin. En av de tidigaste och mest populära var Nashs axiomatiska tillvägagångssätt [ 43.501. Nash försökte axiomatiskt definiera en "rättvis" lösning på en förhandlingssituation. Han räknade upp följande kriterier som de som en rättvis lösning skulle uppfylla: ( 1 ) Individuell rationalitet (det skulle inte vara rättvist för en deltagare att få mindre än han skulle ändå utan ett avtal). (2) Pareto optimalitet (en rättvis lösning kommer inte att specificera ett avtal som skulle kunna förbättras för en deltagare utan att skada den andra). ( 3 ) Symmetri (om situationen är symmetrisk. Det vill säga, båda agenterna skulle få samma nytta utan ett avtal, och för varje möjlig affär, den symmetriska affären är också möjlig. Då bör en rättvis lösning också vara symmetrisk, dvs. ge båda deltagarna samma nytta). (4) Varians i fråga om omvandlingar av lineal-utility. Tänk dig till exempel två agenter som förhandlar om hur man delar 100 dollar. Om en agent mäter hans nytta i dollar medan den andra mäter hans i cent. Det bör inte påverka den rättvisa lösningen. På samma sätt, om en agent redan har $ 10 i banken, och utvärderar affären som ger honom.x dollar som att ha nytta 10 + x medan den andra bedömer en sådan affär som att ha nytta.t-, bör det inte påverka den rättvisa lösningen (dvs. förändring av ursprung påverkar inte lösningen). 5) Oberoende av irrelevanta altcrnativcs. Tänk dig två agenter som förhandlar om hur man delar IO, tusen cent. Nash lösning kommer att vara 5.000 cent för varje, på grund av symmetri antagandet ovan. Föreställ dig nu att samma agenter förhandlar över 100 dollar. Även om det nu finns några avtal som de inte kan nå (till exempel. Den ena där en agent får $49.99 och den andra $30.01. lösningen ska vara densamma. Eftersom den ursprungliga lösningen på 5.000 cent fortfarande kan hittas i den nya affären utrymme. Nash visade att produkten maximerar lösningen inte bara mättar ovanstående kriterier. men är den enda lösning som tillfredsställer dem. De fyra första kriterierna ovan är uttryckligen eller implicit antagna i vår egen strategi (i själva verket. Vår version av det fjärde antagandet ovan är till exempel mer restriktiv än Nash's). De femte kriterierna ovan är inte ussutmd i vårt arbete, men visar sig vara sant i vissa fall ändå. Vi USC Nash-lösningen, i allmänhet, som ett rimligt förhandlingsresultat, när den är tillämplig. Nash, dock. hade vissa antaganden om utrymmet för avtal som vi inte håller. Problemet med Nash-förhandlingarna förutsätter till exempel en avgränsad, konvex, kontinuerlig och stängd förhandlingsregion. I våra agentförhandlingar utgår vi inte från att avtalen är konvexa och inte heller att de är kontinuerliga. I denna förordning gäller följande definitioner: "Ej tillämpligt": "Ej tillämpligt" eller "Ej tillämpligt" eller "Ej tillämpligt" för "Ej tillämpligt" för "Ej tillämpligt" för "Ej tillämpligt" för "Ej tillämpligt" för "Ej tillämpligt" för "Ej tillämpligt" för "Ej tillämpligt" för "Ej tillämpligt". En produkt maximizin g mekanism (PMM) över en uppsättning avtal är en mekanism som har en förhandlingsstrategi som är i jämvikt med sig själv-om alla agenter använder denna förhandlingsstrategi, kommer de överens om en affär i NS som maximerar produkten av agenternas nytta [SO]. Om det finns mer än en sådan affär som G. Ziorkin, J.S. Rosen.~chein/Art~ci~l fnteiligence 86 (1996) 195-244 22s maximerar produkten, mekanismen väljer en godtyckligt, med lika stor sannolikhet. Observera att en PMM per definition uppfyller de stabilitets- och effektivitetskriterier som anges i avsnitt 5. Det monotona koncessionsprotokoll som anges ovan i avsnitt 2.5. Jag har en ~uilibrium strategi för varje affär typ som ger avtal om en affär i NS som maximerar produkten av agenternas verktyg. Dessa strategier bygger på Zeuthen-riskkriterier [741] och presenterades i [751. Därför är det monotona koncessionsprotokollet (se avsnitt 25.1) en PMM.  Ibland har agenter inte fullständig information om varandras mål. Detta väcker frågan om agenter kan dra nytta av att dölja mål, eller tillverkning konstgjorda mål. Denna lögn kan antingen ske explicit, genom att deklarera falska mål, eller implicit, genom att bete sig som om dessa falska mål var sanna, beroende på den specifika förhandlingsmekanismen. Vårt arbete i tidigare uppsatser [75.77.78] fokuserade delvis på kombinationer av förhandlingsmekanismer och områden där agenter inte har något incitament att ljuga. En förhandlingsmekanism kallas incitamentskompatibel när strategin att tala sanning (eller att uppföra sig enligt dina verkliga mål) är i jämvikt (dvs. när en agent använder strategin är det bästa den andra agenten kan göra att använda samma strategi). I postmen domänen [ 751, identifierade vi tre typer av lögner: 1) dölja uppgifter (t.ex., en bokstav är dold) ; (2) fantom uppgifter (t.ex., agenten hävdar att ha en bokstav, som är obefintlig och inte kan produceras av lögnaktig agent); 3) lockbete uppgifter (t.ex., agenten hävdar att ha en bokstav, som är obefintlig men kan tillverkas på begäran om det behövs). Eftersom vissa avtal kan kräva skriftväxling, kan en fantom lögn avslöjas, medan en lockbete lögn (och naturligtvis en dold lögn) inte kan. Således är en fantom lögn under vissa förhandlingsmekanismer "inte säker". Olika domäner skiljer sig åt när det gäller hur lätt eller svårt det är att generera lockbete uppgifter. I detta avsnitt ger vi en karakterisering av förhållandet mellan olika typer av lögner, domänattribut och transaktionstyper. Det finns tre typer av lögner i TOD, och vi har övervägt tre domänattribut (subadditionalitet, konkavitet, modularitet) och tre klasser av optimala förhandlingsmekanismer, baserade på ren, all-eller-ingenting, och blandade affärer. Den resulterande matrisen tre gånger tre gånger tre representeras i bild. 5................................................................ Dess notation beskrivs nedan. Betrakta posten under subadditive, allt-eller-ingenting deal, lockbete lögn (vi ska hänvisa till detta som post [a, j, z] ). Inträdet L på den positionen innebär att för varje optimal förhandlingsmekanism som bygger på allt-eller-ingenting-avtal, det finns en subadditiv domän och ett möte sådan att minst en agent har incitament att ligga med en lockbete lögn (L innebär lögn kan vara fördelaktigt). Ingången T i position [b, k. z] innebär att för varje konkava domän och varje möte inom detta område, under någon optimal förhandlingsmekanism baserad på blandade avtal, agenter inte har ett incitament att ljuga med lockbete lögner (T innebär att berätta sanningen är alltid fördelaktigt). Posterna i tabellen markerade T/P (t.ex. [a,j, y] ) hänvisar till lögner som inte är fördelaktiga eftersom de alltid kan upptäckas (i varje möte inom domänen) ; om agenten talar sanning, beror det på att han är rädd för det straff som kommer att tas ut om hans lögn upptäcks. Således kan T/P omvandlas till T om den optimala förhandlingsmekanismen innehåller en tillräckligt hög straff för upptäckta lögner. I tabellen finns det ett samband mellan celler. Det faktum att posten [a,_j,x] är T innebär att posten [b.j, x] också kommer att vara T (detta betecknas av /* singelaxeln pilen i den första cellen, och,7 pilen går in i T i cellen [ b,j, x] ). På liknande sätt [b, j, x 1 är T innebär att posten [c,j. x 1 kommer att vara T (och är också betecknad med pilar). Det beror på att modulära domäner är konkava. och konkava domäner är subadditiva; om det inte finns något incitament att ligga ens i en subadditiv domän, kommer det säkert inte att finnas något incitament att ligga i konkava eller modulära domäner (som är subklasser av subadditiva domäner). På samma sätt, I, posten i [u, i. x 1 innebär att [b, i, x] också kommer att ha en L-post: om en fördelaktig lögn kan hittas i en modulär domän, då kan det säkert hittas i en konkava domän (en superuppsättning). Dessa nedåt påverkan av L är också markerade i tabellen. med J pilar. Det finns också ett samband mellan vissa tabellposter med samma domänattribut (dessa relationer betecknas med dubbla axelpilar som +). Till exempel, om det inte finns något incitament att ljuga i allmänna blandade erbjudanden, det finns inget incitament att ligga i all-eller-ingenting erbjudanden (som är en delmängd). T i cell lb, k, z] innebär alltså T i cell [b,j,z] (det innebär också [b,k,y], vilket i sin tur innebär [b, j, y 1,.). För att fylla i tabellen behöver vi därför bara visa ett litet antal "fasta punkter", vilket i sin tur innebär alla andra tabellposter. De fasta punkter som behöver visas är numrerade i tabellen från I till 8. Vi demonstrerar värdena för dessa 8 celler, och presenterar några andra teorem som gör allmänna uttalanden om optimala förhandlingsmekanismer. G. Zlotkin, De fyra incitament kompatibla fasta punkter bestäms av teorem nedan. Teorem 20 (punkt 1). För varje möte i u ho-agent subaddit~ve TOD, och varje optimal förhandlingsmekanism över allt-eller-ingenting erbjudanden, varje "dold" lögn är inte fördelaktigt. Eftersom en allt-eller-ingenting-affär alltid är ett kandidatavtal kan förhandlingsmekanismen godtyckligt välja det. Detta är anledningen till att L i [a, k, z] är underförstått av L i [a, j, z]. Om det finns ett möte där en av agenterna har ett incitament att ljuga när förhandlingarna är över allt-eller-ingenting-avtal, då i samma möte samma agenter har samma incitament att ljuga när man förhandlar om allmänna blandade avtal: avtalet kan alltid vara en allt-eller-ingenting-affär. En annan konsekvens är följande teorem. På grund av teorem ovan, är det tydligt att för konkava domäner, agenter inte kan dra nytta av genom att ljuga när allt-eller-ingenting affärer är i bruk-dvs., alla optimala förhandlingsförfaranden över allt-eller-ingenting-avtal är incitament kompatibla. Detta gäller även modulära domäner (ett delfall). Detta kan ses i tabellen, där hela raden allt-eller-ingenting är märkt T för modulära och konkava domäner. Dessutom, i en subadditiv domän där lockbete uppgifter inte kan genereras, ett optimalt förhandlingsförfarande över allt-eller-ingenting handlar om en straffmekanism för upptäckta lögner är incitament kompatibel (detta visades, i en annan form, i [ 751). Detta kan ses i tabellen, där raden "allt" eller "ingenting" är märkt med T och T/P (utom locktångskolonnen). (Fyll i punkt 4)............................................................................................................. För varje möte i en tvåagent modulär TOD, och varje optimal förhandlingsmekanism över rena affärer, varje "decoy" lögn är inte välgörande.  Teorem 25 Icke-incitament kompatibla, jixed punkter För ett exempel på en fördelaktig fantom ligger i en konkava domän med hjälp av en förhandlingsmekanism över rena erbjudanden, överväga följande exempel i brevmen domän begränsad till grafer som har en träd topologi (denna domän är konkava, på grund av Theorem 6) : Exempel på en fantom bokstav. Betrakta grafen som ges till vänster om Fig. 6 (längden, och därmed kostnaden, av varje kant är skriven bredvid den). Postkontoret är roten till trädet; både agenterna Ai och A2 måste leverera bokstäver till noder a och 0. Varje agent har en 0,5 chans att leverera bokstäverna till (I (Utility = 2) och en 0,5 chans att leverera bokstäverna till b (Utility = 4). Den förväntade nyttan för båda är 3. Vad händer när AI skapar en fantom bokstav, och berättar A2 att han har en annan bokstav att leverera till nod c? Se höger sida av Bild. 6............................................................. Kostnaden för Al att leverera sina brev plus fantombrevet är nu 12. Det skulle inte vara individuellt rationellt för A2 att besöka c; A1 kommer alltså att behöva besöka c, och han kunde leverera AZ'S brev till b på sin väg. Så de kommer överens om en affär där A 1 levererar bokstäverna till b och c (med uppenbar nytta av 4, och verklig nytta av 4). Därför har Als verktyg stigit från 3 till 4 genom att skapa detta fantombrev. Denna lögn är också en "säker" lögn, eftersom A2 inte kan kontrollera om fantombrevet faktiskt levererades. För ett exempel på ett fördelaktigt lockbete ligger i en subadditiv domän (t.ex. postmen domän med en obegränsad graf topologi) med hjälp av en förhandlingsmekanism över allor-ingenting erbjudanden, överväga följande exempel. Exempel. Låt grafen vara som i bild. 7............................................................ Varje kant mellan noderna har kostat mig. Agent Al måste leverera bokstäver till noder d. e, f och g, med en total kostnad på 6. Agent A2 måste leverera bokstäver till noder b och c, med en total kostnad på 4. Om Al berättar sanningen, kommer båda verktygen att vara 1.5 (Al kommer att göra hela cykeln med sannolikhet &). Efter Al ligger med productible lockbete brev till node h, hans uppenbara kostnad är fortfarande 6. Leverans av hela uppsättningen bokstäver, nu (tydligen) kostar dock 9. De kommer att enas om affären som ger båda agenterna synbar nytta av 0,5. Agent A2 kommer att göra hela leveransen, inklusive lockbete bokstaven, med sannolikhet 6, i själva verket få nytta av 0,5. Agent Al, dock, kommer helt enkelt att göra cykeln (dvs. utan lockbete bokstaven), med sannolikhet g, att få en verklig nytta av 1,72. Att ljuga är alltså till nytta för Al: att tala sanning ger honom en verklig nytta på 1,5, medan lögn ger honom en verklig nytta på 1,72. Exemplet ovan är ett exempel på ett mer allmänt fall. Det visar sig att om en agent vet förhållandet mellan hans och hans motståndares totala kostnader i en allt-eller-ingenting förhandling, är det möjligt för honom att på ett tillförlitligt sätt generera en fördelaktig "default" lögn som består av lockbete uppgifter. I en subadditiv domän, som postmen domän, kan han generera extra lockbete uppgifter "längs vägen" (dvs. det ökar inte hans fristående kostnad), men som förbättrar sin position i det slutliga avtalet. Detta kan endast göras av A1 när kostnaden för Ti är större än kostnaden för T2. Exemplet ovan är ett exempel på denna situation. Det viktiga resultatet här är att lögnen kan genereras på ett tillförlitligt sätt utan att ha fullständig information om den andra agentens uppgifter. För att demonstrera fasta punkter 7 och 8 tar vi med oss två exempel från postmendomänen som har som topologi en stjärnas; detta är en modulär TOD, och representeras i Bild. 8............................................................... Postkontoret ligger i mitten av stjärnan, och längden på linjerna representerar avstånden från postkontoret. Betrakta det vänstra exemplet i bild. 8............................................................... Båda agenterna måste leverera bokstäver till noder b (på ett avstånd av 1) och e (på ett avstånd av 2). Observera att c(T,) = c(T2) = c(Tl U T2) = 6. Om båda agenterna talar sanning kommer förhandlingsmekanismen godtyckligt skicka en till nod b och en till nod e. Om agent A1 döljer sitt brev till nod b, då den enda rena affären som maximerar produkten av agenternas verktyg är den som skickar agent A1 till nod b (!) Agent Al drar nytta av sin lögn. Underrättelsetjänsten 86 (1996) 195-244 (AI,A~) Bild 8............................................................... Slar topologier för brevbärare leverans. Tänk på det rätta exemplet i bild. 8............................................................... Agent Ai måste leverera en uppsättning bokstäver som innehåller de till noder a, c, d, e. och f. Agent A2 måste leverera en uppsättning bokstäver som innehåller de till noder a, b. c. d. och e. Observera att c( Tl) = c(T2) = 10, och c(Tl UT2) = I?. Om Al döljer sitt brev till nod a, då låt r; vara hans uppenbara uppsättning uppgifter (utan nod a). Observera att, (r;) = 8, och c(T; i_l T?) = 12. Hur långt är det kvar tills vi har kommit? Använda någon PMM, under antagandet att Als sanna uppsättning uppgifter är T;, de kan komma överens om en blandad affär (X, Y) : p sådan att X = {a,f}, Y = {b,c,d,e}, och p = i (kalla denna affär a*). Låt UT stå för nyttan av AI från S*. och cl; stå för AZ's verktyg från samma affär. Verktygskl: = U; = 3. Men Als verkliga verktyg är IO -$4 -$ IO = 4.5 vilket är större än 4, det verktyg han skulle ha fått om han hade berättat sanningen. Den allt-eller-ingenting affären är inte fördelaktigt för Al eftersom agenterna skulle komma överens om sannolikheten p = 6, vilket skulle ge agent Al en verklig nytta av 10-h 12-62 = 32 < 4. Men den förväntade utbetalningen för den ljugande agenten är 4i, dvs. fortfarande över 4, även när förhandlingsmekanismen ibland väljer allt-eller-ingenting-affären, så den ljugande agenten gynnar. För att ge agenter en lämplig interaktionsmiljö där de kan samordna, kan det vara önskvärt att upprätta protokoll på hög nivå som motiverar socialt fördelaktigt (och individuellt fördelaktigt) beteende. Spelteori kan ge verktyg som är lämpliga för utformningen av dessa protokoll. Några av de attribut som designers kanske vill se i interaktionsmiljöer är effektivitet. stabilitet och enkelhet. Utformningen av lämpliga protokoll är nära ansluten till den domän där agenter kommer att agera. Vissa protokoll kan vara lämpliga för en domän och olämpliga för en annan. I nästan alla fall är det viktigt att tillhandahålla protokoll som kan hantera ofullständig information från smittämnen, samtidigt som stabiliteten i den övergripande mekanismen upprätthålls. I den här artikeln har vi presenterat en allmän domänteori att använda för att analysera förhandlingsprotokoll. Vi har karakteriserat uppgiftsorienterade domäner (TODs), som täcker en viktig uppsättning av multiagentiska interaktioner. G. Uotkin, Vi har presenterat flera exempel på TOD, och undersökt tre attribut som dessa domäner kan uppvisa, nämligen subadditionalitet, konkavitet och modularitet. Vi har sedan räknat upp förhållandet mellan dealtyper, domänattribut och typer av bedrägeri, med fokus på om en agent i en TOD med en given attribut och dealtyp är motiverad att alltid berätta sanningen. I synnerhet har vi visat att i konkava TOD finns det ingen fördel med att en agent ljuger när allt-eller-ingenting-avtal används. I en allmän subadditiv domän, dock, när agenter kan generera lockbete uppgifter, även allor-ingenting affärer är inte tillräckligt för att skapa stabilitet (känslor lögner). Dessutom visade vi att det i subadditiva domäner ofta finns nyttiga lockbete lögner som inte kräver fullständig information om den andra agentens mål.
Merparten av forskningen utvecklar protokoll och strategier för agenter som omfördelar uppgifter sinsemellan (t.ex. Om det inte finns några uppgifter som tyder på att det finns en risk för att det finns en risk för att det uppstår en allvarlig risk för en allvarlig störning, ska den behöriga myndigheten i den medlemsstat där den behöriga myndigheten har sitt säte underrätta den behöriga myndigheten i den medlemsstat där den behöriga myndigheten har sitt säte om detta.
Mechanism design for automated negotiation, and its application to task oriented domains
{'venue': 'ARTIFICIAL INTELLIGENCE', 'journal': None, 'mag_field_of_study': ['Computer Science']}