Page 1 of 1

Theory Tea 2013-2014

Posted: Tue Nov 12, 2013 12:05 am
by XaviannNJ
Την Τετάρτη θα έχουμε το πρώτο Theory Tea για φέτος.

Το theory tea επανέρχεται αυτή την Τετάρτη, στις 1, στην αίθουσα Α41. Για αυτή την εβδομάδα το κάνουμε Τετάρτη και αποφεύγουμε την Παρασκευή καθώς ενδέχεται να είναι κλειστό το πανεπιστήμιο.

Θα μας μιλήσει ο Ευριπίδης Μπάμπης, ο οποίος είναι καθηγητής στο
Universite Pierre et Marie Curie, στο Παρίσι
και το θέμα της ομιλίας θα είναι

Energy-efficient scheduling algorithms

Re: Theory Tea 2013-2014

Posted: Wed Nov 13, 2013 12:27 pm
by XaviannNJ
Αλλάξαμε αίθουσα λόγω πλημμύρας :!: :!: Το tea θα γινει στην Α42

Re: Theory Tea 2013-2014

Posted: Wed Nov 13, 2013 7:06 pm
by stoupeace
Πώς ήταν? Τι περίπου ειπώθηκε?

Re: Theory Tea 2013-2014

Posted: Thu Nov 21, 2013 12:49 pm
by XaviannNJ
Παρασκευή,Α31,στις 5! :smt006

Αυτη την εβδομάδα θα μας μιλήσει η Svetlana Obraztsova, από το ΕΜΠ.
Εξακολουθούν να υπάρχουν προβλήματα στην Α41, επομένως
θα γίνει στην αίθουσα Α31, στις 5.

Speaker: Svetlana Obraztsova, National Technical University of Athens

Title: Plurality Voting with Truth-biased Agents

Abstract: We study a game-theoretic model for Plurality voting, one of the most well-studied and widely-used voting rules. It is well known that the most standard game-theoretic approaches can be problematic in the sense that they lead to a multitude of Nash equilibria, many of which are counter-intuitive. Instead, we focus on a model recently proposed to avoid such issues.
The main idea of the model is that voters have incentives to be truthful when their vote is not pivotal, i.e., when they cannot change the outcome by a unilateral deviation. This modification is quite powerful and recent simulations reveal that equilibria which survive this refinement tend to have nice properties.

We undertake a theoretical study of pure Nash and strong Nash equilibria of this model under Plurality. For pure Nash equilibria we provide characterizations based on understanding some crucial properties about the structure of equilibrium profiles. These properties demonstrate how the model leads to filtering out undesirable equilibria. We also prove that deciding the existence of an equilibrium with a certain candidate as a winner is NP-hard. We then move on to strong Nash equilibria, where we obtain analogous characterizations. Finally, we also observe some relations between strong Nash equilibria and Condorcet winners, which demonstrate that this notion forms an even better refinement of stable profiles.

This is joint work with Vangelis Markakis and David Thompson.

Re: Theory Tea 2013-2014

Posted: Thu Nov 28, 2013 9:11 am
by XaviannNJ
Παρασκευή 29/11,και πάλι στην Α31,στις 5!

Αυτη την Παρασκευή θα μας μιλήσει ο Γιάννης Γιώτης για sponsored search auctions.
Θα παραμείνουμε στην Α31, (όσο παραμένουν τα προβλήματα στην Α41)

Ακολουθούν οι λεπτομέρειες,

Ομιλητής: Γιάννης Γιώτης, μεταδιδακτορικός ερευνητής, ΟΠΑ
Τίτλος: On the Stability of Generalized Second Price Auctions with Budgets

The Generalized Second Price (GSP) auction that is used typically to model sponsored search auctions, does not include the notion of budget constraints, which is present in practice. Motivated by this, we introduce different variants of GSP auctions that take budgets into account in natural ways. We examine their stability by focusing on the existence of 1) Nash equilibria and 2) envy-free assignments. We highlight the differences between these mechanisms and find that only some of them exhibit both notions of stability. This shows the importance of carefully picking the right mechanism to ensure stable outcomes in the presence of budgets.

Joint work with Josep Diaz, Lefteris Kirousis, Vangelis Markakis, Maria Serna

Re: Theory Tea 2013-2014

Posted: Thu Dec 05, 2013 6:10 pm
by XaviannNJ
Αυτή την Παρασκευή θα κάνω ένα mini-tutorial για μοντέλα διάχυσης σε κοινωνικά δίκτυα.
Θα είναι μια αρκετά περιληπτική version ενός tutorial που έκανα το καλοκαίρι σε ένα summer school σε συνδυασμό στο τέλος και με αποτελέσματα από μια εργασία μας (μαζί με τον Χρήστο Αμανατίδη και τον Βασίλη Τζούμα).

Παραμένουμε στην αίθουσα Α36.

The talk will evolve around the question: how do ideas, behaviors, or commercial products spread through a social network and how do we achieve (approximately) optimal propagation of a new trend or a new product? The processes by which new behavioral patterns spread in a population have been an object of study in the social sciences for the last decades. Inspired by empirical studies, some basic mathematical models have been developed to capture diffusion. The value of such models is that they help us understand better the diffusion mechanisms and make predictions about the success of a new product. In all such models, a user is influenced only by the behavior of its neighbors in the graph of the social network, i.e., his social circle. Hence, the propagation typically begins by a relatively small set of people who adopt the new product (early adopters) and then the spread continues as the remaining people adjust their behavior based on word-of-mouth effects.

We will first overview the prevalent models that have been proposed in the literature. We will then introduce algorithmic and game-theoretic questions that arise naturally in this context. Namely, from an algorithmic point of view, we are interested in finding the most influential set of nodes in the network so as to maximize the spread of a product. Concerning game-theoretic aspects, we will consider models with two or more competing products that spread simultaneously over a network. If time permits, we will overview recent work in the literature involving the properties of Nash equilibria in such games.

The last part of the talk is joint work with Christos Amanatidis and Vasilis Tzoumas.

Re: Theory Tea 2013-2014

Posted: Fri Dec 13, 2013 12:48 am
by XaviannNJ
αυριο :!: :!: :!:

Αυτή την Παρασκευή θα μας επισκεφτεί ο Βαγγέλης Πάσχος από το Παρίσι.
Στην αίθουσα Α36.

V. Paschos, LAMSADE, Universite Paris-Dauphine, France
Title: Maximum Minimal Vertex Cover

Re: Theory Tea 2013-2014

Posted: Wed Dec 18, 2013 3:44 pm
by XaviannNJ
Αυτή την Παρασκευή θα κάνουμε το τελευταίο theory tea της χρονιάς,
για να ευχηθούμε και καλές γιορτές σε όλους :)

Θα μας μιλήσει ο Δημήτρης Λέτσιος, ο οποίος μας επισκέπτεται από το Παρίσι.

Λεπτομέρειες θα ανακοινωθούν σε επόμενο email.

Αίθουσα Α36 στις 5.

:smt114 :smt114

Re: Theory Tea 2013-2014

Posted: Fri Dec 20, 2013 2:36 am
by XaviannNJ
Ακολουθούν οι λεπτομέρειες για το αυριανό theory tea (A36 στις 5).

Speaker: Dimitris Letsios, University of Evry, France
Title: "Energy-Aware Scheduling and Routing"

Energy consumption of computer systems has become a major issue nowadays.
One way to manage the energy consumption of a computing device is
by proper scaling of the processor's speed through the operating system.
High processor's speeds imply high performance at the price of high energy consumption and the goal is to minimize energy consumption and optimize performance.
Our main task is the design of efficient speed scaling algorithms.
The theoretical study of speed scaling was initiated in a seminal paper
by Yao, Demers and Shenker (FOCS'95).
In order to measure the energy consumption of the processor, the authors adopted the so called cube-root rule according to which the power consumption of a processor is a convex function of its speed.
The aim of this talk is to present speed scaling algorithms for scheduling and routing applications.