BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Amos Fiat

Amos Fiat appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computer Science and Game TheoryData Structures and AlgorithmsArtificial IntelligenceDiscrete MathematicsDistributed, Parallel, and Cluster ComputingNetworking and Internet Architecture

Catalog footprint

What is connected

13works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

13 published item(s)

preprint2021arXiv

(Almost Full) EFX Exists for Four Agents (and Beyond)

The existence of EFX allocations is a major open problem in fair division, even for additive valuations. The current state of the art is that no setting where EFX allocations are impossible is known, and EFX is known to exist for ($i$) agents with identical valuations, ($ii$) 2 agents, ($iii$) 3 agents with additive valuations, ($iv$) agents with one of two additive valuations and ($v$) agents with two-valued instances. It is also known that EFX exists if one can leave $n-1$ items unallocated, where $n$ is the number of agents. We develop new techniques that allow us to push the boundaries of the enigmatic EFX problem beyond these known results, and, arguably, to simplify proofs of earlier results. Our main results are ($i$) every setting with 4 additive agents admits an EFX allocation that leaves at most a single item unallocated, ($ii$) every setting with $n$ additive valuations has an EFX allocation with at most $n-2$ unallocated items. Moreover, all of our results extend beyond additive valuations to all nice cancelable valuations (a new class, including additive, unit-demand, budget-additive and multiplicative valuations, among others). Furthermore, using our new techniques, we show that previous results for additive valuations extend to nice cancelable valuations.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On Voting and Facility Location

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Pricing Online Decisions: Beyond Auctions

We consider dynamic pricing schemes in online settings where selfish agents generate online events. Previous work on online mechanisms has dealt almost entirely with the goal of maximizing social welfare or revenue in an auction settings. This paper deals with quite general settings and minimizing social costs. We show that appropriately computed posted prices allow one to achieve essentially the same performance as the best online algorithm. This holds in a wide variety of settings. Unlike online algorithms that learn about the event, and then make enforceable decisions, prices are posted without knowing the future events or even the current event, and are thus inherently dominant strategy incentive compatible. In particular we show that one can give efficient posted price mechanisms for metrical task systems, some instances of the $k$-server problem, and metrical matching problems. We give both deterministic and randomized algorithms. Such posted price mechanisms decrease the social cost dramatically over selfish behavior where no decision incurs a charge. One alluring application of this is reducing the social cost of free parking exponentially.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Labeling Approach to Incremental Cycle Detection

In the \emph{incremental cycle detection} problem arcs are added to a directed acyclic graph and the algorithm has to report if the new arc closes a cycle. One seeks to minimize the total time to process the entire sequence of arc insertions, or until a cycle appears. In a recent breakthrough, Bender, Fineman, Gilbert and Tarjan \cite{BeFiGiTa11} presented two different algorithms, with time complexity $O(n^2 \log n)$ and $O(m \cdot \min \{m^{1/2}, n^{2/3} \})$, respectively. In this paper we introduce a new technique for incremental cycle detection that allows us to obtain both bounds (up to a logarithmic factor). Furthermore, our approach seems more amiable for distributed implementation.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Minimal Indices for Successor Search

We give a new successor data structure which improves upon the index size of the Pǎtraşcu-Thorup data structures, reducing the index size from $O(n w^{4/5})$ bits to $O(n \log w)$ bits, with optimal probe complexity. Alternatively, our new data structure can be viewed as matching the space complexity of the (probe-suboptimal) $z$-fast trie of Belazzougui et al. Thus, we get the best of both approaches with respect to both probe count and index size. The penalty we pay is an extra $O(\log w)$ inter-register operations. Our data structure can also be used to solve the weak prefix search problem, the index size of $O(n \log w)$ bits is known to be optimal for any such data structure. The technical contributions include highly efficient single word indices, with out-degree $w/\log w$ (compared to the $w^{1/5}$ out-degree of fusion tree based indices). To construct such high efficiency single word indices we device highly efficient bit selectors which, we believe, are of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Tight Lower Bounds on Envy-Free Makespan Approximation

In this work we give a tight lower bound on makespan approximations for envy-free allocation mechanism dedicated to scheduling tasks on unrelated machines. Specifically, we show that no mechanism exists that can guarantee an envy-free allocation of jobs to $m$ machines with a makespan of less than a factor of $O(\log m)$ of the minimal makespan. Combined with previous results, this paper definitively proves that the optimal algorithm for obtaining a minimal makespan for any envy-free division can at best approximate the makespan to a factor of $O(\log m)$.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Truth and Envy in Capacitated Allocation Games

We study auctions with additive valuations where agents have a limit on the number of goods they may receive. We refer to such valuations as {\em capacitated} and seek mechanisms that maximize social welfare and are simultaneously incentive compatible, envy-free, individually rational, and have no positive transfers. If capacities are infinite, then sequentially repeating the 2nd price Vickrey auction meets these requirements. In 1983, Leonard showed that for unit capacities, VCG with Clarke Pivot payments is also envy free. For capacities that are all unit or all infinite, the mechanism produces a Walrasian pricing (subject to capacity constraints). Here, we consider general capacities. For homogeneous capacities (all capacities equal) we show that VCG with Clarke Pivot payments is envy free (VCG with Clarke Pivot payments is always incentive compatible, individually rational, and has no positive transfers). Contrariwise, there is no incentive compatible Walrasian pricing. For heterogeneous capacities, we show that there is no mechanism with all 4 properties, but at least in some cases, one can achieve both incentive compatibility and envy freeness.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Combinatorial Auctions with Budgets

We consider budget constrained combinatorial auctions where bidder $i$ has a private value $v_i$, a budget $b_i$, and is interested in all the items in $S_i$. The value to agent $i$ of a set of items $R$ is $|R \cap S_i| \cdot v_i$. Such auctions capture adword auctions, where advertisers offer a bid for ads in response to an advertiser-dependent set of adwords, and advertisers have budgets. It is known that even of all items are identical and all budgets are public it is not possible to be truthful and efficient. Our main result is a novel auction that runs in polynomial time, is incentive compatible, and ensures Pareto-optimality for such auctions when the valuations are private and the budgets are public knowledge. This extends the result of Dobzinski et al. (FOCS 2008) for auctions of multiple {\sl identical} items and public budgets to single-valued {\sl combinatorial} auctions with public budgets.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On the Interplay between Incentive Compatibility and Envy Freeness

We study mechanisms for an allocation of goods among agents, where agents have no incentive to lie about their true values (incentive compatible) and for which no agent will seek to exchange outcomes with another (envy-free). Mechanisms satisfying each requirement separately have been studied extensively, but there are few results on mechanisms achieving both. We are interested in those allocations for which there exist payments such that the resulting mechanism is simultaneously incentive compatible and envy-free. Cyclic monotonicity is a characterization of incentive compatible allocations, local efficiency is a characterization for envy-free allocations. We combine the above to give a characterization for allocations which are both incentive compatible and envy free. We show that even for allocations that allow payments leading to incentive compatible mechanisms, and other payments leading to envy free mechanisms, there may not exist any payments for which the mechanism is simultaneously incentive compatible and envy-free. The characterization that we give lets us compute the set of Pareto-optimal mechanisms that trade off envy freeness for incentive compatibility.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Envy, Multi Envy, and Revenue Maximization

We study the envy free pricing problem faced by a seller who wishes to maximize revenue by setting prices for bundles of items. If there is an unlimited supply of items and agents are single minded then we show that finding the revenue maximizing envy free allocation/pricing can be solved in polynomial time by reducing it to an instance of weighted independent set on a perfect graph. We define an allocation/pricing as \textit{multi envy free} if no agent wishes to replace her allocation with the union of the allocations of some set of other agents and her price with the sum of their prices. We show that it is \textit{coNP}-hard to decide if a given allocation/pricing is multi envy free. We also show that revenue maximization multi envy free allocation/pricing is \textit{APX} hard. Furthermore, we give efficient algorithms and hardness results for various variants of the highway problem.

0 citations0 reviewsNo code linkedOpen access
preprint2002arXiv

Competitive Paging Algorithms

The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. This paper introduces the marking algorithm, a simple randomized on-line algorithm for the paging problem, and gives a proof that its performance guarantee (competitive ratio) is O(log k). In contrast, no deterministic on-line algorithm can have a performance guarantee better than k.

0 citations0 reviewsNo code linkedOpen access