On Knapsack Problems, Auction Mechanisms, And NFT Standards

5 min readFeb 7, 2021

1 NFT Trading: A Perspective of the Discrete World

ERC-20 standard appeared on Ethereum blockchain in 2016, brought ICO mania in 2017 and De-Fi Cambrian in 2020 to this ecosystem. At the same time period, an unignorable trend was also slowly emerging, which is named Non-fungible Token, become one of the most important complement to ERC-20. It appeared in cat cultivation in Crypto-Kitties, real estate, and household auctions in Decentraland, 3rd party on-chain trading platforms of games like Enjin, and also ENS — Ethereum Name Services ( similar to DNS, Domain Name Service on the Internet). The most important similarity of these applications is that all single token minted are heterogeneous, under the same standard: Technically, tokens share the same interfaces to interact with people or smart contracts, but their internal utility and exterior may be very different.

When we make decisions in the physical world, our allocation of stocks, cash, and cryptocurrencies proportions are continuous, but the demand for specific real estate, luxury cars, yachts, or even private jets is often discrete: The result of the decision is basically a binary decision — which means we only have a choice between 0 and 1. AMM models like Uniswap, the most important innovation on trading ERC-20 tokens, has nearly nothing to do with massive NFT transactions unless you take some compromising approaches. Examples are given by UniSocks and NFTX: Unisocks simulate ERC-721 tokens with ERC-20 tokens through socks redemption, and NFTX directly turn ERC-721 into ERC-20 through its protocols to enhance liquidity just like REITS.

Computer theorists Merkle and Hellman proposed the Knapsack problem in 1978, which keeps the problem still in the discrete world. The problem can be formulated as Given a set of items, each item has its own weight and price. How do we choose goods within the limited total weight in order to pack up the goods with the highest total value? Similar problems often appear in the fields of business, combinatorics, computational complexity theory, cryptography, and applied mathematics. In the physical world, whether they are antique traders or collectors, they will all face a more difficult problem, since different collectors have different preferences on the same set of collections.

2 On Mechanism Design: How Founders of Auctionomics won 2020 Nobel Prize in Economics

On October 12th, Robert B. Wilson and Paul R. Milgrom from Stanford University in the United States shared this honor for “improving auction theory and inventing new auction methods”. The two economists not only designed a “simultaneous multi-round auction”, but also established Auctionomics. In the period from 1994 to 2014, the US government relied on this design to acquire a total of $120B USD from the radio spectrum license auction as fiscal revenue, effectively met the discrete combination requirements from 3 to 4 major mobile ISP for frequency bands that interfere with each other and simultaneously keep the rent close to the optima.

In the book “ Discovering Prices: Auction Design in Markets with Complex Constraints”, the principle of increasing marginal cost and the theory of British auctions and Vickery auctions are particularly impressive. In Uniswap’s model, the continuous British auction of ERC-20 enables a smooth depth for trading. By replacing ERC-20 with NFT, the actual price may fall somewhere between the British auction and the Vickery auction.

3 On NFT Composability Standard: A Simple Exploration

Since 2015, the Ethereum community and Ethereum-based NFT projects have spontaneously explored the concept of NFT, and standards such as ERC-721 and ERC-1155 have been implemented.

The Ethereum community proposed ERC-998 Composable NFTs (Composable NFTs, i.e. cNFT, https://github.com/mattlockyer/composables-998). It is an extension for NFT that allowing any NFT to contain other NFTs or FTs(In ERC-20 format). When transferring cNFT, it means transferring the entire hierarchical structure and ownership of cNFT. For example, ERC-721 in the housing transaction represents the abstract whole of the house, but in fact, a house is a collection of a whole set of things, such as a unique land use right (ERC-721), fish tank (ERC-721), and fish tank In the water (ERC-20). cNFT is a natural extension.

A simplified version of composability standard — ERC1155 is introduced by Enjin, for online game items that are “somewhat homogenous”, batch processing of ERC-721 standard tokens will be easier to operate. Based on the initial design of ENJ, DEGO team also proposed their improved version: ERC908, which consume DEGO token to call contract through interfaces of ERC908 tokens.

Project Hashmask is a bold move in the domain of NFT: It has not brought its own standard to NFT users yet, but it is very hopeful that the properties, the rarity of these properties, the name changing tokens(ERC-20) that NFT contains may form a group of necessary interfaces for NFTs. At the same time, NFTX provides a confidential wrapper smart contract to repack revealed NFTs back to the status of unrevealed: Rethink popular Gatcha culture in Japan, or newly listed $POPMART(HK09992).

4 A Liquidity Design Proposed by xDeFiLabs

After referring to UniSocks, Perpetual Protocol, NFTX, and other projects, xDeFiLabs proposed a demo of the NFT Gatcha first-time auction system based on vAMM:

4.1 Mathematical model:

(vaE+ aE) * (aG+vaG) = C

4.2 Uniswap-style pool setup:

One side is the Ethereum pool, with Etherum amount aE.

There is also a number of virtual Ethereum of amount vaE.

On the other side is the NFT list. The composition of the list is {sold NFTs (wish list)}, and {unsold NFTs}. The length of the list is determined when initialized. {unsold NFTs} amount aG participates in the calculation, and the initial status of {sold NFTs (wish list)} is the empty set.

There is also a vaG parameter, the number of virtual Gatchas.

C is the constant product.

4.3 Bonding Curve

If a pool is initiated in the way that 4.1 and 4.2 proposed, gatcha price will go up (increasing marginal cost). Considering a relatively fair auction, the price of the last Gatcha in the pool will not be too expensive.

4.4 An Example:

Gatcha ask and bid prices will be discrete:

Ask price:


Bid price:


With some initial parameters setup:

1st Gatcha price fp= ~0.25ETH

Highest Gatcha price hp = ~1ETH

Initial aE = 0

Initial aG = 100

Virtual amount parameters will be deducted as:

vaG = sqrt(ep/sp) * Initial aG — Initial aG = 100

vE = (Initial aG +vaG)*fp = 50

C = vaE * (Initial aG +vaG) = 10000

Each time a Gatcha is bough from, or sold back to this pool, ask and bid price will shift accordingly.

4.5 Smart Contract Structure:

A A pool of ETH

B An ordered dictionary of ERC721, which records sold/unsold Gatcha status

C Parameters

D Contract calculating ask/bid logic, refer to Uniswap

E The confidential contracts and necessary random number generators.

F A front-end displaying necessary information.

The long-tail liquidity of the NFT marketplace will be stimulated, instead of an “Art Hype”, this setup is close to the logic of Italian art collectors to trade any possible combination of the collection in their community.

5 Conclusions

After composability has been sufficiently built, art galleries with art wishlists will be assembled to reveal the preferences of collectors, which will also attract more NFT arbitrageurs ( Scientists worked so hard on ERC-20 tokens arbitraging ). The xDeFiLabs team will also continue their exploration on the possibility of multi-round multiple auctions of long-tail NFT assets.