JCJavier Cembrano

Javier Cembrano

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Javier Cembrano has a total of 16 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Impartial selection under combinatorial constraints

    by Javier Cembrano, Max Klimm, Arturo Merino

  • Open Access

    On the strategyproof allocation of items under a budget constraint

    by Javier Cembrano, Max Klimm, Martin Knaack

  • Improved Bounds for Single-Nomination Impartial Selection

    by Javier Cembrano, Felix Fischer, Max Klimm

    A randomized selection mechanism returns a probability distribution over individuals based on mutual nominations among them; it is impartial if the selection probability of each individual is independent of the nominations they cast and [ ]-optimal if the expected number of nominations received by the selected individual is always at least [ ] times that received by any individual. When individuals can cast multiple nominations, the permutation mechanism is [ ]-optimal, and this is the best possible. We show that the permutation mechanism does not provide the best possible factor in the natural situation when individuals cast exactly one nomination. Specifically, we provide a tight analysis of the permutation mechanism showing that it is [ ]-optimal in this case, and we design a new mechanism that is [ ]-optimal for [ ]. We further prove that no impartial mechanism can be better than [ ]-optimal. Funding: This research was supported by the Deutsche Forschungsgemeinschaft [Grant 431465007] and by the Engineering and Physical Sciences Research Council [Grant EP/T015187/1].

  • Open Access

    Impartial Selection with Predictions

    by Javier Cembrano, Felix Fischer, Max Klimm

    We study the selection of agents based on mutual nominations, a theoretical problem with many applications from committee selection to AI alignment. As agents both select and are selected, they may be incentivized to misrepresent their true opinion about the eligibility of others to influence their own chances of selection. Impartial mechanisms circumvent this issue by guaranteeing that the selection of an agent is independent of the nominations cast by that agent. Previous research has established strong bounds on the performance of impartial mechanisms, measured by their ability to approximate the number of nominations for the most highly nominated agents. We study to what extent the performance of impartial mechanisms can be improved if they are given a prediction of a set of agents receiving a maximum number of nominations. Specifically, we provide bounds on the consistency and robustness of such mechanisms, where consistency measures the performance of the mechanisms when the prediction is accurate and robustness its performance when the prediction is inaccurate. For the general setting where up to $k$ agents are to be selected and agents nominate any number of other agents, we give a mechanism with consistency $1-O\big(\frac{1}{k}\big)$ and robustness $1-\frac{1}{e}-O\big(\frac{1}{k}\big)$. For the special case of selecting a single agent based on a single nomination per agent, we prove that $1$-consistency can be achieved while guaranteeing $\frac{1}{2}$-robustness. A close comparison with previous results shows that (asymptotically) optimal consistency can be achieved with little to no sacrifice in terms of robustness.

  • Open Access

    Online Proportional Apportionment

    by Javier Cembrano, Jose Correa, Svenja M. Griesbach, Victor Verdugo

    Traditionally, the problem of apportioning the seats of a legislative body has been viewed as a one-shot process with no dynamic considerations. While this approach is reasonable for some settings, dynamic aspects play an important role in many others. We initiate the study of apportionment problems in an online setting. Specifically, we introduce a framework for proportional apportionment with no information about the future. In this model, time is discrete and there are $n$ parties that receive a certain share of the votes at each time step. An online algorithm needs to irrevocably assign a prescribed number of seats at each time, ensuring that each party receives its fractional share rounded up or down, and that the cumulative number of seats allocated to each party remains close to its cumulative share up to that time. We study deterministic and randomized online apportionment methods. For deterministic methods, we construct a family of adversarial instances that yield a lower bound, linear in $n$, on the worst-case deviation between the seats allocated to a party and its cumulative share. We show that this bound is best possible and is matched by a natural greedy method. As a consequence, a method guaranteeing that the cumulative number of seats assigned to each party up to any step equals its cumulative share rounded up or down (global quota) exists if and only if $n\leq 3$. Then, we turn to randomized allocations and show that, for $n\leq 3$, we can randomize over methods satisfying global quota with the additional guarantee that each party receives, in expectation, its proportional share in every step. Our proof is constructive: Any method satisfying these properties can be obtained from a flow on a recursively constructed network. We showcase the applicability of our results to obtain approximate solutions in the context of online dependent rounding procedures.

  • New Combinatorial Insights for Monotone Apportionment

    by Javier Cembrano, José Correa, Ulrike Schmidt-Kraepelin, Alexandros Tsigonias-Dimitriadis, Victor Verdugo

    The apportionment problem constitutes a fundamental problem in democratic societies: How to distribute a fixed number of seats among a set of states in proportion to the states’ populations? This—seemingly simple—task has led to a rich literature and has become well known in the context of the U.S. House of Representatives. In this paper, we connect the design of monotone apportionment methods to classic problems from discrete geometry and combinatorial optimization and explore the extent to which randomization can enhance proportionality. We first focus on the well-studied family of stationary divisor methods, which satisfy the strong population monotonicity property, and show that this family produces only a slightly superlinear number of different outputs as a function of the number of states. While our upper and lower bounds leave a small gap, we show that—surprisingly—closing this gap would solve a long-standing open problem from discrete geometry, known as the complexity of k-levels in line arrangements. The main downside of divisor methods is their violation of the quota axiom, that is, every state should receive [ ] or [ ] seats, where [ ] is the proportional share of the state. As we show that randomizing over divisor methods can only partially overcome this issue, we propose a relaxed version of divisor methods in which the total number of seats may slightly deviate from the house size. By randomizing over these methods, we can simultaneously satisfy population monotonicity, quota, and ex-ante proportionality. Finally, we turn our attention to quota-compliant methods that are house-monotone, that is, no state may lose a seat when the house size is increased. We provide a polyhedral characterization based on network flows, which implies a simple description of all ex-ante proportional randomized methods that are house-monotone and quota-compliant. Funding: This work was supported by National Science Foundation (DMS-1928930); Agencia Nacional de Investigación y Desarrollo (Anillo ACT210005, Center for Mathematical Modeling FB210005, FONDECYT 1241846); Alfred P. Sloan Foundation (G-2021-16778).


  • Open Access

    Optimal impartial correspondences

    by Javier Cembrano, Felix Fischer, Max Klimm

    We study mechanisms that select a subset of a set of agents based on nominations among them. The goal is to maximize the minimum number of nominations received by any selected agent, subject to an impartiality constraint that the selection of a particular agent must be independent of the nominations cast by that agent. For situations where each agent casts at most d nominations, we give a mechanism that selects at most $$d+1$$ d + 1 agents and only selects agents who receive a maximum number of nominations or the maximum number of nominations minus one. We then show that this is best possible in the sense that no impartial mechanism can only select agents receiving a maximum number of nominations, even without any restrictions on the number of selected agents. We finally establish the following trade-off between the maximum number of agents selected and the minimum number of nominations for any selected agent when there are no constraints on the number of nominations each agent can cast: when selecting at most k agents out of n , it is possible to only select agents that receive at least the maximum number of nominations minus $$\big \lfloor \frac{n-2}{k-1} \big \rfloor +1$$ ⌊ n - 2 k - 1 ⌋ + 1 .

  • Open Access

    Proportionality in multiple dimensions to design electoral systems

    by Javier Cembrano, José Correa, Gonzalo Díaz, Victor Verdugo

    Proportionality is a foundational principle in the election of representatives for legislative bodies. In this work, we provide an axiomatic justification for a recently proposed notion of multidimensional proportionality and extend it to incorporate two common electoral constraints: vote threshold for list eligibility and the election of the most-voted candidate in each district. Building on these results, we design methods based on multidimensional proportionality and apply them to the 2021 Chilean Constitutional Convention election, considering political lists, districts, and genders as dimensions. We evaluate the resulting apportionments according to three criteria: proportionality, representativeness, and voting power. Whereas local and global methods exhibit a natural trade-off between local and global proportionality, incorporating the election of district-level winners into methods based on 3-dimensional proportionality enables a balance between both notions while ensuring higher representativeness and a more equitable voting power. These findings are further supported by experiments on the 2023 Finnish Parliamentary Election.


  • Open Access

    Near-feasible Fair Allocations in Two-sided Markets

    by Javier Cembrano, Andrés Moraga, Victor Verdugo


  • Open Access

    Packing a Knapsack with Items Owned by Strategic Agents

    by Javier Cembrano, Max Klimm, Martin Knaack

    This paper considers a scenario within the field of mechanism design without money where a mechanism designer is interested in selecting items with maximum total value under a knapsack constraint. The items, however, are controlled by strategic agents who aim to maximize the total value of their items in the knapsack. This is a natural setting, e.g., when agencies select projects for funding, companies select products for sale in their shops, or hospitals schedule MRI scans for the day. A mechanism governing the packing of the knapsack is strategyproof if no agent can benefit from hiding items controlled by them to the mechanism. We are interested in mechanisms that are strategyproof and $α$-approximate in the sense that they always approximate the maximum value of the knapsack by a factor of $α\in [0,1]$. First, we give a deterministic mechanism that is $\frac{1}{3}$-approximate. For the special case where all items have unit density, we design a $\frac{1}φ$-approximate mechanism where $1/φ\approx 0.618$ is the inverse of the golden ratio. This result is tight as we show that no deterministic strategyproof mechanism with a better approximation exists. We further give randomized mechanisms with approximation guarantees of $1/2$ for the general case and $2/3$ for the case of unit densities. For both cases, no strategyproof mechanism can achieve an approximation guarantee better than $1/(5φ-7)\approx 0.917$.