Introducere în licitatii combinatorie

Licitaţii combinatorii licitatii sunt cele în care ofertanţii pot plasa oferte pe combinations de elemente, numite pachete'',''mai degrabă decât doar elemente individuale. Studiul de licitaţii combinatorii este în mod inerent interdisciplinare. Licitaţii combinatoriale sunt în cadrul licitaţiilor primul rând, un subiect economişti au studiat extensiv 1. Licitarea Pachetul aduce in cercetarea operationala, în special tehnicile de optimizare de la combinatorii şi programării matematice. În cele din urmă, informatica este preocupat cu expresivitate de limbi diferite de licitare, precum şi aspectele algoritmice ale problemei combinatorial. Studiul de licitaţii combinatorii astfel se afla la intersectia de economie, operaţiunile de cercetare, şi informatică. În această carte, ne uităm la combinatorial licitaţii din toate cele trei perspective. Întradevăr, contribuţia noastră este de a face acest lucru întrun mod integrat şi cuprinzător. Provocarea iniţială în cercetare interdisciplinară este definirea unui limbaj comun. Am făcut un efort pentru a folosi terminologia coerentă în întreaga carte, cu condiţiile cele mai comune definite în glosar.

Există numeroase exemple de licitaţii combinatorii în practică. Aşa cum este tipic pentru multe domenii, practica teoria precede. Licitaţii combinatorii simplă au fost folosite de mai multe decenii, de exemplu licitatii imobiliare,. O procedură comună este să scoată la licitaţie elemente individuale, şi apoi, la sfârşitul anului, să accepte ofertele de pachete de produse. În cazul în care o sumă licitată pachet depăşeşte suma de sume licitate individuale pentru elementele din pachet, atunci elementele sunt vândute ca un pachet. În această carte vom lua în considerare o varietate de mult mai general licitaţii combinatorii, dar ingredientulcheie este aceeaşi ca în acest caz simplu: fiecare ofertant poate depune oferte pe pachete de produse.

Recent, o varietate de industrii au angajat licitaţii combinatorii. De exemplu, acestea au fost utilizate pentru transport camion, rute de autobuz, şi industriale de achiziţii publice, şi au fost propuse pentru sosirea la aeroport şi a sloturilor de plecare, precum şi pentru alocating spectrului de frecvenţe radio pentru servicii de comunicaţii fără fir. Atât Statele Unite ale Americii şi Nigeria au desfăşurat licitaţii combinatorii pentru spectrul de frecvenţe radio. În fiecare caz, motivaţia convingatoare pentru utilizarea unei licitaţii combinatoriale este prezenţa de complementaritate între elementele care diferă în funcţie de ofertanţi. De exemplu, un camionagiu cost cu o schimbare de manipulare transporturilor întro singură bandă depinde de incarcatura sale în alte benzi. În mod similar, un telefon mobil operatorul poate licenţe de valoare în cele două oraşe învecinate mai mult decât suma valorilor licenţei individuale, deoarece clienţii operatorului valoarea roaming între oraşe.

I.1 Teoria de bază licitaţiilor

Teoria licitaţiilor este printre subiectele cele mai influente şi pe scară largă a studiat în economie în ultimii patruzeci de ani. Licitatii cere şi răspundeţi la întrebările cele mai fundamentale în economie: cine ar trebui sa mărfurilor şi la ce preţuri? Pentru a răspunde la aceste întrebări, licitatii sta la baza microa pieţelor. Întradevăr, multe moderne de marsupermarketuri sunt organizate ca licitaţii.

Pentru a înţelege rolul de licitaţii combinatorii, este util să pas înapoi şi să se gândească licitaţii, în general. Unele tipuri de licitaţie sunt familiare, cum ar fi licitaţie crescătorlicitată în engleză folosite în cadrul licitaţiilor online de consum multe, sau primulpretoferta sigilate licitatie utilizate în mai multe achiziţii publice. Mai fundamental, licitaţiile sunt distingediferenţiate, nu numai de regulile de licitatie, cum ar fi crescător comparativ cu oferta în plic închis, ci de mediul de licitaţie. Aceste licitaţii combinatorii poate fi studiat întro gamă largă de medii de licitatie. Caracteristici importante, inclusiv numerele de vânzători şi cumpărători, numărul de articole să fie tranzacţionate, preferinţele părţilor, precum şi forma de participanţilor informaţii private au cu privire la preferinţele stabili toate mediului licitaţie.

Mediul de referinţă este modelul valoarea privat, introduse de Vickrey (1961), care Ausubel şi Milgrom (capitolul 1 din prezentul volum) discuta în detaliu. În modelul valoarea privat, fiecare ofertant are o valoare pentru fiecare pachet de elemente, şi aceste valori nu depind de informaţiile private ale celorlalţi ofertanţi. Fiecare ofertant cunoaşte valorile lui, dar nu şi valorile celorlalţi ofertanţi. De hârtie seminal Vickrey lui, menţionate în său 1996 Premiul Nobel în economie, şia prezentat modelul independent valoarea privat, a demonstrat de licitare comportament echilibru în cadrul unei licitaţii primulpreţ, şi apoi a arătat că licitarea veridice ar putea fi indusă ca o strategie dominantă de a modificarea preţurilor regulă: fiecare ofertant să plătească costul de oportunitate sociale din câştigurile sale, mai degrabă decât suma licitată lui. În cele din urmă, el a arătat întrun exemplu ce sar fi dovedit mai târziu genoral ca teorema venituri de echivalenţă: mecanisme diferite licitatie care duce la aceeaşi alocare a mărfurilor randament acelaşi venit către vânzător.

Astfel, atunci când licitarea un singur element a ofertanţilor n, ale căror payoffs sunt liniare în evaluarea ofertant a elementului şi de bani (u i ¼ V I p, în cazul în care U este ofertant de utilitate I, V I este i de valoarea obiectului, iar p este preţul plătit pentru element), şi în cazul în care fiecare valoare este elaborate independent de distribuţie a probabilităţii aceeaşi, atât în prima licitaţie de atribuirepreţ şi al doilea preţ element pentru a ofertantului cu cea mai mare valoare şi randament vânzătorului acelaşi venit de aşteptat.

Cele mai multe dintre capitole din această carte utilizării modelului Vickrey lui valoare privat, şi de multe face uz de regula de stabilire a preţurilor Vickrey, cel puţin ca un punct de referinţă pentru compararea cu mecanisme alternative.

Wilson (1969) a avut teoria licitaţie întro direcţie nouă. El a introdus modelul comun licitaţie valoare, în care elementele au aceeasi valoare a tuturor ofertanţilor, dar această valoare este incert şi depinde de informaţiile private ale tuturor ofertanţilor. El a derivat prima analiza de licitare echilibru cu valori comune, demonstrând importanţa de oferta o condiţionat pe informaţii negative câştigătoare presupune, şi evitând astfel ceea ce ar fi numit mai târziu * câştigătorul de blestemul tendinţa de ofertanţi, care nu inteleg ca câştigător este veşti proaste despre o estimare de valoare, să plătească mai mult decât elementul este în valoare.

Milgrom acordate documentele începutul lui Wilson în mai multe moduri. Cel mai important, el introduse un model de licitaţie, cu atât valoarea privat şi elemente comune valoarea. Modelul valorii privată a Vickrey şi modelul valorii comune a Wilson reprezintă două extreme de cazuri. Aceste modele sunt extrem de utile în derivă rezultate teoretice solide, dar cele mai multe medii de practic licitatie au elemente atât private cât şi de valoarea comună. Milgrom (1981) a arătat importanţa proprietăţii monotone raportului risc în obţinerea de rezultate întrun model hibrid realist. 2 În special, monotone proprietatea raportului risc, împreună cu ipoteza lui Wilson de independenţă condiţionată, înseamnă că 1) ofertanţii utilizeze strategii de monotone de licitare, şi 2) faptul că un monotone strategia care îndeplinesc condiţia de ordinul întâi constituie un echilibru.

Modelul Milgrom a condus la modelul afiliate valorile (Milgrom şi Weber 1982), în care un ofertant valoarea lui depinde direct de informaţiile private ale tuturor ofertanţilor. Stare critică aici, în strânsă legătură cu proprietatea monoton raportului risc în Milgrom 1981, este faptul că semnalele ofertanţilor, de obicei, estimările de valoare, sunt afiliate variabile aleatoare. Acest lucru se ridică la condiţia plauzibil că, dacă un ofertant are un semnal mare de valoare, este mai probabil ca semnalele de ceilalţi ofertanţi sunt ridicate. Lucrarea arata ca rezultat Vickrey veniturile echivalenţa nu mai are atunci când vom introduce un element de valoare comună. În special, veniturile din standard, ASCTION formate diferite şi pot fi clasificate. Formate, cum ar fi licitaţiile ascendentă, în care preţul este legat de mai multe informaţii private afiliate, randament venituri mai mari.

Munca mai devreme de Vickrey, Wilson, şi Milgrom fost în mare măsură axat pe o analiză equilibrium şi compararea de formate standard de licitatie. Myerson condus de dezvoltare a teoriei mecanismului de design, care permite cercetătorului de a caracteriza rezultatele echilibrul de toate mecanismele de licitaţie, precum şi identificarea mecanismelor optime * acele mecanisme care maximizează unele obiective, cum ar fi veniturile vânzător. Prima lui APcarea a fost la licitaţii. Myerson (1981) a determinatmaximizarea veniturilor ASCTION cu riscneutru ofertanţi şi informaţii private independente. A dovedit, de asemenea, o teoremă de venituri generale de echivalenţă care spune că veniturile depind în mod fundamental privind modul în care li se atribuie elemente * ¥ oricare două formate de licitatie care conduc la acelaşi atribuirea elementelor randament veniturile acelaşi vânzător.

Truc în analiza Myerson a fost recunoscând că orice licitaţie poate fi reprezentat ca un mecanism de directe, în care ofertanţii raporta simultan lor privată informaţii şi apoi mecanismul stabileşte sarcinile şi plăţile efectuate pe baza vector de rapoarte. Pentru orice echilibru de niciun joc licitaţie, există un mecanism echivalent direct în care ofertanţii raport veridic tipuri şi sunt de acord să participe. Prin urmare, fără a pierde din generalitate, putem uita la mecanismele de stimulare compatibil şi individual raportuluinal pentru a înţelege proprietăţile toate jocurile licitatie. Compatibilitatea de stimulare are în vedere faptul că ofertanţii au informaţii private despre valorile lor; individuUAL raţionalitate respectă decizia participarea voluntară ofertanţi. Această idee cheie este cunoscut sub numele de principiul revelaţia (Myerson 1979).

Myerson şi Satterthwaite (1983) folosesc aceasta tehnica pentru a dovedi generale Impossitatea de negociere eficientă atunci când nu este cunoscut faptul că profitul din comerţul există, adică, atunci când nu este sigur că un acord reciproc avantajos este posibil. Această imposibilitate aceeaşi extinde şi la licitaţii, în care atât vânzători şi cumpărători deţin informaţii private, deşi eficienţa devine posibilă atunci când comercianţii proprii în comun elementele (Cramton, Gibbons, şi Klemperer 1987). De asemenea, în cazul în care rolurile de cumpărător şi vânzător nu sunt fixe exante, dar comercianţii pot lua fie pe rol, în funcţie de preţ, atunci există mecanisme eficiente (Wilson 1993).

Aceste lucrări timpurii a dus la dezvoltarea rapidă a teoriei licitaţie în anii 1980 şi 1990. În plus, literaturi mari empirice şi experimentale au răsărit din teoria. O serie de articole şi cărţi rezuma acest lucru (de exemplu, McAfee şi McMillan 1987; Kagel şi Roth 1995; Klemperer 2000, 2004; Krishna 2002 şi Milgrom 2004).

I.2 Combinatorie licitatii

O deficienţă de cele mai multe dintre lucrările menţionate mai sus (Milgrom 2004 este o excepţie) este incapacitatea de a recunoaşte că, în multe medii de îngrijire licitaţie ofertanţii în moduri complexe despre pachetele de obiectele pe care le castiga. Avantajul de licitaţii combinatorii (AC) este faptul că ofertantul poate exprima mai deplin preferinţele sale. Acest lucru este deosebit de important atunci când elementele sunt completează. Elementele sunt atunci când completează un set de elemente are utilitate mai mare decât suma de utilitati pentru elemente individuale (de exemplu, o pereche de pantofi valorează mai mult decât valoarea unui pantof lăsat singur plus valoarea unui pantof drept singur). Proiectantul licitatie derivă, de asemenea, valoarea de la AC. Permiterea mai multi ofertanti pe deplin săşi exprime preferinţele de multe ori duce la îmbunătăţirea eficienţei economice (alocarea un produs pentru cei care au cea mai mare valoare) şi cu venituri mai mare licitatie.

Cu toate acestea, alături de avantajele lor, AC ridica o serie de întrebări şi provocări. Această carte este dedicată discutării aceste întrebări, precum şi progresele considerabile realizate în răspunsul lor.

I.3 Tipuri de licitatii combinatorie

Cartea începe în partea I, cu o descriere şi o analiză a diferitelor combinatoriale ASCTION mecanisme.

Licitatia mai faimos combinatorie este generalizarea combinatoriale a licitaţiei Vickrey deja menţionat, VickreyClarkeGroves (VCG) mecanism. Ausubel şi Milgrom (capitolul 1) exploreze întrebarea de ce licitatie Vickrey, cu proprietăţile sale atragatoare teoretic, este văzut atât de puţin în practică. Întro licitatie VCG (numit, de asemenea, o licitatie Vickrey), ofertanţii raport evaluările lor pentru toate pachetele, elementele sunt alocate în mod eficient pentru a maximiza valoarea totală. Fiecare câştigător plăteşte costul de oportunitate al lui castigate: valoarea elementare care ar fi obţinute prin atribuirea elemente ofertantului în funcţie de utilizarea lor lângă cele mai bune în rândul celorlalţi ofertanţi. În acest fel, un ofertant câştigător atinge un profit egal cu contribuţia sa la valoarea totală elementare, şi aceasta este o strategie dominantă pentru ofertantul să prezinte un raport sincer valorile sale. Realizarea eficienţa întradevărdominant strategii este remarcabil. Cu toate acestea, există deficienţe grave. Cel mai important, ofertanţilor li se cere săşi exprime valorile pentru toate ambalajele, fără ajutorul de orice informaţii despre preţuri. De asemenea, atunci când mărfurile nu sunt substitute, veniturile vânzătorul poate fi prea mică, 3 adăugarea de ofertanţii sau creşterea valorilor ofertantul poate reduce veniturile vânzătorului: Capitolul 1 discută, de asemenea, alte limitări de licitaţie Vickrey.

În capitolul 2, Parkes analizează iterativ licitaţii combinatorii. O motivaţie majoră pentru un proces iterativ este de a ajuta ofertanţi şi exprime preferinţele lor prin furnizarea de proprovizorii de stabilire a preţurilor şi de informaţii de alocare. Aceste informaţii ajută ofertanţi şi concentreze eforturile lor de evaluare cu privire la opţiunile care sunt cele mai relevante.

În capitolul 3, Ausubel şi Milgrom ia în considerare licitatie proxy ascendentă (Ausubel şi Milgrom 2002) ca o alternativă la licitatie Vickrey. Fiecare ofertant susţine valoroase ation informaţii la un agent proxy. Agenţii proxy licitată iterativ, licitare pe ambalaj cele mai profitabile, ori de câte ori agentul proxy nu este un câştigător provizoriu. Licitaţie se termină atunci când nici un agent proxy care nu este un castigator provizoriu are o ofertă profitabilă. Licitaţia proxy crescător permite pentru ofertanţii să aibă constrângeri bugetare. În absenţa unor constrângeri bugetare, şi atunci când mărfurile sunt substitute pentru toţi ofertanţii, licitatie proxy crescător dă acelaşi rezultat ca la licitaţie Vickrey. Mai multe seraliat, licitatie proxy crescător găseşte un punct de ofertantoptim în bază cu privire la preferinţele raportate. Mai mult decât atât, toate punctele optime din punctul de ofertant de bază sunt Nash equilibRIA în joc licitaţie, dacă vom presupune informaţii complete despre valorile (fiecare ofertant cunoaşte valorile celorlalţi ofertanţi). Licitaţia proxy crescător multe adrese de dezavantaje ale licitaţiei Vickrey în medii cu unele complemente.

În capitolul 4, Cramton studii licitatie simultană crescător (ASA). ASA nu este o licitaţie combinatorica, pentru că sumele licitate întrun ASA sunt plasate pentru elemente individuale, mai degrabă decât de pachete de produse. Cu toate acestea, ASA sa dovedit a fi o metoda foarte eficienta de licitaţie mai multe elemente legate de (a se vedea Cramton 1998, 2002; Milgrom 2004).

Vânzarea simultană şi sumele licitate crescător permite descoperirea preţ, care ajuta la construirea ofertanti de pachete de dorit de articole. ASA rămâne un reper util pentru compararea cu adevărat licitaţii combinatorii.

În capitolul 5, Ausubel, Cramton, Milgrom şi propune licitatie ceasulproxy ca un design practic combinatorie. O licitaţie fază ceas este urmată de o rundă de cel mai bun proxyşifinala. Abordarea combina descoperire preţul simple şi transparente de licitaţie ceas cu eficienta a licitaţiei proxy. De stabilire a preţurilor liniare se menţine cât mai mult posibil, dar apoi este abandonat în etapa a proxy pentru a îmbunătăţi eficienţa şi de a spori veniturile vânzător. Abordare are multe avantaje faţă de licitatie simultaneprecedenţi crescător. În special, licitatie ceasulproxy nu are nici o expunere proLEM, elimina stimulente pentru reducerea cererii, şi previne majoritatea strategiilor coluziv de licitare. Fără a rundă cel mai bun proxyşifinala, autorii prezinta o licitatie iterativ combinatorii, care pot fi puse în aplicare ca o licitaţie ceas simplu, evitânduse toate problemele de calcul complexitatea întrun proces de descoperire cu preţ extrem de utile (Ausubel şi Cramton 2004). Mai mult de două duzini de mare miza licitaţii în mai multe ţări şi mai multe industrii au folosit acest format de licitatie recent.

Capitolul 6 discută o combinatorii PAUZĂ procedura de licitaţie numită, propus de Frank Kelly şi Richard Steinberg, care scuteşte adjudecătorului de a se confrunta determinarea''câştigătorul problemă,''discutat mai jos, o problema de calcul dificil de rezolvat. Sub PAUSE, sarcina de a evalua o sumă licitată combinatorii este transferată la ofertant face ofertei; adjudecătorului nevoie decât să confirme termenului de valabilitate a ofertei, o computationally problemă maleabil. În consecinţă, deşi PAUZA permise toate ofertele combinatorial, procedura este atât de calcul maleabil pentru adjudecător şi transparent la ofertanţi. În capitolul lor, Land, Powell, şi Steinberg se concentreze specificaţiile din punct de vedere cu privire la comportamentul ofertant în conformitate cu PAUZĂ.

I.4 Licitarea şi eficienţă

După cum sa menţionat mai sus, licitaţii combinatorii da naştere la o serie de întrebări interesante şi provocări. Pentru a începe cu, se pune problema a ceea ce ar trebui să fie licitarea limbajul. Opţiuni diferite variază în expresivitate şi în simplitate. O sumă licitată la o licitatie este o expresie a preferinţei ofertantului pentru rezultate diferite. Calea cea mai directă de a captura o astfel de dorinţă este de a avea un ofertant da o valoare monetară pentru fiecare alocare posiBLE. Aceasta permite săşi exprime toate preferinţele posibile, dar nu este simplu. Având în vedere ofertanţii n şi elementele m, este nevoie de un ofertant să prezinte o ofertă de dimensiune n m. Dacă noi, casume nu externalităţi, astfel încât fiecare ofertant ii pasa doar despre elementele el însuşi primeşte, complexitatea scade la 2 m, care este încă imposibil pentru toţi, dar mici m.

Partea a IIa carte se adresează atât limbi de licitare şi întrebări de eficienţă. ASCTION teorie presupune, în general, un număr fix de ofertanţi cu fiecare ofertant care acţionează în mod independent în conformitate cu normele de licitatie. Un simplu abatere de la acest model este pentru un singur ofertant de a acţiona ca ofertanţi multiple. Licitarea astfel de sub pseudonim, este ject subcapitolul 7. Yokoo arată că licitaţia Vickrey nu este imun la această problemă, cu excepţia cazului în submodularity ofertant condiţie este îndeplinită. Şi întradevăr, toate licitatiile eficiente suferă de această problemă. Este, uneori, profitabil pentru un ofertant la licitaţie ca mai multe licitatăders, mai degrabă decât una, şi aceasta subminează eficienţa.

În capitolul 8, Bikhchandani şi Ostroy examineze să facă legătura între licitaţii eficient pentru multe elemente şi teoria dualitate. Vickrey licitatie poate fi considerat ca un echilibru de tarifare eficient, ceea ce corespunde la soluţia optimă a unei anumite liniar de programare (LP) problemă şi dualul său. O cumpărători''sunt substitute''condiţie este necesară şi suficientă pentru echilibrul de stabilire a preţurilor pentru a obţine rezultatul Vickrey. Astfel, atunci când cumpărătorii sunt substitute, un echilibru de tarifare eficientă poate fi obţinută cu orice algoritm LP. Algoritmul simplex poate fi gândit ca o abordare statică pentru a determina rezultatul Vickrey. Alternativ, primar dualalgoritm poate fi considerat ca o metodă de descentralizată şi dinamică de determinare a echilibrului de stabilire a preţurilor, astfel cum în licitaţie proxy crescător din capitolul 3.

În capitolul 9, Nisan analizează o varietate de limbi de licitare şi proprietăţile lor. De exemplu, vedem că acolo SAU (''aditiv sau'') licitate, care permit ofertantul să facă nonexclusive oferă pe fascicule, poate captura toate, şi numai, a aditivului superevaluări. În contrast, XOR (exclusiv''sau'') licitate, care permit ofertantul să facă oferte exclusive pe fascicule, poate captura toate evaluările, deşi ele pot solicita o expresie exponenţial mai mare decât cea sau sumele licitate. Cu toate acestea, solicitând un agent de a dezvălui un plin valoroase ation funcţia de multe ori nu este necesar, deoarece multe părţi din ea pot fi irelevante pentru calculul de alocare.

În capitolul 10, Sandholm şi Boutilier uităm la modul în care funcţia de evaluare a agenţilor poate fi obţină bucată cu bucată, după cum este necesar de către adjudecător. Una dintre întrebările ce formă există interogări poate lua. Sandholm şi ia în considerare mai multe Boutilier primar forme, inclusiv întrebări despre valorile absolute pachet, interogări cu privire la diferenţele între valorile pachet doi, o ordonare simplă pe valori pachet, şi multe altele. Printre rezultatele experimentale care arată este faptul că, în practică, doar o mică frac în aplicare a preferinţelor trebuie să fie dezvăluit. Printre rezultatele teoretice prezentate sunt unele clase naturale de evaluare în cazul în care preferinţele poate fi determinat cu un număr polinom de interogări, chiar şi în cel mai rău caz, faptul că, chiar dacă preferinţele real doar se încadrează aproximativ în aceste clase, o apropiere pot fi găsite cu un poli numărul de interogări nomial, şi de faptul că nu poate fi superputere exponenţială în intercalarea interogări în agenţi (de exemplu, să decidă ce să ceară un agent bazat pe ceea ce altii au dezvăluit).

În capitolul 11, Segal întreabă câţi biţi de informaţii sunt necesare pentru a calcula o alocare eficientă, indiferent de protocolul utilizat şi fără a ţine seama de problemele de stimulente. Un rezultat prevede ca orice mecanism care este garantat pentru a calcula o alocare eficientă trebuie neapărat descoperi, de asemenea, preţurile de sprijin (deşi acestea va fi, în general, fi nici anonim, nici liniar). Adresele principal Segal întrebarea este cum se poate compromis gradul de comunicare necesare cu excedent economic câştigat. De exemplu, protocolul triviale în care ofertanţii comunică valoarea lor pentru întregul set de mărfuri, care este alocat cel mai mare ofertant (din nou, ignorând problema stimulentelor), garanţii 1 = n al excedentului disponibile (în cazul în care n este numărul de ofertanţi) în timp ce f necesită o singură sumă licitată de la fiecare ofertant. Un mecanism mai elaborate randamentele 1/√_m de excedent disponibile, unde m este numărul de bunuri. Interesant, acest lucru este de asemenea, o limită inferioară pentru orice protocol de funcţionare a căror timp este polinomial în m.

I.5 Complexitatea şi Consideraţii Algorithmic

Odată ce limba de licitare este fix, ramane intrebarea cu privire la modul de alocare a calcula, având în vedere un set de oferte. Aceasta problema, numita problema determinarea câştigătorului (WDP) a primit o atenţie considerabilă în literatura de specialitate, şi este principala preocupare de partea III.

În capitolul 12, Lehmann, Muller, si Sandholm oferi o formulare precisă a gradul problemă şi de a explora proprietăţile sale de bază complexitatea. Problema este aceasta: Având în vedere un set de sumele licitate în cadrul unei licitaţii combinatorica, găsi o alocare de un produs pentru ofertanti, inclusiv posibilitatea ca adjudecătorului păstrează unele elemente, care maximizează adjudecătorului revenue. Problema, care este cel mai natural reprezentat ca un program întreg (IP), este în mod inerent complex. Mai precis, este NPcompletă, în sensul că un algoritm polinomial în timp, care este garantat pentru a calcula alocare optimă este puţin probabil să existe. Chiar mai rău, problema nu este uniform approximable, în sensul următor: aproape sigur, nu există un algoritm polinomial în timp şi o d constantă că, pentru toate intrările, algoritmul produce un raspuns care este de cel puţin 1 = d corect răspuns optim.

Am apoi urmaţi această introducere pentru a sobering WDP cu o veste bună. În primul rând, în capitolul 13, Muller explorează unele constrângeri cu privire la un set de oferte care să garanteze că A ˚ polinomiale timp soluţie nu există. Un astfel de condiţie este pentru matrice constrângere care urmează să fie total unimodular. Un caz special de acest lucru este de bunuri liniară, de exemplu, în cazul în care fiecare este suma licitată pentru unele întinde contigue de timp, pe o maşină la comun, problema poate fi rezolvată în timp patratic. Apoi, în capitolul 14, se uită la Sandholm algoritmi pentru rezolvarea problemei generale. Deşi ştim că, în cel mai rău caz orice algoritm se va desfăşura în timp exponenţială, există reguli de degetul mare pentru căutarea în spaţiul de alocările că, în practică ne permit de a rezolva probleme mari (de exemplu, cu sute de mii de oferte si zeci de mii de articole). Sandholm se concentrează asupra complet HEUristici, cei care să garanteze că o soluţie optimă este găsit, dar nu garantează timpul de execuţie.

Discuţia de WDP în capitolele 12, 13, şi 14 ignoră problemele legate de stimulente. Optimizarea este presupus a fi moştenit de la un mecanism, cum ar fi VCG mecanism, dar fără a rezolvat ceea ce priveşte mecanismul de origine. Aşa cum sa discutat, aceste probleme sunt greu de calcul, şi recunosc, uneori, doar suboptimal soluţiiţiilor. În capitolul 15, Ronen se uita la impactul de optimizare suboptimale astfel de proprietăţi de stimulare a mecanismelor. De exemplu, el arată că cu procedurile suboptimal, mecanismul de VCG nu mai este individual raţionale, şi nici nu este compatibilă stimulent. Cu toate acestea, el prezintă o modificare de VCG care restabileşte individuale raportului nalityşi, întro anumită măsură, compatibilitate de stimulare. Capitol se referă la mai multe alte teme, inclusiv un mecanism nonVCG computational, care este uşor şi stimulente, tive compatibil, a căror eficienţă economică, întrun domeniu restrâns, este mărginită de la 1/√_m mai jos de 1 = m, unde m este numărul de bunuri.

În capitolul final al partea III, capitolul 16, Pekec şi Rothkopf consideră potrivite modalităţi de a reduce sau de a evita dificultăţi de calcul în licitaţii combinatorii.

autorii de revizuire pe scurt a problemelor de calcul în proiectarea licitatie combinatorie, contextul de proiectare licitaţie, inclusiv informaţiile disponibile pentru proiectant şi proprietăţi pe care proiectantul licitaţie trebuie compromis în selectarea formatul şi procedurile de licitaţie. Cea mai mare parte din capitolul lor discuta oportunităţi pentru atenuarea problemelor de calcul, la patru puncte în licitaţie: înainte de depunerea ofertei, la data depunerii ofertei, după depunerea suma licitată, dar înainte de anunţarea unui set tentativă a ofertelor câştigătoare, şi după anunţarea unui set tentativă de a câştiga sume licitate.

I.6 Testare şi punere în aplicare

În partea a IVa, vom ridica intrebarea cum de a testa experimental diverse solutii propuse la WDP, precum şi cele mai bune modalităţi de a testa şi de punerea în aplicare a mecanismelor de la partea I.

În capitolul 17, Hoffman, Menon, van den Heever, Wilson şi ia în considerare cele mai bune modalităţi de punere în aplicare la licitaţie proxy crescător din capitolul 3. Ei consideră trei abordări pentru accelerarea algoritmului. Primul lucru implică înapoi de la alocare eficientă şi începând cu preţurile Vickrey, care oferă o limită inferioară a preţurilor. A doua abordare, scalarea creştere, rezolvă problema cu creşteri mari suma licitată şi apoi susţine sus şi rezolvă problema din nou cu câte redusă până când se obţine precizia dorită. A treia abordare combină ultimele două. Aceste trei abordări fiecare reduce dramatic numărul de iteraţii necesare pentru a determina rezultatul proxy crescător.

În capitolul 18, LeytonBrown şi Shoham prezent combinatorie suita de teste licitaţiilor (CATS). CATS este un pachet software la dispoziţia publicului, care generează o varietate de probleme de determinare câştigător. Mai precis, aceasta pune în aplicare mai multe parametrizate famIlies de distribuţii suma licitată, unele bazate pe lumea reala aplicaţii (cum ar fi reţelele de transport), şi unele pe distribuţiile istorice folosite de catre cercetatori in domeniu.

Scopul CATS este de a servi ca o suita de testare uniformă pentru algoritmi WDP, şi a fost utilizat pe scară largă în această calitate.

În capitolul 19, LeytonBrown, Nudelman, şi Şoham CATS folosi pentru a prezice ori runNing de algoritmi pentru problema determinarea câştigătorului. Dificultatea este că, deoarece problema este NPcompletă, chiar şi în cele mai bune proceduri euristice va avea exponential timp, în unele cazuri. În multe aplicaţii, este important să se cunoască în adVance cât de mult timp un algoritm dat va rula pe un moment dat (de exemplu, o licitaţie pentru producţia de energie are nevoie de mâine pentru a stabili un program de funcţionare de bine în avans de mâine). Autorii descriu modul în care tehnicile de învăţare maşină pot fi folosite pentru a prezice acest timp de funcţionare fiabil, şi care oferă o dată în poziţiasunt cele mai predictive de acest timp de funcţionare. Ca un bonus, ele descriu, de asemenea, o abordare de portFolio la WDP, prin algoritmi mai multe concurente sunt presate în funcţiune, şi pentru fiecare exemplu, algoritmul care este prezis de a efectua cel mai bun este ales.

I.7 Licitatii combinatoriale în practică

In lucrarea lor seminal la licitaţii combinatorica, Rassenti, Smith, şi Bulfin (1982) prezintă o licitaţie sigilatoferta combinatorice pentru alocarea de sloturi de timp aeroport (de exemplu, sloturi pentru decolare şi aterizare) pentru companiile aeriene concurente 4 sloturi de aterizare Chiar dacă sunt incluse. cu sloturi decolare (la fel ca pantofii stânga şi dreapta sunt incluse), necesitatea unei licitaţii combinatorii Rezultă din cele de moduri diferite pe care companiile aeriene pachete valoare de sloturi: unele sunt substitute, unele sunt completează, precum şi evaluările variază în funcţie de companii aeriene. Deşi licitaţii, combinatorii sau altfel, nu au fost încă să fie folosit pentru alocarea pista de rare capacity, congestie la multe aeroporturi majore devine o ce în ce mai dificil proLEM. Administraţia Federală a Aviaţiei este de a evalua acum o abordare licitatie combinatorii pentru New York LaGuardia Airport.

Sectiunea finala a cartii, partea V, consideră că patru cereri importante ale combinatorial licitatii. Capitolul 20 preia tema de licitatii pentru sloturi de timp la aeroport. Ball, Donohue, Hoffman şi oferă sugestii pentru mecanisme de transport în comun de aerTION sisteme, atât pentru a extinde capacitatea şi de a se asigura că actuala capacitate, limitată este utilizat în condiţii de siguranţă şi eficient. Autorii încep prin a oferind o descriere a conservatorlui de aviaţie sistemul american, detalii procedurile actuale de alocare a sloturilor orare de aterizare timp, şi explică modul în care mecanismele de piaţă, de compensare ar putea fi capabil de a rectifica multe din neajunsurile sistemului actual. Acestea includ o prezentare a unora dintre componentele pe care ei cred ca sunt necesare pentru a asigura succesul combinatoriale ASCţiilor în această setare.

În capitolul 21, Caplice şi Sheffi explora modul în licitaţii combinatorii sunt utilizate pentru achiziţionarea de servicii de transport de marfă, cu accent pe acele atribute de transport care fac licitaţii combinatorii deosebit de atractive, precum şi descrie unele dintre elementele unice de licitaţii de transport. Ele prezintă astfel de licitaţii prima din punctul de vedere al adjudecătorului, că este, expeditorul, apoi din punctul de vedere al ofertantului, sau operatorul de transport. Aceasta este urmată de o discuţie a relaţiei dintre naveleexpeditori şi transportatori, precum contractele pe care le guvernează au anumite caracteristici care le diferenţiază întro anumită măsură, de la licitaţii pentru alte aplicaţii iile discutate în altă parte în carte. De fapt, tipuri de oferte de transport sunt utilizate în distinctiv ca industria, astfel încât nu există o întreagă secţiune le discutăm. În acest industry, determinarea problema câştigătorul este cunoscut sub numele de Cesiune Carrier''proLEM,''următorul subiect în capitolul. În cele din urmă, autorii prezinta lecţii de la practica.

În capitolul 22, ne deplasăm din sectorul privat în sectorul public. ca Cantillon Pesendorfer şi explică, pe piata londoneza cu autobuzul rute oferă un exemplu timpuriu de utilizarea unui format de licitaţie combinatorii în domeniul achiziţiilor publice. Autoritatea de responsabilă pentru furnizarea şi achiziţionarea de servicii de transport public în Greater Londra pe suprafaţă în valoare de 900 milioane dolari, a fost Londra regionale de transport (LRT). Autorii prezinta cele patru probleme majore cu care se confruntă LRT. În primul rând, ceea ce set de contracte ar trebui să fie licitat? În al doilea rând, modul în care ar trebui să LRT licitaţie aceste contracte? În al treilea rând, care ar trebui să fie permis să participe? În cele din urmă, ce criterii ar trebui să le folosesc pentru a atribuirea contractelor de achiziţii? Autorii discuta, de asemenea, motivaţiile pentru a depune o ofertă pachet, o descriere a lor de date, împreună cu date statistice sumare, iar în cele din urmă lor analiza empirică.

Ultimul capitol al cărţii, capitolul 23, discută licitaţii combinatorii pentru Indus de achiziţii publice proces, care este potenţial unul dintre domeniile cele mai mari cererea pentru comlicitaţii binatorial. După cum a subliniat de către autori, Bichler, Davenport, Hohner, şi Kalagnanam, AC au deja transformat întrun subiect de interes pentru furnizorii de software şi managerii de achiziţii publice în domeniul business-to-business. Cu toate acestea, în ciuda rapoarte de existenţa unui număr de aplicaţii de licitaţii combinatorii în indus de achiziţii publice proces, documentare şi informare publică privind detaliile de design sunt rare, probabil din cauza eforturilor de a proteja informaţiile de proprietate. Acest capitol descrie practica actuală în acest domeniu, inclusiv un studiu de caz de la Mars, Inc

I.8 Concluzie

Domeniul de licitaţii combinatorii a crescut rapid în ultimii zece ani. Acest volum îşi propune să facă aceste cunoştinţe accesibile la un grup larg de cercetători şi practicieni. Speranta noastra este ca integrarea de lucru de la cele trei discipline de bază în economie, operaţiunile de cercetare şi informatică va îmbunătăţi în mod semnificativ dezvoltarea teoriei şi de aplicare a acestui domeniu în curs de dezvoltare.

Ia act de

1. Cercetatorii au fost, de asemenea, operaţiuni de contributori activi la muncă mai devreme la licitatii, a se vedea, de exemplu, Friedman 1956 şi Rothkopf 1969. Într-adevăr, cele mai multe dintre lucrările timpurii privind licitaţii apărut pentru prima dată în reviste de cercetare operaţiuni.

2. O densitate de probabilitate f funcţia satisface monoton proprietatea raportului risc în cazul în care raportul f(v|t)/f(v|s) este slab în creştere în v, pentru toate t > s. De obicei, f (v|s) este densitatea de probabilitate a v valoarea unui ofertant lui condiţionată de e semnal (o estimare a valorii). Intuitiv, probabilitatea de valori mari creşte cu estimare a valorii.

3. Marfa sunt substitute atunci când creşterea preţului nu se reduce cererea pentru celelalte.

4. Aceasta a fost prima lucrare majoră pe licitaţii combinatorii. Acesta a introdus multe idei importante, cum ar fi formularea programării matematice a problemei adjudecătorului, să facă legătura între problema determinarea câştigătorului şi problema de ambalare stabilit, precum şi eliberarea concomitentă de complexitate de calcul, utilizarea unor tehnici din economie experimentale pentru testarea licitaţii combinatorii, şi luarea în considerare a problemelor de compatibilitate de stimulare a cererii şi revelaţie în licitaţii combinatorii.

Referinte

Ausubel, Lawrence M. şi Peter Cramton (2004),''Licitarea multe bunuri divizibile,''Jurnalul Oficial al Asociatiei Economice Europene, 2, 480493, AprilMay.

Ausubel, Lawrence M. Paul şi Milgrom (2002),''licitatii Crescatoare cu licitare de pachete, frontiere''de Economie teoretică, 1, 142, h www.bepress.com/bejte/frontiers/vol1/iss1/art1 i.

Cramton, Peter (1998),''licitatii Ascendent,''European Economic Review, 42, 745756.

Cramton, Peter (2002),''licitatii Spectrum,''în Martin Cave, Majumdar Summit-ului, şi Ingo Vogelsang, eds, Manualul de Telecomunicaţii Economie, Amsterdam:. Elsevier Science BV, Capitolul 14, 605639.

Cramton, Peter, Robert Gibbons, şi Paul Klemperer (1987),''dizolvarea unui parteneriat eficient,''Econometrica, 55, 615632.

Friedman, Lawrence (1956),''O strategie de licitare competitivă,''Operations Research, 4, 104112.

Kagel, John H. şi Alvin E. Roth (1995), Manualul de Economie experimentale, Princeton, NJ: Princeton University Press.

Klemperer, Paul (2000), Teoria economică de licitatii, Cheltenham, Marea Britanie: Edward Elgar.

Klemperer, Paul (2004), Licitatii: Teoria si practica, Princeton, NJ: Princeton University Press.

Krishna, Vijay (2002), Teoria licitaţiilor, San Diego, CA: Comunicat de Academic.

McAfee, R. Preston şi John McMillan (1987),''Licitaţii şi licitare,''Journal of Economic Literature, 25, 699738.

Milgrom, Paul R. (1981),''Aşteptările Rational, Achiziţionarea de informaţii, şi oferte competitive,''Econometrica, 49, 921943.

Milgrom, Paul (2004), Teoria licitaţiilor Punerea la locul de muncă, Cambridge: Cambridge University Press

.

Milgrom, Paul R. şi Robert J. Weber (1982),''O teorie a Licitaţii şi oferte competitive,''Econometrica, 50, 10891122.

Myerson, Roger B. (1979),''Compatibilitatea de stimulare şi Problemă negociere,''Econometrica, 47, 6173.

Myerson, Roger B. (1981),''Proiectare licitaţiilor Optimal, Matematică''de Operations Research, 6, 5873.

Myerson, Roger B. şi Mark A. Satterwaite (1983),''Mecanisme eficiente de comercializare a cotelor de Bilatteral,''Jurnalul de Teorie Economică, 29, 265281.

Rassenti, Stephen J., Vernon L. Smith, şi Robert L. Bulfin (1982),''o licitatie combinatorie Mecanismul pentru timpul alocat Slot Aeroport,''Bell Journal of Economics, 13, 402417.

Rothkopf, Michael H. (1969),''Un model de oferte competitive Rational,''Managementul Ştiinţă, 15, 362372.

Vickrey, William (1961), Counterspeculation'', Licitaţii, şi a ofertelor competitive sigilat,''Jurnalul de Finante, 16, 837.

Wilson, Robert (1969),''cu oferte competitive de informaţii disparate,''Managementul Ştiinţă, 15, 446448.

Wilson, Robert (1993), Design''de procedurile de tranzactionare eficient,''în Daniel Friedman şi Rust John, eds, Piata Licitaţie duble:. Instituţii, teorii, şi probă, Reading, MA: Addison Wesley Publishing Company, capitolul 5, 125152.