Algorithmic Game Theory

Analysing Strategic Behaviour in the Context of Resource Allocation and User Evaluations

Algorithmic game theory studies scenarios involving the interaction of rational agents. It is concerned with statements regarding the results of strategic behaviour when agents are in competition with each other and develops algorithms which are based on these results. Network Function Virtualisation is an example for a scenario here, which also occurs in the context of the Collaborative Research Centre 901 “On-The-Fly-Computing”.

Algorithmic game theory is concerned with issues relating
to the results of strategic actions of autonomous actors. We
investigate the computational complexity of outcome forecasts
for the distributed allocation of resources, e.g. capacities in
networks or the computing powers of servers. Furthermore,
we examine the behaviour of dynamic adjustment processes
when agents repeatedly respond to the actions of other agents:
What time do such processes have? Do they converge to stable
states? How inefficient are these systems?

Allocation of Resources

We have dealt in several studies with the allocation of
resources among strategic participants from a game theoretical
point of view. We have used the well-known model of
Congestion Games for this purpose. A lot of players who, for
example, represent our OTF service providers in the context
of the Collaborative Research Centre 901 can use a set of
resources (such as services from service providers), but these
resources are associated with costs depending on the number
of users. Each player has different amounts of resources available
depending on what they have to offer. We investigated
two specific characteristics of this model. On the one hand,
we looked at heterogeneous participants who pursue different
objective functions and examined which guarantees remain
about equilibrium states. On the other hand, we have dealt
with the distribution of costs and have considered a different
model than the proportional distribution. The focus was on the
calculation of approximate equilibria in this model.

Disaggregation of User Ratings

We also addressed the issue of consistent processing of
user reviews of composed services. The aim was to add
ratings to the individual services from data on composed
services. Since these are ratings of many individual users,
we discuss combinations of aggregation (about users) and
disaggregation (in individual ratings). Assuming that the
result should not depend on the order of the application of
these operations, it turns out that the (weighted) arithmetic
mean as aggregator together with the Shapley value as
disaggregator represents a meaningful combination. Here,
it means that it does not depend on the above mentioned
order and that the manipulation possibilities of a single
user are strongly limited. The characterisation of this solution
by an extended list of axioms is still open.

Supported by:

  • DFG Collaborative Research Centre 901 “On-TheFly Computing”, subproject A3