From da43b9311a53daa9c120735c60e9ba9e1955990c Mon Sep 17 00:00:00 2001 From: Markus Teich Date: Fri, 14 Oct 2016 23:40:38 +0200 Subject: fix preparation for M+1st price auctions --- tex-stuff/math.tex | 20 +++++++++++++------- 1 file changed, 13 insertions(+), 7 deletions(-) (limited to 'tex-stuff/math.tex') diff --git a/tex-stuff/math.tex b/tex-stuff/math.tex index ae66608..60568cf 100644 --- a/tex-stuff/math.tex +++ b/tex-stuff/math.tex @@ -192,13 +192,19 @@ M+1st Price Auction schemes. We took the simplest one, interlacing the bids, so that no two bidders are allowed to bid the same price. On the application level we will still handle $k_{\text{app}}$ different prices, but within libbrandt we will multiply that by a factor of $n$ to get $k_{\text{lib}}=nk_{\text{app}}$. -Then each bidder $i$ is only allowed to place his bid $b$ on prices $p$ with -$\exists a\in{[1,k_{\text{app}}]}:b=an-i+1$. This condition will be checked by -an additional proof in the first round of the protocol and ensures that the -bidders with a lower index win in case of ties. This expansion will be done -right at the beginning of an auction by libbrandt. In the remaining part about -the M+1st Price Auction Protocols we will use $k$ instead of $k_{\text{lib}}$, -so $k$ will be divisible by $n$ without remainder. + +The bids are scaled up as well by the mapping $\forall +i\in{[1,n]}:b_{i,\text{lib}}=b_{i,\text{app}}n-i+1$. Therefore the set of +allowed bids for bidder $i$ is defined as $\{j|k_{\text{lib}}-j+1\equiv +i\pmod{n}\}$. + +This restriction will be checked by an additional proof in the first round of +the protocol and ensures that the bidders with a lower index win in case of +ties. The expansion will be done right at the beginning of an auction by +libbrandt and the reverse mapping is applied before reporting the auction +outcome to the application, so this expansion is transparent to the application. +In the remaining part about the M+1st Price Auction Protocols we will use $k$ +instead of $k_{\text{lib}}$, so $k$ will be divisible by $n$ without remainder. Unfortunately this tie breaking simplification has the downside of revealing the identity and bid of the bidder who had the highest bid amongst the losing -- cgit v1.2.3