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).

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.

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.

Consider a seller that intends to auction some item. The seller can invest money and effort in advertising in different market segments in order to recruit n bidders to the auction. Alternatively, the seller can have a much cheaper and focused marketing operation and recruit the same number of bidders from a single market segment. Which marketing operation should the seller choose?

The classical degree realization problem is defined as follows: Given a sequence d̄ = (d_1,…,d_n) of positive integers, construct an n-vertex graph in which each vertex u_i has degree d_i (or decide that no such graph exists). In this article, we present and study the related selected neighbor degree realization problem, which requires that each vertex u_i of G has a neighbor of degree d_i. We solve the problem when G is required to be acyclic (i.e., a forest), and present a sufficient and necessary condition for a given sequence to be realizable.

We study graph realization problems from a distributed perspective. The problem is naturally applicable to the distributed construction of overlay networks that must satisfy certain degree or connectivity properties, and we study it in the node capacitated clique (NCC) model of distributed computing, recently introduced for representing peer-to-peer networks.We focus on two central variants, degree-sequence realization and minimum threshold-connectivity realization. In the degree sequence problem, each node v is associated with a degree d(v), and the resulting degree sequence is realizable if it is possible to construct an overlay network in which the degree of each node v is d(v). The minimum threshold-connectivity problem requires us to construct an overlay network that satisfies connectivity constraints specified between every pair of nodes.Overlay network realizations can be either explicit or implicit. Explicit realizations require both endpoints of any edge in the realized graph to be aware of the edge. In implicit realizations, on the other hand, at least one endpoint of each edge of the realized graph needs to be aware of the edge.The main realization algorithms we present are the following. (1) A $\tilde O(\min \{ \sqrt m ,\Delta \} )$ time algorithm for implicit realization of a degree sequence. Here, Δ = maxvd(v) is the maximum degree and m = (1/2) v d(v) is the number of edges in the final realization. (2) A $\tilde O\left( \Delta \right)$ time algorithm for an explicit realization of a degree sequence. We first compute an implicit realization and then transform it into an explicit one in $\tilde O\left( \Delta \right)$ additional rounds. (3) A $\tilde O\left( \Delta \right)$ time algorithm for the threshold connectivity problem that obtains an explicit solution and an improved $\tilde O\left( 1 \right)$ algorithm for implicit realization when all nodes know each other’s IDs. These algorithms are 2-approximations w.r.t. the number of edges. Our algorithms are complemented by lower bounds showing tightness up to log n factors. Additionally, we provide algorithms for realizing trees and an $\tilde O\left( 1 \right)$ round algorithm for approximate degree sequence realization.

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).

This paper demonstrates that the Preferential Attachment rule naturally emerges in the context of evolutionary network formation, as the unique Nash equilibrium of a simple social network game. In this game, each node aims at maximizing its degree in the future, representing its social capital in the "society" formed by the nodes and their connections. This result provides additional formal support to the commonly used Preferential Attachment model, initially designed to capture the "rich get richer" aphorism. In the process of establishing our result, we expose new connections between Preferential Attachment, random walks, and Young»s Lattice.

As part of a national strategic plan recently established by the Ministry of Education in Israel to strengthen science and technology education, an innovative Computer Science (CS) curriculum for middle school was developed. One main goal of the new curriculum is to expose students at an early stage of education to the fundamentals of CS and computational thinking, and to encourage students to study CS in the future. We present the curriculum and its initial implementation, focusing on issues of teachers' professional development.

Attracting students to computer science studies has always been a challenge. Contests play an important role as a source of inspiration and can increase students' interest in the contest's related domain. The Beaver international contest on computer science and computer fluency was established with the goal of conveying computer science concepts to as many youngsters as possible and of motivating them to become more interested in computing. For the last few years the contest has been operating in several countries in Europe (http://www.bebras.org). Recently, in order to attract youngsters to study computer science, it was planned to initiate the Beaver project in Israel, while adapting its framework to the requirements of the national educational system.

Attracting young students to computer science studies has always been a challenge. We present a unique outreach program: the Beaver international contest on informatics and computer fluency that was established with the goal to convey computing concepts to as many youngsters as possible in a way that can motivate them to be more interested in computing. For the last few years the contest has been operating in several countries in Europe (http://www.bebras.org). Recently, in order to attract youngsters to study computer science, the Beaver project was initiated in Israel by adapting its framework to the requirements of the national educational system.

With the development of XML Web Services, the Internet could become an integral part of and the basis for teaching computer science and software engineering. The approach has been applied to a university course for students studying introduction to computer science from the point of view of software development in a stateless, Internet environment. The feedback obtained from the course attests to its success. This article is an attempt to focus attention on stateless programming and to give this paradigm its appropriate status in computer science studies. The course could provide an alternative to traditional patterns of computer science. The walk-through presented here is a way of demonstrating this new paradigm. The starting point for the course is the understanding of the Internet environment and the stateless HTTP request, followed by the use and development of XML Web Services integrated with XML and XML schemas, databases and SQL language.