Algorithmic Game Theory

Analysing Strategic Behaviour and Different Disaggregation Methods

Algorithmic game theory studies scenarios involving the interaction of rational agents. On the one hand, we look at scenarios in which the actors choose resources to satisfy their (resource-depended) demands. On the other hand, we analyse different disaggregation methods, especially with regard to their stability.

Fair Resource Allocation in Networks

In networks, there are typically different limited resources available. Different participants like service providers in the Internet need different resources with different priorities. For some applications, a high throughput is needed, for others a low latency. This heterogeneity can be modelled as a game in which each service provider acts as a player and has an individual objective function. We use a linear combination of two well-known functions or different aggregation functions on the single values. We consider states which are reached by using natural dynamics if we assume the players to be rational and selfish. Besides pure equilibria, we also focus on the existence of approximate equilibria as well as the quality, complexity and computation of these states.

In a further model in this scenario, we consider fair cost sharing. Instead of dividing the occurring costs at a resource proportional to the participating players and their consumption, we use a cost function in which each player has to pay exactly the value by which increased the total costs at this resource when he joined it.

Resource Allocation in Networks

Disaggregation of User Feedback

In the context of the Collaborative Research Center 901, we consider a market where services are compositions of a number of basic services. Customers may be asked to evaluate the quality of the composed service after purchase. Typically, the quality of basic services is not observable and hence cannot be evaluated. The question we are studying is whether it is possible to use consumer evaluations on final service compositions to assess the quality of basic services. As there are many consumers evaluating, two questions arise. First, how should we aggregate evaluations across customers? And, second, how should we disaggregate information on composed services to arrive at a valuation of components?

Aggregation and Disaggregation of User Feedback

Supported by:

  • DFG Collaborative Research Centre 901 “On-TheFly Computing”, subproject A3
  • EU project (IP) “Foundational Research on MULTIlevel comPLEX networks and systems” (MULTIPLEX)