Grant Title:
COMBINATORIAL AUCTIONS IN CoW
Author:
Mr Nicola (name) Dimitri (surname)
About You:
I am a Professor of Economics at the University of Siena (Italy) one of the oldest Universities in the world, dating back to 1240. The University, as well as the School/Department of Economics , are sensed to be among the best in the country, with extended international visibility. The University was originally promoted and supported by the Siena Municipality, since Siena was an important City State for about 300 years, until 1555. The city is one of the best preserved medieval cities in Italy, and for this reason Unesco Heritage.
Besides my research activity, which you could see on my CV, it may be of interest for you to know that in recent years I’ve been teaching in Siena three courses: Monetary Economics (Undergraduate), Game Theory (Master), Advanced Microeconomics Master and PhD). I’ve also gave several lectures/courses elsewhere, also on the Economics of Blockchain and Cryptocurrencies.
My interest on combinatorial auctions in CoW is motivated by long-standing involvement with auctions (since 2004) as Teacher, Researcher and Consultant (Italian Ministry of Economics/Foreign Affairs) and more recent involvement (2017) concerning decentralized ledgers and cryptocurrencies.
On my Departmental Web page you can find an updated CV of mine Curriculum – Nicola Dimitri
In yellow I highlighted the works and activities related to blockchain/cryptocurrencies while in blue those related to combinatorial auctions.
For your perusal, below I extracted those recent publications which are closer to the project content
Bitcoin Mining as a Contest, Ledger, 2, 31-37 (2017)
Combinatorial Advertising Internet Auctions, Electronic Commerce Research and
Applications, 32, 49-56 (2018).
The Blockchain Technology; Some Theory and Applications, Maastricht School of Management Working Paper, 2017/3 (2017)
Transaction Fees, Block Size Limit and Auctions in Bitcoin, Ledger, 4, 68-81, (2019)
Monetary Dynamics with “Proof of Stake”, Frontiers in Blockchain doi: 10.3389/fbloc.2021.443966 (2021)
Consensus: Proof of Work, Proof of Stake and Structural Alternatives, in Enabling the Internet of Value, (Vadgama N., Xu J, Tasca P. eds) Springer Verlag, (2022)
Proof of Stake in Algorand, ACM Distributed Ledger Technologies: Research and Practice (2022)
The Economics of Consensus in Algorand, Fintech, 2, 164-179 (2022)
Quadratic Voting in Blockchain, Information,18, 305 (2022)
Liquid Proof-of-Stake in Tezos: An Economic Analysis, Information, 13, 556, (2022)
Who are the arbitrageurs? Empirical evidence from Bitcoin traders in the Mt. Gox exchange platform (with Saggese P, Belmonte A., Bohme R., Facchini A.), Journal of Economic Behavior and Organization, 213, 251-270 (2023)
The Economic Value of Dual Token Blockchains, Mathematics, 11, 1-19, 3757 (2023)
Voting in DAOs (forthcoming) ACM Distributed Ledger Technologies: Research and Practice (2023)
Artificial Intelligence: Economic Perspectives and Models (with Naudè W., Gries T., eds) (forthcoming) Cambridge University Press (2024)
Notice also that I’ve been recently engaged in other blockchain-related projects, receiving research grants from Algorand, Tezos, VeChain, NEAR, NEO, and that I am Associate Editor of the journals “Frontiers in Blockchain” and “IET Blockchain”. Besides having been used for those Blockchains internal decision making, as you can see, most of the research projects performed for other blockchains has been published in international scholarly journals.
Grant Category:
Other/miscellaneous
Grant Description:
COMBINATORIAL AUCTIONS IN CoW
By Nicola Dimitri
Professsor of Ecoonomics
University of Siena- Italy
Introduction
As a follow up to discussions with Andrea Canidio, and comments from CoW members, on the potential interest of CoW, for considering to implement Combinatorial Auctions (CA), I decided to submit the following project for funding.
Transactions and Solvers in CoW
To discuss how CA my be introduced in CoW’s activity consider the following, simplest, example. Suppose there are two proposed transactions. In the first transaction, call it 〖 T〗_1 a user supplies the quantity〖 s〗_a of token A to be exchanged against units of token B. If, currently, the prevailing price at which A and B exchange in the market is〖 p〗_ab, expressed in terms of A/B, then the number of B units received in exchange is clearly 〖 s〗_b=〖 s〗_a/〖 p〗_ab .
In the second transaction, call it 〖 T〗_2, a user supplies the quantity〖 s〗_c of token C to be exchanged against units of token D. If, currently, the prevailing price at which C and D exchange in the market is〖 p〗_cd, expressed in terms of C/D, then the number of D units received in exchange is clearly 〖 s〗_d=〖 s〗_c/〖 p〗_cd .
Notice that any quantity s_b^‘>〖 s〗_b and s_d^’>〖 s〗_d of, respectively, B and D, that would be exchanged against〖 s〗_a and 〖 s〗_c, will be preferred by the users to the market condition. Therefore, in the example the market condition represents a lower bound (LB), a floor, to the amount of token acceptable by the users in trading the token through CoW. In what follows the notion of LB, which we may also call Minimum Exchanged Quantity (MEQ), is going to play an important role.
Fees
The above considerations do not take into account the exchange fees, as well as possible other payments, time delays and additional frictions that may occur when exchanging directly in the market. We indicate with〖 f〗_ab the fees to be paid to trade token A against B and 〖 f〗_cd the fees to be paid to trade token C and against B. Finally, we assume that f_ab are paid in terms of B tokens while〖 f〗_cd in terms of D tokens. Therefore, against 〖 s〗_a the number of B tokens units obtained by the user would be 〖 s〗_b-〖 f〗_ab=〖 s〗_a/〖 p〗_ab and, similarly, 〖 s〗_d-〖 f〗_cd=〖 s〗_c/〖 p〗_cd would be the number of D token units against obtained by the user against〖 s〗_c.
Bearing in mind that exchange fees, transactions fees etc can play an important role in users’ decisions, to keep the exposition simple, henceforth we assume they are equal to zero. Indeed, the presence of fees will leave the main arguments basically unaltered.
Ether Equivalence of 〖 s〗_b and 〖 s〗_d
An additional notion that, below, will be operationally useful is the one of “Ether Equivalence” to an amount of tokens. Suppose E stands for Ether tokens while〖 p〗_eb and 〖 p〗_ed are the prices at which, respectively, B and D exchange in the market with E.
Then 〖 q〗_eb=〖 p〗_eb 〖 s〗_b and 〖 q〗_ed=〖 p〗_ed 〖 s〗_d represent, respectively, the quantity of Ethers that can be obtained by trading〖 s〗_a in 〖 T〗_1 and〖 s〗_c in 〖 T〗_2.
We shall define〖 q〗_eb and 〖 q〗_ed as the “Ether Equivalent” quantities exchanged against, respectively, 〖 s〗_a and 〖 s〗_b. The notion of Ether Equivalence will be useful to harmonize the different units of measurements appearing in the two transactions.
It is important to point out that Ether Equivalence is only an internal, accounting, criterion of CoW to compare transactions with different units of measurements. Therefore, when a transaction will be implemented,CoW will return to the user the token that she required, and not Ethers. The calculation of Ether Equivalence will be made at the exchange rate prevailing at the time when the order of exchange was submitted.
Notice that such “equivalence” operation could have been done with respect to any other token/currency exchanged in the market. Indeed, we could have computed, with the same criterion, the Bitcoin, €, USD etc equivalence. Assuming absence of arbitrage possibilities in the market, then which token/currency is used to calculate the equivalence will not matter for our main goal, which is to harmonize the units of measurement of the different transactions.
In what follows, we shall always assume that CoW will assign transactions to Solvers to maximize the total Ether Equivalent (EE) of the Solvers’ proposals.
2.2 Solvers and Incentives
Now, still for simplicity, suppose there are two Solvers X and Y, with 〖 q〗_ebx and 〖 q〗_eby in 〖 T〗_1, 〖 q〗_edx and 〖 q〗_edy in 〖 T〗_2 respectively, the EE of X and Y, in the two transactions taken individually. Furthermore, define 〖 q〗_ebdx, 〖 q〗_ebdy to be the EE concerning both transactions.
Before proceeding, the following issue needs to be pointed immediately. As above, leaving aside for the sake of exposition exchange fees etc., the solutions proposed by the Solvers need to satisfy the following incentive constraints. Start with〖 T〗_1 only; if s_b^* is the number of B token units offered by X to the user then it should satisfy the following weak inequality s_b^*≥〖 s〗_b=〖 s〗_a/〖 p〗_ab . Indeed, if the inequality was not satisfied the user would have been better off by exchanging 〖 s〗_a directly in the market, without contacting CoW. That is, according to the terminology already introduced at the beginning of the Section, it must be s_b^*≥LB. Therefore, it must also be that 〖 q〗_ebx=〖 p〗_eb s_b^*≥〖 p〗_eb 〖 s〗_b, namely 〖 q〗eb 〖 s〗b represents the lower bound for q_ebx. An analogous reasoning applies for〖 q〗(eby,) 〖 q〗(edx,) 〖 q〗_edy. By extending the argument, for 〖 q〗_ebdx the Solver will have to specify the amount of B tokens, and of D tokens, that will propose against, respectively, 〖 s〗_a and 〖 s〗_c. If s_b^() and s_d^() are such amounts the Solver proposal now will need to satisfy two constraints: s_b^()≥〖 s〗_b, s_d^()≥〖 s〗_d which will of course, in turn, satisfy 〖 q〗_ebdx=〖 p〗_eb s_b^()+〖 p〗_ed s_d^()≥〖 p〗_eb s_b+〖 p〗_ed s_d
From now on, we shall assume that all the solvers’ proposals satisfy the above incentive constraints.
Table 1 below illustrates the proposals
Table 1
〖 T〗_1 〖 T〗_2 〖 T〗_1+〖 T〗_2
X 〖 q〗_ebx 〖 q〗_edx 〖 q〗_ebdx
Y 〖 q〗_eby 〖 q〗_edy 〖 q〗_ebdy
Notice that it may be 〖 q〗_ebdx 〖≠ q〗_ebx+〖 q〗_edx because, when a solver operates on both auctions may exploit financial, positive/negative, sinergies which could induce the above inequality. Such “sinergies” could be due to fixed costs, specialization in exchanging some niche tokens etc.
Table 2 below presents a numerical example of Table 1.
Table 2
〖 T〗_1 〖 T〗_2 〖 T〗_1+〖 T〗_2
X 〖 q〗_ebx=2 〖 q〗_edx=3 〖 q〗_ebdx=7
Y 〖 q〗_eby=3 〖 q〗_edy=1 〖 q〗_ebdy=5
If the T_1, 〖 T〗_2 and 〖 T〗_1+〖 T〗_2 are interpreted as the Solvers proposals, in related fist price sealed-bid auctions, numbers in Table 2 suggest that both solvers X,Y can offer a EE on both auctions 〖 q〗_ebdx=7,〖 q〗_ebdx=5 which are larger than the sum of the EE that they could offer in the single transactions 〖 q〗_ebx+〖 q〗_edx=5 and 〖 q〗_eby+〖 q〗_edy=4. An alternative numerical example could be as in Table 3 below
Table 3
〖 T〗_1 〖 T〗_2 〖 T〗_1+〖 T〗_2
X 〖 q〗_ebx=2 q_edx=3 〖 q〗_ebdx=4
Y 〖 q〗_eby=3 〖 q〗_edy=1 〖 q〗_ebdy=5
where the EE on the single transactions 〖 q〗_edx+〖 q〗_eby=6 are, globally, larger than the EE on both transactions 〖 q〗_ebdx=4 and 〖 q〗_ebdy=5.
The above numerical examples are instrumental to introduce the following section.
Auctions Formats
In this section we discuss three possible auctions (seald bid) formats with which CoW could use to assign the two transactions to the Solvers.
Independent Auctions Only
The first possible format that CoW could consider is to ask the Solvers to propose an offer for the two transactions individually, and then allocate each transaction to the best offer. In this case the equivalence transformation would not be needed since the comparison will be between transactions of the same type.
Drawing from Table 2, in Table 4 below 〖 T〗_1 would be assigned to Y and 〖 T〗_2 would be assigned to X, with the total EE being 〖 q〗_edx+〖 q〗_eby=6.
Table 4
〖 T〗_1 〖 T〗_2
X 〖 q〗_ebx=2 〖 q〗_edx=3
Y 〖 q〗_eby=3 〖 q〗_edy=1
What could be for CoW the advantages of individual auctions? The main one is that on single transactions there could be very specialised Solvers who may offer extremely good conditions, which they could not offer when they are forced to make a proposal for both auctions. As for possible disadvantages, the main ones are the following two. First, the global EE could be larger if the combined auction on both transactions would be allowed, due to economies of scale etc. Secondly, with individual auctions one of the two transactions may receive no offer, because none of the Solvers is interested on it, which may be inefficient for CoW’s business. Broadly speaking, Solvers which are quite good on both transactions may be disadvantaged in the competition as compared to Solvers which are very good on single transactions.
Combined Auctions Only
Drawing from Table 3, in this case we would have
Table 5
〖 T〗_1+〖 T〗_2
X 〖 q〗_ebdx=4
Y 〖 q〗_ebdy=5
which solves some of the problems with individual auctions, but may generate a total EE which is lower than what CoW could have obtained with individual auctions, as when comparing Table 4 with Table 5. Additionally, those Solvers which specialize only on a certain category of transactions may be disadvantaged in the competition for transactions.
Combinatorial Auctions
Combinatorial auctions allow Solvers to offer for individual transactions, combined transactions or for both, as in Table 2 that we replicate below
Table 6
〖 T〗_1 〖 T〗_2 〖 T〗_1+〖 T〗_2
X 〖 q〗_ebx=2 q_edx=3 〖 q〗_ebdx=7
Y 〖 q〗_eby=3 〖 q〗_edy=1 〖 q〗_ebdy=5
Table 6 contains what are called “conditional” or “contingent” offers. The interpretation is the following: for example〖 “q〗_ebx=2 is valid if 〖 T〗_1 only would be assigned to X” while “〖 q〗_ebdy=5 is valid if both〖 T〗_1 and 〖 T〗_2 would be assigned to Y”. Since transactions are allocated to maximize the total EE then it would be convenient for CoW to assign both of them to X, since〖 q〗_ebdx=7 is larger than any other possible assignment combination.
Therefore, CA are the most general auction formats, which may give the opportunity to specialised Solvers as well as to generalist Solvers, those which are sufficiently good in all transactions, to show their best proposals. This way CoW will not have to choose, from the beginning, between individual only, or combined only, transaction auctions.
What could be the limitations of CA? The first one may be the computational burden in finding the EE maximizing assignment of transactions, when their number grows. Indeed, with N transactions, if CoW would allow Solvers to present an offer for every possible combination of transactions each Solver can submit up to 〖(2〗^N-1) offers, which is exponentially growing in N.
For example, in Table 7 below it is immediate to see that it is optimal to assign the first transaction to Y and the second to X as the sum of their EEs is 8.
Table 7
〖 T〗_1 〖 T〗_2 T_1+〖 T〗_2
X 〖 q〗_ebx=2 q_edx=4 〖 q〗_ebdx=7
Y 〖 q〗_eby=4 〖 q〗_edy=1 〖 q〗_ebdy=3
However, in general, with N transactions and K Solvers, when allowing to offer for every combination then CoW may receive up to 〖K(2〗^N-1) prroposals which could be a very large number. So, finding the optimal assignment of transactions may be computationally demanding. For this, there are two main approaches: on the one hand, CoW may decide to admit only a limited number of combinations while, on the other hand, CoW may decide to use a software to determine the optimal assignment.
Implementation by CoW
Based on the above considerations, in this Section I sketch the steps that CoW may undertake to implement Combinatorial Auctions.
For the sake of generality, in what follows we assume that Solvers are allowed to submit proposals for any possible combination of transactions. We also assume that this is not an obligation for the Solvers.
Collect 〖 T〗_1,〖 T〗_2,…,〖 T〗_N transactions on Ethereum. We call T the set of transactions. As above, each Solver can submit up to 〖(2〗^N-1) proposals, one for each possible non-empty subset of transactions A⊆T.
For each transaction, CoW considers the market price and computes the number of tokens/currencies that would be exchanged in the market against the supplied tokens/currencies. For example, suppose in the generic transaction〖 T〗_n the user supplies 10BTC in exchange of $. On 21 September 2023, at h11.22 a.m., the exchange rate $/BTC on CoinMarketCap was 26858$. Therefore, on the market the user could have obtained 268580$ with 10BTC
For each subset of transactions A⊆T ask the Solvers to provide a proposal (if the Solvers wish to submit one) for the transactions included in A, under the condition that for each transaction in A the proposed exchange quantity is no lower than the one obtainable on the market.
Considering again the above〖 T〗_n, against 10BTC the Solvers cannot propose less than 268580$. Indeed, as we previously said, otherwise the user could trade directly 10BTC on the market and obtain 268580$ in return, which in fact represents the lower bound 〖 L〗n for that transaction.
This implies that CoW, when asking Solvers to send their proposals, will first have to specify the N lower bounds 〖 L〗(1,)….,〖 L〗_N, that the Solvers have to satisfy in any of their proposals. Such lower bounds apply to a single transaction, as well as to combined transactions, proposals.
For each Solver’s proposal CoW calculates the Ether Equivalent of each transaction in that proposal.
Suppose the above T_n transaction belongs to a proposal, submitted by a Solver, defined by the subset A={T_n,T_m }⊆T of transactions, where T_m is another generic transaction. Suppose also that, in the proposal, for T_n the amount of $ offered by the Solver is 270000$. Since the exchange rate $/Ether was, at the same hour and date, 1611$, the Ether Equivalent of 270000$ is 270000/1611∼168E. If, for example, the Ether Equivalence of T_m, in the A proposal, is 200E, it follows that the Ether Equivalence for the A proposal is (168E+200E=368E).
Compute the EE of all proposals submitted by each Solver. To better illustrate the point, below we extend the previous 2 transactions 2 Solvers example, to a 3 transactions, hence T={T_1,T_2,T_3 }, with 5 Solvers example. The 7 possible subsets of transactions on which Solvers can submit a proposal are:
A={T_1 }, B={T_2 }, C={T_3 }, AB={T_1,T_2 }, AC={T_1,T_3 },BC={T_2,T_3 },ABC={T_1,T_2,T_3 }
Table 8 below illustrates a possible scenario of Ether Equivalent proposals.
Table 8
Ether Equivalent of the proposals received by CoW
A B C AB AC BC ABC
Solver 1 195 150 190 360 580
Solver2 195
Solver 3 190 160 160 360 370 570
Solver 4 195
Solver 5 192 550
Hence, based on Table 8 Solvers’ proposals, how are the transaction going to be assigned? If CoW allocates the transactions according to the Total Ether Equivalence Maximization Principle, then T_1 should be allocated to Solver 1, T_2 to solver 2 and T_3 to Solver 3 as the sum oof the three Ether Equivalent individual proposals, (195+195+195=585) is larger than any other possible combination of proposals received by CoW.
Finally, CoW will pay the users behind the three transactions the tokens, currencies, requested in those transactions. As said, the Ether Equivalence computation will only be internal to CoW to harmonize the different units of measurements and select among proposals. Indeed, for example if T_1=$/BTC,T_2=ADA/SOL,T_3=ALGO/BNB their comparison would be difficult to make, and this is why CoW would want to compute EE. However, once the notion of EE has been used by CoW to assign the transactions then the user behind T_1 will receive $ against BTC, the one behind T_2 will receive ADA against SOL and the one behind T_3 will receive ALGO against BNB, according to the proposals made by the winning Solvers.
Finally, notice that the empty cells in Table 8 are due either to Solvers not proposing for those combinations or, alternatively, to proposals which CoW excluded they did not satisfy LB in the incentive constraints previously discussed.
Project proposal
Based on the above Sections, the ultimate goal of the project would consist in a rigorous, though widely accessible, written report on how to implement Combinatorial Auctions in CoW, with an extended discussion of their pros and cons for CoW. If of interest for CoW, the report may later substantiate in a paper to be submitted to an international peer reviewed journal for publication. This may further enhance the visibility of the method for CoW and help the ecosystem in this sense. In my CV you can see that this is what happened with most of the research grants that I received from the Algorand, Tezos, Near, Neo and Vechain blockchains.
Since its introductions in 1982 A Combinatorial Auction Mechanism for Airport Time Slot Allocation on JSTOR CA have been extensively used in many areas. The number of academic and applied contributions on CA is by now massive and, given my understanding of CoW’s activity, I believe it should be of interest for CoW to explore the potentials of CA.
Grant Goals and Impact:
As above, the main goal of the report is to produce a document which CoW could use as a supporting element when considering whether or not to implement Combinatorial Auctions. Under appropriate conditions, implementing such auctions may induce meaningful benefits for CoW and, consequently its all ecosystem.
Milestones:
I’m expecting to work for about 40 days on the project, spread over one year. However, since I much like this project I’m of course open to discussion on this
Milestone Due Date Payment
Milestone 0 start of the project
Milestone 1 after 6 months (upon approval of the draft report)
Milestone 2 after 12 Months (upon approval of the final version of the report)
Milestone1
This milestone will consist in the a partial, incomplete, version of the written report. Despite being partial, I plan to include in it most of the fundamental elements concerning the implementation of Combinatorial Auctions in CoW, advantages and limitations.
Milestone 2
The last milestone would consist in the final version of the report, which will include several findings and recommendations for CoW. As said, the report intends to support CoW’s decision making in relation to Combinatorial Auctions
Funding Request:
If well designed and well implemented the benefits induced by combinatorial auctions on CoW’s business can potentially be large. Indeed, they may spur a higher level of competition among Solvers, which would translate into better conditions offered by Solvers to CoW, hence to CoW’s users. This would of course positively reflect into future business perspectives for CoW. As said, since I expect to work for 40 days on the project, and because in EU for scientific consultancy I’m normally paid more than 500€ per day, the requested funding would be 18.000 USD, about 307000 CoW tokens and 19000 xDAI token. (exchange rates from CoinMarketCap, 26 September 2023). Again, since I much like the project I’m open too discussion on this.
Budget Breakdown:
Since I’m planning to work uniformly, throughout the 12 months, on the project, I propose the funds to be split into 3 instalments of the same size 6000 US, to be paid at milestones 0, 1,2.
Gnosis Chain Address (to receive the grant):
0x8849…20c34a METAMASK
Other Information:
I think all the relevant information is on my CV.
Referral:
As I mentioned at the beginning of the project, the idea of submitting a project proposal came after discussions with Andrea Canidio
Terms and Conditions:
By submitting this grant application, I acknowledge and agree to be bound by the CoW DAO Participation Agreement and the CoW Grant Terms and Conditions.
|