Theory Tea 2017-2018

[Georgemanif]

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

Η πρώτη ομιλία θα γίνει από τον κ. Μαρκάκη, αυτή την Παρασκευή 2/2, στις 17:00.
Ως συνήθως, αίθουσα Α36.

Η ομιλία αφορά δημοπρασίες και ακολουθούν ο τίτλος και η περίληψη.

Title: On the Performance of Deferred- Acceptance Auctions

Abstract:
Deferred Acceptance (DA) auctions were introduced by Milgrom and Segal (2014), motivated by the design of spectrum auctions. This framework is based on backward-greedy algorithms and yields mechanisms with remarkable incentive properties. In particular, auctions that fit under this framework are group-strategyproof, and can be implemented as an obviously-strategyproof ascending auction. Most existing works on DA auctions however considered only binary single-parameter problems, where each bidder is either accepted or rejected by the mechanism. In this talk, we will first overview the framework along with results on the binary setting. We will then provide a generalization of the DA auction framework to non-binary settings, that allow outcomes with multiple "levels of service" instead of an accept/reject decision. We will then describe how to apply this in order to obtain approximately welfare-maximizing DA auctions for a number of basic mechanism design problems, including: problems with polymatroid constraints or multiple knapsack constraints, the problem of scheduling jobs to minimize their total weighted completion time, and multi-unit auctions.
This is joint work with Vasilis Gkatzelis and Tim Roughgarden.

[Georgemanif]

Αυτή την Παρασκευή θα μας μιλήσει ο Γιώργος Μπίρμπας.

Όπως πάντα, στην αίθουσα Α36, στις 5.
Ακολουθούν οι πληροφορίες για την ομιλία.

Title: Truthful Allocation Mechanisms without Payments: Characterization and Implications on Fairness

Abstract:
We study the mechanism design problem of allocating a set of indivisible items without monetary transfers. Despite the vast literature on this very standard model, it still remains unclear how do truthful mechanisms look like. We focus on the case of two players with additive valuation functions and our purpose is twofold.

First, our main result provides a complete characterization of truthful mechanisms that allocate all the items to the players. Our characterization reveals an interesting structure underlying all truthful mechanisms, showing that they can be decomposed into two components: a \textit{selection part} where players pick their best subset among prespecified choices determined by the mechanism, and an \textit{exchange part} where players are offered the chance to exchange certain subsets if it is favorable to do so.

In the remaining paper, we apply our main result and derive several consequences on the design of mechanisms with fairness guarantees. We consider various notions of fairness, (indicatively, maximin share guarantees and envy-freeness up to one item) and provide tight bounds for their approximability. Our work settles some of the open problems in this agenda, and we conclude by discussing possible extensions to more players.


Joint work with Georgios Amanatidis, George Christodoulou, Evangelos Markakis

[chrisagelou]

Αυτή την Παρασκευή θα μας μιλήσει ο Ορέστης Τελέλης,
Επικ. Καθηγητής στο Πανεπιστήμιο Πειραιώς, και πρώην μέλος της ομάδας μας.

Στις 17:00, αίθουσα Α36. Αυτό είναι και το τελευταίο meeting που έχουμε πριν το Πάσχα.

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

"On Envy-Free Revenue Approximation for Combinatorial Buyers with Budgets"

We study the computation of revenue-maximizing envy-free outcomes, in a monopoly
market with budgeted buyers. We focus on buyers with combinatorial valuation
functions, that are defined over subsets of distinct goods. For single-minded
buyers, we show a best possible polynomial-time approximation of the optimum
envy-free revenue. Subsequently, we establish that, even for two identical
additive buyers, the problem is not approximable in polynomial time. In an
attempt to identify tractable families of the problem's instances, we introduce
a notion of budget compatible buyers, that have at enough budget to "cover"
their value for any single good. Under this assumption, we establish
approximation upper bounds for buyers with submodular valuation functions over
preference subsets, as well as for buyers with identical subadditive valuation
functions. We also analyze an algorithm for budget compatible buyers with
arbitrary additive valuation functions, which approximates the optimum envy-free
revenue within a constant factor, for a constant number of buyers. We conclude
with several interesting open questions.
This is a joint work with Vangelis Markakis and Apostolos Ntokos.

[chrisagelou]

Γεια σε όλους και χρόνια πολλά!



Αυτή την Παρασκευή θα μας μιλήσει ο Στέφανος Λεονάρδος, ο οποίος ολοκλήρωσε πρόσφατα την διδακτορική του διατριβή στο ΕΚΠΑ. Η ομιλία αφορά ένα μέρος του διδακτορικού του, και παρακάτω ακολουθούν οι σχετικές πληροφορίες.



Αίθουσα Α36, στις 17:00



Ομιλητής: Στέφανος Λεονάρδος, Τμ. Μαθηματικών, ΕΚΠΑ.

Title: On the Commitment Value and Commitment optimal Strategies in Bimatrix Games.



Abstract:

Given a bimatrix game, the associated leadership or commitment games are defined as the games at which one player, the leader, commits to a (possibly mixed) strategy and the other player, the follower, chooses his strategy after being informed of the irrevocable commitment of the leader (but not of its realization in case it is mixed). Based on a result by von Stengel & Zamir (2010), the notions of commitment value and commitment optimal strategies for each player are discussed as a possible solution concept. It is shown that in non-degenerate bimatrix games (a) pure commitment optimal strategies together with the follower's best response constitute Nash equilibria, and (b) strategies that participate in a completely mixed Nash equilibrium are strictly worse than commitment optimal strategies, provided they are not matrix game optimal. Finally, for various classes of bimatrix games that generalize zero sum games, the relationship between the maximin value of the leader's payoff matrix, the Nash equilibrium payoff and the commitment optimal value is established.

[chrisagelou]

Αυτή την Παρασκευή θα έχουμε ως επισκέπτη τον υποψήφιο διδάκτορα Γρηγόρη Κουμούτσο από την Ολλανδία,
από το Πολυτεχνείο TU Eindhoven.

Παρακάτω ακολουθούν οι λεπτομέρεις για την ομιλία του. Επίσης, μια και πληθαίνουν οι αιτήσεις για μεταπτυχιακά στην Ολλανδία τα τελευταία έτη, αν θέλει κάποιος να μιλήσει στον Γρηγόρη για τη ζωή και τα πανεπιστήμια στην Ολλανδία πριν ή μετά την ομιλία, ενημερώστε με.

Αίθουσα Α36, στις 17:00

Title: Algorithms for k-Server Problems

Abstract:
The k-server problem is one of the most natural and fundamental online
problems and its study has been quite influential in the development of
competitive analysis. Despite various remarkable developments, several
natural variants and generalizations of the k-server problem are very
poorly understood.
In particular, they exhibit very different and intriguing behavior and the
techniques for the standard k-server problem do not apply to them.
Getting a better understanding of such problems is a natural step towards
building a deeper theory of online computation.

In this talk, I will discuss some recent results on variants of the
k-server problem, in particular: i) the resource augmentation version (the
(h,k)-server problem), where
the performance of the online algorithm with k servers is compared to the
offline optimal solution with h \leq k servers, ii) the weighted k-server
problem, in which servers have different weights and iii) the generalized
k-server problem, where each server lies in its own metric space.

[chrisagelou]

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

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

Στην αίθουσα Α36, στις 17:00.

Ακολουθεί τίτλος και abstract

Speaker: Eftychia Vakaliou
Title: An Improved Envy-Free Cake Cutting Protocol for Four Agents

Abstract:
We consider the classic cake-cutting problem of producing envy-free allocations, restricted to the case of four agents. The problem asks for a partition of the cake to four agents, so that every agent finds her piece at least as valuable as every other agent's piece. The problem has an interesting history. Although the case of three agents is solvable with less than 15 queries, for four agents no bounded procedure was known until the recent breakthroughs of
Aziz and Mackenzie (2016). The main drawback of these new algorithms, however, is that they are quite complicated and with a very high query complexity. With four agents, the number of queries required is close to 600. In this work we provide an improved, simpler algorithm for four agents, which reduces the current complexity by a factor of 3.4. Our algorithm builds on the approach of
Aziz and Mackenzie by incorporating new insights and simplifying several steps.
The algorithm starts with an envy-free partial allocation and a leftover residue. It repeatedly reduces the residue and updates the allocation until certain structural properties are satisfied. These properties allow us to quickly produce a complete allocation without introducing any envy.
Overall, this results in an algorithm with lower complexity, which we believe is more intuitive and easier to grasp.

This is joint work with G. Amanatidis, G. Christodoulou, J. Fearnley, E. Markakis, A. Psomas

[parasleivadaros]

Αυτή την Παρασκευή θα μας μιλήσει ο Βασίλης Γρηγοριάδης, ο οποίος είναι διδάκτορας του ΕΚΠΑ, και μέχρι πρόσφατα ερευνητής στο πανεπιστήμιο του Τορίνο.

Η ομιλία θα γίνει στις 3 και όχι στις 5 που είναι συνήθως, στην αίθουσα Α36.
Ακολουθεί παρακάτω τίτλος και περίληψη.

Τίτλος:
Κυρτά παραγόμενα σύνολα και υπολογισιμότητα

Περίληψη:
Ασχολούμαστε με σύνολα A του Ευκλείδειου n-διάστατου χώρου τα οποία είναι κυρτά και τα οποία μπορούν να κατασκευαστούν χρησιμοποιώντας (α) n-διάστατους κύβους καθώς και (β) τις πράξεις των ενώσεων ή τομών από ήδη κατασκευασθέντα σύνολα A_i, i=0,1,2,..., (Borel σύνολα). Σύμφωνα με ένα αποτέλεσμα του Preiss μπορούμε να προχωρήσουμε σε μια ανακατασκευή του προηγούμενου κυρτού συνόλου A, έτσι ώστε οι ενώσεις στο (β) να λαμβάνονται με αύξοντα τρόπο, και συνεπώς τα ενδιάμεσα σύνολα A_i να είναι και αυτά κυρτά σύνολα. Με άλλα λόγια κάθε κυρτό Borel σύνολο είναι "κυρτά παραγόμενο''.

Σε αυτή την ομιλία παρουσιάζουμε ένα αποτέλεσμα που λέει ότι η προηγούμενη ανακατασκευή γίνεται με υπολογίσιμο τρόπο: υπάρχει ένας αλγόριθμος που μετατρέπει την περιγραφή -σύμφωνα με τον Borel τρόπο- του αρχικού κυρτού συνόλου σε μια περιγραφή του σύμφωνα με τον κυρτά παραγόμενο τρόπο.

Βασικά συστατικά της κατασκευής του αλγορίθμου είναι η αναδρομή σε υπολογίσιμα δέντρα (Kleene), ο αλγόριθμος υπολογισμού της κυρτής θήκης πεπερασμένου συνόλου σημείων, καθώς και συνδυαστικά εργαλεία της περιγραφικής θεωρίας συνόλων