Venus AUEB Forum

Γεια σε όλους και καλή ακαδημαική χρονιά!

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

Αυτή την Πέμπτη (και όχι Παρασκευή καθώς υπήρχε κάποιο κώλυμα) θα μας μιλήσει η Αλκμήνη Σγουρίτσα, η οποία κάνει το διδακτορικό της στο University of Liverpool, για ανάλυση δημοπρασιών.

Στις 17:00, και αιθουσα Α36. Ακολουθούν τα στοιχεία της ομιλίας.

Title: On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources

Authors: George Christodoulou, Alkmini Sgouritsa, Bo Tang

Abstract:
We study the efficiency of the proportional allocation mechanism, that is widely used to
allocate divisible resources. Each agent submits a bid for each divisible resource and receives a
fraction proportional to her bids. We quantify the inefficiency of Nash equilibria by studying
the Price of Anarchy (PoA) of the induced game under complete and incomplete information.
When agents' valuations are concave, we show that the Bayesian Nash equilibria can be arbitrarily
inefficient, in contrast to the well-known 4/3 bound for pure equilibria [Johari, Tsitsiklis 2004]. Next, we
upper bound the PoA over Bayesian equilibria by 2 when agents' valuations are subadditive,
generalizing and strengthening previous bounds on lattice submodular valuations. Furthermore,
we show that this bound is tight and cannot be improved by any simple or scale-free mechanism.
Then we switch to settings with budget constraints, and we show an improved upper bound on
the PoA over coarse-correlated equilibria. Finally, we prove that the PoA is exactly 2 for pure
equilibria in the polyhedral environment.

Title: Duality Theory for Optimal Multidimensional Auctions

Abstract:

In this talk we will present a general duality-theory framework for revenue maximization in additive Bayesian auctions involving many bidders, multiple items and arbitrary joint value distributions. Although the single-item case has been resolved in a very elegant way by the seminal work of Myerson [1981], optimal solutions involving more items still remain elusive. The framework extends linear programming duality and complementarity to constraints with partial derivatives. The dual system reveals the geometric nature of the problem and highlights its connection with the theory of bipartite graph matchings.

We demonstrate the power of the framework by applying it to special single-bidder settings with independent item valuations drawn from various distributions of interest, to design both exact and approximately optimal auctions. Previous exact solutions were essentially only known for up to two items and for a very limited number of specific distributions. The duality framework is used not only for proving optimality, but perhaps more importantly, for deriving the optimal auctions themselves; as a result, these mechanisms are defined by natural geometric constraints.

Joint work with Elias Koutsoupias (University of Oxford)

Αυτή την Παρασκευή θα κανω μια παρουσίαση για καποια προβλήματα σε fair division (cake-cutting problems) και εν τελει θα μιλήσω και για μια πρόσφατη δουλειά μας πανω σε αυτά με τον Γ. Αμανατίδη και άλλους συνεργάτες. Όποιος θέλει μπορεί να φέρει κάποια τούρτα για να εφαρμόσουμε τους αλγορίθμους σε πραγματικό cake

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

Title: Maximin share allocations and other solution concepts in fair division

Abstract:
We study fair division problems, where a set of resources needs to be allocated to a set of agents in some fair manner.
The first part of the talk will give an overview of some solution concepts that are used in fair division, along with existing results (in particular, we will mainly discuss the notions of proportionality, envy-freeness, maximin fair shares, and competitive equilibrium from equal incomes).
In the second part of the talk, we will focus on the problem of computing maximin share guarantees, a recently introduced fairness notion. Given a set of n agents, the maximin share of a single agent is the best that he can guarantee to himself, if he partitions the goods into n bundles
and then let other agents choose a bundle before him (i.e., running a generalization of the cut-and-choose protocol). The objective then is to find
a partition, so that each player is guaranteed his maximin share. In
the presence of indivisible goods, such allocations are not guaranteed
to exist, hence, we resort to approximation algorithms. I will present
a 2/3-approximation algorithm, which runs in polynomial time for any number of agents and goods, improving upon previous results in the literature. We will also investigate some special cases where we can provide better guarantees.
Finally, I will conclude the talk with some more open problems on fair division with either divisible or indivisible items.

Parts of this talk are based on joint work with Georgios Amanatidis, Afshin Nikzad, Amin Saberi

Αυτη την Παρασκευή θα μας μιλήσει ο Krzysztof Sornat για προβλήματα ψηφοφοριών τύπου approval voting. O Krzysztof μας επισκέπτεται από το University of Wroclaw της Πολωνίας και θα είναι εδώ μέχρι τέλη Νοέμβρη.

Μιλώντας για ψηφοφορίες, υπάρχει επίσης ένα ενδιαφέρον event gia e-voting την ερχόμενη Δευτέρα στην Τεχνόπολη. Δείτε εδώ:
http://www.demos-voting.org/event

Ακολουθούν οι λεπτομέρειες της ομιλίας της Παρασκευής (Α36 στις 17:00)

Krzysztof Sornat, Phd candidate University of Wroclaw

Title: PTAS for Minimax Approval Voting.

Abstract:
We consider Approval Voting systems where each voter decides on a subset to candidates he/she approves. We focus on the optimization problem of finding the committee of fixed size k minimizing the maximal Hamming distance from a vote. In this paper we give a PTAS for this problem and hence resolve the open question raised by Carragianis et al. [AAAI'10]. The result is obtained by adapting the techniques developed by Li et al. [JACM'02] originally used for the less constrained Closest String problem. The technique relies on extracting information and structural properties of constant size subsets of votes.

Joint work with Jarek Byrka

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

Αυριο θα εχουμε καποιες παρουσιασεις φοιτητών για το μαθημα μας "Ειδικα Θεματα Αλγοριθμων"
και με την ευκαιρία θα το συνδυασουμε με κοπή πίτας για το theorygroup, καφέ, κτλ.

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