Supply-chain auktion
En supply chain-auktion är en auktion för att samordna handeln mellan olika leverantörer och konsumenter i en supply chain . Det är en generalisering av en dubbelauktion . I en dubbelauktion involverar varje affär två agenter - en köpare och en säljare, så "försörjningskedjan" innehåller bara en enda länk. I en allmän auktion i leveranskedjan kan varje affär involvera många olika agenter, till exempel: en säljare, en medlare, en transportör och en köpare.
Auktion för en linjär leveranskedja
Babaioff och Nisan presenterar en auktion för fallet där försörjningskedjan är linjär - varje nod i kedjan förbrukar utdata från föregående nod och producerar input för nästa nod. Det finns en klass av initiala leverantörer , flera klasser av omvandlare och en klass av slutkonsumenter .
Deras vanliga exempel är en lemonadmarknad, där det finns tre typer av agenter: plockare , pressare och drickare :
- Varje plockare plockar en enda citron från ett närliggande träd, för en fast kostnad;
- Varje pressare tar en enda citron och pressar den i ett glas lemonad, för en fast kostnad;
- Varje drinkare vill dricka ett enda glas lemonad, och har ett fast positivt värde för detta glas.
På denna marknad involverar varje affär tre agenter - en av varje slag. Kostnaderna/värdena för olika agenter av samma slag kan skilja sig åt, så det är önskvärt att arrangera handeln med en sanningsenlig mekanism . Babaioff och Nisan föreslår att man genomför tre olika dubbelauktioner - en för varje typ av agenter:
- En citronauktion - där säljarna är plockarna, och det finns "virtuella köpare" vars värde är värdet av en drinkare minus kostnaden för en pressmaskin;
- En klämauktion - där säljarna är klämarna och det finns "virtuella köpare" vars värde är värdet av en drinkare minus kostnaden för en plockare;
- En juiceauktion - där köparna är de som dricker, och det finns "virtuella säljare" vars kostnad är kostnaden för en plockare plus kostnaden för en pressare;
För varje dubbelauktion finns det flera alternativ, till exempel: en VCG-auktion (som är sanningsenlig och effektiv men har ett underskott), eller en handelsreducerande auktion (som är sanningsenlig och inte har något underskott utan bara är ungefär effektiv).
De föreslår två protokoll för att kombinera de olika dubbelauktionerna till ett enda resultat:
- Symmetric Protocol - varje marknad genomför en separat dubbelauktion - det finns ingen central marknad. För att säkerställa materialbalansen bör dubbelauktionsregeln som används på marknaderna vara konsekvent , dvs genomföra samma antal affärer. Eftersom antalet optimala affärer är detsamma på alla marknader är VCG-auktionen (som alltid gör alla optimala affärer) konsekvent. På samma sätt är handelsreduktionsregeln (som gör alla optimala affärer minus en) konsekvent. Men McAfees regel (som antingen gör alla optimala erbjudanden, är alla utom en, beroende på värdena) är inte konsekvent.
- Pivot Protocol - en av marknaderna (t.ex. slutkonsumentens) genomför en dubbelauktion, och skickar resultaten till de andra marknaderna före/efter i kedjan, och de använder informationen för att genomföra sina egna dubbelauktioner. För att säkerställa att det inte finns något underskott bör dubbelauktionsregeln som används på marknaderna inte ha något underskott, och dessutom bör den uppfylla ett starkare villkor - det pris som en köpare betalar måste vara minst lika stort som den lägsta kostnaden för en icke-handelsförsäljare. Detta villkor gäller för handelsreduktionsregeln, men inte nödvändigtvis för McAfees regel.
Exempel
Anta att det finns tre plockare med värden -3, -6, -7 (negativa värden anger kostnader); tre klämmor med värden -1, -3, -6; och tre konsumenter med värden +12, +11, +7. Följande tabell presenterar de tre dubbla auktionerna (de fetstilta värdena anger de faktiska handlarna; de icke fetstilta värdena är de virtuella handlarna beräknade som summan/skillnaden mellan andra handlares värden.
| Citronmarknad | Klämning marknad | Juicemarknad | Kombinerad | |
|---|---|---|---|---|
| Köparnas värderingar: | +11,+8,+1 | +9,+5,+0 | +12,+11,+7 | |
| Säljarens värderingar: | -3,-6,-7 | -1,-3,-6 | -4,-9,-13 | |
| Symmetriskt protokoll, VCG-auktion (sanningsenlig och effektiv) |
Två säljare (plockare) säljer för -7 = max(-8,-7). |
Två säljare (squeezers) säljer för -5 = max(-5,-6). |
Två köpare (drickare) köper för +9 = max(+9,+7). |
Två plockare plockar för -7; Två klämmor squeeze för -5; Två drinkare dricker för +9; Socialvård 12+11-1-3-3-6 = +10 ; Underskott -3 per enhet = -6 . |
| Symmetriskt protokoll, Handelsreducerande auktion (sanningsenlig och har inget underskott) |
En säljare (väljare) säljer för -6; | En säljare (squeezer) säljer för -3; | En köpare (drickare) köper för +11;
|
En plockare väljer -6; En squeezer pressar för -3; En drinkare dricker för +11; Socialvård 12-1-3 = +8 ; Överskott +2 per enhet = +2 . |
| Symmetriskt protokoll, Marknadsjämviktsresultat (effektiv och budgetbalanserad) |
Två säljare (plockare) säljer för -6; |
Två säljare (squeezers) säljer för -3; |
Två köpare (drickare) köper för +9; |
Två plockare plockar för -6; Två klämmor squeeze för -3; Två drinkare dricker för +9; Socialvård 12+11-1-3-3-6 = +10 ; Budgeten är balanserad. |
| Pivotprotokoll (börjar på juicemarknaden), VCG-auktion (sanningsenlig och effektiv) |
Handelsstorleken är 2, så två säljare (plockare) säljer; deras pris är max(-8, -7)=-7. |
Handelsstorleken är 2, så två säljare (pressare) sälja; deras pris är max(-11--6,-6)=-5. Skicka till tidigare marknad handelsstorlek (2) och försäljningspriset (-11--3=-8) |
Två köpare (drickare) köper för +9; Två säljare (virtuella) säljer för -11 = max(-11,-13); Skicka till tidigare marknad handelsstorlek (2) och försäljningspriset (-11). |
Två plockare plockar för -7; Två klämmor squeeze för -5; Två drinkare dricker för +9; Socialvård 12+11-1-3-3-6 = +10 ; Underskott -3 per enhet = -6 . |
Auktion för en riktad acyklisk graf
Babaioff och Walsh utökar ovanstående arbete till fallet där leveranskedjan kan vara vilken som helst acyklisk graf. Som ett exempel betraktar de följande marknad med sex agenttyper:
- Citronplockare - varje plockar 1 kg citroner, för en fast kostnad;
- Sockertillverkare - var och en producerar 0,5 kg socker till en fast kostnad;
- Juicepressar - var och en omvandlar 1 kg citroner till 0,5 liter juice, för en fast kostnad;
- Lemonadproducenter - var och en omvandlar 1 kg socker plus 0,5 gallon juice till 1 gallon lemonad, för en fast kostnad;
- Juiceköpare - var och en vill ha 0,5 gallon juice och har ett fast värde för det;
- Lemonadköpare - var och en vill ha 1 gallon lemonad och har ett fast värde för det.
Upphandlingsauktion
Chen, Roundy, Zhang och Janakiraman studerar en annan miljö där det finns en enda köpare och en enda artikel, men det finns olika producenter på olika leveransplatser. Köparen behöver en annan mängd av varan på olika efterfrågelägen. Köparen genomför en omvänd auktion . Köparen måste, utöver produktionskostnaden, även betala kostnaden för transport från utbudsplatserna till efterfrågeplatserna. De presenterar tre olika mekanismer: den första är sanningsenlig och effektiv när det gäller utbudet, men bortser från transportkostnaderna; den andra är sanningsenlig och effektiv när det gäller leverans och transport, men kan vara värre för köparen; den tredje är sanningsenlig endast för producenterna men inte för köparen.
- ^ a b Babaioff, M.; Nisan, N. (2004-05-01). "Samtidiga auktioner över hela leveranskedjan" . Journal of Artificial Intelligence Research . 21 : 595-629. doi : 10.1613/jair.1316 . ISSN 1076-9757 .
- ^ a b Babaioff, Moshe; Walsh, William E. (2005-03-01). "Incitament-kompatibla, budgetbalanserade, men ändå mycket effektiva auktioner för att skapa en leveranskedja". Beslutsstödssystem . 39 (1): 123–149. doi : 10.1016/j.dss.2004.08.008 .
- ^ a b Chen, Rachel R.; Roundy, Robin O.; Zhang, Rachel Q.; Janakiraman, Ganesh (2005-03-01). "Effektiva auktionsmekanismer för upphandling av försörjningskedjan". Management Science . 51 (3): 467–482. doi : 10.1287/mnsc.1040.0329 . ISSN 0025-1909 .