Information Technology Reference
In-Depth Information
winning profitable goods with complementarities in future auctions. We present
initial results using a straightforward machine learning technique that is able
to learn intuitive bidding strategies that can be interpreted from an economic
perspective for this dicult problem. In a strongly competitive scenario with
intelligent bidders, the profits of the agents are reduced to near marginal costs.
This is in line with economic theory, but our experimental results are a validation
for a large-scale, adaptive MAS.
We present a more in-depth analysis from a game theoretical perspective. We
link results of our experiments to outcomes of
n
2 player iterated prison-
ers' dilemma (
nIP D
). Analytical results are first presented for two players. The
dominant strategy of the individual agents is to overbid for items in auctions
in order to achieve higher profits in future auctions at the expense of the other
agent. We show that the profits of both agents are however lower if both agents
follow this strategy. This is in line with the two player prisoners' dilemma game
where higher returns are received if both agents cooperate (do not overbid),
but the dominant strategy is for both agents to defect (overbid). We generalize
these results for
n>
2 players and show that defection, i.e. strategic overbid-
ding, is the dominant strategy for all agents. Our analysis indicates that the
computational results of the experiments are indicative for the properties of
the domain with complementarities. More sophisticated learning algorithms for
the agents will arrive at similar results in equilibrium. However, we argue, and
support through experimental results, that agents can have a first-mover advan-
tage when choosing a more fine-tuned defect strategy, especially under changing
circumstances.
The rest of the document is structured as follows: Section 2 formally defines
the agents and the auctions. Section 3 discusses how an agent can exploit expec-
tation of future auctions using machine learning techniques. Section 4 presents
experimental results where strategically bidding agents compete with opponents
for various representative settings. Section 5 presents the game theoretical link
to the
nIP D
. Section 6 discusses how bidders, given our results, can still benefit
from adaptive bidding strategies. Section 7 discusses and concludes.
≥
2
The Model: Agents and Auctions
In this section we present the model of the agents and auctions. We use a rel-
atively simple model with a limited problem domain. The model is however of
sucient complexity to allow for profitable opportunistic bidding by agents, es-
pecially if faced by opposing agents that do not consider the worth of future
auctions. We present the agents and auctions from a logistics perspective to fa-
cilitate some of the intuitions in the choice of the model. We discuss the agents
as representing trucks that transport the won loads.
Each
agent
i
from the set
Agents
,where
2, has an integer
capacity >
0 constraint. Each auctioned load
l
has a dimension of 1. The number
of the loads won by agent
agent
j
cannot exceed its capacity. Agents are limited
in their capacity and must target the loads that maximize utility. Finally, the
|
Agents
|≥
