Improved flooding of broadcast messages using extended multipoint relaying

A common operation in wireless ad hoc networks is the flooding of broadcast messages to establish network topologies and routing tables. The flooding of broadcast messages is, however, a resource consuming process. It might require the retransmission of messages by most network nodes. It is, therefore, very important to optimize this operation. In this paper, we first analyze the multipoint relaying (MPR) flooding mechanism used by the Optimized Link State Routing (OLSR) protocol to distribute topology control (TC) messages among all the system nodes. We then propose a new flooding method, based on the fusion of two key concepts: distance-enabled multipoint relaying and connected dominating set (CDS) flooding. We present experimental simulationsthat show that our approach improves the performance of previous existing proposals.

Efficient priority rules

We study the assignment of indivisible objects with quotas (houses, jobs, or offices) to a set of agents (students, job applicants, or professors). Each agent receives at most one object and monetary compensations are not possible. We characterize efficient priority rules by efficiency, strategy-proofness, and renegotiation-proofness. Such a rule respects an acyclical priority structure and the allocations can be determined using the deferred acceptance algorithm.

Efficient and stable collective choices under gregarious preferences

We consider collective choice problems where a set of agents have to choose an alternative from a finite set and agents may or may not become users of the chosen alternative. An allocation is a pair given by the chosen alternative and the set of its users. Agents have gregarious preferences over allocations: given an allocation, they prefer that the set of users becomes larger. We require that the final allocation be efficient and stable (no agent can be forced to be a user and no agent who wants to be a user can be excluded). We propose a two-stage sequential mechanism whose unique subgame perfect equilibrium outcome is an efficient and stable allocation which also satisfies a maximal participation property.

A parameter-free approach for solving combinatorial optimization problems through biased randomization of efficient heuristics

This paper discusses the use of probabilistic or randomized algorithms for solving combinatorial optimization problems. Our approach employs non-uniform probability distributions to add a biased random behavior to classical heuristics so a large set of alternative good solutions can be quickly obtained in a natural way and without complex conguration processes. This procedure is especially useful in problems where properties such as non-smoothness or non-convexity lead to a highly irregular solution space, for which the traditional optimization methods, both of exact and approximate nature, may fail to reach their full potential. The results obtained are promising enough to suggest that randomizing classical heuristics is a powerful method that can be successfully applied in a variety of cases.

ILS-ESP An efficient, simple, and parameter-free algorithm for solving the permutation flow-shop problem

From a managerial point of view, the more effcient, simple, and parameter-free (ESP) an algorithm is, the more likely it will be used in practice for solving real-life problems. Following this principle, an ESP algorithm for solving the Permutation Flowshop Sequencing Problem (PFSP) is proposed in this article. Using an Iterated Local Search (ILS) framework, the so-called ILS-ESP algorithm is able to compete in performance with other well-known ILS-based approaches, which are considered among the most effcient algorithms for the PFSP. However, while other similar approaches still employ several parameters that can affect their performance if not properly chosen, our algorithm does not require any particular fine-tuning process since it uses basic "common sense" rules for the local search, perturbation, and acceptance criterion stages of the ILS metaheuristic. Our approach defines a new operator for the ILS perturbation process, a new acceptance criterion based on extremely simple and transparent rules, and a biased randomization process of the initial solution to randomly generate different alternative initial solutions of similar quality -which is attained by applying a biased randomization to a classical PFSP heuristic. This diversification of the initial solution aims at avoiding poorly designed starting points and, thus, allows the methodology to take advantage of current trends in parallel and distributed computing. A set of extensive tests, based on literature benchmarks, has been carried out in order to validate our algorithm and compare it against other approaches. These tests show that our parameter-free algorithm is able to compete with state-of-the-art metaheuristics for the PFSP. Also, the experiments show that, when using parallel computing, it is possible to improve the top ILS-based metaheuristic by just incorporating to it our biased randomization process with a high-quality pseudo-random number generator.

Solving two production scheduling problems with sequence-dependent set-up times

In today’s competitive markets, the importance of goodscheduling strategies in manufacturing companies lead to theneed of developing efficient methods to solve complexscheduling problems.In this paper, we studied two production scheduling problemswith sequence-dependent setups times. The setup times areone of the most common complications in scheduling problems,and are usually associated with cleaning operations andchanging tools and shapes in machines.The first problem considered is a single-machine schedulingwith release dates, sequence-dependent setup times anddelivery times. The performance measure is the maximumlateness.The second problem is a job-shop scheduling problem withsequence-dependent setup times where the objective is tominimize the makespan.We present several priority dispatching rules for bothproblems, followed by a study of their performance. Finally,conclusions and directions of future research are presented.

A retail benchmarking approach to efficient two-way access pricing

We study a retail benchmarking approach to determine access prices for interconnected networks. Instead of considering fixed access charges as in the existing literature, we study access pricing rules that determine the access price that network i pays to network j as a linear function of the marginal costs and the retail prices set by both networks. In the case of competition in linear prices, we show that there is a unique linear rule that implements the Ramsey outcome as the unique equilibrium, independently of the underlying demand conditions. In the case of competition in two-part tariffs, we consider a class of access pricing rules, similar to the optimal one under linear prices but based on average retail prices. We show that firms choose the variable price equal to the marginal cost under this class of rules. Therefore, the regulator (or the competition authority) can choose one among the rules to pursue additional objectives such as consumer surplus, network coverage or investment: for instance, we show that both static and dynamic e±ciency can be achieved at the same time.

On the set of subrings wich are directed unions of Artinian subrings

The paper contributes to the investigation of zero-dimensional rings which can be written as a directed union of Artinian subrings. We give conditions on DU(R) in order to be nonempty.

Efficient bidding with externalities

We implement a family of efficient proposals to share benefits generated in environments with externalities. These proposals extend the Shapley value to games with externalities and are parametrized through the method by which the externalities are averaged. We construct two slightly different mechanisms: one for environments with negative externalities and the other for positive externalities. We show that the subgame perfect equilibrium outcomes of these mechanisms coincide with the sharing proposals.

Observability and overcoming coordination failure in organizations

Many organizations suffer poor performance because its members fail to coordinate on efficient patterns of behavior. In previous research, we have shown that financial incentives can be used to find a way out of such performance traps. Here we examine the sensitivity of this result to the ability of people to observe others' choices. Our experiments are set in a corporate environment where subjects' payoffs depend on coordinating at high effort levels; the underlying game being played repeatedly by the employees of an experimental firm is a weak-link game. Treatments vary along two dimensions. First, subjects either start with low financial incentives for coordination, which typically leads to coordination failure, and then are switched to higher incentives or start with high incentives, which typically yield effective coordination, and are switched to low incentives. Second, as the key treatment variable, subjects either observe the effort levels chosen by all employees in their experimenta

Fair and efficient student placement with couples

We study situations of allocating positions or jobs to students or workers based on priorities. An example is the assignment of medical students to hospital residencies on the basis of one or several entrance exams. For markets without couples, e.g., for ``undergraduate student placement,'' acyclicity is a necessary and sufficient condition for the existence of a fair and efficient placement mechanism (Ergin, 2002). We show that in the presence of couples, which introduces complementarities into the students' preferences, acyclicity is still necessary, but not sufficient (Theorem 4.1). A second necessary condition (Theorem 4.2) is ``priority-togetherness'' of couples. A priority structure that satisfies both necessary conditions is called pt-acyclic. For student placement problems where all quotas are equal to one we characterize pt-acyclicity (Lemma 5.1) and show that it is a sufficient condition for the existence of a fair and efficient placement mechanism (Theorem 5.1). If in addition to pt-acyclicity we require ``reallocation-'' and ``vacancy-fairness'' for couples, the so-called dictator-bidictator placement mechanism is the unique fair and efficient placement mechanism (Theorem 5.2). Finally, for general student placement problems, we show that pt-acyclicity may not be sufficient for the existence of a fair and efficient placement mechanism (Examples 5.4, 5.5, and 5.6). We identify a sufficient condition such that the so-called sequential placement mechanism produces a fair and efficient allocation (Theorem 5.3).

Sharing the surplus: a just and efficient proposal for environments with externalities

Economic activities, both on the macro and micro level, often entail wide-spread externalities. This in turn leads to disputes regarding the compensation levels to the various parties affected. We propose a general, yet simple, method of deciding upon the distribution of the gains (costs) of cooperation in the presence of externalities. This method is shown to be the unique one satisfying several desirable properties. Furthermore, we illustrate the use of this method to resolve the sharing of benefits generated by international climate control agreements.

Forming efficient networks

In this paper, we suggest a simple sequential mechanism whose subgame perfect equilibria give rise to efficient networks. Moreover, the payoffs received by the agents coincide with their Shapley value in an appropriately defined cooperative game.

A change would do you good . . . An experimental study on how to overcome coordination failure in organizations

Many organizations suffer poor performance because individuals within the organization fail to coordinate on efficient patterns of behavior. Using controlled laboratory experiments, we study how financial incentives can be used to find a way out of such performance traps. Our experiments are set in a corporate environment where subjects' payoffs depend on coordinating at high effort levels; the underlying game being played repeatedly by employees is a weak-link game. In an initial phase, the benefits of coordination are low relative to the cost of increased effort. Play in this initial phase typically converges to an inefficient outcome with employees failing to coordinate at high effort levels. The experimental design then explores the effects of varying the financial incentives to coordinate at a higher effort level. We find that an increase in the benefits of coordination leads to improved coordination, but, surprisingly, large increases have no more impact than small increases. Once subj

A maximal domain of preferences for tops-only rules in the division problem

The division problem consists of allocating an amount M of a perfectly divisible good among a group of n agents. Sprumont (1991) showed that if agents have single-peaked preferences over their shares, the uniform rule is the unique strategy-proof, efficient, and anonymous rule. Ching and Serizawa (1998) extended this result by showing that the set of single-plateaued preferences is the largest domain, for all possible values of M, admitting a rule (the extended uniform rule) satisfying strategy-proofness, efficiency and symmetry. We identify, for each M and n, a maximal domain of preferences under which the extended uniform rule also satisfies the properties of strategy-proofness, efficiency, continuity, and "tops-onlyness". These domains (called weakly single-plateaued) are strictly larger than the set of single-plateaued preferences. However, their intersection, when M varies from zero to infinity, coincides with the set of single-plateaued preferences.