Invited Session Thu.2.MA 005

Thursday, 13:15 - 14:45 h, Room: MA 005

Cluster 8: Game theory [...]

Efficiency and optimization in games


Chair: Ioannis Caragiannis



Thursday, 13:15 - 13:40 h, Room: MA 005, Talk 1

Francesco Pasquale
Logit dynamics: Expected social welfare, mixing time, and metastability

Coauthors: Vincenzo Auletta, Diodato Ferraioli, Paolo Penna, Giuseppe Persiano


Logit dynamics [Blume, Games and Economic Behavior, 1993] is a randomized best response dynamics for strategic games: at every time step a player is selected uniformly at random and she chooses a new strategy according to a probability distribution biased toward strategies promising higher payoffs. This process defines an ergodic Markov chain over the set of strategy profiles, whose unique stationary distribution we regard as the long-term equilibrium concept for the game.
We are interested in the stationary performance of the game (the expected social welfare when the profiles are random according to the stationary distribution) and in the time it takes to get close to the stationary distribution (mixing time). When the mixing time is large the stationary distribution loses its appeal as equilibrium concept and we look for "regularities'' at time-scales shorter than mixing time (metastability).
In this talk we give an overview of our recent results on stationary expected social welfare, mixing time, and metastability of logit dynamics for some classes of games.



Thursday, 13:45 - 14:10 h, Room: MA 005, Talk 2

Vasilis Gkatzelis
Truthful mechanisms for proportionally fair allocations

Coauthors: Richard Cole, Gagan Goel


We study the problem of designing mechanisms to allocate a heterogeneous set of divisible goods among a set of agents in a fair manner. We consider the well known solution concept of proportional fairness that has found applications in many real-world scenarios. Although finding a proportionally fair solution is computationally tractable, it cannot be implemented in a truthful manner. To overcome this, in this paper, we give mechanisms which are truthful and achieve proportional fairness in an approximate manner. We use a strong notion of approximation, requiring the mechanism to give each agent a good approximation of its proportionally fair utility. A motivating example is provided by the massive privatization auction in the Czech republic in the early 90s.



Thursday, 14:15 - 14:40 h, Room: MA 005, Talk 3

Giorgos Christodoulou
Coordination mechanisms for selfish routing games

Coauthors: Kurt Mehlhorn, Evangelia Pyrga


We reconsider the well-studied Selfish Routing game with
affine latency functions. The Price of Anarchy for this class of
games takes maximum value 4/3; this maximum is
attained already for a simple
network of two parallel links, known as Pigou's network. We improve upon
the value 4/3, for networks of parallel links, by means of Coordination Mechanisms.


  Most online loan lenders allow getting New Jersey Loans Online without visiting a bank, straight to your bank account. They were lucky to produce Viagra Sublingual which dissolves under the tongue and penetrates into the blood causing erection faster than any other drugs.