Author name cluster

Avi Cohen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

SODA Conference 2023 Conference Paper

Interdependent Public Projects

Avi Cohen
Michal Feldman
Divyarthi Mohan
Inbal Talgam-Cohen

In the interdependent values (IDV) model introduced by Milgrom and Weber [1982], agents have private signals that capture their information about different social alternatives, and the valuation of every agent is a function of all agent signals. While interdependence has been mainly studied for auctions, it is extremely relevant for a large variety of social choice settings, including the canonical and practically important setting of public projects. The IDV model is much more realistic but also very challenging relative to the standard independent private values model. Welfare guarantees for IDV have been achieved mainly through two alternative conditions known as single-crossing and submodularity over signals (SOS). In either case, the existing theory falls short of solving the public projects setting. Our contribution is twofold: (i) We give a useful characterization of truthfulness for IDV public projects, parallel to the known characterization for independent private values, and identify the domain frontier for which this characterization applies; (ii) Using this characterization, we provide possibility and impossibility results for welfare approximation in public projects with SOS valuations. Our main impossibility result is that, in contrast to auctions, no universally truthful mechanism performs better for public projects with SOS valuations than choosing a project at random. Our main positive result applies to excludable public projects with SOS, for which we establish a constant factor approximation similar to auctions. Our results suggest that exclusion may be a key tool for achieving welfare guarantees in the IDV model. * The full version of the paper can be accessed at https: //arxiv. org/abs/2204. 08044. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement no. 866132), by the Israel Science Foundation (ISF grant nos. 317/17 and 336/18), by an Amazon Research Award, and by the NSF-BSF (grant no. 2020788).

Details

AAAI Conference 2022 Conference Paper

Almost Full EFX Exists for Four Agents

Ben Berger
Avi Cohen
Michal Feldman
Amos Fiat

The existence of EFX allocations of goods 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 yet, existence results are known only for very restricted settings, such as: (i) agents with identical valuations, (ii) 2 agents, and (iii) 3 agents with additive valuations. 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 result is that every setting with 4 additive agents admits an EFX allocation that leaves at most a single item unallocated. Beyond our main result, we introduce a new class of valuations, termed nice cancelable, which includes additive, unit-demand, budget-additive and multiplicative valuations, among others. Using our new techniques, we show that both our results and previous results for additive valuations extend to nice cancelable valuations.

PDF Details

TCS Journal 2022 Journal Article

Hotelling games in fault-prone settings

Chen Avin
Avi Cohen
Zvi Lotker
David Peleg

The n-player Hotelling game calls for each player to choose a point on the line segment, so as to maximize the size of his Voronoi cell. This paper studies the Hotelling game in fault-prone settings. Two fault models are studied: line faults and player faults. The first model assumes that the environment is prone to failure: with some probability, a disconnection occurs at a random point on the line, splitting it into two separate segments and modifying each player's Voronoi cell accordingly. A complete characterization of the Nash equilibria of this variant is provided for every n. Additionally, a one to one correspondence is shown between equilibria of this variant and of the Hotelling game with no faults. The second fault model assumes the players are prone to failure: each player is removed from the game with some probability, changing the payoffs of the remaining players accordingly. It is shown that for n ≥ 3 this variant of the game has no Nash equilibria.

Details DOI

MFCS Conference 2021 Conference Paper

Budgeted Dominating Sets in Uncertain Graphs

Keerti Choudhary
Avi Cohen
N. S. Narayanaswamy
David Peleg
R. Vijayaragunathan

We study the Budgeted Dominating Set (BDS) problem on uncertain graphs, namely, graphs with a probability distribution p associated with the edges, such that an edge e exists in the graph with probability p(e). The input to the problem consists of a vertex-weighted uncertain graph 𝒢 = (V, E, p, ω) and an integer budget (or solution size) k, and the objective is to compute a vertex set S of size k that maximizes the expected total domination (or total weight) of vertices in the closed neighborhood of S. We refer to the problem as the Probabilistic Budgeted Dominating Set (PBDS) problem. In this article, we present the following results on the complexity of the PBDS problem. 1) We show that the PBDS problem is NP-complete even when restricted to uncertain trees of diameter at most four. This is in sharp contrast with the well-known fact that the BDS problem is solvable in polynomial time in trees. We further show that PBDS is 𝖶[1]-hard for the budget parameter k, and under the Exponential time hypothesis it cannot be solved in n^o(k) time. 2) We show that if one is willing to settle for (1-ε) approximation, then there exists a PTAS for PBDS on trees. Moreover, for the scenario of uniform edge-probabilities, the problem can be solved optimally in polynomial time. 3) We consider the parameterized complexity of the PBDS problem, and show that Uni-PBDS (where all edge probabilities are identical) is 𝖶[1]-hard for the parameter pathwidth. On the other hand, we show that it is FPT in the combined parameters of the budget k and the treewidth. 4) Finally, we extend some of our parameterized results to planar and apex-minor-free graphs. Our first hardness proof (Thm. 1) makes use of the new problem of k-Subset Σ-Π Maximization (k-SPM), which we believe is of independent interest. We prove its NP-hardness by a reduction from the well-known k-SUM problem, presenting a close relationship between the two problems.

Details

IROS Conference 2020 Conference Paper

The AmphiSTAR High Speed Amphibious Sprawl Tuned Robot: Design and Experiments

Avi Cohen
David Zarrouk

This paper details the development, modeling and performance of AmphiSTAR, a novel high-speed amphibious robot. The palm size AmphiSTAR, which belongs to the family of STAR robots, is a "wheeled" robot fitted with propellers at its bottom that allow it to crawl on the ground and run (i. e. hover) on water at high speeds. The AmphiSTAR is inspired by two members of the animal kingdom. It possesses a sprawling mechanism inspired by cockroaches, and it is designed to run on water at high speeds like the Basilisk lizard. We start by presenting the mechanical design of the robot and its control system. Then we model AmphiSTAR when crawling, swimming and running on water. We then report experiments on the robot to measure its lift and thrust forces in its on-water running mode and evaluate its energy consumption. The results show that in the on-water running mode, the lift forces are a function of the work volume of the propellers whereas the thrust forces are a linear function of the propellers' rotating speed. Based on these results, the final version of the 3D printed robot was built and experimentally tested in multiple scenarios. The experimental robot can crawl over the ground with performances similar to the original STAR robot and can attain speeds of 3. 6 m/s. The robot can run continuously on water surfaces at speeds of 1. 5 m/s. It can also swim (i. e. float while advancing by rotating its propellers) at low speeds and transition from swimming to crawling (see video).

Details