3
$\begingroup$

I had the following idea of Reinforcement Learning:

  • There is the RL agent and the environment. The agent can execute actions, sends them to the environment and receives an observation and a reward (a float).
  • Accounting problem: The reward might be delayed.
  • Learning algorithms: Q-learning is one example. It basically tries to learn the mapping between State x Action to reward and works like this

Can Reinforcement Learning work for a setting similar to Dutch auctions?

  • The agent can make 3 actions: Increase, keep or lower the price
  • The agents goal is to sell the item for the highest price. So the agent is the auctioneer.
  • The auction item does not change. The bidders are anonymous and thus don't give a hint about their behavior.
  • This means the observations are the same, only the time to the end gets lower - independently of the action of the agent.
$\endgroup$
  • $\begingroup$ Seems to be called the "optimal price control problem". $\endgroup$ – Martin Thoma Nov 6 '17 at 19:10
2
$\begingroup$

Whether or not a Dutch Auction can be framed as a reinforcement learning problem depends on whether there is meaningful state that can be changed by the auctioneer's actions.

If the bidders are behaving in a simplified rational manner* - e.g. they are working to a simple mechanic of buying the item when it reaches a price they have decided to pay - then the behaviour of the auctioneer will not make much difference, it is very formulaic as it is already part of a price optimising strategy. There is no meaningful state change between actions - the bidder valuations and attention stay fixed no matter what the auctioneer does. In an extreme, automated case, the optimal action would be to set a very high initial price and then reduce it in many small increments so as to trigger the highest purchase possible from bidders. This is not done in real auctions because it is a waste of everyone's time (and it would be weird, socially). However, it shows you a problem with the framing of the problem. In a basic rational setting, with nothing to gain or lose apart from money and value of the item, there is little room for altering strategy.

The problem becomes far more interesting when bidders are not purely rational optimisers themselves (or have some other unknown values related to the auction such as personal time they are willing to invest in the process, or rivalry with other bidders), and when some information is available about their past behaviour, or at least in general about human behaviour. In that case the problem can modelled as a Partially Observable Markov Decision Process (POMDP), and you can concern yourself with rewards that might vary due to your actions - e.g. risk of making bidders skittish with "odd" behaviour as the auctioneer. There are limits to this due to the anonymous bidders. If you kept bidder identity between items (if a single auction consisted if multiple item sales with the same bidders) then you might gain some information on each sale in order to optimise better your actions within that auction.

Another possible way to have stateful behaviour is if item ownership has value, such that market forces of supply/demand come into effect (once a bidder has one item maybe they value the next one less, or maybe more if multiple items have higher value to the bidder when kept together). Again this is only going to be relevant to the auctioneer if bidder identities remain constant for a multi-item auction, and even then only makes a difference if there is non-rational pricing behaviour in the bidders.

The main problem you will have with training RL auctioneer to work with non-rational bidders, is modelling those bidders. You could maybe bootstrap with data from real auctions with human auctioneers - this can still be done in a Q learning framework. Q-Learning can learn about optimal policy from observing non-optimal behaviour within limits, optimal actions still need to be observed, but don't have to all be in the same episodes. However, in general to improve from that model and apply reinforcement learning, you have to you put it in control. When it explored unusual actions in order to learn, that could make it a liability if real money was at stake - to defend against this you may need to keep action choice limited.


* Staying with "purely rational" approaches, you could get more sophisticated. You could maybe model the bidders as trying to predict the auctioneer and other bidder's next action, and extract the best expected value, in which case you have framed the problem more like adversarial game theory. This could make the auctioneer's actions have more impact. The most interesting part of this is occurring in the bidder though, not the auctioneer, as the bidder would have to incorporate a meaningful value to owning the item and be smart enough to second-guess other bidder's valuations.

The auctioneer's goal would then be to find the best price that the highest bidder was willing to pay, and behave so that the highest bidder predicted that a rival would bid on the next lower increment. This would be very similar to the non-rational approach in practice, but more tractable to do in simulation - you would need a good simulated model of the bidders before you could train an auctioneer, and the bidders would probably need to be RL or similar too, with both auctioneer and bidder models evolving together.

Intuitively, and assuming the game theory model was stable here, I would expect the auctioneer, with no other information to go on than the number of bidders, would have an optimal strategy where selling price decreased in increments inversely sized to some fractional power of the number of bidders, as more rivals means that bidders will predict rivals willing to pay values closer to their own evaluation. A partially stochastic policy might also be favourable to the auctioneer, as being unpredictable means that bidders cannot rely on guessing the next price reduction accurately (although they might counter that by choosing whether to bid stochastically).

$\endgroup$
  • 1
    $\begingroup$ "If the bidders are behaving in a purely rational manner - e.g. they are working to a simple mechanic of buying the item when it reaches a price they are willing to pay". I don't think that is rational. Rational for the bidder is to buy when he is willing to pay the price AND when he thinks that waiting longer will make him not get the item. Also, what if there are multiple auctions with similar items? Maybe some of which the auctioneer is not aware of? $\endgroup$ – Martin Thoma Nov 6 '17 at 21:14
  • $\begingroup$ Very interesting answer. Thank you! What I meant with my comment is that the bidders might make assumptions about the other bidders. Maybe the time to end, maybe the price for the last similar item. With "anonymous" I mainly meant that I don't have other information about the bidders. Intersting thought, I didn't think of the idea that keeping a history might change things. $\endgroup$ – Martin Thoma Nov 6 '17 at 21:28
  • $\begingroup$ Do you know of other algorithms that could be applied for the auctioneer? $\endgroup$ – Martin Thoma Nov 6 '17 at 21:29
  • $\begingroup$ @MartinThoma: You could directly search for and evaluate a policy using e.g. Genetic Algorithm. However, I think any such search faces the problem of "are the bidders rational bots" and generally whether it is worth modelling the bidders or needing to throw the algorithm into the wild to learn. I've tried to address your point by extending the answer. $\endgroup$ – Neil Slater Nov 6 '17 at 21:35
  • $\begingroup$ @MartinThoma: Yes I agree that fully rational and logical bidders would base decisions on predicting the auctioneer and bidders in order to reduce the price. I've added that, as it does point to maybe using RL to resolve things, but you will end up needing to model the bidders somehow, which is hard. $\endgroup$ – Neil Slater Nov 6 '17 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.