Distributed systems, like the internet, are difficult to organize with traditional computer science methods. Due to the size and dynamics of these systems, the design of protocols and algorithms needs to focus on scalability, adaptivity and the possibility of distributed execution. When autonomous subsystems compete for available resources, game theoretic methods are required to design mechanisms providing participants with incentives to cooperate.
Facility Location in Dynamic Networks
The Facility Location problem is an important research topic in theoretical computer science. It is often used as a benchmark problem for the development of both sequential and distributed approximation algorithms for a range of problems. A reason for this is the locality which is inherent to the Facility Location problem. The objective is to determine a cost-effective placement of services or resources onto nodes of a computer network. On the one hand, one wants to find a resource allocation that uses as few nodes a possible (since this is associated with very high costs), while on the other hand, one wants to guarantee all customers to be as close as possible to the resources or service-providing nodes. Here, proximity is defined by the quality of the latencies, which are on the connections between clients and service providing nodes.
Difficulties of the Facility Location variant studied by us are the huge size of the considered networks and the ongoing dynamics which these networks are subjected to. Due to the continuous changes in the networks, it has become necessary to use algorithms that adapt their solutions to the current situation while providing a solution with sufficient quality at all times.
This is only possible with the use of distributed and especially local algorithms. The algorithms only use information from their immediate environment for their decisions and thus can handle arbitrarily scaling networks. This local approach allows a direct and rapid handling of the dynamics occurring in the networks: Nodes themselves can make faster decisions and calculate more new solutions than a centralized entity ever could.
A Probabilistic Consumer Model for Internet Advertisement
Advertisement Placement
A central problem in advertising products on the internet is the selection of websites that are very likely visited by potential customers. We assume that customer’s purchase stimulus grows stronger every time he observes an advertisement on the respective product. Placement remains to be optimized, such that the expected return on sales is maximized, while the advertisement costs remain low.
This problem can be approached twofold. If we assume a single provider, we first have to be able to rate a selection of websites. We are interested in the expected time it takes for a customer to visit a certain number of them. Additionally, we are looking for an algorithmic way to determine a solution that is as good as possible.
On the current internet market, there are several providers with similar products, so the problem is given a game-theoretical aspect. Several providers compete for the same customers and influence each other. They follow strategies, such as to never place their own advertisements next to the competitors’ ones or to be present in only certain areas of the internet. We analyze such strategies with the goal to obtain optimal rules of conduct for systems with multiple egotistical actors. Those strategies are used in huge dynamic markets as researched in the collaborative research centre On-The-Fly Computing.
Contact:
Dipl.-Inform. Peter Pietrzyk
E-mail: Peter.Pietrzyk@hni.upb.de
Phone: +49 (0) 5251/60 64 69
Dipl.-Math. Andreas Cord-Landwehr
E-mail: Andreas.Cord-Landwehr@hni.upb.de
Phone: +49 (0) 5251/60 64 27
Jun.-Prof. Dr. rer.nat. Patrick Briest
E-mail: Patrick.Briest@hni.upb.de
Phone: +49 (0) 5251/60 64 57
Maximilian Drees, M.Sc.
E-mail: Maximilian.Drees@hni.upb.de
Phone: +49 (0) 5251/60 64 34
