|
|
 |
|
Jeudi 5 Décembre
| Heure: |
11:00 - 12:00 |
| Lieu: |
Salle G203 |
| Résumé: |
On the Computation of Strategyproof and Fair Picking Sequences |
| Description: |
Hugo Gilbert When allocating indivisible items to agents, it is known that the only strategyproof mechanisms that satisfy a set of rather mild conditions are constrained serial dictatorships (also known as non-interleaving picking sequences): given a fixed order over agents, at each step the designated agent chooses a given number of items (depending on her position in the sequence). With these rules, agents who come earlier in the sequence have a larger choice of items. However, this advantage can be compensated by a higher number of items received by those who come later. How to balance priority in the sequence and number of items received is a nontrivial question. In this presentation, we use a model parameterized by a mapping from ranks to scores, a social welfare functional, and a distribution over preference profiles. For several meaningful choices of parameters, we show that an optimal sequence can be computed exactly in polynomial time or approximated by resorting to sampling.
Joint work with Sylvain Bouveret, Jérôme Lang, and Guillaume Méroué. |
Jeudi 12 Décembre
| Heure: |
10:30 - 11:30 |
| Lieu: |
A303 |
| Résumé: |
Optimizing alphabet reduction pairs of arrays |
| Description: |
Sophie Toulouse In a previous work, we introduced alphabet reduction pairs of arrays (ARPAs), a family of combinatorial designs, to transport differential approximation results for k-CSPs over an alphabet of size p ? k to k-CSPs over an alphabet ?q of size q > p. ARPAs on ?q consist of two arrays of q columns satisfying the following conditions: the first array must contain a certain word composed of all symbols of ?q; no row of the second array can involve more than p different symbols of ?q; the two arrays must coincide on any subset of k columns. In the context of approximation, the target word in the first array represents an optimal solution that the second array allows us to associate with assignments involving at most p different values. Thus, we want to maximize the frequency of this particular word, and refer to ARPAs that achieve this as optimal.
To study optimal ARPAs, we consider a seemingly simpler family of combinatorial designs, called Cover Pairs of Arrays (CPAs), which can be viewed as a Boolean interpretation of ARPAs. The two arrays of a CPA still share the same number q of columns, and must match on any k of them; but they take Boolean entries, the second array is restricted to words with at most p ones, and we want to maximize the frequency of the word of q ones in the first array. Using combinatorics and linear programming, we establish the equivalence between ARPAs and CPAs in terms of maximizing the frequency of the target word. In addition, we provide optimal constructions for the case where k ? {1, 2, p}.
These results establish the optimality of ARPAs given in previous work for the case where p = k, and highlight the relevance of CPAs for the approximability of k CSPs. They also raise new questions about ARPAs, which we will discuss along with other questions about related combinatorial designs that allow refining our knowledge of how well k-CSP-q reduces to k-CSP-p.
Joint work with Jean-François Culus. |
|
|
