Sahil Dev

Sahil Dev

Research Partner: Vivekjyoti Banerjee

Advisor: Dr. John Dickerson 

Optimal Auction Design Through Deep Learning!

We are designing a machine learning model that is capable of acting as an auctioneer and performing the ideal auction.

An ideal auction has the following characteristics:

1. Agents are incentivized to bid honestly. If an agent values a product at a certain price, it does not benefit them to bid less than that price in order to get the item for a lower price.

2. The auctioned items go to the agents who value those items the highest.

3. The agents who receive those items spend as much as they are willing to spend on them.

Terminology:

Machine Learning - a type of computer program that is capable of learning on its own and making decisions

Deep Learning - a machine learning model designed to mimic the learning capabilities of the human brain

Auction - a system where many agents are competing to buy a product and maximize their utility

Agent - a player in a competitive system; in auctions, agents are bidders

Bid - the amount that an agent says they are willing to spend on a product, whether or not it is the true amount they would be willing to spend

Utility - the value an agent gets from a result; if an agent values an item at $100, but they only spend $80 on it, their utility is $20; if the auctioneer values an item at $50 and sells it for $80, their utility is $30

Regret - informally, the regret someone might feel when they realize that if they had bid less, they could have paid less for the item; if the "winning" agent wins an item for $80, but the second-highest bid is $70, their regret is $10 because they could have saved about $10 by bidding just over $70.

We want to design an ideal auction because it makes everyone happy. The auctioneer gets as much money as anyone is willing to spend, and the agents that get the items are the agents that value them the most. Any other agents would not be willing to spend as much on those items as the agents that received it.

Why you should care:

Big companies like Google and Amazon care a lot about optimal auction design. You may not know it, but every time you see an advertisement, an auction is taking place with thousands of agents bidding to be the winner of that ad space so they can advertise just for you. Of course, these agents are computer programs designed to get that ad space for as cheap as possible, but also run as fast as possible so you don't notice a thing when ads load.

If we are able to perform this auction ideally, all agents benefit, including the auctioneer. The auctioneer gets the highest possible revenue, since that is the most anyone is willing to pay for that ad space, and the winner is the agent that values it the most, and the agent does not regret bidding as high as they bid.

Logbook

Note: This research has been a whole lot of reading so far and not much of anything else. We won't get to look at fun coding stuff for a while. I'm sorry. On the bright side, I don't think this project will involve that ghastly looking Virtual Machine nonsense everyone else has been dealing with, so that's nice.

March 5, 2020:

We have been doing a lot of reading lately. Dr. Dickerson is asking us to read four or five chapters from this 775-page textbook called Algorithmic Game Theory, which totals to something like 150 pages, so I expect this to take a few weeks. The first chapter of the textbook gives a good introduction to game theory as a whole. It discusses Nash equilibria and dominant strategies in detail. A dominant strategy is a strategy that a player can take in a "game" such that it is the best strategy regardless of the strategies of other players. Nash equilibrium is a set of strategies for the players in the game such that no player can change their strategy to get a better outcome.

The Dutting paper Optimal Auctions through Deep Learning, states that their neural network architecture with two hidden layers of 100 nodes (and about 10000 edges) took about nine hours, or 540 minutes, to train. The choice of this architecture appears to be somewhat arbitrary. We suggest that an architecture with three hidden layers of 10 nodes (about 300 total edges) could drastically reduce training time, but hopefully still maintain sufficient, or even better performance.

300 edges / 10000 edges = ? minutes / 540 minutes

16 minutes = 540 minutes * 300 edges / 10000 edges

So we can reduce the 9 hour training period to under 20 minutes just by reducing the number of nodes in the hidden layers. We will need functioning code to replicate this in order to test if our hypothesis is correct.

February 27, 2020:

I finally have a project! I will be working on designing an optimal auction through deep learning. This is based on the 2017 paper from Paul Dutting et al., which discusses how auctions can be designed to perform optimally from the auctioneer’s perspective to maximize the value returned from the auction. Auctions are not a deterministic system, and a bidder has a strategic incentive to lie about how much they value a certain product. The paper proposes the use of neural networks (a form of machine learning) to implement this auction method. For this to work, we need the following information:

1. The value distribution of the auctioned product(s); e.g. 80% of the time, this product sells between $10 and $15.

2. Each agent's stated value for the product(s).

We should also note that not all auction methods are equal. There are auctions where the auctioneer states progressively increasing values or decreasing values, blind auctions where the highest bidder pays what they wrote, blind auctions where the highest bidder pays what the second-highest bidder wrote, and more. Each method has its advantages and disadvantages. The neural network works by receiving all the valuations in a blind way, then assigning products and prices accordingly.

Also, I have a friend! I will be working on this research with my friend Vivekjyoti Banerjee.

February 20, 2020:

I have met with my advisor now, and we discussed possible research into Universal Adversarial Training. There actually is not very much research done about UAT yet, but it can present a huge security risk if systems have not been trained against adversarial data. The good thing is, UAT can be extrapolated out to almost any form of data modeling; all it takes is some method of perturbing data, whether it is adding a static effect to an image, scrambling some words in a piece of text, or messing with the pitch of an audio recording.

We can actually train against this adversarial data by perturbing our own data and teaching the model to classify the data correctly still. This makes the model more robust. We can also defend against adversarial data by teaching the model to classify adversarial data into its own category of "perturbation". A good solution may consist of a combination of both methods.

February 13, 2020:

I have read through a few of Dr. Dickerson's previous papers, which is what I am presenting this week. His most recent projects include:

Scalable Robust Kidney Exchange: provides a method for pairing and swapping kidney donors who are incompatible with their receivers

Universal Adversarial Training: covers efficient production and detection of adversarial information; the results of this paper provide a theoretical method to determine whether data is adversarial

Balancing the Tradeoff between Profit and Fairness in Rideshare Platforms During High-Demand Hours: “[aims] to design an online matching policy that balances the tradeoff between the two objectives of maximizing profit and fairness”; limit the ability of rideshare drivers to select riders based on implicit or explicit bias

Adversarial Training is when training data is introduced to a machine learning model that is intentionally incorrect or even has some strange underlying perturbation, which can compromise the performance of the model.

February 6, 2020:

At this point, I have not had a chance to select a project yet. I will be meeting with my research advisor, Dr. John Dickerson next week to discuss a potential project. I have looked up a little bit about machine learning to refresh myself for the presentation, though I have taken a few classes in data science and machine learning, so nothing is new to me yet.