Amos Fiat

Yossi Azar, Amos Fiat, Federico Fusco

We study sequential bilateral trade where sellers and buyers valuations are completely arbitrary (i.e., determined by an adversary). Sellers and buyers are strategic agents with private valuations for the good and the goal is to design a mechanism that maximizes efficiency (or gain from trade) while being incentive compatible, individually rational and budget balanced. In this paper we consider gain from trade which is harder to approximate than social welfare. We consider a variety of feedback scenarios and distinguish the cases where the mechanism posts one price and when it can post different prices for buyer and seller. We show several surprising results about the separation between the different scenarios. In particular we show that (a) it is impossible to achieve sublinear $α$-regret for any $α<2$, (b) but with full feedback sublinear $2$-regret is achievable (c) with a single price and partial feedback one cannot get sublinear $α$ regret for any constant $α$ (d) nevertheless, posting two prices even with one-bit feedback achieves sublinear $2$-regret, and (e) there is a provable separation in the $2$-regret bounds between full and partial feedback.

Ran Canetti, Amos Fiat, Yannai A. Gonczarowski

A central tenet in mechanism design is the ability to irrevocably commit to a mechanism. Commitment is achieved by public declaration, letting players verify incentive properties in advance and the outcome in retrospect. However, public declaration can reveal superfluous information that is private to the mechanism designer, such as her target function or costs. We propose a new approach to commitment, and show how to commit to, and run, any given mechanism without disclosing it, while enabling the verification of incentive properties and the outcome -- all without any mediators. Our framework leverages zero-knowledge proofs -- a cornerstone of modern cryptographic theory.

Yossi Azar, Itamar Biran, Amos Fiat

We study the minimization counterpart of the classic prophet inequality, often termed the min prophet or cost prophet inequality. Unlike the maximization setting, where simple threshold algorithms achieve half of the prophet's value, the minimization setting is significantly harder, with an exponential lower bound even for i.i.d.\ variables. We study a multi-choice relaxation in which the algorithm may select multiple variables and gets to choose the best amongst them (the minimum amongst those selected). Our goal is to minimize the expected number of selections while achieving a constant competitive ratio. For adversarial order, we show that a constant competitive ratio requires a nearly linear number of choices in expectation, ergo, $Ω(n/\ln n)$. In contrast, we show that for the prophet secretary model (random order) one can attain constant competitiveness while requiring only an exponentially smaller expected number of choices i.e. $O(\ln n)$. We give a refined analysis and define $M$ to be the ratio of the minimum expected value of any single variable to the expected minimum value of all variables (the prophet's value) and present an algorithm that achieves a constant competitive ratio with $O(\min\{\ln \ln M, \ln n\})$ choices in expectation for the prophet secretary. We show that this is tight up to low order log factors even for the special case of the i.i.d. model. We also show that if we insist on a deterministic bound on the number of choices then every constant competitive algorithm requires $n$ choices. This holds even in the i.i.d.\ setting Finally, we consider a variant where both the algorithm and the adversary choose $r$ values and pay their sum, this is the minimization multi unit version. We extend our techniques to the multi-unit variant for i.i.d.\ variables, achieving a constant competitive ratio with a small expected number of choices.

Michal Feldman, Amos Fiat, Yael Nissan et al.

We introduce epistemic pairwise maximin share (EPMMS), a new fairness notion for fair division of indivisible goods. Two fundamental notions in this setting are envy-freeness up to any item (EFX) and pairwise maximin share (PMMS), with PMMS being stronger than EFX. While EFX has been extensively studied, far less is known about PMMS. Recent work shows that relaxing EFX via an epistemic perspective leads to substantial progress on the EFX problem, raising the question of whether a similar approach can advance our understanding of PMMS. Motivated by this, we initiate the study of EPMMS, the epistemic relaxation of PMMS. EPMMS is more challenging than EEFX: the key approaches underlying recent progress on epistemic EFX inherently fail to extend to EPMMS. We establish the following results. (1) For additive valuations, $4/5$-EPMMS allocations exist and can be efficiently computed. (2) For bivalued valuations, EPMMS allocations exist and can be efficiently computed; in fact, we obtain the stronger guarantee of epistemic groupwise maximin share (EGMMS), which also strengthens the existence of MMS allocations for this setting. (3) We prove that EPMMS allocations exist in two settings where MMS allocations need not exist: instances with three additive agents or two types of additive agents.

Michal Feldman, Amos Fiat, Iddan Golomb

We study mechanisms for candidate selection that seek to minimize the social cost, where voters and candidates are associated with points in some underlying metric space. The social cost of a candidate is the sum of its distances to each voter. Some of our work assumes that these points can be modeled on a real line, but other results of ours are more general. A question closely related to candidate selection is that of minimizing the sum of distances for facility location. The difference is that in our setting there is a fixed set of candidates, whereas the large body of work on facility location seems to consider every point in the metric space to be a possible candidate. This gives rise to three types of mechanisms which differ in the granularity of their input space (voting, ranking and location mechanisms). We study the relationships between these three classes of mechanisms. While it may seem that Black's 1948 median algorithm is optimal for candidate selection on the line, this is not the case. We give matching upper and lower bounds for a variety of settings. In particular, when candidates and voters are on the line, our universally truthful spike mechanism gives a [tight] approximation of two. When assessing candidate selection mechanisms, we seek several desirable properties: (a) efficiency (minimizing the social cost) (b) truthfulness (dominant strategy incentive compatibility) and (c) simplicity (a smaller input space). We quantify the effect that truthfulness and simplicity impose on the efficiency.