house_auction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d7235eff",
   "metadata": {},
   "source": [
    "# Multiple Good Allocation Mechanisms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b11dfb1e",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "!pip install prettytable"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "934ec007",
   "metadata": {},
   "source": [
    "## Overview\n",
    "\n",
    "This lecture describes two mechanisms for allocating $ n $ private goods (“houses”)  to $ m $ people (“buyers”).\n",
    "\n",
    "We assume that  $ m > n $ so that there are more potential buyers than there are houses.\n",
    "\n",
    "Prospective buyers regard the houses  as **substitutes**.\n",
    "\n",
    "Buyer $ j $ attaches  value $ v_{ij} $ to house $ i $.\n",
    "\n",
    "These  values are **private**\n",
    "\n",
    "- $ v_{ij} $ is  known only to person $ j $ unless person $ j $ chooses to tell someone.  \n",
    "\n",
    "\n",
    "We require that a mechanism allocate **at most** one house to one prospective buyer.\n",
    "\n",
    "We describe two distinct mechanisms\n",
    "\n",
    "- A multiple rounds, ascending bid auction  \n",
    "- A special case of a Groves-Clarke [[Groves, 1973](https://python.quantecon.org/zreferences.html#id22)], [[Clarke, 1971](https://python.quantecon.org/zreferences.html#id23)] mechanism with a benevolent social planner  \n",
    "\n",
    "\n",
    ">**Note**\n",
    ">\n",
    ">In 1994, the multiple rounds, ascending bid auction was actually used by Stanford University to sell leases to 9 lots on the Stanford campus to eligible faculty members.\n",
    "\n",
    "We begin with  overviews of the two mechanisms."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b296a5d7",
   "metadata": {},
   "source": [
    "## Ascending Bids Auction for Multiple Goods\n",
    "\n",
    "An auction is administered by an **auctioneer**\n",
    "\n",
    "The auctioneer has an $ n \\times 1 $ vector $ r $ of reservation prices on the $ n $ houses.\n",
    "\n",
    "The auctioneer sells house $ i $ only if the final price bid for it exceeds $ r_i $\n",
    "\n",
    "The auctioneer  allocates all $ n $ houses **simultaneously**\n",
    "\n",
    "The auctioneer does not know bidders’ private values $ v_{ij} $\n",
    "\n",
    "There are multiple **rounds**\n",
    "\n",
    "- during each round, active participants can submit bids on any of the  $ n $ houses  \n",
    "- each bidder can bid on only one house during one round  \n",
    "- a person who was high bidder on a particular house in one round  is understood to submit  that same bid for the same  house in the next round  \n",
    "- between rounds, a bidder who was not a high bidder can change the house on which he/she chooses to bid  \n",
    "- the auction ends when the price of no house changes from one round to the next  \n",
    "- all $ n $ houses are allocated after the final round  \n",
    "- house $ i $  is retained by the auctioneer if not prospective buyer offers more that $ r_i $ for the house  \n",
    "\n",
    "\n",
    "In this auction,  person $ j $ never tells anyone else his/her private values $ v_{ij} $"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a2388f2c",
   "metadata": {},
   "source": [
    "## A Benevolent Planner\n",
    "\n",
    "This mechanism is designed so that all prospective buyers voluntarily choose to reveal their private values to a **social planner** who uses them to construct a socially optimal allocation.\n",
    "\n",
    "Among all feasible allocations,  a **socially optimal allocation** maximizes the sum of  private values across all prospective buyers.\n",
    "\n",
    "The planner tells everyone in advance how he/she will allocate houses based on the matrix of values that prospective buyers report.\n",
    "\n",
    "The mechanism provide every prospective buyer an incentive to reveal his vector of private values to the planner.\n",
    "\n",
    "After the planner receives everyone’s vector of private values, the planner deploys a **sequential** algorithm to determine an **allocation** of houses and a set of **fees** that he charges awardees  for the negative **externality** that their presence impose on other prospective buyers."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8b341e43",
   "metadata": {},
   "source": [
    "## Equivalence of Allocations\n",
    "\n",
    "Remarkably, these two mechanisms can produce virtually identical allocations.\n",
    "\n",
    "We construct Python code for both mechanism.\n",
    "\n",
    "We also work out some examples by hand or almost by hand.\n",
    "\n",
    "Next, let’s dive down into the details."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7332479",
   "metadata": {},
   "source": [
    "## Ascending Bid Auction"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d090d31",
   "metadata": {},
   "source": [
    "### Basic Setting\n",
    "\n",
    "We start with  a more detailed description of the setting.\n",
    "\n",
    "- A seller owns $ n $ houses that he wants to sell for the maximum possible amounts to a  set of $ m $ prospective eligible buyers.  \n",
    "- The seller wants to sell at most one house to each potential  buyer.  \n",
    "- There are $ m $ potential eligible buyers, identified by $ j = [1, 2, \\ldots, m] $  \n",
    "  - Each potential  buyer is permitted  to buy at most  one house.  \n",
    "  - Buyer $ j $ would be willing to pay at most $ v_{ij} $ for house $ i $.  \n",
    "  - Buyer $ j $  knows $ v_{ij}, i= 1, \\ldots , n $, but no one else does.  \n",
    "  - If buyer $ j $ pays $ p_i $ for house $ i $, he enjoys surplus value $ v_{ij} - p_i $.  \n",
    "  - Each buyer $ j $ wants to choose the $ i $ that maximizes his/her surplus value $ v_{ij} - p_i $.  \n",
    "  - The seller wants to maximize $ \\sum_i p_i $.  \n",
    "\n",
    "\n",
    "The seller conducts a **simultaneous, multiple goods, ascending bid auction**.\n",
    "\n",
    "Outcomes of the  auction  are\n",
    "\n",
    "- An $ n \\times 1 $ vector $ p $ of sales prices $ p = [p_1, \\ldots, p_n] $ for the\n",
    "  $ n $ houses.  \n",
    "- An $ n \\times m $ matrix $ Q $ of $ 0 $’s and $ 1 $’s, where $ Q_{ij} = 1 $ if and only if person $ j $ bought house $ i $.  \n",
    "- An $ n \\times m $ matrix $ S $ of surplus values consisting of all zeros unless\n",
    "  person $ j $ bought house $ i $, in which case $ S_{ij} = v_{ij} - p_i $  \n",
    "\n",
    "\n",
    "We describe  rules for the auction it terms of  **pseudo  code**.\n",
    "\n",
    "The pseudo code will provide a road map for writing Python code to implement the auction."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b878419a",
   "metadata": {},
   "source": [
    "## Pseudocode\n",
    "\n",
    "Here is a quick sketch of a possible simple structure for our Python code\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "- $ n, m $.  \n",
    "- an $ n \\times m $ non-negative matrix $ v $ of  private values  \n",
    "- an $ n \\times 1 $ vector $ r $  of seller-specified reservation prices  \n",
    "- the seller will not accept a price less than $ r_i $ for house $ i $  \n",
    "- we are free to think of these reservation prices as private values of a fictitious $ m +1 $ th buyer who does not actually participate in the auction  \n",
    "- initial bids can be thought of starting at $ r $  \n",
    "- a scalar $ \\epsilon $ of seller-specified minimum price-bid increments  \n",
    "\n",
    "\n",
    "For each round of the auction, new bids on a house  must be at least the prevailing highest bid so far **plus** $ \\epsilon $\n",
    "\n",
    "**Auction Protocols**\n",
    "\n",
    "- the auction consists of a  finite number of **rounds**  \n",
    "- in each round, a prospective buyer can bid on one and only one house  \n",
    "- after each round,  a  house is temporarily awarded to the person who made the  highest bid for that house  \n",
    "  - temporarily winning bids on each house are announced  \n",
    "  - this sets the stage to move on to the next round  \n",
    "- a new round is held  \n",
    "  - bids for temporary winners from the previous round are again attached to the houses on which they bid; temporary winners of the last round  leave their bids from the previous round unchanged  \n",
    "  - all other active  prospective buyers must submit a new bid on some house  \n",
    "  - new bids on a house must be at least equal to the prevailing temporary price that won the last round **plus** $ \\epsilon $  \n",
    "  - if a person does not submit a new bid and was also not a temporary winner from the previous round, that  person must  drop out of the auction permanently  \n",
    "  - for each house, the highest bid, whether it is a new bid or was the temporary winner from the previous round, is announced, with the person who made that new (temporarily) winning bid being (temporarily) awarded the house to start the next round  \n",
    "- rounds continue until no price on **any** house changes from the previous round  \n",
    "- houses are sold to the winning bidders from the final round at the prices that they bid  \n",
    "\n",
    "\n",
    "**Outputs:**\n",
    "\n",
    "- an $ n \\times 1 $ vector $ p $ of sales prices  \n",
    "- an $ n \\times m $ matrix $ S $ of surplus values consisting of all zeros unless\n",
    "  person $ j $ bought house $ i $, in which case $ S_{ij} = v_{ij} - p_i $  \n",
    "- an $ n \\times (m+1) $  matrix $ Q $ of $ 0 $’s and $ 1 $’s that tells which buyer bought which  house.  (The last column  accounts for unsold houses.)  \n",
    "\n",
    "\n",
    "**Proposed buyer strategy:**\n",
    "\n",
    "In this pseudo code and the actual Python code below, we’ll assume that all buyers choose to use the following  strategy\n",
    "\n",
    "- The strategy is optimal  for each buyer  \n",
    "\n",
    "\n",
    "Each buyer $ j = 1, \\ldots, m $ uses the same strategy.\n",
    "\n",
    "The strategy has the form:\n",
    "\n",
    "- Let $ \\check p^t $ be the $ n \\times 1 $ vector of  prevailing highest-bid prices  at the beginning of round $ t $  \n",
    "- Let $ \\epsilon>0 $ be the minimum bid increment specified by the seller  \n",
    "- For each prospective buyer $ j $, compute the index of the best house to bid on during round $ t $, namely\n",
    "  $ \\hat i_t = \\textrm{argmax}_i\\{  [  v_{ij} - \\check p^t_i - \\epsilon  ]\\} $  \n",
    "- If $ \\max_i\\{  [  v_{ij} - \\check p^t_i - \\epsilon  ]\\} $  $ \\leq $ $ 0 $, person $ j $ permanently drops out of the auction at round $ t $  \n",
    "- If  $ v_{\\hat i_t, j} - \\check p^t_i - \\epsilon>0 $, person $ j $ bids $ \\check p^t_i + \\epsilon $ on house $ j $  \n",
    "\n",
    "\n",
    "**Resolving ambiguities**: The protocols  we have described so far leave open two possible sources of ambiguity.\n",
    "\n",
    "(1) **The optimal bid choice for buyers in each round.** It is possible that a buyer has the same surplus value for multiple houses. The  argmax function in Python always returns the first argmax element. We instead  prefer to randomize among such winner. For that reason,  we write our own argmax function below.\n",
    "\n",
    "(2) **Seller’s choice of winner if same price bid cast by several buyers.** To resolve  this ambiguity, we use the np.random.choice function below.\n",
    "\n",
    "Given the randomness in outcomes, it is possible that different  allocations  of houses could emerge from the same inputs.\n",
    "\n",
    "However, this will happen only when the bid price increment $ \\epsilon $ is nonnegligible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9fed38d0",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import prettytable as pt\n",
    "\n",
    "np.random.seed(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "657babc3",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "np.set_printoptions(precision=3, suppress=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6ca1aa84",
   "metadata": {},
   "source": [
    "## An Example\n",
    "\n",
    "Before building a Python class, let’s step by step solve things almost “by hand”  to grasp  how the auction proceeds.\n",
    "\n",
    "A step-by-step procedure also helps reduce bugs, especially when the value matrix is peculiar (e.g. the differences between values are negligible, a column containing identical values or multiple buyers have the same valuation etc.).\n",
    "\n",
    "Fortunately, our auction  behaves well and  robustly with various peculiar matrices.\n",
    "\n",
    "We provide some examples later in this lecture."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "af2ca156",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "v = np.array([[8, 5, 9, 4],\n",
    "              [4, 11, 7, 4],\n",
    "              [9, 7, 6, 4]])\n",
    "n, m = v.shape\n",
    "r = np.array([2, 1, 0])\n",
    "ϵ = 1\n",
    "p = r.copy()\n",
    "buyer_list = np.arange(m)\n",
    "house_list = np.arange(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "21e61300",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "v"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f07c3a1",
   "metadata": {},
   "source": [
    "Remember that column indexes $ j $ indicate buyers and row indexes $ i $ indicate houses.\n",
    "\n",
    "The above value matrix $ v $ is peculiar in the sense that Buyer 3 (indexed from 0) puts the same value $ 4 $ on  every house being sold.\n",
    "\n",
    "Maybe buyer 3 is a bureaucrat who purchases these house simply by following  instructions from his superior."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3821bb5f",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0cb66ba5",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "def find_argmax_with_randomness(v):\n",
    "    \"\"\"\n",
    "    We build our own verion of argmax function such that the argmax index will be returned randomly\n",
    "    when there are multiple maximum values. This function is similiar to np.argmax(v,axis=0)\n",
    "\n",
    "    Parameters:\n",
    "    ----------\n",
    "    v: 2 dimensional np.array\n",
    "\n",
    "    \"\"\"\n",
    "\n",
    "    n, m = v.shape\n",
    "    index_array = np.arange(n)\n",
    "    result=[]\n",
    "\n",
    "    for ii in range(m):\n",
    "        max_value = v[:,ii].max()\n",
    "        result.append(np.random.choice(index_array[v[:,ii] == max_value]))\n",
    "\n",
    "    return np.array(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d83fe56c",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "def present_dict(dt):\n",
    "    \"\"\"\n",
    "    A function that present the information in table.\n",
    "\n",
    "    Parameters:\n",
    "    ----------\n",
    "    dt: dictionary.\n",
    "\n",
    "    \"\"\"\n",
    "\n",
    "    ymtb = pt.PrettyTable()\n",
    "    ymtb.field_names = ['House Number', *dt.keys()]\n",
    "    ymtb.add_row(['Buyer', *dt.values()])\n",
    "    print(ymtb)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "827138bf",
   "metadata": {},
   "source": [
    "**Check Kick Off Condition**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2e456bbd",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "def check_kick_off_condition(v, r, ϵ):\n",
    "    \"\"\"\n",
    "    A function that checks whether the auction could be initiated given the reservation price and value matrix.\n",
    "    To avoid the situation that the reservation prices are so high that no one would even bid in the first round.\n",
    "\n",
    "    Parameters:\n",
    "    ----------\n",
    "    v : value matrix of the shape (n,m).\n",
    "\n",
    "    r: the reservation price\n",
    "\n",
    "    ϵ: the minimun price increment in each round\n",
    "\n",
    "    \"\"\"\n",
    "\n",
    "    # we convert the price vector to a matrix in the same shape as value matrix to facilitate subtraction\n",
    "    p_start = (ϵ+r)[:,None] @ np.ones(m)[None,:]\n",
    "\n",
    "    surplus_value = v - p_start\n",
    "    buyer_decision = (surplus_value > 0).any(axis = 0)\n",
    "    return buyer_decision.any()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1c288ccc",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "check_kick_off_condition(v, r, ϵ)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d770e53",
   "metadata": {},
   "source": [
    "### round 1\n",
    "\n",
    "**submit bid**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8a73d098",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "def submit_initial_bid(p_initial, ϵ, v):\n",
    "    \"\"\"\n",
    "    A function that describes the bid information in the first round.\n",
    "\n",
    "    Parameters:\n",
    "    ----------\n",
    "    p_initial: the price (or the reservation prices) at the beginning of auction.\n",
    "\n",
    "    v: the value matrix\n",
    "\n",
    "    ϵ: the minimun price increment in each round\n",
    "\n",
    "    Returns:\n",
    "    ----------\n",
    "    p: price array after this round of bidding\n",
    "\n",
    "    bid_info: a dictionary that contains bidding information (house number as keys and buyer as values).\n",
    "\n",
    "    \"\"\"\n",
    "\n",
    "    p = p_initial.copy()\n",
    "    p_start_mat = (ϵ + p)[:,None] @ np.ones(m)[None,:]\n",
    "    surplus_value = v - p_start_mat\n",
    "\n",
    "    # we only care about active buyers who have positve surplus values\n",
    "    active_buyer_diagnosis = (surplus_value > 0).any(axis = 0)\n",
    "    active_buyer_list = buyer_list[active_buyer_diagnosis]\n",
    "    active_buyer_surplus_value = surplus_value[:,active_buyer_diagnosis]\n",
    "    active_buyer_choice = find_argmax_with_randomness(active_buyer_surplus_value)\n",
    "    # choice means the favourite houses given the current price and ϵ\n",
    "\n",
    "    # we only retain the unique house index because prices increase once at one round\n",
    "    house_bid =  list(set(active_buyer_choice))\n",
    "    p[house_bid] += ϵ\n",
    "\n",
    "    bid_info = {}\n",
    "    for house_num in house_bid:\n",
    "        bid_info[house_num] = active_buyer_list[active_buyer_choice == house_num]\n",
    "\n",
    "    return p, bid_info"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ce9cf900",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "p, bid_info = submit_initial_bid(p, ϵ, v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "43c9ef07",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "723e0b18",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "present_dict(bid_info)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d8d24b7",
   "metadata": {},
   "source": [
    "**check terminal condition**\n",
    "\n",
    "Notice that  two buyers bid for house 2 (indexed from 0).\n",
    "\n",
    "Because the auction protocol does not specify  a selection rule in this case, we simply select a winner **randomly**.\n",
    "\n",
    "This is reasonable because the seller can’t distinguish these buyers and  doesn’t know the valuation of each buyer.\n",
    "\n",
    "It is both convenient and practical for him to just pick a winner randomly.\n",
    "\n",
    "There is a  50% probability that Buyer 3 is chosen as the winner for house 2, although he values it less than buyer 0.\n",
    "\n",
    "In this case, buyer 0 has to bid one more time with a higher price, which crowds out Buyer 3.\n",
    "\n",
    "Therefore, final price could be 3 or 4, depending on the winner in the last round."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c30e19c2",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "def check_terminal_condition(bid_info, p, v):\n",
    "    \"\"\"\n",
    "    A function that checks whether the auction ends.\n",
    "\n",
    "    Recall that the auction ends when either losers have non-positive surplus values for each house\n",
    "    or there is no loser (every buyer gets a house).\n",
    "\n",
    "    Parameters:\n",
    "    ----------\n",
    "    bid_info: a dictionary that contains bidding information of house numbers (as keys) and buyers (as values).\n",
    "\n",
    "    p: np.array. price array of houses\n",
    "\n",
    "    v: value matrix\n",
    "\n",
    "    Returns:\n",
    "    ----------\n",
    "    allocation: a dictionary that descirbe how the houses bid are assigned.\n",
    "\n",
    "    winner_list: a list of winners\n",
    "\n",
    "    loser_list: a list of losers\n",
    "\n",
    "    \"\"\"\n",
    "\n",
    "    # there may be several buyers bidding one house, we choose a winner randomly\n",
    "    winner_list=[np.random.choice(bid_info[ii]) for ii in bid_info.keys()]\n",
    "\n",
    "    allocation = {house_num:winner for house_num,winner in zip(bid_info.keys(),winner_list)}\n",
    "\n",
    "    loser_set = set(buyer_list).difference(set(winner_list))\n",
    "    loser_list = list(loser_set)\n",
    "    loser_num = len(loser_list)\n",
    "\n",
    "    if loser_num == 0:\n",
    "        print('The auction ends because every buyer gets one house.')\n",
    "        return allocation,winner_list,loser_list\n",
    "\n",
    "    p_mat = (ϵ + p)[:,None] @ np.ones(loser_num)[None,:]\n",
    "    loser_surplus_value = v[:,loser_list] - p_mat\n",
    "    loser_decision = (loser_surplus_value > 0).any(axis = 0)\n",
    "\n",
    "    print(~(loser_decision.any()))\n",
    "\n",
    "    return allocation,winner_list,loser_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f15c9383",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "allocation,winner_list,loser_list = check_terminal_condition(bid_info, p, v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5acb91f1",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "present_dict(allocation)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dc072c3b",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "winner_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ead9216b",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "loser_list"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "537ff421",
   "metadata": {},
   "source": [
    "### round 2\n",
    "\n",
    "From the second round on, the auction proceeds differently from the first round.\n",
    "\n",
    "Now only active losers (those who have positive surplus values) have  an incentive to submit bids to displace temporary winners from the previous round."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eb7b26e5",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "def submit_bid(loser_list, p, ϵ, v, bid_info):\n",
    "    \"\"\"\n",
    "    A function that executes the bid operation after the first round.\n",
    "    After the first round, only active losers would cast a new bid with price as old price + increment.\n",
    "    By such bid, winners of last round are replaced by the active losers.\n",
    "\n",
    "    Parameters:\n",
    "    ----------\n",
    "    loser_list: a list that includes the indexes of losers\n",
    "\n",
    "    p: np.array. price array of houses\n",
    "\n",
    "    ϵ: minimum increment of bid price\n",
    "\n",
    "    v: value matrix\n",
    "\n",
    "    bid_info: a dictionary that contains bidding information of house numbers (as keys) and buyers (as values).\n",
    "\n",
    "    Returns:\n",
    "    ----------\n",
    "    p_end: a price array after this round of bidding\n",
    "\n",
    "    bid_info: a dictionary that contains updated bidding information.\n",
    "\n",
    "    \"\"\"\n",
    "\n",
    "    p_end=p.copy()\n",
    "\n",
    "    loser_num = len(loser_list)\n",
    "    p_mat = (ϵ + p_end)[:,None] @ np.ones(loser_num)[None,:]\n",
    "    loser_surplus_value = v[:,loser_list] - p_mat\n",
    "    loser_decision = (loser_surplus_value > 0).any(axis = 0)\n",
    "\n",
    "    active_loser_list = np.array(loser_list)[loser_decision]\n",
    "    active_loser_surplus_value = loser_surplus_value[:,loser_decision]\n",
    "    active_loser_choice = find_argmax_with_randomness(active_loser_surplus_value)\n",
    "\n",
    "    # we retain the unique house index and increasing the corresponding bid price\n",
    "    house_bid = list(set(active_loser_choice))\n",
    "    p_end[house_bid] += ϵ\n",
    "\n",
    "    # we record the bidding information from active losers\n",
    "    bid_info_active_loser = {}\n",
    "    for house_num in house_bid:\n",
    "        bid_info_active_loser[house_num] = active_loser_list[active_loser_choice == house_num]\n",
    "\n",
    "    # we update the bidding information according to the bidding from actice losers\n",
    "    for house_num in bid_info_active_loser.keys():\n",
    "        bid_info[house_num] = bid_info_active_loser[house_num]\n",
    "\n",
    "    return p_end,bid_info"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9b415aaa",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "p,bid_info = submit_bid(loser_list, p, ϵ, v, bid_info)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "74be41e9",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "91c48ac0",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "present_dict(bid_info)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fe944128",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "allocation,winner_list,loser_list = check_terminal_condition(bid_info, p, v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7583125e",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "present_dict(allocation)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "badd870e",
   "metadata": {},
   "source": [
    "### round 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f250ec00",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "p,bid_info = submit_bid(loser_list, p, ϵ, v, bid_info)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8520a10f",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7021c79c",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "present_dict(bid_info)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d7eae5f6",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "allocation,winner_list,loser_list = check_terminal_condition(bid_info, p, v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "68e0e8cd",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "present_dict(allocation)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "401dc22b",
   "metadata": {},
   "source": [
    "### round 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f03d97da",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "p,bid_info = submit_bid(loser_list, p, ϵ, v, bid_info)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "114920c9",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "35656284",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "present_dict(bid_info)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b839ed08",
   "metadata": {},
   "source": [
    "Notice that  Buyer 3 now switches  to bid for house 1 having recongized that  house 2 is no longer his best option."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67bcaddd",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "allocation,winner_list,loser_list = check_terminal_condition(bid_info, p, v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ce5d1238",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "present_dict(allocation)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "432c379b",
   "metadata": {},
   "source": [
    "### round 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0e11d9be",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "p,bid_info = submit_bid(loser_list, p, ϵ, v, bid_info)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eeedef3b",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1ac476fd",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "present_dict(bid_info)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "371ec38b",
   "metadata": {},
   "source": [
    "Now Buyer 1 bids for house 1 again with price at 4, which crowds out Buyer 3, marking the end of the auction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1cb489cb",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "allocation,winner_list,loser_list = check_terminal_condition(bid_info, p, v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b8113bb5",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "present_dict(allocation)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "56fbcb9f",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "# as for the houses unsold\n",
    "\n",
    "house_unsold_list = list(set(house_list).difference(set(allocation.keys())))\n",
    "house_unsold_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4ef5dd87",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "total_revenue = p[list(allocation.keys())].sum()\n",
    "total_revenue"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06406bf0",
   "metadata": {},
   "source": [
    "## A Python Class\n",
    "\n",
    "Above we simulated an ascending bid auction step by step.\n",
    "\n",
    "When defining  functions, we repeatedly computed some intermediate objects because our Python function loses track of variables once the  function is executed.\n",
    "\n",
    "That of course led  to redundancy in our code\n",
    "\n",
    "It is much more efficient  to collect all of the aforementioned code into a class that  records information about all rounds."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6f732d6f",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "class ascending_bid_auction:\n",
    "\n",
    "    def __init__(self, v, r, ϵ):\n",
    "        \"\"\"\n",
    "        A class that simulates an ascending bid auction for houses.\n",
    "\n",
    "        Given buyers' value matrix, sellers' reservation prices and minimum increment of bid prices,\n",
    "        this class can execute an ascending bid auction and present information round by round until the end.\n",
    "\n",
    "        Parameters:\n",
    "        ----------\n",
    "        v: 2 dimensional value matrix\n",
    "\n",
    "        r: np.array of reservation prices\n",
    "\n",
    "        ϵ: minimum increment of bid price\n",
    "\n",
    "        \"\"\"\n",
    "\n",
    "        self.v = v.copy()\n",
    "        self.n,self.m = self.v.shape\n",
    "        self.r = r\n",
    "        self.ϵ = ϵ\n",
    "        self.p = r.copy()\n",
    "        self.buyer_list = np.arange(self.m)\n",
    "        self.house_list = np.arange(self.n)\n",
    "        self.bid_info_history = []\n",
    "        self.allocation_history = []\n",
    "        self.winner_history = []\n",
    "        self.loser_history = []\n",
    "\n",
    "\n",
    "    def find_argmax_with_randomness(self, v):\n",
    "        n,m = v.shape\n",
    "        index_array = np.arange(n)\n",
    "        result=[]\n",
    "\n",
    "        for ii in range(m):\n",
    "            max_value = v[:,ii].max()\n",
    "            result.append(np.random.choice(index_array[v[:,ii] == max_value]))\n",
    "\n",
    "        return np.array(result)\n",
    "\n",
    "\n",
    "    def check_kick_off_condition(self):\n",
    "        # we convert the price vector to a matrix in the same shape as value matrix to facilitate subtraction\n",
    "        p_start = (self.ϵ + self.r)[:,None] @ np.ones(self.m)[None,:]\n",
    "        self.surplus_value = self.v - p_start\n",
    "        buyer_decision = (self.surplus_value > 0).any(axis = 0)\n",
    "        return buyer_decision.any()\n",
    "\n",
    "\n",
    "    def submit_initial_bid(self):\n",
    "        # we intend to find the optimal choice of each buyer\n",
    "        p_start_mat = (self.ϵ + self.p)[:,None] @ np.ones(self.m)[None,:]\n",
    "        self.surplus_value = self.v - p_start_mat\n",
    "\n",
    "        # we only care about active buyers who have positve surplus values\n",
    "        active_buyer_diagnosis = (self.surplus_value > 0).any(axis = 0)\n",
    "        active_buyer_list = self.buyer_list[active_buyer_diagnosis]\n",
    "        active_buyer_surplus_value = self.surplus_value[:,active_buyer_diagnosis]\n",
    "        active_buyer_choice = self.find_argmax_with_randomness(active_buyer_surplus_value)\n",
    "\n",
    "        # we only retain the unique house index because prices increase once at one round\n",
    "        house_bid =  list(set(active_buyer_choice))\n",
    "        self.p[house_bid] += self.ϵ\n",
    "\n",
    "        bid_info = {}\n",
    "        for house_num in house_bid:\n",
    "            bid_info[house_num] = active_buyer_list[active_buyer_choice == house_num]\n",
    "        self.bid_info_history.append(bid_info)\n",
    "\n",
    "        print('The bid information is')\n",
    "        ymtb = pt.PrettyTable()\n",
    "        ymtb.field_names = ['House Number', *bid_info.keys()]\n",
    "        ymtb.add_row(['Buyer', *bid_info.values()])\n",
    "        print(ymtb)\n",
    "\n",
    "        print('The bid prices for houses are')\n",
    "        ymtb = pt.PrettyTable()\n",
    "        ymtb.field_names = ['House Number', *self.house_list]\n",
    "        ymtb.add_row(['Price', *self.p])\n",
    "        print(ymtb)\n",
    "\n",
    "        self.winner_list=[np.random.choice(bid_info[ii]) for ii in bid_info.keys()]\n",
    "        self.winner_history.append(self.winner_list)\n",
    "\n",
    "        self.allocation = {house_num:[winner] for house_num,winner in zip(bid_info.keys(),self.winner_list)}\n",
    "        self.allocation_history.append(self.allocation)\n",
    "\n",
    "        loser_set = set(self.buyer_list).difference(set(self.winner_list))\n",
    "        self.loser_list = list(loser_set)\n",
    "        self.loser_history.append(self.loser_list)\n",
    "\n",
    "        print('The winners are')\n",
    "        print(self.winner_list)\n",
    "\n",
    "        print('The losers are')\n",
    "        print(self.loser_list)\n",
    "        print('\\n')\n",
    "\n",
    "\n",
    "    def check_terminal_condition(self):\n",
    "        loser_num = len(self.loser_list)\n",
    "\n",
    "        if loser_num == 0:\n",
    "            print('The auction ends because every buyer gets one house.')\n",
    "            print('\\n')\n",
    "            return True\n",
    "\n",
    "        p_mat = (self.ϵ + self.p)[:,None] @ np.ones(loser_num)[None,:]\n",
    "        self.loser_surplus_value = self.v[:,self.loser_list] - p_mat\n",
    "        self.loser_decision = (self.loser_surplus_value > 0).any(axis = 0)\n",
    "\n",
    "        return ~(self.loser_decision.any())\n",
    "\n",
    "\n",
    "    def submit_bid(self):\n",
    "        bid_info = self.allocation_history[-1].copy()  # we only record the bid info of winner\n",
    "\n",
    "        loser_num = len(self.loser_list)\n",
    "        p_mat = (self.ϵ + self.p)[:,None] @ np.ones(loser_num)[None,:]\n",
    "        self.loser_surplus_value = self.v[:,self.loser_list] - p_mat\n",
    "        self.loser_decision = (self.loser_surplus_value > 0).any(axis = 0)\n",
    "\n",
    "        active_loser_list = np.array(self.loser_list)[self.loser_decision]\n",
    "        active_loser_surplus_value = self.loser_surplus_value[:,self.loser_decision]\n",
    "        active_loser_choice = self.find_argmax_with_randomness(active_loser_surplus_value)\n",
    "\n",
    "        # we retain the unique house index and increasing the corresponding bid price\n",
    "        house_bid = list(set(active_loser_choice))\n",
    "        self.p[house_bid] += self.ϵ\n",
    "\n",
    "        # we record the bidding information from active losers\n",
    "        bid_info_active_loser = {}\n",
    "        for house_num in house_bid:\n",
    "            bid_info_active_loser[house_num] = active_loser_list[active_loser_choice == house_num]\n",
    "\n",
    "        # we update the bidding information according to the bidding from actice losers\n",
    "        for house_num in bid_info_active_loser.keys():\n",
    "            bid_info[house_num] = bid_info_active_loser[house_num]\n",
    "        self.bid_info_history.append(bid_info)\n",
    "\n",
    "        print('The bid information is')\n",
    "        ymtb = pt.PrettyTable()\n",
    "        ymtb.field_names = ['House Number', *bid_info.keys()]\n",
    "        ymtb.add_row(['Buyer', *bid_info.values()])\n",
    "        print(ymtb)\n",
    "\n",
    "        print('The bid prices for houses are')\n",
    "        ymtb = pt.PrettyTable()\n",
    "        ymtb.field_names = ['House Number', *self.house_list]\n",
    "        ymtb.add_row(['Price', *self.p])\n",
    "        print(ymtb)\n",
    "\n",
    "        self.winner_list=[np.random.choice(bid_info[ii]) for ii in bid_info.keys()]\n",
    "        self.winner_history.append(self.winner_list)\n",
    "\n",
    "        self.allocation = {house_num:[winner] for house_num,winner in zip(bid_info.keys(),self.winner_list)}\n",
    "        self.allocation_history.append(self.allocation)\n",
    "\n",
    "        loser_set = set(self.buyer_list).difference(set(self.winner_list))\n",
    "        self.loser_list = list(loser_set)\n",
    "        self.loser_history.append(self.loser_list)\n",
    "\n",
    "        print('The winners are')\n",
    "        print(self.winner_list)\n",
    "\n",
    "        print('The losers are')\n",
    "        print(self.loser_list)\n",
    "        print('\\n')\n",
    "\n",
    "\n",
    "    def start_auction(self):\n",
    "        print('The Ascending Bid Auction for Houses')\n",
    "        print('\\n')\n",
    "\n",
    "        print('Basic Information: %d houses, %d buyers'%(self.n, self.m))\n",
    "\n",
    "        print('The valuation matrix is as follows')\n",
    "        ymtb = pt.PrettyTable()\n",
    "        ymtb.field_names = ['Buyer Number', *(np.arange(self.m))]\n",
    "        for ii in range(self.n):\n",
    "            ymtb.add_row(['House %d'%(ii), *self.v[ii,:]])\n",
    "        print(ymtb)\n",
    "\n",
    "        print('The reservation prices for houses are')\n",
    "        ymtb = pt.PrettyTable()\n",
    "        ymtb.field_names = ['House Number', *self.house_list]\n",
    "        ymtb.add_row(['Price', *self.r])\n",
    "        print(ymtb)\n",
    "        print('The minimum increment of bid price is %.2f' % self.ϵ)\n",
    "        print('\\n')\n",
    "\n",
    "        ctr = 1\n",
    "        if self.check_kick_off_condition():\n",
    "            print('Auction starts successfully')\n",
    "            print('\\n')\n",
    "            print('Round %d'% ctr)\n",
    "\n",
    "            self.submit_initial_bid()\n",
    "\n",
    "            while True:\n",
    "                if self.check_terminal_condition():\n",
    "                    print('Auction ends')\n",
    "                    print('\\n')\n",
    "\n",
    "                    print('The final result is as follows')\n",
    "                    print('\\n')\n",
    "                    print('The allocation plan is')\n",
    "                    ymtb = pt.PrettyTable()\n",
    "                    ymtb.field_names = ['House Number', *self.allocation.keys()]\n",
    "                    ymtb.add_row(['Buyer', *self.allocation.values()])\n",
    "                    print(ymtb)\n",
    "\n",
    "                    print('The bid prices for houses are')\n",
    "                    ymtb = pt.PrettyTable()\n",
    "                    ymtb.field_names = ['House Number', *self.house_list]\n",
    "                    ymtb.add_row(['Price', *self.p])\n",
    "                    print(ymtb)\n",
    "\n",
    "                    print('The winners are')\n",
    "                    print(self.winner_list)\n",
    "\n",
    "                    print('The losers are')\n",
    "                    print(self.loser_list)\n",
    "\n",
    "                    self.house_unsold_list = list(set(self.house_list).difference(set(self.allocation.keys())))\n",
    "                    print('The houses unsold are')\n",
    "                    print(self.house_unsold_list)\n",
    "\n",
    "                    self.total_revenue = self.p[list(self.allocation.keys())].sum()\n",
    "                    print('The total revenue is %.2f' % self.total_revenue)\n",
    "\n",
    "                    break\n",
    "\n",
    "                ctr += 1\n",
    "                print('Round %d'% ctr)\n",
    "                self.submit_bid()\n",
    "\n",
    "            # we compute the surplus matrix S and the quantity matrix X as required in 1.1\n",
    "            self.S = np.zeros((self.n, self.m))\n",
    "            for ii,jj in zip(self.allocation.keys(),self.allocation.values()):\n",
    "                self.S[ii,jj] = self.v[ii,jj] - self.p[ii]\n",
    "\n",
    "            self.Q = np.zeros((self.n, self.m + 1))  # the last column records the houses unsold\n",
    "            for ii,jj in zip(self.allocation.keys(),self.allocation.values()):\n",
    "                self.Q[ii,jj] = 1\n",
    "            for ii in self.house_unsold_list:\n",
    "                self.Q[ii,-1] = 1\n",
    "\n",
    "            # we sort the allocation result by the house number\n",
    "            house_sold_list = list(self.allocation.keys())\n",
    "            house_sold_list.sort()\n",
    "\n",
    "            dict_temp = {}\n",
    "            for ii in house_sold_list:\n",
    "                dict_temp[ii] = self.allocation[ii]\n",
    "            self.allocation = dict_temp\n",
    "\n",
    "        else:\n",
    "            print('The auction can not start because of high reservation prices')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eb409852",
   "metadata": {},
   "source": [
    "Let’s use our class to conduct the auction described in one of the above examples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1d055ac4",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "v = np.array([[8,5,9,4],[4,11,7,4],[9,7,6,4]])\n",
    "r = np.array([2,1,0])\n",
    "ϵ = 1\n",
    "\n",
    "auction_1 = ascending_bid_auction(v, r, ϵ)\n",
    "\n",
    "auction_1.start_auction()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "29b3f280",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "# the surplus matrix S\n",
    "\n",
    "auction_1.S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2b718efe",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "# the quantity matrix X\n",
    "\n",
    "auction_1.Q"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c35a4f7b",
   "metadata": {},
   "source": [
    "## Robustness Checks\n",
    "\n",
    "Let’s do some stress testing of our code by applying it to  auctions characterized by different matrices of private values.\n",
    "\n",
    "**1. number of houses = number of buyers**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ba058765",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "v2 = np.array([[8,5,9],[4,11,7],[9,7,6]])\n",
    "\n",
    "auction_2 = ascending_bid_auction(v2, r, ϵ)\n",
    "\n",
    "auction_2.start_auction()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dbe0e339",
   "metadata": {},
   "source": [
    "**2. multilple excess buyers**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7c495887",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "v3 = np.array([[8,5,9,4,3],[4,11,7,4,6],[9,7,6,4,2]])\n",
    "\n",
    "auction_3 = ascending_bid_auction(v3, r, ϵ)\n",
    "\n",
    "auction_3.start_auction()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51a7b50a",
   "metadata": {},
   "source": [
    "**3. more houses than buyers**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "40ae2347",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "v4 = np.array([[8,5,4],[4,11,7],[9,7,9],[6,4,5],[2,2,2]])\n",
    "r2 = np.array([2,1,0,1,1])\n",
    "\n",
    "auction_4 = ascending_bid_auction(v4, r2, ϵ)\n",
    "\n",
    "auction_4.start_auction()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93cf2053",
   "metadata": {},
   "source": [
    "**4. some houses have extremely high reservation prices**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9d4123ce",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "v5 = np.array([[8,5,4],[4,11,7],[9,7,9],[6,4,5],[2,2,2]])\n",
    "r3 = np.array([10,1,0,1,1])\n",
    "\n",
    "auction_5 = ascending_bid_auction(v5, r3, ϵ)\n",
    "\n",
    "auction_5.start_auction()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73bca60a",
   "metadata": {},
   "source": [
    "**5. reservation prices are so high that the auction can’t start**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "545e1aa2",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "r4 = np.array([15,15,15])\n",
    "\n",
    "auction_6 = ascending_bid_auction(v, r4, ϵ)\n",
    "\n",
    "auction_6.start_auction()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "adf848c4",
   "metadata": {},
   "source": [
    "## A Groves-Clarke Mechanism\n",
    "\n",
    "We now decribe an alternative way for society to allocate $ n $  houses to $ m $ possible buyers in a way that maximizes\n",
    "total value across all potential buyers.\n",
    "\n",
    "We continue to assume that each buyer can purchase at most one house.\n",
    "\n",
    "The mechanism  is a very special case of a Groves-Clarke mechanism [[Groves, 1973](https://python.quantecon.org/zreferences.html#id22)], [[Clarke, 1971](https://python.quantecon.org/zreferences.html#id23)].\n",
    "\n",
    "Its special structure substantially simplifies writing Python code to find an optimal allocation.\n",
    "\n",
    "Our mechanims works like this.\n",
    "\n",
    "- The values $ V_{ij} $ are private information to person $ j $  \n",
    "- The mechanism makes each person $ j $ willing to  tell a social planner his private values $ V_{i,j} $ for all $ i = 1, \\ldots, n $.  \n",
    "- The social planner  asks all potential bidders to tell the planner  their private values $ V_{ij} $  \n",
    "- The social planner tells no one these, but uses them to allocate houses and set prices  \n",
    "- The mechanism is designed in a way that makes all prospective buyers want to tell the planner their private values  \n",
    "  - truth telling is a dominant strategy for each potential buyer  \n",
    "- The planner finds a house, bidder pair with highest private value by computing\n",
    "  $ (\\tilde i, \\tilde j) = \\operatorname{argmax} (V_{ij}) $  \n",
    "- The planner assigns house $ \\tilde i $ to buyer $ \\tilde j $  \n",
    "- The planner charges buyer $ \\tilde j $ the price $ \\max_{- \\tilde j} V_{\\tilde i,  j} $, where   $ - \\tilde j $ means all $ j $’s except $ \\tilde j $.  \n",
    "- The planner creates a   matrix of private values for the remaining houses $ -\\tilde i $ by deleting row (i.e., house) $ \\tilde i $ and column (i.e., buyer) $ \\tilde j $ from $ V $.  \n",
    "  - (But in doing this, the planner keeps track of the  real names of the bidders and the houses).  \n",
    "- The planner returns  to the original step and repeat it.  \n",
    "- The planner iterates until all $ n $  houses  are allocated and the charges for  all $ n $ houses are set.  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b1ffe7e2",
   "metadata": {},
   "source": [
    "## An Example Solved by Hand\n",
    "\n",
    "Let’s see how our Groves-Clarke algorithm would work for the following simple  matrix $ V $ matrix of private values\n",
    "\n",
    "$$\n",
    "V =\\begin{bmatrix} 10 & 9 & 8 & 7 & 6 \\cr\n",
    "                    9 & 9 & 7 & 6 & 6 \\cr\n",
    "                    8 & 6 & 6 & 9 & 4 \\cr\n",
    "                    7 & 5 & 6 & 4 & 9 \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "**Remark:** In the first step, when the highest private value corresponds to more than one house, bidder pairs, we choose the pair with the highest sale price. If a highest sale price corresponds to two or more pairs with highest private values, we randomly choose one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "352550ef",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "np.random.seed(666)\n",
    "\n",
    "V_orig = np.array([[10, 9, 8, 7, 6],  # record the origianl values\n",
    "                   [9, 9, 7, 6, 6],\n",
    "                   [8, 6, 6, 9, 4],\n",
    "                   [7, 5, 6, 4, 9]])\n",
    "V = np.copy(V_orig)  # used iteratively\n",
    "n, m = V.shape\n",
    "p = np.zeros(n) # prices of houses\n",
    "Q = np.zeros((n, m)) # keep record the status of houses and buyers"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "392b1286",
   "metadata": {},
   "source": [
    "**First assignment**\n",
    "\n",
    "First, we find house, bidder pair with highest private value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cee2cb07",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "i, j = np.where(V==np.max(V))\n",
    "i, j"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3213f99",
   "metadata": {},
   "source": [
    "So, house 0 will be sold to buyer 0 at a price of 9. We then update the sale price of house 0 and the status matrix Q."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b7cedfbf",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "p[i] = np.max(np.delete(V[i, :], j))\n",
    "Q[i, j] = 1\n",
    "p, Q"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa66d03f",
   "metadata": {},
   "source": [
    "Then we remove row 0 and column 0 from $ V $. To keep the real number of houses and buyers, we set this row and this column to -1, which will have the same result as removing them since $ V \\geq 0 $."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a753f151",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "V[i, :] = -1\n",
    "V[:, j] = -1\n",
    "V"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00753de0",
   "metadata": {},
   "source": [
    "**Second assignment**\n",
    "\n",
    "We find house, bidder pair with the highest private value again."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7dc80288",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "i, j = np.where(V==np.max(V))\n",
    "i, j"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28c2d197",
   "metadata": {},
   "source": [
    "In this special example, there are three pairs (1, 1), (2, 3) and (3, 4) with the highest private value. To solve this problem, we choose the one with highest sale price."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "986787df",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "p_candidate = np.zeros(len(i))\n",
    "for k in range(len(i)):\n",
    "    p_candidate[k] = np.max(np.delete(V[i[k], :], j[k]))\n",
    "k, = np.where(p_candidate==np.max(p_candidate))\n",
    "i, j = i[k], j[k]\n",
    "i, j"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab4f5279",
   "metadata": {},
   "source": [
    "So, house 1 will be sold to buyer 1 at a price of 7. We update matrices."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e33b65a9",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "p[i] = np.max(np.delete(V[i, :], j))\n",
    "Q[i, j] = 1\n",
    "V[i, :] = -1\n",
    "V[:, j] = -1\n",
    "p, Q, V"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "27281d03",
   "metadata": {},
   "source": [
    "**Third assignment**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f952ee14",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "i, j = np.where(V==np.max(V))\n",
    "i, j"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f45b43e",
   "metadata": {},
   "source": [
    "In this special example, there are two pairs (2, 3) and (3, 4) with the highest private value.\n",
    "\n",
    "To resolve the  assignment, we choose the one with highest sale price."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b86726dd",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "p_candidate = np.zeros(len(i))\n",
    "for k in range(len(i)):\n",
    "    p_candidate[k] = np.max(np.delete(V[i[k], :], j[k]))\n",
    "k, = np.where(p_candidate==np.max(p_candidate))\n",
    "i, j = i[k], j[k]\n",
    "i, j"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28fd45c8",
   "metadata": {},
   "source": [
    "The two pairs even have the same sale price.\n",
    "\n",
    "We randomly choose one pair."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aa5954ba",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "k = np.random.choice(len(i))\n",
    "i, j = i[k], j[k]\n",
    "i, j"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b0be010",
   "metadata": {},
   "source": [
    "Finally, house 2 will be sold to buyer 3.\n",
    "\n",
    "We update matrices accordingly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "80eba561",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "p[i] = np.max(np.delete(V[i, :], j))\n",
    "Q[i, j] = 1\n",
    "V[i, :] = -1\n",
    "V[:, j] = -1\n",
    "p, Q, V"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8588c08c",
   "metadata": {},
   "source": [
    "**Fourth assignment**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2ee79600",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "i, j = np.where(V==np.max(V))\n",
    "i, j"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3fc2d84",
   "metadata": {},
   "source": [
    "House 3 will be sold to buyer 4.\n",
    "\n",
    "The final outcome  follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c038dd23",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "p[i] = np.max(np.delete(V[i, :], j))\n",
    "Q[i, j] = 1\n",
    "V[i, :] = -1\n",
    "V[:, j] = -1\n",
    "S = V_orig*Q - np.diag(p)@Q\n",
    "p, Q, V, S"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "74b2ade8",
   "metadata": {},
   "source": [
    "## Another Python Class\n",
    "\n",
    "It is efficient to assemble our calculations in a single Python Class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "81fc09a3",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "class GC_Mechanism:\n",
    "\n",
    "    def __init__(self, V):\n",
    "        \"\"\"\n",
    "        Implementation of the special Groves Clarke Mechanism for house auction.\n",
    "\n",
    "        Parameters:\n",
    "        ----------\n",
    "        V: 2 dimensional private value matrix\n",
    "\n",
    "        \"\"\"\n",
    "\n",
    "        self.V_orig = V.copy()\n",
    "        self.V = V.copy()\n",
    "        self.n, self.m = self.V.shape\n",
    "        self.p = np.zeros(self.n)\n",
    "        self.Q = np.zeros((self.n, self.m))\n",
    "        self.S = np.copy(self.Q)\n",
    "\n",
    "    def find_argmax(self):\n",
    "        \"\"\"\n",
    "        Find the house-buyer pair with the highest value.\n",
    "        When the highest private value corresponds to more than one house, bidder pairs,\n",
    "        we choose the pair with the highest sale price.\n",
    "        Moreoever, if the highest sale price corresponds to two or more pairs with highest private value,\n",
    "        We randomly choose one.\n",
    "\n",
    "        Parameters:\n",
    "        ----------\n",
    "        V: 2 dimensional private value matrix with -1 indicating revomed rows and columns\n",
    "\n",
    "        Returns:\n",
    "        ----------\n",
    "        i: the index of the sold house\n",
    "\n",
    "        j: the index of the buyer\n",
    "\n",
    "        \"\"\"\n",
    "        i, j = np.where(self.V==np.max(self.V))\n",
    "\n",
    "        if (len(i)>1):\n",
    "            p_candidate = np.zeros(len(i))\n",
    "            for k in range(len(i)):\n",
    "                p_candidate[k] = np.max(np.delete(self.V[i[k], :], j[k]))\n",
    "            k, = np.where(p_candidate==np.max(p_candidate))\n",
    "            i, j = i[k], j[k]\n",
    "\n",
    "            if (len(i)>1):\n",
    "                k = np.random.choice(len(i))\n",
    "                k = np.array([k])\n",
    "                i, j = i[k], j[k]\n",
    "        return i, j\n",
    "\n",
    "    def update_status(self, i, j):\n",
    "        self.p[i] = np.max(np.delete(self.V[i, :], j))\n",
    "        self.Q[i, j] = 1\n",
    "        self.V[i, :] = -1\n",
    "        self.V[:, j] = -1\n",
    "\n",
    "    def calculate_surplus(self):\n",
    "        self.S = self.V_orig*self.Q - np.diag(self.p)@self.Q\n",
    "\n",
    "    def start(self):\n",
    "        while (np.max(self.V)>=0):\n",
    "            i, j = self.find_argmax()\n",
    "            self.update_status(i, j)\n",
    "            print(\"House %i is sold to buyer %i at price %i\"%(i[0], j[0], self.p[i[0]]))\n",
    "            print(\"\\n\")\n",
    "        self.calculate_surplus()\n",
    "        print(\"Prices of house:\\n\", self.p)\n",
    "        print(\"\\n\")\n",
    "        print(\"The status matrix:\\n\", self.Q)\n",
    "        print(\"\\n\")\n",
    "        print(\"The surplus matrix:\\n\", self.S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f11e70f8",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "np.random.seed(666)\n",
    "\n",
    "V_orig = np.array([[10, 9, 8, 7, 6],\n",
    "                   [9, 9, 7, 6, 6],\n",
    "                   [8, 6, 6, 9, 4],\n",
    "                   [7, 5, 6, 4, 9]])\n",
    "gc_mechanism = GC_Mechanism(V_orig)\n",
    "gc_mechanism.start()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea28f8ce",
   "metadata": {},
   "source": [
    "### Elaborations\n",
    "\n",
    "Here we use some additional notation designed to conform with standard notation in parts of the VCG literature.\n",
    "\n",
    "We want to verify that our pseudo code is indeed a **pivot mechanism**, also called a **VCG** (Vickrey-Clarke-Groves) mechanism.\n",
    "\n",
    "- The mechanism is named after [[Groves, 1973](https://python.quantecon.org/zreferences.html#id22)], [[Clarke, 1971](https://python.quantecon.org/zreferences.html#id23)], and [[Vickrey, 1961](https://python.quantecon.org/zreferences.html#id24)].  \n",
    "\n",
    "\n",
    "To prepare for verifying this, we add some notation.\n",
    "\n",
    "Let $ X $ be the set of feasible allocations of houses under the protocols above (i.e., at most one house to each person).\n",
    "\n",
    "Let $ X(v) $ be the allocation that the mechanism chooses for matrix $ v $ of private values.\n",
    "\n",
    "The mechanism maps a matrix $ v $ of private values into an $ x \\in X $.\n",
    "\n",
    "Let $ v_j(x) $ be the value that person $ j $ attaches to allocation $ x \\in X $.\n",
    "\n",
    "Let $ \\check t_j(v) $ the payment that the mechanism charges person $ j $.\n",
    "\n",
    "The  VCG mechanism chooses the allocation\n",
    "\n",
    "\n",
    "<a id='equation-eq-gc1'></a>\n",
    "$$\n",
    "X(v)  = \\operatorname{argmax}_{x \\in X} \\sum_{j=1}^m v_j(x) \\tag{74.1}\n",
    "$$\n",
    "\n",
    "and charges person $ j $ a “social cost”\n",
    "\n",
    "\n",
    "<a id='equation-eq-gc2'></a>\n",
    "$$\n",
    "\\check t_j(v) = \\max_{x \\in  X} \\sum_{k \\neq j} v_k(x) -  \\sum_{k \\neq j} v_k(X(v)) \\tag{74.2}\n",
    "$$\n",
    "\n",
    "In our setting, equation [(74.1)](#equation-eq-gc1) says that the VCG allocation allocates houses to maximize the total value of the successful prospective buyers.\n",
    "\n",
    "In our setting, equation [(74.2)](#equation-eq-gc2) says that the mechanism charges people for the externality that their presence in society imposes on other prospective buyers.\n",
    "\n",
    "Thus, notice that according to equation [(74.2)](#equation-eq-gc2):\n",
    "\n",
    "- unsuccessful prospective buyers pay $ 0 $ because removing  them from “society” would not affect the allocation chosen by the mechanim  \n",
    "- successful prospective buyers pay the difference between the total value society could achieve without them present and the total value that others present in society do achieve under the mechanism.  \n",
    "\n",
    "\n",
    "The generalized second-price auction described in our pseudo code above does indeed satisfy (1).\n",
    "We want to compute $ \\check t_j $ for $ j = 1, \\ldots, m $ and compare with $ p_j $ from the second price auction."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5723141c",
   "metadata": {},
   "source": [
    "### Social Cost\n",
    "\n",
    "Using the GC_Mechanism class, we can  calculate the social cost of each buyer.\n",
    "\n",
    "Let’s see a simpler example with private value matrix\n",
    "\n",
    "$$\n",
    "V =\\begin{bmatrix} 10 & 9 & 8 & 7 & 6 \\cr\n",
    "                    9 & 8 & 7 & 6 & 6 \\cr\n",
    "                    8 & 7 & 6 & 5 & 4 \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "To begin with, we implement the GC mechanism and see the outcome."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2e30f402",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "np.random.seed(666)\n",
    "\n",
    "V_orig = np.array([[10, 9, 8, 7, 6],\n",
    "                   [9, 8, 7, 6, 6],\n",
    "                   [8, 7, 6, 5, 4]])\n",
    "gc_mechanism = GC_Mechanism(V_orig)\n",
    "gc_mechanism.start()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "353a397e",
   "metadata": {},
   "source": [
    "We exclude buyer 0 and calculate the allocation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ff962c8a",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "V_exc_0 = np.copy(V_orig)\n",
    "V_exc_0[:, 0] = -1\n",
    "V_exc_0\n",
    "gc_mechanism_exc_0 = GC_Mechanism(V_exc_0)\n",
    "gc_mechanism_exc_0.start()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b31faad4",
   "metadata": {},
   "source": [
    "Calculate the social cost of buyer 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f6ffc5c6",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "print(\"The social cost of buyer 0:\",\n",
    "     np.sum(gc_mechanism_exc_0.Q*gc_mechanism_exc_0.V_orig)-np.sum(np.delete(gc_mechanism.Q*gc_mechanism.V_orig, 0, axis=1)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "41da229a",
   "metadata": {},
   "source": [
    "Repeat this process for buyer 1 and buyer 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5a4e24e2",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "V_exc_1 = np.copy(V_orig)\n",
    "V_exc_1[:, 1] = -1\n",
    "V_exc_1\n",
    "gc_mechanism_exc_1 = GC_Mechanism(V_exc_1)\n",
    "gc_mechanism_exc_1.start()\n",
    "\n",
    "print(\"\\nThe social cost of buyer 1:\",\n",
    "     np.sum(gc_mechanism_exc_1.Q*gc_mechanism_exc_1.V_orig)-np.sum(np.delete(gc_mechanism.Q*gc_mechanism.V_orig, 1, axis=1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3ef3d34c",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "V_exc_2 = np.copy(V_orig)\n",
    "V_exc_2[:, 2] = -1\n",
    "V_exc_2\n",
    "gc_mechanism_exc_2 = GC_Mechanism(V_exc_2)\n",
    "gc_mechanism_exc_2.start()\n",
    "\n",
    "print(\"\\nThe social cost of buyer 2:\",\n",
    "     np.sum(gc_mechanism_exc_2.Q*gc_mechanism_exc_2.V_orig)-np.sum(np.delete(gc_mechanism.Q*gc_mechanism.V_orig, 2, axis=1)))"
   ]
  }
 ],
 "metadata": {
  "date": 1714442505.6057816,
  "filename": "house_auction.md",
  "kernelspec": {
   "display_name": "Python",
   "language": "python3",
   "name": "python3"
  },
  "title": "Multiple Good Allocation Mechanisms"
 },
 "nbformat": 4,
 "nbformat_minor": 5
}