 |
AUTHOR: Georgiou Konstantinos
TITLE: Online Algorithms and Game Theory
RESEARCH AREAS:
- Game Theory and Networking Theory
ADVISORY COMMITTEE:
- Supervisor: Koutsoupias Elias
- Advisor: Zissimopoulos Vassilios
- Advisor: Kolliopoulos Stavros
DESCRIPTION:
We are interested in a scheduling problem know as the carpool scheduling. In this problem, a set of n people form a carpool. Each day a subset of the players will arrive to a gathering point and one should drive. A method (algorithm) for determining online which person should drive any given day is required. Any algorithm is analyzed according to the fairness it can maintain, an issue introduced by Game Theory. It is known that every deterministic algorithm can maintain Θ(n) fairness, while it is an open question to close the gap for probabilistic algorithms between Ω((logn)^1/3) and O(sqrt(nlogn)).
Moreover we are interested in distributed Mechanism Design. In the multicast cost sharing problem, a distinguished node offers a service to n agents of a tree-network. Every agent has to declare her utility for the service. We need a truthful Mechanism that decides the receiver’s set and the allocation of the cost to every agent of the set. Every Mechanism has to respect many issues and it is a challenge to reduce the communication cost of the distributed implementation of any such Mechanism for networks with constant-cost links or with costs that are defined by concave functions. In addition, a probabilistic version of distributed Mechanism could improve the communication cost, the balance of the budget and the maximization of the welfare.
|
![]](../images/rdcorner.gif){kind=small}