Budget-Balance, Fairness and Minimal Manipulability

A common real-life problem is to fairly allocate a number of indivisible objects and a fixed amount of money among a group of agents. Fairness requires that each agent weakly prefers his consumption bundle to any other agent’s bundle. Under fairness, efficiency is equivalent to budget-balance (all the available money is allocated among the agents). Budget-balance and fairness in general are incompatible with non-manipulability (Green and Laffont, 1979). We propose a new notion of the degree of manipulability which can be used to compare the ease of manipulation in allocation mechanisms. Our measure counts for each problem the number of agents who can manipulate the rule. Given this notion, the main result demonstrates that maximally linked fair allocation rules are the minimally manipulable rules among all budget-balanced and fair allocation mechanisms. Such rules link any agent to the bundle of a pre-selected agent through indifferences (which can be viewed as indirect egalitarian equivalence).

Structural budget balance: methodology and estimation for the Chilean central government 1987-2001

Includes bibliography

A Convex Optimization Framework for Almost Budget Balanced Allocation of a Divisible Good

We address the problem of allocating a single divisible good to a number of agents. The agents have concave valuation functions parameterized by a scalar type. The agents report only the type. The goal is to find allocatively efficient, strategy proof, nearly budget balanced mechanisms within the Groves class. Near budget balance is attained by returning as much of the received payments as rebates to agents. Two performance criteria are of interest: the maximum ratio of budget surplus to efficient surplus, and the expected budget surplus, within the class of linear rebate functions. The goal is to minimize them. Assuming that the valuation functions are known, we show that both problems reduce to convex optimization problems, where the convex constraint sets are characterized by a continuum of half-plane constraints parameterized by the vector of reported types. We then propose a randomized relaxation of these problems by sampling constraints. The relaxed problem is a linear programming problem (LP). We then identify the number of samples needed for ``near-feasibility'' of the relaxed constraint set. Under some conditions on the valuation function, we show that value of the approximate LP is close to the optimal value. Simulation results show significant improvements of our proposed method over the Vickrey-Clarke-Groves (VCG) mechanism without rebates. In the special case of indivisible goods, the mechanisms in this paper fall back to those proposed by Moulin, by Guo and Conitzer, and by Gujar and Narahari, without any need for randomization. Extension of the proposed mechanisms to situations when the valuation functions are not known to the central planner are also discussed. Note to Practitioners-Our results will be useful in all resource allocation problems that involve gathering of information privately held by strategic users, where the utilities are any concave function of the allocations, and where the resource planner is not interested in maximizing revenue, but in efficient sharing of the resource. Such situations arise quite often in fair sharing of internet resources, fair sharing of funds across departments within the same parent organization, auctioning of public goods, etc. We study methods to achieve near budget balance by first collecting payments according to the celebrated VCG mechanism, and then returning as much of the collected money as rebates. Our focus on linear rebate functions allows for easy implementation. The resulting convex optimization problem is solved via relaxation to a randomized linear programming problem, for which several efficient solvers exist. This relaxation is enabled by constraint sampling. Keeping practitioners in mind, we identify the number of samples that assures a desired level of ``near-feasibility'' with the desired confidence level. Our methodology will occasionally require subsidy from outside the system. We however demonstrate via simulation that, if the mechanism is repeated several times over independent instances, then past surplus can support the subsidy requirements. We also extend our results to situations where the strategic users' utility functions are not known to the allocating entity, a common situation in the context of internet users and other problems.

A strategy-proof and budget-balanced mechanism for carbon footprint reduction by global companies

The problem addressed in this paper is concerned with an important issue faced by any green aware global company to keep its emissions within a prescribed cap. The specific problem is to allocate carbon reductions to its different divisions and supply chain partners in achieving a required target of reductions in its carbon reduction program. The problem becomes a challenging one since the divisions and supply chain partners, being autonomous, may exhibit strategic behavior. We use a standard mechanism design approach to solve this problem. While designing a mechanism for the emission reduction allocation problem, the key properties that need to be satisfied are dominant strategy incentive compatibility (DSIC) (also called strategy-proofness), strict budget balance (SBB), and allocative efficiency (AE). Mechanism design theory has shown that it is not possible to achieve the above three properties simultaneously. In the literature, a mechanism that satisfies DSIC and AE has recently been proposed in this context, keeping the budget imbalance minimal. Motivated by the observation that SBB is an important requirement, in this paper, we propose a mechanism that satisfies DSIC and SBB with slight compromise in allocative efficiency. Our experimentation with a stylized case study shows that the proposed mechanism performs satisfactorily and provides an attractive alternative mechanism for carbon footprint reduction by global companies.

Cost Sharing Mechanisms for Business Clusters with Strategic Firms

A business cluster is a co-located group of micro, small, medium scale enterprises. Such firms can benefit significantly from their co-location through shared infrastructure and shared services. Cost sharing becomes an important issue in such sharing arrangements especially when the firms exhibit strategic behavior. There are many cost sharing methods and mechanisms proposed in the literature based on game theoretic foundations. These mechanisms satisfy a variety of efficiency and fairness properties such as allocative efficiency, budget balance, individual rationality, consumer sovereignty, strategyproofness, and group strategyproofness. In this paper, we motivate the problem of cost sharing in a business cluster with strategic firms and illustrate different cost sharing mechanisms through the example of a cluster of firms sharing a logistics service. Next we look into the problem of a business cluster sharing ICT (information and communication technologies) infrastructure and explore the use of cost sharing mechanisms.

Truthful and Quality Conscious Query Incentive Networks

Query incentive networks capture the role of incentives in extracting information from decentralized information networks such as a social network. Several game theoretic tilt:Kids of query incentive networks have been proposed in the literature to study and characterize the dependence, of the monetary reward required to extract the answer for a query, on various factors such as the structure of the network, the level of difficulty of the query, and the required success probability.None of the existing models, however, captures the practical andimportant factor of quality of answers. In this paper, we develop a complete mechanism design based framework to incorporate the quality of answers, in the monetization of query incentive networks. First, we extend the model of Kleinberg and Raghavan [2] to allow the nodes to modulate the incentive on the basis of the quality of the answer they receive. For this qualify conscious model. we show are existence of a unique Nash equilibrium and study the impact of quality of answers on the growth rate of the initial reward, with respect to the branching factor of the network. Next, we present two mechanisms; the direct comparison mechanism and the peer prediction mechanism, for truthful elicitation of quality from the agents. These mechanisms are based on scoring rules and cover different; scenarios which may arise in query incentive networks. We show that the proposed quality elicitation mechanisms are incentive compatible and ex-ante budget balanced. We also derive conditions under which ex-post budget balance can beachieved by these mechanisms.

Redistribution Mechanisms for Assignment of Heterogeneous Objects

There are p heterogeneous objects to be assigned to n competing agents (n > p) each with unit demand. It is required to design a Groves mechanism for this assignment problem satisfying weak budget balance, individual rationality, and minimizing the budget imbalance. This calls for designing an appropriate rebate function. When the objects are identical, this problem has been solved which we refer as WCO mechanism. We measure the performance of such mechanisms by the redistribution index. We first prove an impossibility theorem which rules out linear rebate functions with non-zero redistribution index in heterogeneous object assignment. Motivated by this theorem,we explore two approaches to get around this impossibility. In the first approach, we show that linear rebate functions with non-zero redistribution index are possible when the valuations for the objects have a certain type of relationship and we design a mechanism with linear rebate function that is worst case optimal. In the second approach, we show that rebate functions with non-zero efficiency are possible if linearity is relaxed. We extend the rebate functions of the WCO mechanism to heterogeneous objects assignment and conjecture them to be worst case optimal.

A new approach to the design of electronic exchanges

Electronic Exchanges are double-sided marketplaces that allows multiple buyers to trade with multiple sellers, with aggregation of demand and supply across the bids to maximize the revenue in the market. In this paper, we propose a new design approach for an one-shot exchange that collects bids from buyers and sellers and clears the market at the end of the bidding period. The main principle of the approach is to decouple the allocation from pricing. It is well known that it is impossible for an exchange with voluntary participation to be efficient and budget-balanced. Budget-balance is a mandatory requirement for an exchange to operate in profit. Our approach is to allocate the trade to maximize the reported values of the agents. The pricing is posed as payoff determination problem that distributes the total payoff fairly to all agents with budget-balance imposed as a constraint. We devise an arbitration scheme by axiomatic approach to solve the payoff determination problem using the added-value concept of game theory.

Characterizing distribution rules for cost sharing games

In noncooperative cost sharing games, individually strategic agents choose resources based on how the welfare (cost or revenue) generated at each resource (which depends on the set of agents that choose the resource) is distributed. The focus is on finding distribution rules that lead to stable allocations, which is formalized by the concept of Nash equilibrium, e.g., Shapley value (budget-balanced) and marginal contribution (not budget-balanced) rules.

Recent work that seeks to characterize the space of all such rules shows that the only budget-balanced distribution rules that guarantee equilibrium existence in all welfare sharing games are generalized weighted Shapley values (GWSVs), by exhibiting a specific 'worst-case' welfare function which requires that GWSV rules be used. Our work provides an exact characterization of the space of distribution rules (not necessarily budget-balanced) for any specific local welfare functions remains, for a general class of scalable and separable games with well-known applications, e.g., facility location, routing, network formation, and coverage games.

We show that all games conditioned on any fixed local welfare functions possess an equilibrium if and only if the distribution rules are equivalent to GWSV rules on some 'ground' welfare functions. Therefore, it is neither the existence of some worst-case welfare function, nor the restriction of budget-balance, which limits the design to GWSVs. Also, in order to guarantee equilibrium existence, it is necessary to work within the class of potential games, since GWSVs result in (weighted) potential games.

We also provide an alternative characterization—all games conditioned on any fixed local welfare functions possess an equilibrium if and only if the distribution rules are equivalent to generalized weighted marginal contribution (GWMC) rules on some 'ground' welfare functions. This result is due to a deeper fundamental connection between Shapley values and marginal contributions that our proofs expose—they are equivalent given a transformation connecting their ground welfare functions. (This connection leads to novel closed-form expressions for the GWSV potential function.) Since GWMCs are more tractable than GWSVs, a designer can tradeoff budget-balance with computational tractability in deciding which rule to implement.

O controle social na construção e democratização da política de Assistência Social: o papel dos conselhos e a realidade de um município da Baixada Fluminense

A presente dissertação tem como propósito, a partir do processo de construção e democratização da Política de Assistência Social no Brasil, pós SUAS, analisar o controle social tendo como objeto o Conselho Municipal de Assistência Social do município de Mesquita, na região da Baixada Fluminense / RJ e as condições de trabalho dos Assistentes Sociais nesses espaços. Inicialmente, abordamos a Política de Assistência Social no Brasil, desde a criação da extinta Legião Brasileira de Assistência Social (LBA), até os dias atuais, ressaltando os avanços na parte jurídico-legal-normativa desta política, o que tem se tornado um campo propício e amplo para o mercado de trabalho dos assistentes sociais na contemporaneidade. No debate do controle social na Política de Assistência, destacamos três importantes temáticas: a relação das entidades da sociedade civil com os conselheiros governamentais, nos espaços de representação política, democrática, deliberativa e paritária nos conselhos de assistência social; a participação dos segmentos de usuários dos serviços sócio assistenciais do município de Mesquita e, ainda, as condições em que vem ocorrendo à participação dos assistentes sociais nos espaços de controle social no município, através de relações de trabalho precárias, no que se refere à desregulamentação de direitos sociais trabalhistas dos profissionais. Para o estudo, analisamos as Atas do período de 2011-2012, e realizamos entrevistas semi-estruturadas com os conselheiros governamentais e não governamentais do Conselho Municipal de Assistência Social de Mesquita (CMAS), que atuaram no mesmo período, gestão empossada em Dezembro de 2011, após resultado do processo eleitoral das entidades da sociedade civil do CMAS. Dentre os achados da investigação, a partir do material empírico, mediado pelo pensamento de autores que discutem esta temática e pela legislação destacam-se: a superioridade da Representação Governamental sobre a Representação da Sociedade Civil no CMAS; não monitoramento e fiscalização do saldo orçamentário pelo CMAS / Mesquita; precarização das relações de trabalho na SEMAS / Mesquita; descontinuidade do Programa de Capacitação dos Conselheiros do CMAS / Mesquita; despreparo técnico dos conselheiros para apreciação de prestação de contas no CMAS, com ausência de tempo hábil para análise; manipulação política por parte da representação governamental no CMAS; o poder de influência do governo é maior do que da sociedade civil; necessidade de capacitação técnica, e principalmente capacitação ética e política dos conselheiros governamentais e da sociedade civil; precariedade dos equipamentos públicos dos SEMAS / Mesquita; parca participação dos Usuários dos Serviços Socioassistenciais na esfera do conselho, dentre outros aspectos que serão tratados nesta dissertação. Em suma, estes são as principais conclusões de forma resumida e sintética que abordaremos mais detalhadamente nas considerações finais deste trabalho.

(Minimally) 'epsilon'-incentive compatible competitive equilibria in economies with indivisibilities

We consider competitive and budget-balanced allocation rules for problems where a number of indivisible objects and a fixed amount of money is allocated among a group of agents. In 'small' economies, we identify under classical preferences each agent's maximal gain from manipulation. Using this result we find the competitive and budget-balanced allocation rules which are minimally manipulable for each preference profile in terms of any agent's maximal gain. If preferences are quasi-linear, then we can find a competitive and budget-balanced allocation rule such that for any problem, the maximal utility gain from manipulation is equalized among all agents.

Self-defeating austerity? Assessing the impact of fiscal consolidations on unemployment

The great recession of 2008/2009 has had a huge impact on unemployment and public finances in most advanced countries, and these impacts were magnified in the southern Euro area countries by the sovereign debt crisis of 2010/2011. The fiscal consolidation imposed by the European Union on highly indebted countries was based on the assumptions of the so-called expansionary austerity. However, the reality so far shows proof to the contrary, and the results of this paper support the opposing view of a self- defeating austerity. Based on the input-output relations of the productive system, an unemployment rate/budget balance trade-off equation is derived, as well as the impact of a strong fiscal consolidation based on social transfers and the notion of neutral budget balance. An application to the Portuguese case confirms the huge costs of a strong fiscal consolidation, both in terms of unemployment and social policy regress, and it allows one to conclude that too much consolidation in one year makes consolidation more difficult in the following year.

Balancing the (carbon) budget: Using linear inverse models to estimate carbon flows and mass-balance 13C:15N labelling experiments in low oxygen sediments.

Over 1 million km² of seafloor experience permanent low-oxygen conditions within oxygen minimum zones (OMZs). OMZs are predicted to grow as a consequence of climate change, potentially affecting oceanic biogeochemical cycles. The Arabian Sea OMZ impinges upon the western Indian continental margin at bathyal depths (150 - 1500 m) producing a strong depth dependent oxygen gradient at the sea floor. The influence of the OMZ upon the short term processing of organic matter by sediment ecosystems was investigated using in situ stable isotope pulse chase experiments. These deployed doses of ¹³C:¹⁵N labeled organic matter onto the sediment surface at four stations from across the OMZ (water depth 540 - 1100 m; [O₂] = 0.35 - 15 μM). In order to prevent experimentally anoxia, the mesocosms were not sealed. ¹³C and ¹⁵N labels were traced into sediment, bacteria, fauna and ¹³C into sediment porewater DIC and DOC. However, the DIC and DOC flux to the water column could not be measured, limiting our capacity to obtain mass-balance for C in each experimental mesocosm. Linear Inverse Modeling (LIM) provides a method to obtain a mass-balanced model of carbon flow that integrates stable-isotope tracer data with community biomass and biogeochemical flux data from a range of sources. Here we present an adaptation of the LIM methodology used to investigate how ecosystem structure influenced carbon flow across the Indian margin OMZ. We demonstrate how oxygen conditions affect food-web complexity, affecting the linkages between the bacteria, foraminifera and metazoan fauna, and their contributions to benthic respiration. The food-web models demonstrate how changes in ecosystem complexity are associated with oxygen availability across the OMZ and allow us to obtain a complete carbon budget for the stationa where stable-isotope labelling experiments were conducted.