Theory Tea 2014-2015

[XaviannNJ]

Γεια σας!

Το Theory Tea για το ακαδημαικό έτος 2014-2015 ξεκινάει αυτή την Παρασκευή 12/9!
Για όσους δεν το ξέρουν,είναι ομιλίες που αφορούν τον τομέα της θεωρητικής Πληροφορικής. Γίνεται (σχεδόν) κάθε Παρασκευή στις 5 το απόγευμα,συνήθως στην Α41 ή την Α36. Παρέχεται δωρεάν τσάι,καφες και διάφορα βουτήματα.

Η πρώτη ομιλία έχει τίτλο "Linear Regression as a Non-Cooperative Game" και θα πραγματοποιηθεί από τον Στρατή Ιωαννίδη. Ακολουθεί το abstract και περισσότερες λεπτομέρειες για τον ομιλητή.

Title: Linear Regression as a Non-Cooperative Game
Abstract: The statistical analysis of personal data is a cornerstone of several experimental sciences, such as medicine and sociology, and has recently become a commonplace—yet controversial—aspect of the Internet economy. The monetary and societal benefits of statistical estimation over personal data are often off-set by a privacy cost incurred by participating individuals. We propose a game-theoretic model to express this trade-off in the context of linear regression, a ubiquitous statistical task. In particular, we consider an analyst wishing to learn a linear model over responses solicited from several individuals. Though individuals benefit from correct estimation of the model, they also incur a privacy cost when revealing their responses. To address this, individuals strategically add noise to their responses, to minimize a cost that captures both how well the model is estimated, as well as the privacy violation they incur. We study the Nash equilibria of the resulting non-cooperative game, establishing the existence of a unique equilibrium for which costs are finite. We also determine the price of stability for several classes of privacy and estimation costs. Finally, we prove that estimating the linear model through a generalized least-squares minimization is optimal among all linear unbiased estimators: this result extends the famous Aitken/Gauss-Markov theorem in statistics, indicating that its conclusion persists even when individuals add noise strategically.

This is joint work with Patrick Loiseau and Michela Chessa.

Bio: Stratis Ioannidis is a senior researcher at the Technicolor research center in Los Altos, CA. He received an M.Sc. (2004) and a Ph.D. (2009) in Computer Science from the University of Toronto, Canada, and a B.Sc. (2002) in Electrical and Computer Engineering from the National Technical University of Athens, Greece. Until 2011, he was a postdoctoral researcher at the Technicolor research center in Paris, France.

Παρασκευή 12/9,17.00 στην Α41. Σας περιμένουμε.

[XaviannNJ]

Μεθύριο στις 4 στην Α41 θα γινουν οι ακόλουθες ομιλίες.

Αυτή την Παρασκευή θα έχουμε 2 ομιλίες.

Θα ξεκινήσουμε με μια παρουσίαση διπλωματικής από το μεταπτυχιακό μας,
και στη συνέχεια θα μας μιλήσει ο Μανώλης Πουντουράκης, επισκέπτης από το Northwestern University.

Το πρόγραμμα αναλυτικά (αίθουσα Α41):

16:00 - 17:00
Βασίλης Ρήγας, Μεταπτυχιακός φοιτητής, Επιστήμη Υπολογιστών, ΟΠΑ
Τίτλος: On a game-theoretic approach for modeling the WWW

17:15 - 18:15
Manolis Pountourakis, PhD candidate, Northwestern University

Title: Mechanisms for Hiring a Matroid Base without Money

Abstract:
We consider the problem of designing mechanisms for hiring a matroid base without money. In our model, the elements of a given matroid correspond to agents who might misreport their actual costs that are incurred if they are hired. The goal is to hire a matroid base of minimum total cost. There are no monetary transfers involved. We assume that the reports are binding in the sense that an agent's cost is equal to the maximum of his declared and actual costs. Our model encompasses a variety of problems as special cases, such as computing a minimum cost spanning tree or finding minimum cost allocation of jobs to machines.

We derive a polynomial-time randomized mechanism that is truthful in expectation and achieves an approximation ratio of $(m-r)/2+1$, where $m$ and $r$ refer to the number of elements and the rank of the matroid, respectively. We also prove that this is best possible by showing that no mechanism that is truthful in expectation can achieve a better approximation ratio in general. If the declared costs of the agents are bounded by the cost of a socially optimal solution, we are able derive an improved approximation ratio of $3\sqrt{m}$. For example, this condition is satisfied if the costs constitute a metric in the graphical matroid.

Our mechanism iteratively extends a partial solution by adding feasible elements at random. As it turns out, this algorithm achieves the best possible approximation ratio if it is equipped with a distribution that is optimal for the allocation of a single task to multiple machines. This seems surprising given that matroids allow for much richer combinatorial structures than the assignment of a single job.

[XaviannNJ]

Παρασκευη, 5μμ, Α36

Αυτή την Παρασκευή θα μιλήσω εγώ για μια πρόσφατη εργασία μας.
Τίτλος και abstract παρακάτω.

Επιστρέφουμε στην αίθουσα Α36, στις 5.
Ίσως τις επόμενες φορές φέτος το μεταφέρουμε τις Τετάρτες, θα υπάρξει νεότερη ανακοίνωση για αυτό.

Title: On the Convergence of Iterative Voting: How Restrictive should Restricted Dynamics be?

Abstract:
We study convergence properties of iterative voting procedures. Such procedures are defined by a voting rule and a (restricted) iterative process, where at each step one agent can modify his vote towards a better outcome for himself. It is already known that if the iteration dynamics (the manner in which voters are allowed to modify their votes) are unrestricted, then the voting process may not converge. For most common voting rules such lack of convergence may be observed even under the best response dynamics. It is therefore important to investigate whether and which natural restrictions on the dynamics of iterative voting procedures can guarantee convergence. To this end, we provide two general conditions on the dynamics based on iterative myopic improvements, each of which is sufficient for convergence. We then identify several classes of voting rules (including Positional Scoring Rules, Maximin, Copeland and Bucklin), along with their corresponding iterative processes, for which at least one of these conditions hold.
Our work generalizes recent results and relaxes a number of restrictive assumptions made in previous research.

This is joint work with Svetlana Obraztsova, Maria Polukarov, Zinovi Rabinovich, and Nicholas R. Jennings

[XaviannNJ]

Αύριο στις 17.00 το επόμενο! Αίθουσα άγνωστη,για την ώρα αλλά μάλλον θα πραγματοποιηθεί στο κτήριο της Ευελπίδων.

Αυτη την Παρασκευή θα μας επισκεφτούν από το Πολυτεχνείο Κρήτης
ο κ. Χαλκιαδάκης, Επικ. Καθηγητής στη σχολή ΗΜΜΥ και ο υποψήφιος διδάκτορας με τον οποίο συνεργάζονται, Χάρης Ακασιάδης. Θα μας μιλήσει ο Χάρης για μια πρόσφατη δουλειά τους. Ακολoυθεί παρακάτω ο τιτλος και το abstract.
Αν και γενικά θα κάνουμε τις Τεταρτες το σεμινάριο, αυτη τη βδομάδα θα το έχουμε την Παρασκευή μια και ο ομιλητής δεν μπορούσε άλλη μέρα.


Speaker: Charilaos Akasiadis, Technical University of Crete
Title: Cooperative Electricity Consumption Shifting in the Smart Grid

Abstract:

The transition to a Smart Electricity Grid is a challenging problem, given
also the increased levels of penetration of energy produced via renewable
sources into the Grid. As such, the proactive balancing between the amount
of electricity produced and consumed is a requirement. Here we present a
directly applicable scheme for power consumption shifting, and the
effective balancing of the electricity consumption curve corresponding to
some future date (e.g., the day ahead). It is a proactive scheme, rather
than a last-minute peak trimming one; and it can employ the services of
either individual or cooperating consumer agents alike.

Agents participating in the scheme, however, are motivated to form
cooperatives, in order to reduce their electricity bills via lower group
prices granted for sizable consumption shifting from high to low demand
time intervals. The scheme takes into account individual costs, and uses a
strictly proper scoring rule to reward contributors according to
efficiency. Cooperative members, in particular, can attain variable
reduced electricity price rates, given their different load-shifting
capabilities. This allows even agents with initially forbidding shifting
costs to participate in the scheme, by means of a weakly budget-balanced,
truthful reward sharing mechanism that we put forward.

Now, one major problem arising in this domain is assessing the
participating agents’ uncertainty, and correctly predicting their future
behaviour. Thus, we adopt two stochastic filtering techniques, the
Unscented Kalman Filter and the Histogram Filter, and use them to
effectively monitor the trustworthiness of agent statements regarding
their final actions. Interestingly, our UKF filter is equipped with a
Gaussian Process regression model. We incorporate these techniques within
our demand management scheme. Our simulation results confirm that these
techniques provide tangible benefits regarding enhanced consumption
reduction performance, and increased financial gains for the cooperative.

This talk will be presenting work that appeared in the following
publications:

Akasiadis, Charilaos, and Georgios Chalkiadakis. "Agent Cooperatives for
Effective Power Consumption Shifting." AAAI. 2013.
http://www.aaai.org/ocs/index.php/AAAI/ ... /view/6193

Akasiadis, Charilaos, and Georgios Chalkiadakis. "Stochastic Filtering
Methods for Predicting Agent Performance in the Smart Grid."
ECAI/PAIS-2014.
http://ebooks.iospress.nl/publication/37172

[XaviannNJ]

Η ομιλία θα γίνει στην αίθουσα 606 (Ευελπιδων 47Α και Λευκάδος).

[XaviannNJ]

Επόμενο theory tea την Τεταρτη στις 5(αίθουσα Α36).

Αυτη την εβδομάδα μας επισκέπτεται από την Ολλανδία
ο Krzysztof Apt. Ο Krzysztof είναι μέλος της ομάδας Αλγοριθμικής Θεωρίας Παιγνίων στο CWI (Center for Math and Computer Science, Amsterdam),
και θα μας δώσει ομιλία την Τετάρτη στις 5, για κάποια προβλήματα που πηγαζουν απο το χωρο των κοινωνικών δικτύων.

Θα είναι εδώ σχεδόν όλη την εβδομάδα, και θα χαρεί να μιλήσει με φοιτητές ή άλλους συναδέλφους. Όποιος ενδιαφέρεται να τον συναντήσει μπορεί να μου στείλει email.

Ακολουθούν οι πληροφορίες για την ομιλία.

Τετάρτη 3/12,17:00, αίθουσα Α36, πτέρυγα Αντωνιάδου

Krzysztof R. Apt
CWI and University of Amsterdam

Title: Coordination games on graphs

Abstract:

Consider the following strategic game on a finite graph. The players
are the nodes. Each node selects a colour from a set of colours
(privately) available for it. The payoff to a node is the number of
neighbours who chose the same colour.

These games capture the idea of coordination in a local setting. We
show that they have an exact potential and have strong equilibria when
the underlying graph is a pseudoforest. We also exhibit some other
classes of graphs for which a strong equilibrium exists. However, in
general strong equilibria do not need to exist. Further, we study the
(strong) price of stability and anarchy. Finally, we consider the
problems of computing strong equilibria and of determining whether a
joint strategy is a strong equilibrium.

This is a joint work with Mona Rahn, Guido Schaefer and Sunil Simon.

[*estrngd]

Οι ομιλίες δεν είναι στα ελληνικά;

[XaviannNJ]

Οι ομιλίες δεν είναι στα ελληνικά;

Συνήθως είναι. Η συγκεκριμένη δεν θα είναι,γιατί ο ομιλητής είναι από το εξωτερικό.

[XaviannNJ]

Υπενθυμίζω την σημερινή εκδήλωση!

[XaviannNJ]

Η επόμενη ομιλία είναι αύριο, στις 5, στην Α36.

Την ερχόμενη τεταρτη θα μας μιλήσουν
από κοινού ο Γιάννης Μούρτος, Επικ. Καθηγητής από το ΔΕΤ,
μαζί με τον Παύλο Ειρηνάκη, μεταδιδάκτορας επίσης απο το ΔΕΤ.

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

Ακολουθεί περίληψη της ομιλίας, η οποία αφορά γάμους και άλλα ενδιαφέροντα ταιριάσματα

Polyhedral results for two-sided stable matchings, P. Eirinakis, D. Magos, I. Mourtos

Abstract
We examine variants of two-sided matchings under preferences from a polyhedral perspective. That is, for each such variant, we investigate the polytope defined as the convex hull of integer vectors that are feasible with respect to a given integer programming formulation. This includes the identification of a minimal set of inequalities describing this polytope and relevant properties such its dimension and its diameter. This analysis becomes plausible only after combining several aspects of the problem, e.g., an associated partial ordered set, and after addressing several intermediate, yet interesting on their own, questions.

[XaviannNJ]

Την Τετάρτη θα γίνει το τελευταίο (και εορταστικό) theory tea της χρονιάς.
Α36, στις 5.Ακολουθούν λεπτομέρειες.

Αυτή την Τετάρτη θα έχουμε το τελευταίο theory tea της χρονιάς,
επομένως και με περισσότερα γλυκά, κτλ για να ευχηθούμε και χρόνια πολλά!

Επισκέπτης μας ένας παλιός φοιτητής μας, ο Αλέξανδρος Ψωμάς, τώρα υποψήφιος διδάκτορας στο Berkeley. Παρακάτω η περίληψη της ομιλίας.

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


Title: On the Complexity of Dynamic Mechanism Design

Abstract:
We introduce a dynamic mechanism design problem in which the designer wants to offer for sale an item to an agent, and another item to the same agent at some point in the future. The agent's joint distribution of valuations for the two items is known, and the agent knows the valuation for the current item (but not for the one in the future). The designer seeks to maximize expected revenue, and the auction must be deterministic, truthful, and ex post individually rational. The optimum mechanism involves a protocol whereby the seller elicits the buyer's current valuation, and based on the bid makes two take-it-or-leave-it offers, one for now and one for the future. We show that finding the optimum deterministic mechanism in this situation - arguably the simplest meaningful dynamic mechanism design problem imaginable - is NP-hard. We also prove several positive results, among them a polynomial linear programming-based algorithm for the optimum randomized auction (even for many bidders and periods), and we show strong separations in revenue between non-adaptive, adaptive, and randomized auctions, even when the valuations in the two periods are uncorrelated. Finally, for the same problem in an environment in which contracts cannot be enforced, and thus perfection of equilibrium is necessary, we show that the optimum randomized mechanism requires multiple rounds of cheap talk-like interactions.

Joint work with Christos Papadimitriou, George Pierrakos, Aviad Rubinstein

[XaviannNJ]

Το Theory Tea ξαναξεκινάει σήμερα στην Α36,στις 5. Η σημερινή ομιλία θα ξεκινήσει όσο πιο κοντά στις 5 γίνεται λόγω κωλύματος του ομιλητή. Μετά θα έχει και βασιλόπιτα.
Ακολουθούν λεπτομέρειες στην συνέχεια.

Εύχομαι χρόνια πολλά και καλή χρονιά σε όλους!

Ξεκινάμε πάλι αυτή την Τετάρτη, με ομιλητή τον Βασίλη Ζήκα, από το ETH στη Ζυρίχη.

Ως συνηθως, στην Α36 στις 5. Ακολουθεί η περίληψη της ομιλίας, και ενα συντομο βιογραφικό του ομιλητή.


Vassilis Zikas, ETH Zurich

Title: The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults


Abstract:
The vast majority of works on secure multi-party computation (MPC) assume a full communication pattern: every party exchanges messages with {\em all} the network participants over a complete network of point-to-point channels. This can be problematic in modern large scale networks, where the number of parties can be of the order of millions, as for example when computing on large distributed data.

Motivated by the above observation, Boyle, Goldwasser, and Tessaro [TCC 2013] recently put forward the notion of {\em communication locality}, namely, the total number of point-to-point channels that each party uses in the protocol, as a quality metric of MPC protocols. They proved that assuming a public-key infrastructure (PKI) and a common reference string (CRS), an MPC protocol can be constructed for
computing any $n$-party function, with communication locality $\bigo[\log^c n]$ and round complexity $\bigo[\log^{c'} n]$, for appropriate constants $c$ and $c'$. Their protocol tolerates a static (i.e., non-adaptive) adversary corrupting up to $t<(\frac{1}{3}-\epsilon)n$ parties for any given constant $0<\epsilon<\frac{1}{3}$. These results leave open the following questions:

(1) Can we achieve low communication locality and round complexity while tolerating {\em adaptive} adversaries?

(2) Can we achieve low communication locality with {\em optimal resiliency} $t<n/2$?


In this work we answer both questions affirmatively. We consider the Boyle {\em et al.} model, where we replace the CRS with a symmetric-key infrastructure (SKI). In this model we give a protocol with communication locality and round complexity \polylog[n] (similarly to Boyle {\em et al.}) which tolerates up to $t<n/2$ {\em adaptive} corruptions, under a standard intractability assumption for adaptively secure protocols, namely, the existence of trapdoor permutations whose domain has invertible sampling. This is done by using the SKI to derive a sequence of random {\it hidden communication graphs} among players. A central new technique shows how to use these graphs to emulate a complete network in \polylog[n] rounds while preserving \polylog[n] locality. We also show how to remove the SKI setup assumption at the cost, however, of increasing the communication locality (but not the round complexity) by a factor of~$\sqrt{n}$.

This is joint work with Nishanth Chandran, Wutichai Chongchitmate, Juan A. Garay, Shafi Goldwasser, and Rafail Ostrovsky.


Short Bio:
Vassilis Zikas is a Senior Reseach Associate at the Department of Computer Science of ETH Zurich. Dr. Zikas joined ETH Zurich in 2014 and is supported by a career development grant from the Swiss National Science Foundation (SNF). Prior to joining ETH Dr. Zikas was a postdoctoral researcher at UCLA (working with Rafail Ostrovsky) and at University of Maryland (working with Jonathan Katz). Dr. Zikas received his PhD in computer science from ETH Zurich in 2010 (advisor: Ueli Maurer, thesis: Generalized Corruption Models in Secure Multi-Party Computation.)

[XaviannNJ]

Ξεκινάμε ομιλίες για το νέο εξάμηνο την Παρασκευή 27/3, στις 5. Ακολουθούν λεπτομέρειες:

Αργήσαμε λίγο αλλά ξεκινάμε πάλι το theory tea για αυτό
το εξάμηνο. Η ομιλία είναι την Παρασκευή, καθώς είναι αργία αυτή η Τετάρτη.
Θα μας μιλήσει ο Γιώργος Αμανατίδης, υποψήφιος διδάκτορας της ομάδας μας για μια πρόσφατη κοινή μας δουλειά. Το θέμα αφορά συστηματα ψηφοφοριών που χρησιμοποιούνται συνήθως για εκλογές επιτροπών, συμβουλίων, κτλ (approval voting).
Παρασκευή 27/3, 17:00
Αίθουσα Α36,
Ομιλητής: Γιώργος Αμανατίδης,
Υποψήφιος Διδάκτορας, ΟΠΑ
Title: Multiple Referenda and Multi-winner Elections Using Hamming Distances: Complexity and Manipulability
Abstract:
We study multiple referenda and committee elections, when the ballot of each voter is simply a set of approved binary issues (or candidates). Two well-known rules under this model are the commonly used candidate-wise majority, also called the minisum rule, as well as the minimax rule. In the former, the elected committee consists of the candidates approved by a majority of voters, whereas the latter picks a committee minimizing the maximum Hamming distance to all ballots.
As these rules are in some ways extreme points in the whole spectrum of solutions, we consider a general family of rules, using the Ordered Weighted Averaging (OWA) operators. Each rule is parameterized by a weight vector, showing the importance of the i-th highest Hamming distance of the outcome to the voters. The objective then is to minimize the weighted sum of the (ordered) distances. We study mostly computational, but also manipulability properties for this family. We first exhibit that for many rules, it is NP-hard to find a winning committee. We then proceed to identify cases where the problem is either efficiently solvable, or approximable with a small approximation factor. Finally, we investigate the issue of manipulating such rules and provide conditions that make this possible.
This is joint work with Nathanael Barrot, Jerome Lang, Evangelos Markakis, Bernard Ries

[XaviannNJ]

Την Τετάρτη στις 5 θα μιλήσει ο Βαγγέλης Αναγνωστόπουλος, παλιός φοιτητής του τμήματός μας και μεταπτυχιακός φοιτητής στο Μεταπτυχιακο Προγραμμα Λογικης και Αλγορίθμων.
Αίθουσα: Α36
Ακολουθούν τίτλος και abstract της ομιλίας:

Title: Low-quality dimension reduction and high-dimensional Approximate Nearest Neighbor

Abstract:
The approximate nearest neighbor problem ($\epsilon$-ANN) in Euclidean settings is a fundamental question, which has been addressed by two main approaches: Data-dependent space partitioning techniques perform well when the dimension is relatively low, but are affected by the curse of dimensionality. On the other hand, locality sensitive hashing has polynomial dependence in the dimension, sublinear query time with an exponent inversely proportional to the error factor $\epsilon$, and subquadratic space requirement.

We generalize the Johnson-Lindenstrauss lemma to define ``low-quality'' mappings to a Euclidean space of significantly lower dimension, such that they satisfy a requirement weaker than approximately preserving all distances or even preserving the nearest neighbor. This mapping guarantees, with arbitrarily high probability, that an approximate nearest neighbor lies among the $k$ approximate nearest neighbors in the projected space. This leads to a randomized tree based data structure that avoids the curse of dimensionality for $\epsilon$-ANN.
Our algorithm, given $n$ points in dimension $d$, achieves space usage in $O(dn)$, preprocessing time in $O(dn\log n)$, and query time in $O(d n^{\rho}\log n)$, where $\rho$ is proportional to $1-{1}/{\ln \ln n}$, for fixed $\epsilon \in (0,1)$. It employs a data structure, such as BBD-trees, that efficiently finds $k$ approximate nearest neighbors. The dimension reduction is larger if one assumes that pointsets possess some structure, namely bounded expansion rate. We implement our method and present experimental results in up to 500 dimensions and $10^5$ points, which show that the practical performance is better than predicted by the theoretical analysis. In addition, we compare our approach with E2LSH.

Authors: Evangelos Anagnostopoulos, Ioannis Z. Emiris, Ioannis Psarros

[XaviannNJ]

Επόμενη ομιλία την Τετάρτη, στις 5, στην Α36. Θα μιλήσει ο Γιώργος Ζώης,υποψήφιος διδάκτορας του τμήματος. Λεπτομέρειες εδώ:

http://aiw.cs.aueb.gr/TheoryGroup/abstr ... 42015.html

[XaviannNJ]

Ακολουθεί η ανακοίνωση για αυτή την Τετάρτη:

Αυτές τις μέρες είναι εδώ ένα πρώην μέλος της ομάδας μας,
η Svetlana Obraztsova και θα μας δώσει ομιλία την Τετάρτη.

Όπως πάντα, αιθουσα Α36, στις 5.

Svetlana Obraztsova, post-doctoral researcher,
Tel-Aviv University

Title: Voting games

Abstract: Multi-agent decision problems, in which independent agents have to
agree on a joint plan of action or allocation of resources, are
central to various applications. Often in such settings, agents'
individual preferences over available alternatives may vary, and they
may try to reconcile these differences by voting. Based on the fact
that agents may have incentives to vote strategically and misreport
their real preferences, much of the literature in computational social
choice focuses on evaluating voting rules by their resistance to
strategic behaviour and uses computational complexity as a barrier to
them. In contrast, more recent works (from 2010 onwards) take another
natural approach and analyze voting scenarios from a game-theoretic
perspective, viewing strategic parties as players and examining
possible stable outcomes of their interaction (i.e., equilibria). The talk
will give an overview of the existing results in this---fairly
new---line of research.

[XaviannNJ]

Τελευταίο theory tea της χρονιάς αύριο:

Αυτη την Τετάρτη θα έχουμε την τελευταία ομιλία για αυτη την χρονιά.
Θα μας μιλήσει ο Γιώργος Μπίρμπας, υποψήφιος διδάκτορας του τμήματός μας,
για μια κοινη μας πρόσφατη εργασία. Αφορά μοντέλα για participatory sensing environments.

Ακολουθούν οι πληροφορίες για την ομιλία.

Ομιλητής: Γεώργιος Μπίρμπας, Υποψήφιος Διδάκτορας, ΟΠΑ

Title: Cost-sharing models in Participatory Sensing
Abstract:
In Smart City and Participatory Sensing initiatives the key concept is
for user communities to contribute sensor information and form
a body of knowledge that can be exploited by innovative applications
and data analytics services. A key aspect in all such platforms is that
sensor information is not free but comes at a cost. As a result, these platforms may suffer due to insufficient sensor information made publicly available
if applications do not share efficiently the cost of the sensor information they consume.

We explore the design of specialized market mechanisms
that match demand to supply while taking into account important positive demand externalities: sensors are digital goods and their cost can be shared by applications.
We focus on the buyer side and define different demand models according to the flexibility in choosing sensor data for satisfying application needs. We then investigate the properties of various cost-sharing mechanisms with respect to efficiency and budget balance.
In doing so, we also propose and study a new mechanism, which although lacks
strategyproofness, it exhibits important efficiency improvement along with certain fairness properties.

This is joint work with Costas Courcoubetis, Ioannis Giotis and Evangelos Markakis

[XaviannNJ]

Η παρακάτω ανακοίνωση δεν αφορά ομιλία στα πλαίσια του Theory Tea,αλλά γενικά έχει πολύ ενδιαφέρον.

Παρουσίαση και Δημόσια Υποστήριξη της Διδακτορικής Διατριβής κ. Γιώργου Κούρουπα

Την Τρίτη 30 Ιουνίου, ώρα 6:00μμ, θα γίνει η δημόσια υποστήριξη-εξέταση της διδακτορικής διατριβής του Γιώργου Κούρουπα με τίτλο «Μελέτη του παγκόσμιου ιστού με χρήση Θεωρίας Οικονομικών και Παιγνίων» στην αίθουσα Α41, στο Κεντρικό Κτίριο ΟΠΑ, Πτέρυγα Αντωνιάδου, 4ο όροφο.
Σας προσκαλώ να την παρακολουθήσετε.
Ακολουθεί περίληψη της ομιλίας.

Μάρθα Σιδέρη
Καθηγήτρια

------------------------------------------------------------------------------------------------
Μελέτη του παγκόσμιου ιστού με χρήση Θεωρίας Οικονομικών και Παιγνίων

Διδακτορική διατριβή Γιώργου Κούρουπα


O Παγκόσμιος ιστός δημιουργήθηκε, υποστηρίζεται και χρησιμοποιείται από ένα σύνολο από εγωιστικές οικονομικές οντότητες, κάθε μια εκ των οποίων προσπαθεί να βελτιστοποιήσει διάφορους παράγοντες, και οι οποίες έχουν ποικίλους βαθμούς ανταγωνισμού και συνεργασίας μεταξύ τους. Στη διατριβή προτείνουμε δυο μοντέλα απεικόνισης του πλέγματος των συμφερόντων στον παγκόσμιο ιστό, στα οποία χρησιμοποιούμε έννοιες, τεχνικές της Μαθηματικής Οικονομικής Θεωρίας και της Θεωρίας Παιγνίων.

Το πρώτο προτεινόμενο μοντέλο είναι οικονομικό και αποτελείται από τρεις τύπους παικτών: (α) Συγγραφείς των εγγράφων (Document Authors), που διαθέτουν περιεχόμενο στον Παγκόσμιο Ιστό. (β) χρήστες (Users) που αναζητούν χρήσιμη πληροφορία στον Παγκόσμιο Ιστό και (γ) μια μηχανή αναζήτησης (Search Engine),η οποία σκοπό έχει να βοηθά το χρήστη να ανακαλύψει τα έγγραφα που τον ενδιαφέρουν. Κατά το μοντέλο αυτό, ο παγκόσμιος ιστός δημιουργείται από την αλληλεπίδραση των προαναφερθέντων παικτών, κάθε ένας εκ των οποίων ενδιαφέρεται να αποκομίσει το μέγιστο δυνατό όφελος από την αλληλεπίδραση με τους άλλους παίκτες. Βασικό στοιχείο του μοντέλου αποτελεί η ωφελιμότητα U(i,d) η οποία συσχετίζει το χρήστη i με το έγγραφο d. Τα ενδιαφέροντα ερωτήματα που εξετάζουμε είναι: Ποια είναι η τιμή της αναρχίας της διαδικασίας εξέλιξης του μοντέλου, δηλαδή ποιο τμήμα της συνολικής ωφελιμότητας είναι δυνατόν να πάρουν οι χρήστες από τον αλγόριθμο αναζήτησης; Ποια είναι η τελική μορφή του παγκόσμιου ιστού, σύμφωνα με το μοντέλο αυτό; Από την πειραματική μελέτη της συμπεριφοράς του μοντέλου συμπεραίνουμε ότι η συνολική ωφελιμότητα είναι αυξάνεται όταν οι χρησιμότητες των χρηστών είναι πιο συγκεντρωμένες (clustered). Επίσης, η κατανομή βαθμών των εγγράφων είναι προφανέστερα κατανομή νόμου δύναμης (power law) στην περίπτωση αυτή. Τέλος, θέτουμε πολλά ενδιαφέροντα ερωτήματα σχετικά με ανταγωνισμό και ποιότητα μηχανών αναζήτησης, αλγορίθμους αναζήτησης και κίνητρα ιστοσελίδων και παραποίηση αποτελεσμάτων μηχανών αναζήτησης (search engine spam).

Το δεύτερο μοντέλο είναι παιγνιοθεωρητικό. Ο παγκόσμιος ιστός μοντελοποιείται ως γράφημα, στο οποίο οι κόμβοι παρέχουν πληροφορίες. Ο χώρος στρατηγικών κάθε κόμβου είναι η επιλογή ενός συνόλου εξερχομένων υπερσυνδέσμων, καθώς και η επιλογή των πιθανοτήτων να ακολουθηθεί καθένας από αυτούς. Η ωφέλεια που έχει ο κόμβος από τις επιλογές του είναι το γινόμενο δύο όρων: (α) Της κίνησης μέσω του κόμβου (η οποία θα μπορούσε να εκφραστεί από την τιμή PageRank στην αλυσίδα Markov που δημιουργήθηκε από τις ενέργειες του κόμβου) και (β) Της ποιότητας του συγκεκριμένου κόμβου, η οποία εκφράζει την ωφέλεια ανά επίσκεψη, όπως για παράδειγμα τη δημιουργία φήμης, ή δυνατότητας κέρδους. Η ποιότητα ενός κόμβου εξαρτάται από το εγγενές περιεχόμενό του, καθώς και από τις τροποποιήσεις στο περιεχόμενο, τις οποίες επιφέρουν οι επιλογές των υπερσυνδέσμων. Ο μοναδικός περιορισμός που θέτουμε στην ποιότητα είναι να είναι κοίλη συνάρτηση της στρατηγικής του κόμβου (της κατανομής δηλαδή πιθανοτήτων στους εξερχόμενους υπερσυνδέσμους). Προτείνουμε ένα φυσικό παράδειγμα μιας τέτοιας συνάρτησης ποιότητας. Αποδεικνύουμε ότι το παιχνίδι που προκύπτει έχει πάντα γνήσια ισορροπία κατά Nash. Τα πειράματα υποδεικνύουν ότι τα σημεία ισορροπίας αυτά υπολογίζονται εύκολα, αποφεύγονται τα αμφίδρομα σημεία ισορροπίας που παρουσιάζονται σε αντίστοιχα μοντέλα της βιβλιογραφίας και έχουν ευνοϊκή τιμή της αναρχίας . Το προκύπτον ως ισορροπία του παιχνιδιού γράφημα έχει σε γενικές γραμμές τα χαρακτηριστικά του παγκόσμιου ιστού. Ενδιαφέροντα ανοικτά προβλήματα είναι ο ακριβής χαρακτηρισμός της πολυπλοκότητας εύρεσης των σημείων ισορροπίας και της τιμής της αναρχίας.

Τέλος, εξετάζουμε πειραματικά δυο ακόμα μοντέλα, τα οποία είναι επεκτάσεις με συναρτήσεις ωφελιμότητας γνωστών μοντέλων δημιουργίας γραφημάτων.