6
$\begingroup$

I am newbie with machine learning. In order to learn more I decided to try solving a specific problem/game that I have in mind. The problem is the following:

I have a list of $N$ items which are auctioned in a random sequence. There are $n$ participants to the auction. They have a fixed budget and $M$ items to buy. Each agent will decide whether to make a bid and how much to bid each time a new item is auctioned; bids have to be integer numbers and the agent with the highest bid gets the item; correspondingly its budget is decreased of the amount of the bid. Items, once bought, cannot be released, so if an agent has already bought $M$ items, it cannot participate to other auctions. If nobody places a bid, the item is discarded and the auction continues with the next one. Thus, an agent ends its auction if it has bought $M$ items or the available budget has reached $0$.

At the end, the value of the final set $I$ of items items bought by each agent is evaluated by an external oracle function $f(I)$. The function is not explicitly known and will in general be more complicated that the sum of values of each item, e.g. two items may be essential parts of a single object and are worthless one without the other. However, it is known that $$ f(I \cup J) \geq f(I) + f(J).$$ Each agent is free to evaluate the function $f$ on any set of items. Each agent's goal is to maximize the value of $f(I)$, where $I$ is the set of items successfully bought by that agent.

Which strategy would you suggest to approach this problem? At each time, the agent has information about the list of items that have been auctioned, which participant has bought each of them and the costs, so that it knows the number of available slots and budget of each participant. According to these data, it must decide if and how much to bid for each item. Note that the list of items is fixed and the function $f$ are fixed. I suppose this is a reinforcement learning question but I don't have a clear understanding of how the input would be structured in this case.

$\endgroup$
  • $\begingroup$ Why do you think that machine learning is the right approach? Why are you limiting yourself to a solution based on machine learning? This sounds like it might potentially be an XY problem. $\endgroup$ – D.W. Aug 21 '17 at 19:12
  • $\begingroup$ About the XY problem, I am not sure that Machine learning is the optimal approach, I just though it was a possible approach to this problem. As I was interested into finding a strategy for this auction problem and in learning ML, I though it could be nice to combine the two things! If you have suggestions about other approaches to the problem (even not involving ML) I would be interested! $\endgroup$ – abenassen Aug 21 '17 at 23:47
  • $\begingroup$ Does every agent use the same function $f$ for evaluating their set of items, or does each agent have its own function $f$? (e.g., maybe Alice prefers paintings of the sea, but Bob prefers statues?) $\endgroup$ – D.W. Aug 22 '17 at 1:11
  • $\begingroup$ The function $f$ is the same for every agent. $\endgroup$ – abenassen Aug 22 '17 at 1:32
0
$\begingroup$

There probably is no solution that will be optimal for all possible situations. So, you are left with heuristics: trying to find a technique that will often work well in the situations that arise for you in practice, but with no guarantees that it will work for everything. Machine learning might be one possible such approach.

You might start by trying to learn the function $f$. You said that the agent is free to invoke $f$ on any set of items. Therefore, a possible starting point is to try to learn a model that predicts $f$: e.g., given a representation of the set $I$, outputs an estimate for $f(I)$. You can easily collect a training set by querying $f$ on many sets and observing its output.

Reinforcement learning would be a plausible approach to the broader problem. There are many approaches to reinforcement learning, but in one typical approach, we need to compute a function $V(a)$ that computes the anticipated value of being in state $a$ (i.e., if the agent is in state $a$ and then follows its policy/strategy, what do we expect the final value of $f(I)$ will be?). Normally machine learning techniques are used to build a model that estimates the value of $V(a)$. This then requires forming a representation of the state $a$, i.e., a feature vector that summarizes or extract relevant information about the current state. The current state includes: (a) the set of items bought by this agent so far, (b) the budget and number of slots available to this agent, (c) the number and list of items remaining to be bought, and (d) information about the other agents, including what they've bought so far and the number of slots and budget remaining to them. So, you can think about how to build a feature vector that represents them, then apply standard methods for reinforcement learning to learn the function $V(a)$.

I suggest reading a tutorial on reinforcement learning to learn more about how it works and see some examples in a simpler setting.

$\endgroup$
  • $\begingroup$ Thanks for your answer, this is exactly what I had in mind. I thought of taking a neural network whose input is a matrix $A_{ij}$, $(N+1)\times n$, where $N$ is the number of items and $n$ the number of agents. Then, $A_{ij}=1$ if the item $i$ is owned by the agent $j$. Last row contains the scaled budgets. When an item is auctioned the corresponding row is set to 0.5 for all agent. The output is a number in $[0,1]$ corresponding to the fraction of the remaining budget that should be bid. Not sure if this is a solid implementation though! $\endgroup$ – abenassen Aug 22 '17 at 11:26
  • $\begingroup$ @abenassen, the way to find out is to try it and see. Often with machine learning, you'll need to do a fair bit of experimentation and just see what works best. $\endgroup$ – D.W. Aug 22 '17 at 17:26

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.