2
$\begingroup$

There are $N$ number of people and $X$ amount of objects with different values. Each person will choose an object and will obtain that objects value. If multiple people choose the same object then the value of the object is shared among the people. For example, If there are 2 objects and 3 people, one of the objects will be chosen by at least 2 people, thus the value of the object is divided over 2.

Each round the people make their decisions with new objects and new values, how can a person maximize their expected values accumulated from their choices in Q number of rounds, in order to win(i.e accumulated most value)? ($Q$ belongs to [1, +infinite).

Note that keeping track of other player's decisions and their accumulated values can help in future decision making.

Note: An approximation would be great as well, so far my strategy is to choose a random object at each round, I am looking for ways to maximize this strategy.

Improve this question
$\endgroup$
10
  • $\begingroup$ Are the objects between rounds unrelated or are they the same objects? seems to me that if the objects are unrelated there is not much to learn between rounds. $\endgroup$
    – Bitwise
    Nov 16, 2012 at 0:12
  • 1
    $\begingroup$ Let me understand this: so $N$ objects arrive in each round, each of which with different value ? -- I guess we know the values of the $N$ objects, but we dont know the choices of the $X - 1$ other players until they make a choice ? $\endgroup$
    – AJed
    Nov 16, 2012 at 1:57
  • 1
    $\begingroup$ @Mike G then you are assuming that players have a fixed strategy. This wasn't stated in the question. Also, if players can learn from their own and other player actions it means their strategy can change each round, so I don't see how it can be fixed or how you could learn it. $\endgroup$
    – Bitwise
    Nov 16, 2012 at 2:14
  • 1
    $\begingroup$ @rizwanhudda I am really not aware if this problem has a formal name, but the tags that I found associated with the nature of this type of problem are (learning opponent strategy under uncertainty) $\endgroup$
    – Mike G
    Nov 16, 2012 at 6:38
  • 1
    $\begingroup$ I think this is a typical example of a problem in Game Theory. You can get answers for each iteration, which is the best object to pick, so you maximize your value. You will probably be lookin in mixed strategy Nash equilibrium. $\endgroup$
    – Nejc
    Nov 16, 2012 at 9:26

2 Answers 2

Reset to default
2
$\begingroup$

One simple way, better than random choice, is to use modification of one step ExpectiMax. Each round you will give each Objects Value some new estimated value V(obj).

V(obj)= $\frac{ObjectValue(obj)}{ ( 1+ \sum\limits_{i=1}^n P_{i}(obj) )}$

where $ P_{i}(obj)$ = probability that person i will chose Object obj

And every round you will chose the one Object with greatest estimated value V.

You can choose at the beginning $ P_{i}(obj)$ to be some function over the Object Value- the bigger the value the greatest probability that it will be picked.

Learning:

From your question "Note that keeping track of other player's decisions and their accumulated values can help in future decision making." and your comment "(learning opponent strategy under uncertainty) " I guess that you need to learn the strategies of your opponents.

One way is after each game to see which Object Value was picked by each of your opponents and how the picked value differs from your expectations ($ P_{i}(obj)$). Using this information you can slightly modify the probabilities $ P_{i}(obj)$ (decrease or increase them a little for specific Object Values) and use the improved probabilities for each of the opponent in the next rounds s.

Improve this answer
$\endgroup$
9
  • $\begingroup$ I had a similar approach, but my challenge remains in adjusting the probability distributions for each player after each round, since each round, the number of objects and their values can change. For example there can be rounds with 4,5 and 6 objects respectively each having different values in each round. $\endgroup$
    – Mike G
    Nov 16, 2012 at 8:26
  • $\begingroup$ Another issue is, other players can choose a strategy that will "skew" your strategy, how can I safe guard against that? $\endgroup$
    – Mike G
    Nov 16, 2012 at 8:27
  • $\begingroup$ You can use ordering of the objects by their values and give the probability by the position in that order. So every round you will be able to order the values and make the probabilities by where is the value in that order.Or even make better distribution. $\endgroup$
    – Anton
    Nov 16, 2012 at 8:30
  • $\begingroup$ Regarding the "skew" -can you explain it more? $\endgroup$
    – Anton
    Nov 16, 2012 at 8:35
  • $\begingroup$ Another flaw in this model is, it maximizes at each round and not the over all return value. For example, consider two objects A and B with values 5 and 3 respectively and two players(player 1 and 2). This model will predict that that player A will be more likely to choose object A because it has a higher value and according to our prior we start with distributions favoring the higher valued objects. Lets assume player 1 is using this model you have described, then object A will have a higher probability than B. So to maximize value player 1 will choose object B to obtain a value of 3 instead $\endgroup$
    – Mike G
    Nov 16, 2012 at 8:39
1
$\begingroup$

First of all, I don't think there is any point in considering rounds, since each round is independent. So if the behavior of the players is not affected by the outcome of the previous rounds, they would play every round as a new round. You probably assume that there is an influence, but then this should be modeled.

Okay but lets come back to a single round. For simplicity assume you have 2 players $A,B$ and two objects with value $6$ and $8$. You can model this as a 2 player game with the following payoff matrix $$ \begin{pmatrix} 3,3 &6,8 \\8,6 & 4,4\end{pmatrix}. $$

This symmetric game has no dominant strategy. So every player should randomize its choice. We have 3 Nash equilibria, shown in the picture

enter image description here

From this I would expect that each players plays the mixed strategy, i.e., pick the item with value 3 with probability $2/7$ and otherwise pick the object with value 4.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The players can dynamically change their strategies in each successive round, playing a Mixed nash every round means the best response(to other players action's) which doesn't necessarily need to be efficient, as described in inefficient equilibriums. Remember that the objective is to accumulate the most points(over Q rounds) in order to win. $\endgroup$
    – Mike G
    Nov 16, 2012 at 9:33
  • $\begingroup$ Yeah, but all players change their strategies simultaneous, right. So how can the outcome of a previous round give new information about the current round? I mean you have public values of the goods, and possibly new goods in every round, so I don't see a chance to learn something (no strategy, no values). You are right that the equilibriums are not necessarily the most efficient outcomes, but we assume that all players play competitive, and assume that every player wants to optimize the outcome, hence assuming an equilibrium seems reasonable. $\endgroup$
    – A.Schulz
    Nov 16, 2012 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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