Designing Efficient Markets & Mechanisms

This paper introduces redundancy-aware greedy algorithms for the cardinality- and budget-constrained maximum coverage problems. Unlike classical greedy procedures, our approach identifies and removes previously selected alternatives that become redundant as new selections are added, thereby freeing capacity or budget for additional selection. To demonstrate practical utility, we analyze an Israel-based broadband infrastructure deployment procurement auction. Our results show that the redundancy-aware algorithm increases the number of connected households while reducing redundant households in overlap areas and approaching the LP-relaxation upper bound. Finally, while the general 1-1/e approximation ratio remains tight in general environments, we show that in a circle-arc environment with alternative length at most k items, the baseline greedy guarantees 3/4, whereas the redundancy-aware algorithm guarantees 3/4+1/4k relative to the optimal solution.

Public broadband subsidy programs increasingly require regulators to allocate limited public funds across many geographically interdependent projects under both informational and computational constraints. When firms may submit bundled offers over clusters of areas, the winner-determination problem becomes combinatorial: the regulator must balance coverage, budget, and overlap across competing offers. We study this problem through the case of broadband deployment procurement in Israel. We compare three allocation rules: (i) a Greedy base-2 algorithm with a worst-case approximation ratio of 1-e^-1 relative to the optimal solution, with computational complexity O(n^4); (ii) the algorithm implemented by the Israeli Ministry of Communications (MoC), which runs in O(n^2) time but has no known worst-case bound; and (iii) a Hybrid algorithm that combines elements of both approaches. Using a case study of fiber-optic deployment in Israel, we show that the Ministry’s algorithm and the Hybrid variant achieve broader coverage at lower cost by reducing costly overlap and improving budget efficiency, thus more effectively meeting auction objectives. Benchmarked against the optimal solution on small instances, all three methods perform close to optimal, with a modest advantage for the Hybrid and MoC algorithms.

This paper compares two optimization approaches for broadband infrastructure investment under budget constraints. The first is a procurement auction based on a greedy base-2 algorithm, which guarantees a worst-case performance ratio of 1 - e^-1 relative to the optimum, with a runtime of O(n^4). The second is a method implemented by the Israeli Ministry of Communications in recent procurement auctions, which runs in O(n^2) time but has no known performance bound. Using the case study of fiber-optic deployment in Israel, we show that the Ministry’s algorithm achieves broader coverage at lower cost, thus more effectively meeting auction objectives. Benchmarking both methods against the optimal solution on small instances, we find that each approaches optimality, with a slight budget-efficiency advantage for the Ministry’s algorithm.

This paper compares two optimization approaches for broadband infrastructure investment under budget constraints. The first is a procurement auction based on a greedy base-2 algorithm, which guarantees a worst-case performance ratio of 1-e^(-1)≈0.632 relative to the optimum, with runtime O(n^4). The second is a method implemented by the Israeli Ministry of Communications in recent procurement auctions, which runs in O(n^2 ) time but has no known performance bound. Using the case study of fiber-optic deployment in Israel, we show that the Ministry’s algorithm achieves broader coverage at lower cost, thus more effectively meeting auction objectives. Benchmarking both methods against the optimal solution on small instances, we find that each approaches optimality, with a slight budget-efficiency advantage for the Ministry’s algorithm.