Noticias en español
Apportionment Mechanisms under Parity Constraints and the case of Chile and a new Political Constitution.
Abstract: How many seats should be allocated to each political party in an election? This question has a long and rich history, and plays a fundamental role in order to ensure appropriate levels of representation in the parliaments. We consider this question in the presence of types (e.g. men and women), where apart from ensuring proportionality at the party level, we also have to find an allocation which is paritary for the types. We consider two different approaches: one of them, with a greedy/local search paradigm, corresponds to a mechanism recently approved in the chilean...
Read MoreOn the two-dimensional knapsack problem for convex polygons.
Abstract: We study the two-dimensional geometric knapsack problem for convex polygons. Given a set of weighted convex polygons and a square knapsack, the goal is to select the most profitable subset of the given polygons that fits non-overlappingly into the knapsack. We allow rotating the polygons by arbitrary angles. In this talk we will first present: – a quasi-poly time O(1)-approximation – a poly time O(1)-approximation algorithm if all input polygons are triangles. We will then look into the setting of resource augmentation, i.e., we allow to increase the size of the...
Read MoreStrategic and Structural Aspects of Bitcoin Mining.
Abstract: Just over a decade ago, Satoshi Nakamoto published a landmark white paper outlining the backbone protocol to Bitcoin, arguably the world’s first mainstream digital currency. Through the Nakamoto protocol and blockchain technology, users can reliably agree upon a common transaction history maintained by miners on the public Bitcoin ledger in a decentralised and anonymous fashion. This is possible in part because agents within the protocol are assumed to be strategic rather than adversarial—a fair assumption when creating a ledger for currency. The Nakamoto protocol is...
Read MorePacing Mechanisms For Ad Auctions.
Abstract: Budgets play a significant role in real-world sequential auction markets such as those implemented by Internet companies. To maximize the value provided to auction participants, spending is smoothed across auctions so budgets are used for the best opportunities. Motivated by pacing mechanisms used in practice by online ad auction platforms, we discuss smoothing procedures that ensure that campaign daily budgets are consistent with maximum bids. Reinterpreting this process as a game between bidders, we introduce the notion of pacing equilibrium, and study properties such as...
Read MoreCombinatorial Optimization Augmented with Machine Learning.
Abstract: Combinatorial optimization often focuses on optimizing for the worst-case. However, the best algorithm to use depends on the “relative inputs”, which is application specific and often does not have a formal definition. The talk gives a new theoretical model for designing algorithms that are tailored to inputs for the application at hand. In the model, learning is performed on past problem instances to make predictions on future instances. These predictions are incorporated into the design and analysis of the algorithm. The predictions can be used to achieve...
Read More