Multi-unit Veiling

Bij veilingen waar meerdere identieke eenheden van een goed beschikbaar zijn, wordt vaak gebruik gemaakt van een multi-unit veiling. Dit is een veilingtype waarbij meerdere kopers tegelijkertijd bieden op een deel van de beschikbare voorraad, met als doel de goederen te verdelen op een manier die de totale opbrengst maximaliseert. In deze opgave analyseren we verschillende manieren om de beschikbare eenheden toe te wijzen en de betalingen van de winnende bieders te berekenen.

Doorheen deze opgave gebruiken we steeds het volgende voorbeeld van een veiling. Er worden 10 ton appels geveild, en er zijn 5 bedrijven die interesse hebben om een deel van deze appels te kopen. De bedrijven hebben de volgende biedingen geplaatst, gesorteerd op bedrijfsnaam:

Bedrijf	Geboden prijs (per ton)	Aantal eenheden
Appelhof BV	€ 480	2 ton
Bakkerij Van den Broek	€ 530	3 ton
Boerenmarkt NV	€ 600	4 ton
Sapcentrale Limburg	€ 650	1 ton
Sapcentrale Limburg	€ 590	1 ton
Sapcentrale Limburg	€ 450	5 ton
Vershandel Janssens	€ 530	3 ton
Vershandel Janssens	€ 350	8 ton

Opdracht

De opdracht bestaat uit vijf deelvragen. Elke deelvraag bouwt verder op de vorige, en wordt dus best in volgorde opgelost.

Doorheen deze opgave zullen we eerst de winnende biedingen bepalen, en vervolgens de betalingen van de winnende bieders berekenen volgens drie verschillende methodes: pay-as-bid, uniforme prijsverdeling, en Vickrey-Clarke-Groves (VCG). Deze laatste manier zetten we ten slotte om in een command line programma dat een veiling uitvoert.

We gebruiken binnen deze opgave de volgende datatypen:

-- | Een hoeveelheid goederen.
type Quantity = Int

-- | Een prijs in euro's, bv. van een bod.
type Price = Double

-- | Een bod in een veiling.
data Bid = Bid {
  bidder      :: String,  -- ^ De naam van het bedrijf die het bod plaatst.
  bidPrice    :: Price,   -- ^ De geboden prijs.
  bidQuantity :: Quantity -- ^ De hoeveelheid goederen die het bedrijf wil kopen.
} deriving (Show, Eq)

-- | Een toewijzing van een hoeveelheid goederen aan een bedrijf.
data Allocation = Allocation {
  allocWinner   :: String,  -- ^ De naam van een bedrijf.
  allocQuantity :: Quantity -- ^ De hoeveelheid goederen die aan het bedrijf zijn toegewezen.
} deriving (Show, Eq)

Kopieer deze datatypen naar uw eigen implementatie, eventueel in een apart bestand AuctionTypes.hs.

Deelvraag 1: Bepaal de Winnaars

In een veiling zijn er slechts een beperkt aantal goederen te koop. Het doel van de veiling is om de goederen te verdelen onder de bieders, zodat de totale opbrengst van de veiling wordt gemaximaliseerd. In deze deelvraag gaan we bepalen welke biedingen worden geaccepteerd, en hoeveel goederen elk bedrijf krijgt toegewezen. Hiervoor gebruiken we de volgende veilingsregels:

1. We accepteren steeds eerst de biedingen met de hoogste prijs per eenheid.
2. Is er een gelijkspel, dan geven we voorrang aan de bieding met de meeste eenheden, en vervolgens aan de bieding die het eerst is ontvangen.
3. Zijn er onvoldoende goederen om een bod volledig te accepteren, dan worden de goederen gedeeltelijk toegewezen.

Bijvoorbeeld, met de voorbeeldbiedingen hierboven, zouden we de volgende biedingen accepteren:

Bedrijf	Geboden prijs (per ton)	Aantal eenheden
Sapcentrale Limburg	€ 650	1 ton
Boerenmarkt NV	€ 600	4 ton
Sapcentrale Limburg	€ 590	1 ton
Bakkerij Van den Broek	€ 530	3 ton
Vershandel Janssens	€ 530	1 ton

Merk op dat hoewel Vershandel Janssens 3 ton aan € 530 per ton wou kopen, er slechts 1 ton over was. Het bedrijf kreeg daarom slechts 1 ton toegewezen.

Implementeer de functie getWinners, gedefinieerd als volgt.

getWinners :: Quantity -> [Bid] -> [Allocation]

Deze functie neemt een totale hoeveelheid te veilen goederen, en een reeks biedingen als invoer. Deze biedingen zijn gerangschikt volgens wanneer ze zijn ontvangen, met de oudste biedingen eerst.

De functie geeft een lijst van toewijzingen terug, volgens de bovenstaande regels. De uitvoer bevat hoogstens één toewijzing per bedrijf: indien een bedrijf meerdere winnende biedingen heeft, worden de toegewezen hoeveelheden samengevoegd. De toewijzingen zijn gesorteerd: bedrijven met een grotere toegekende hoeveelheid gaan voor op bedrijven met een kleinere toegekende hoeveelheid, en bedrijven met een gelijke hoeveelheid worden gesorteerd op bedrijfsnaam.

Voorbeeld

let bids = [
    Bid "Appelhof BV" 480.0 2,
    Bid "Bakkerij Van den Broek" 530.0 3,
    Bid "Boerenmarkt NV" 600.0 4,
    Bid "Sapcentrale Limburg" 650.0 1,
    Bid "Sapcentrale Limburg" 590.0 1,
    Bid "Sapcentrale Limburg" 450.0 5,
    Bid "Vershandel Janssens" 530.0 3,
    Bid "Vershandel Janssens" 350.0 8
]

getWinners 10 bids == [
    Allocation "Boerenmarkt NV" 4,
    Allocation "Bakkerij Van den Broek" 3,
    Allocation "Sapcentrale Limburg" 2,
    Allocation "Vershandel Janssens" 1
]

Deelvraag 2: Bepaal de Betaling (Pay-as-Bid)

Er zijn verschillende manieren om te bepalen hoeveel alle winnaars moeten betalen. De meest eenvoudige manier is het pay-as-bid principe. Hierbij betaalt elk bedrijf de prijs die het zelf heeft geboden, onafhankelijk van de prijzen van andere biedingen.

Gaan we verder met het voorbeeld van de appelveiling, dan zouden de betalingen volgens het pay-as-bid principe als volgt zijn:

Bedrijf	Aantal eenheden	Berekening	Totale betaling
Boerenmarkt NV	4 ton	4 × € 600	€ 2400
Bakkerij Van den Broek	3 ton	3 × € 530	€ 1590
Sapcentrale Limburg	2 ton	1 × € 650 + 1 × € 590	€ 1240
Vershandel Janssens	1 ton	1 × € 530	€ 530

Merk op dat de betaling van Sapcentrale Limburg gebaseerd is op de twee afzonderlijke biedingen die het bedrijf heeft gewonnen (1 ton aan € 650 en 1 ton aan € 590).

Implementeer de functie calculatePaymentsPayAsBid, gedefinieerd als volgt.

calculatePaymentsPayAsBid :: Quantity -> [Bid] -> [(String, Double)]

Deze functie krijgt dezelfde invoer als de getWinners functie: een totale hoeveelheid te veilen goederen, en een reeks biedingen. De functie berekent hoeveel elk winnend bedrijf moet betalen volgens het pay-as-bid principe. De uitvoer is een lijst van betalingen per winnaar (naam, totale betaling). Rond het totale bedrag per winnaar naar boven af op twee decimalen (ceiling), als laatste stap voor het teruggeven van de resultaten. Pas geen afronding toe in tussenberekeningen. Sorteer de uitvoer op totale betaling van hoog naar laag, en vervolgens op bedrijfsnaam.

Voorbeeld

calculatePaymentsPayAsBid 10 bids == [
  ("Boerenmarkt NV", 2400.0),
  ("Bakkerij Van den Broek", 1590.0),
  ("Sapcentrale Limburg", 1240.0),
  ("Vershandel Janssens", 530.0)
]

Deelvraag 3: Bepaal de Betaling (Uniforme Prijsverdeling)

Het pay-as-bid wordt soms gezien als oneerlijk, omdat verschillende bedrijven een verschillende prijs betalen voor dezelfde goederen. Ook zet het bedrijven aan om een lagere prijs te bieden dan ze eigenlijk bereid zijn te betalen, omdat ze willen voorkomen dat ze meer betalen dan nodig is om te winnen.

Een alternatief is de uniforme prijsverdeling, waarbij alle winnaars dezelfde prijs betalen per eenheid. Deze prijs is gelijk aan de laagste prijs die nog een winnend bod heeft.

In de appelvoorbeeldveiling was de laagste winnende prijs € 530 per ton. De betalingen volgens het uniforme prijs principe zouden dan als volgt zijn:

Bedrijf	Aantal eenheden	Berekening	Totale betaling
Boerenmarkt NV	4 ton	4 × € 530	€ 2120
Bakkerij Van den Broek	3 ton	3 × € 530	€ 1590
Sapcentrale Limburg	2 ton	2 × € 530	€ 1060
Vershandel Janssens	1 ton	1 × € 530	€ 530

Implementeer een functie calculatePaymentsUniformPrice, gedefinieerd als volgt.

calculatePaymentsUniformPrice :: Quantity -> [Bid] -> [(String, Double)]

Zoals bij de vorige deelvraag, krijgt deze functie dezelfde invoer als de getWinners functie. De functie bepaalt hoeveel goederen elk bedrijf heeft gewonnen, en berekent vervolgens hoeveel elk bedrijf moet betalen volgens de uniforme prijsverdeling. Rond het totale bedrag per winnaar naar boven af op twee decimalen (ceiling), als laatste stap voor het teruggeven van de resultaten. Pas geen afronding toe in tussenberekeningen. Sorteer de uitvoer op totale betaling van hoog naar laag, en vervolgens op bedrijfsnaam.

Voorbeeld

calculatePaymentsUniformPrice 10 bids == [
  ("Boerenmarkt NV", 2120.0),
  ("Bakkerij Van den Broek", 1590.0),
  ("Sapcentrale Limburg", 1060.0),
  ("Vershandel Janssens", 530.0)
]

Deelvraag 4: Bepaal de Betaling (Vickrey-Clarke-Groves)

Hoewel de uniforme prijsverdeling eerlijker is dan het pay-as-bid principe, laat het nog steeds ruimte voor strategisch gedrag. Bedrijven worden gestimuleerd om een lagere prijs te bieden dan ze eigenlijk bereid zijn te betalen, om te proberen de uniforme prijs te drukken. Dit maakt de veiling minder efficiënt: de totale opbrengst van de veiling is lager dan wanneer bedrijven eerlijk zouden bieden.

De Vickrey-Clarke-Groves (VCG) veiling is een mechanisme dat bedrijven aanmoedigt om eerlijk te bieden: de prijs die een winnaar betaalt is volledig onafhankelijk van zijn eigen bod. In plaats daarvan hangt de prijs af van de biedingen van andere bedrijven (maar is begrensd door het eigen bod).

Een belangrijk concept in de VCG veiling is de "waarde" van een veiling. Dit is de som van alle winnende biedingen, berekend volgens het pay-as-bid principe. Met dit in het achterhoofd, kunnen we de betaling van een winnaar als volgt berekenen:

1. We berekenen hoeveel de winnaar had moeten betalen volgens het pay-as-bid principe, $B$.
2. We berekenen de totale waarde van de veiling, $W$.
3. We berekenen de totale waarde van de hypothetische veiling waarbij de winnaar niet meedoet, $W'$.
4. Het "overbod", de hoeveelheid die de winnaar te veel betaalt, is $W - W'$.
5. Het te betalen bedrag is $W' - W + B$.

Passen we dit toe voor Boerenmarkt NV, dan vinden we dat $B = € 2400$, en $W=( 1 \times €650 + 4 \times €600 + 1 \times €590 + 3 \times €530 + 1 \times €530) = € 5760$. Stel, Boerenmarkt NV had niet meegedaan in de veiling. Dan waren de winnaars als volgt:

Bedrijf	Geboden prijs (per ton)	Aantal eenheden
Sapcentrale Limburg	€ 650	1 ton
Sapcentrale Limburg	€ 590	1 ton
Bakkerij Van den Broek	€ 530	3 ton
Vershandel Janssens	€ 530	3 ton
Appelhof BV	€ 480	2 ton

We vinden dan dat $W' = (1 \times €650 + 1 \times €590 + 3 \times €530 + 3 \times €530 + 2 \times €480) = €5380$. De betaling van Boerenmarkt NV is dan $W' - W + B = €5380 - €5760 + €2400 = €2020$.

Implementeer de volgende twee functies, gedefinieerd als volgt.

wealth :: Quantity -> [Bid] -> Double
calculatePaymentsVCG :: Quantity -> [Bid] -> [(String, Double)]

Beide functies krijgen dezelfde invoer als de vorige deelvragen. De functie wealth berekent de totale waarde van de veiling, volgens het pay-as-bid principe. De functie calculatePaymentsVCG berekent de betalingen per winnaar volgens het VCG principe. Rond het totale bedrag per winnaar naar boven af op twee decimalen (ceiling), als laatste stap voor het teruggeven van de resultaten. Pas geen afronding toe in tussenberekeningen. Sorteer de uitvoer op totale betaling van hoog naar laag, en vervolgens op bedrijfsnaam.

Voorbeeld

wealth 10 bids == 5760.0
calculatePaymentsVCG 10 bids == [
  ("Boerenmarkt NV", 2020.0),
  ("Bakkerij Van den Broek", 1540.0),
  ("Sapcentrale Limburg", 1060.0),
  ("Vershandel Janssens", 480.0)
]

Deelvraag 5: Uitvoeren van de Veiling

Verzamel de implementaties van de vorige deelvragen in een programma dat een veiling uitvoert. Het programma neemt drie argumenten: het aantal eenheden dat geveild wordt, een invoerbestand met de biedingen, en een uitvoerbestand waarin de betalingen worden geschreven. Indien er een incorrect aantal argumenten wordt meegegeven, print het programma de volgende foutmelding, en stopt het met uitvoeren.

Usage: ./Auction <aantal eenheden> <invoerbestand> <uitvoerbestand>

Het invoerbestand is een CSV-bestand. De eerste regel is de kopregel, en bevat de volgende kolommen: bidder, price, en quantity. Elke volgende regel bevat een bod, met de naam van de bieder, de prijs per eenheid, en de hoeveelheid eenheden die de bieder wil kopen. De biedingen zijn gesorteerd volgens wanneer ze zijn ontvangen, met de oudste biedingen eerst. Bedrijfsnamen bevatten nooit een komma.

bidder,price,quantity
Appelhof BV,480.0,2
Bakkerij Van den Broek,530.0,3
Boerenmarkt NV,600.0,4
Sapcentrale Limburg,650.0,1
Sapcentrale Limburg,590.0,1
Sapcentrale Limburg,450.0,5
Vershandel Janssens,530.0,3
Vershandel Janssens,350.0,8

Het programma leest de biedingen in, voert een VCG veiling uit, en schrijft de betalingen naar het uitvoerbestand. De betalingen worden geschreven in het volgende CSV-formaat:

winner,quantity,payment
Boerenmarkt NV,4,2020.0
Bakkerij Van den Broek,3,1540.0
Sapcentrale Limburg,2,1060.0
Vershandel Janssens,1,480.0

Indienen

Zorg ervoor dat volgende bestanden in de root van uw repository staan: Auction.hs en REPORT.md.

• Auction.hs bevat de volledige implementatie van de veiling, inclusief de functies uit deelvragen 1 t.e.m. 5 en een programma om een veiling uit te voeren. Zorg ervoor dat de types Bid en Allocation, en de functies getWinners, calculatePaymentsPayAsBid, calculatePaymentsUniformPrice, wealth, en calculatePaymentsVCG direct beschikbaar zijn bij het laden van Auction.hs in GHCi. Indien u een apart bestand (bv. AuctionTypes.hs) gebruikt, importeer dan de benodigde types in Auction.hs.
• REPORT.md bevat een korte uitleg over de implementatie en de gemaakte keuzes. Indien bepaalde onderdelen niet volledig geïmplementeerd zijn, leg dan uit welke moeilijkheden u bent tegengekomen en wat u geprobeerd hebt om ze op te lossen. Geef ook aan hoe lang er aan de opgave en deelvragen is gewerkt.

Voeg ook uw naam, voornaam en studentennummer toe aan REPORT.md! Anders kan de opgave niet worden geëvalueerd.

U mag alle standaard Haskell modules gebruiken, d.w.z. modules die beschikbaar zijn zonder extra pakketten te installeren (bv. Data.List, Data.Maybe, System.Environment, …). Externe pakketten zoals split zijn niet toegestaan.

Zorg ervoor dat het programma compileerbaar en uitvoerbaar is met:

ghc Auction.hs -o Auction
./Auction <aantal eenheden> <invoerbestand> <uitvoerbestand>

Zorg er ook voor dat de functies correct laden in GHCi:

ghci Auction.hs

Het onderwijsteam zal de functies uit deelvragen 1 t.e.m. 4 handmatig testen via GHCi, en het command line programma uit deelvraag 5 testen via het gecompileerde programma. Indien het programma niet compileert of bepaalde functies niet correct werken, geef dit dan aan in REPORT.md.

Evaluatie

Je wordt verwacht deze opgave in groepen van twee te maken. Hierbij is het gebruik van generative AI om (delen van) de code te schrijven niet toegelaten.

Deze opgave wordt beoordeeld op correctheid, codekwaliteit, en een mondelinge toelichting. We starten met 0 punten, en er kunnen maximaal 10 punten verdiend worden:

• Correctheid draagt bij tot de punten.
• Een gebrek aan codekwaliteit kost punten. Je kan nooit meer dan 3 punten verliezen op codekwaliteit.
• In de mondelinge toelichting moet je kort de werking van je eigen code toelichten waarbij er vanuit het onderwijsteam ook vragen gesteld worden. Je toont hierdoor aan dat je de ingediende code zelf geschreven hebt en dus beheerst. Indien je dit niet overtuigend kan doen, en er hierdoor dus twijfel ontstaat of je de code zelf geschreven hebt, wordt dit als een vorm van plagiaat beschouwd en conform het examenreglement aan de examencommissie gerapporteerd. De examencommissie beslist over de verdere afhandeling en sancties.

Correctheid (max. 10 punten)

De implementatie moet correct werken zoals beschreven in de specificatie.

• getWinners: 2 punten te verdienen
• calculatePaymentsPayAsBid: 2 punten te verdienen
• calculatePaymentsUniformPrice: 1 punt te verdienen
• wealth: 1 punt te verdienen
• calculatePaymentsVCG: 2 punten te verdienen
• Command line programma: 2 punten te verdienen

Codekwaliteit (max. 3 minpunten)

Om een maximaal aantal punten te behalen, moet de code goed gestructureerd zijn, en gebruik maken van goede programmeerpraktijken. Schrijf steeds type signatures bij functies. Werk op een functionele manier, en schrijf duidelijke, beknopte, en becommentarieerde code.

Aspect	Beschrijving
0 minpunten	De code is zeer duidelijk en goed gestructureerd.
1 minpunt	Kleine problemen met de structuur van de code, maar met slechts een kleine impact op de leesbaarheid. Hoewel de code voornamelijk functioneel is, kan er nog imperatieve code aanwezig zijn.
2 minpunten	De code is moeilijk te lezen en te begrijpen, maar met moeite kan ze nog gevolgd worden, of gebruikt een voornamelijk imperatieve programmeerstijl.
3 minpunten	De code is onleesbaar en onbegrijpelijk.