Tag Archives: planning

Items of some interest:

Posted on by

These are my recent Pin​board​.in links:

  • [1206.6866] Sto­chas­tic Opti­mal Con­trol in Con­tin­u­ous Space-​​Time Multi-​​Agent Systems

    “Recently, a the­ory for sto­chas­tic opti­mal con­trol in non-​​linear dynam­i­cal sys­tems in con­tin­u­ous space-​​time has been devel­oped (Kap­pen, 2005). We apply this the­ory to col­lab­o­ra­tive multi-​​agent sys­tems. The agents evolve accord­ing to a given non-​​linear dynam­ics with addi­tive Wiener noise. Each agent can con­trol its own dynam­ics. The goal is to min­i­mize the accu­mu­lated joint cost, which con­sists of a state depen­dent term and a term that is qua­dratic in the con­trol. We focus on sys­tems of non-​​interacting agents that have to dis­trib­ute them­selves opti­mally over a num­ber of tar­gets, given a set of end-​​costs for the dif­fer­ent pos­si­ble agent-​​target com­bi­na­tions. We show that opti­mal con­trol is the com­bi­na­to­r­ial sum of inde­pen­dent single-​​agent single-​​target opti­mal con­trols weighted by a fac­tor pro­por­tional to the end-​​costs of the dif­fer­ent com­bi­na­tions. Thus, multi-​​agent con­trol is related to a stan­dard graph­i­cal model infer­ence prob­lem. The addi­tional com­pu­ta­tional cost com­pared to single-​​agent con­trol is expo­nen­tial in the tree-​​width of the graph spec­i­fy­ing the com­bi­na­to­r­ial sum times the num­ber of tar­gets. We illus­trate the result by sim­u­la­tions of sys­tems with up to 42 agents.”

    coor­di­na­tion agent-​​based emergent-​​design nudge-​​targets control-​​theory

  • [1205.6917] Robust self-​​triggered coor­di­na­tion with ternary controllers

    “This paper regards coor­di­na­tion of net­worked sys­tems, which is stud­ied in the frame­work of hybrid dynam­i­cal sys­tems. We design a coor­di­na­tion scheme which com­bines the use of ternary con­trollers with a self-​​triggered com­mu­ni­ca­tion pol­icy. The com­mu­ni­ca­tion pol­icy requires the agents to col­lect, at each sam­pling time, rel­a­tive mea­sure­ments of their neigh­bors’ states: the col­lected infor­ma­tion is then used to update the con­trol and deter­mine the fol­low­ing sam­pling time. We prove that the pro­posed scheme ensures finite-​​time con­ver­gence to a neigh­bor­hood of a con­sen­sus state. We then study the robust­ness of the pro­posed self-​​triggered coor­di­na­tion sys­tem with respect to skews in the agents’ local clocks, to delays, and to lim­ited pre­ci­sion in com­mu­ni­ca­tion. Fur­ther­more, we present two sig­nif­i­cant vari­a­tions of our scheme. First, we design a time-​​varying con­troller which asymp­tot­i­cally dri­ves the sys­tem to con­sen­sus. Sec­ond, we adapt our frame­work to a com­mu­ni­ca­tion model in which an agent does not poll all its neigh­bors simul­ta­ne­ously, but sin­gle neigh­bors instead. This com­mu­ni­ca­tion pol­icy actu­ally leads to a self-​​triggered “gos­sip” coor­di­na­tion system.”

    network-​​theory multi-​​agent-​​systems mechanism-​​design emergent-​​design consensus-​​systems nudge-​​targets algo­rithms

  • [1205.2607] Simulation-​​Based Game The­o­retic Analy­sis of Key­word Auc­tions with Low-​​Dimensional Bid­ding Strategies

    “We per­form a simulation-​​based analy­sis of key­word auc­tions mod­eled as one-​​shot games of incom­plete infor­ma­tion to study a series of mech­a­nism design ques­tions. Our first ques­tion addresses the degree to which incen­tive com­pat­i­bil­ity fails in gen­er­al­ized second-​​price (GSP) auc­tions. Our results sug­gest that sin­cere bid­ding in GSP auc­tions is a strik­ingly poor strat­egy and a poor pre­dic­tor of equi­lib­rium out­comes. We next show that the rank-​​by-​​revenue mech­a­nism is wel­fare opti­mal, cor­rob­o­rat­ing past results. Finally, we ana­lyze profit as a func­tion of auc­tion mech­a­nism under a series of alter­na­tive set­tings. Our con­clu­sions coin­cide with those of Lahaie and Pen­nock [2007] when val­ues and qual­ity scores are strongly pos­i­tively cor­re­lated: in such a case, rank-​​by-​​bid rules are clearly supe­rior. We diverge, how­ever, in show­ing that auc­tions that put lit­tle weight on qual­ity scores almost uni­ver­sally dom­i­nate the pure rank-​​by-​​revenue scheme.”

    game-​​theory agent-​​based sim­u­la­tion eco­nom­ics auc­tion nudge-​​targets

  • Graph­ing the his­tory of phi­los­o­phy « Drunks&Lampposts

    “Each philoso­pher is a node in the net­work and the lines between them (or edges in the ter­mi­nol­ogy of graph the­ory) rep­re­sents lines of influ­ence. The node and text are sized accord­ing to the num­ber of con­nec­tions (both in and out). The algo­rithm that visu­alises the graph also tends to put the bet­ter con­nected nodes in the cen­tre of the dia­gram so we see the most influ­en­tial philoso­phers, in large text, clus­tered in the cen­tre. It all seems about right with the major fig­ures in the west­ern philo­soph­i­cal tra­di­tion tak­ing the cen­tre stage. (I need to also add the direc­tion of influ­ence with a arrow head – some­thing I’ve not got round to yet.) A short­com­ing how­ever is that this eval­u­a­tion only takes into account direct lines of influ­ence. Indi­rect influ­ence via another per­son in the net­work does not enter into it. This prob­a­bly explains why Descartes is smaller than you’d think. It would also be bet­ter if the nodes were sized only by the num­ber of out­ward con­nec­tions although I think over­all the dif­fer­ences would be slight. I’ll get round to that.”

    visu­al­iza­tion philosopher-​​mining

  • [1206.3666] Unsu­per­vised adap­ta­tion of brain machine inter­face decoders

    “The per­for­mance of neural decoders can degrade over time due to non­sta­tion­ar­i­ties in the rela­tion­ship between neu­ronal activ­ity and behav­ior. In this case, brain-​​machine inter­faces (BMI) require adap­ta­tion of their decoders to main­tain high per­for­mance across time. One way to achieve this is by use of peri­od­i­cal cal­i­bra­tion phases, dur­ing which the BMI sys­tem (or an exter­nal human demon­stra­tor) instructs the user to per­form cer­tain move­ments or behav­iors. This approach has two dis­ad­van­tages: (i) cal­i­bra­tion phases inter­rupt the autonomous oper­a­tion of the BMI and (ii) between two cal­i­bra­tion phases the BMI per­for­mance might not be sta­ble but con­tin­u­ously decrease. A bet­ter alter­na­tive would be that the BMI decoder is able to con­tin­u­ously adapt in an unsu­per­vised man­ner dur­ing autonomous BMI oper­a­tion, i.e. with­out know­ing the move­ment inten­tions of the user. In the present arti­cle, we present an effi­cient method for such unsu­per­vised train­ing of BMI sys­tems for con­tin­u­ous move­ment con­trol. The pro­posed method uti­lizes a cost func­tion derived from neu­ronal record­ings, which guides a learn­ing algo­rithm to eval­u­ate the decod­ing para­me­ters. We ver­ify the per­for­mance of our adap­tive method by sim­u­lat­ing a BMI user with an opti­mal feed­back con­trol model and its inter­ac­tion with our adap­tive BMI decoder. The sim­u­la­tion results show that the cost func­tion and the algo­rithm yield fast and pre­cise tra­jec­to­ries towards tar­gets at ran­dom ori­en­ta­tions on a 2-​​dimensional com­puter screen. For ini­tially unknown and non-​​stationary tun­ing para­me­ters, our unsu­per­vised method is still able to gen­er­ate pre­cise tra­jec­to­ries and to keep its per­for­mance sta­ble in the long term. The algo­rithm can option­ally work also with neu­ronal error sig­nals instead or in con­junc­tion with the pro­posed unsu­per­vised adaptation.”

    FOR-​​SCIENCE brain-​​machine-​​interface user-​​interface adaptive-​​control emergent-​​design

  • [1206.3980] Visu­al­iz­ing Stream­ing Text Data with Dynamic Maps

    “The many end­less rivers of text now avail­able present a seri­ous chal­lenge in the task of glean­ing, ana­lyz­ing and dis­cov­er­ing use­ful infor­ma­tion. In this paper, we describe a method­ol­ogy for visu­al­iz­ing text streams in real time. The approach auto­mat­i­cally groups sim­i­lar mes­sages into “coun­tries,” with key­word sum­maries, using seman­tic analy­sis, graph clus­ter­ing and map gen­er­a­tion tech­niques. It han­dles the need for visual sta­bil­ity across time by dynamic graph lay­out and Pro­crustes pro­jec­tion tech­niques, enhanced with a novel sta­ble com­po­nent pack­ing algo­rithm. The result pro­vides a con­tin­u­ous, suc­cinct view of evolv­ing top­ics of inter­est. It can be used in pas­sive mode for overviews and sit­u­a­tional aware­ness, or as an inter­ac­tive data explo­ration tool. To make these ideas con­crete, we describe their appli­ca­tion to an online ser­vice called TwitterScope.”

    visu­al­iza­tion data algo­rithms user-​​experience

  • [1205.3352] Revis­it­ing the effect of exter­nal fields in Axelrod’s model of social dynamics

    “The study of the effects of spa­tially uni­form fields on the steady-​​state prop­er­ties of Axelrod’s model has yielded plenty of con­tro­ver­sial results. Here we re-​​examine the impact of this type of field for a selec­tion of para­me­ters such that the field-​​free steady state of the model is het­ero­ge­neous or mul­ti­cul­tural. Analy­ses of both one and two-​​dimensional ver­sions of Axelrod’s model indi­cate that, con­trary to pre­vi­ous claims in the lit­er­a­ture, the steady state remains het­ero­ge­neous regard­less of the value of the field strength. Turn­ing on the field leads to a dis­con­tin­u­ous decrease on the num­ber of cul­tural domains, which we argue is due to the insta­bil­ity of zero-​​field het­ero­ge­neous absorb­ing con­fig­u­ra­tions. We find, how­ever, that spa­tially nonuni­form fields that imple­ment a con­sen­sus rule among the neigh­bor­hood of the agents enforces homog­e­niza­tion. Although the over­all effects of the fields are essen­tially the same irre­spec­tive of the dimen­sion­al­ity of the model, we argue that the dimen­sion­al­ity has a sig­nif­i­cant impact on the sta­bil­ity of the field-​​free homo­ge­neous steady state.”

    com­plex­ol­ogy agent-​​based exter­nal­i­ties sim­u­la­tion evolutionary-​​economics nudge-​​targets

  • [1206.3421] Lin­ear Latent Vari­able Mod­els: The lava-​​package

    “An R pack­age for spec­i­fy­ing and esti­mat­ing lin­ear latent vari­able mod­els is pre­sented. The phi­los­o­phy of the imple­men­ta­tion is to sep­a­rate the model spec­i­fi­ca­tion from the actual data, which leads to a dynamic and easy way of mod­el­ing com­plex hier­ar­chi­cal struc­tures. Sev­eral advanced fea­tures are imple­mented includ­ing robust stan­dard errors for clus­tered cor­re­lated data, multi­group analy­ses, non-​​linear para­me­ter con­straints, infer­ence with incom­plete data, max­i­mum like­li­hood esti­ma­tion with cen­sored and binary obser­va­tions, and instru­men­tal vari­able esti­ma­tors. In addi­tion an exten­sive sim­u­la­tion inter­face cov­er­ing a broad range of non-​​linear gen­er­al­ized struc­tural equa­tion mod­els is described. The model and soft­ware are demon­strated in data of mea­sure­ments of the sero­tonin trans­porter in the human brain.”

    ontol­ogy sta­tis­tics algo­rithms R-​​language linear-​​models model-​​view-​​controller design-​​patterns

  • [1205.6129] The Miss­ing Mem­ris­tor: Novel Nan­otech­nol­ogy or rather new Case Study for the Phi­los­o­phy and Soci­ol­ogy of Science?

    “In 2008, it was widely announced that the miss­ing mem­ris­tor, a basic two-​​terminal elec­tri­cal cir­cuit ele­ment, had finally been dis­cov­ered. The mem­ris­tor is the fourth and last such cir­cuit ele­ment and thus com­pletes cir­cuit the­ory. Pre­dicted already in 1971, the even­tual dis­cov­ery of some­thing seem­ingly so basic needed almost 40 years. How­ever, this dis­cov­ery is doubted. The pre­dicted mem­ris­tor has no mate­r­ial mem­ory and is based on mag­netic flux, but the dis­cov­ered devices con­sti­tute ana­logue mem­ory stor­age that do not involve mag­net­ism. The per­son who orig­i­nally pro­posed the mem­ris­tor did not reject the dis­cov­ery but instead changed his mind about what a mem­ris­tor is. We briefly intro­duce the his­tory and then care­fully mem­ris­tance and the mem­ris­tor as such. We dis­cuss its sta­tus as a model rather than a device. We dis­cuss the dis­cov­ered devices, their sta­bil­ity, and how sta­bil­ity relates to the con­sis­tency of the the­o­ret­i­cal enti­ties. A thought exper­i­ment assumes a world with­out mag­net­ism. Induc­tors can­not exist there, but mem­ory resis­tors could still be con­structed. On the same grounds as the mem­ris­tor was his­tor­i­cally pre­dicted, an “induc­tor” could then be pre­dicted. Likely, some­body would also ‘dis­cover’ one. A ten­ta­tive soci­o­log­i­cal analy­sis com­pares to the flawed detec­tion of grav­i­ta­tional waves but comes to very dif­fer­ent conclusions.”

    symmetry-​​is-​​the-​​way-​​things-​​ought-​​to-​​be history-​​of-​​science technical-​​assumptions engineering-​​philosophy

  • [1205.2776] Trans­port on cou­pled spa­tial networks

    “Trans­port processes on spa­tial net­works are rep­re­sen­ta­tive of a broad class of real world sys­tems which, rather than being inde­pen­dent, are typ­i­cally inter­de­pen­dent. We pro­pose a mea­sure of util­ity to cap­ture key fea­tures that arise when such sys­tems are cou­pled together. The cou­pling is defined in a way that is not solely topo­log­i­cal, rely­ing on both the dis­tri­b­u­tion of sources and sinks, and the method of route assign­ment. Using a toy model, we explore rel­e­vant cases by sim­u­la­tion. For cer­tain para­me­ter val­ues, a pic­ture emerges of two regimes. The first occurs when the flows go from many sources to a small num­ber of sinks. In this case, net­work util­ity is largest when the cou­pling is at its max­i­mum and the aver­age short­est path is min­i­mized. The sec­ond regime arises when many sources cor­re­spond to many sinks. Here, the opti­mal cou­pling no longer cor­re­sponds to the min­i­mum aver­age short­est path, as the con­ges­tion of traf­fic must also be taken into account. More gen­er­ally, results indi­cate that cou­pled spa­tial sys­tems can give rise to behav­ior that relies sub­tly on the inter­play between the cou­pling and ran­dom­ness in the source-​​sink distribution.”

    nudge-​​targets network-​​theory emergent-​​design epi­demi­ol­ogy sim­u­la­tion

  • [1206.5849] Under­stand­ing the com­plex­ity of the L’evy-walk nature of human mobil­ity with a multi-​​scale cost/​benefit model

    “Prob­a­bil­ity dis­tri­b­u­tions of human dis­place­ments has been fit with expo­nen­tially trun­cated L’evy flights or fat tailed Pareto inverse power law prob­a­bil­ity dis­tri­b­u­tions. Thus, peo­ple usu­ally stay within a given loca­tion (for exam­ple, the city of res­i­dence), but with a non-​​vanishing fre­quency they visit nearby or far loca­tions too. Herein, we show that an impor­tant empir­i­cal dis­tri­b­u­tion of human dis­place­ments (range: from 1 to 1000 km) can be well fit by three con­sec­u­tive Pareto dis­tri­b­u­tions with sim­ple inte­ger expo­nents equal to 1, 2 and ($gtrap­prox$) 3. These three expo­nents cor­re­spond to three dis­place­ment range zones of about 1 km $less­sim Delta r less­sim$ 10 km, 10 km $less­sim Delta r less­sim$ 300 km and 300 km $less­sim Delta r less­sim $ 1000 km, respec­tively. These three zones can be geo­graph­i­cally and phys­i­cally well deter­mined as dis­place­ments within a city, vis­its to nearby cities that may occur within just one-​​day trips, and visit to far loca­tions that may require multi-​​days trips. The incre­men­tal inte­ger val­ues of the three expo­nents can be eas­ily explained with a three-​​scale mobil­ity cost/​benefit model for human dis­place­ments based on sim­ple geo­met­ri­cal con­strains. Essen­tially, peo­ple would divide the space into three major regions (close, medium and far dis­tances) and would assume that the travel ben­e­fits are randomly/​uniformly dis­trib­uted mostly only within spe­cific urban-​​like areas.”

    Levy-​​flights city-​​planning multiscale-​​phenomena self-​​similarity

  • [1206.7011] Ultra­thin Ter­a­hertz Pla­nar Lenses

    “Con­ven­tional opti­cal com­po­nents shape the wave­front of prop­a­gat­ing light by adjust­ing the opti­cal path length, which requires the use of rather thick lenses, espe­cially for the adjust­ment of ter­a­hertz (THz) radi­a­tion due to its long wave­length. Two ultra­thin THz pla­nar lenses were designed and fab­ri­cated based on inter­face phase mod­u­la­tion of antenna res­o­nance. The lens thick­nesses were extremely reduced to 100 nm, which is only 1⁄4000th of the illu­mi­nat­ing light wave­length. The focus­ing and imag­ing func­tions of the lenses were exper­i­men­tally demon­strated. The ultra­thin opti­cal com­po­nents described herein are a sig­nif­i­cant step toward the devel­op­ment of a micro-​​integrated THz system.”

    optics engineering-​​design nudge-​​targets

  • [1206.3789] Tree decom­po­si­tion and para­me­ter­ized algo­rithms for RNA structure-​​sequence align­ment includ­ing ter­tiary inter­ac­tions and pseudoknots

    “We present a gen­eral set­ting for structure-​​sequence com­par­i­son in a large class of RNA struc­tures that uni­fies and gen­er­al­izes a num­ber of recent works on spe­cific fam­i­lies on struc­tures. Our approach is based on tree decom­po­si­tion of struc­tures and gives rises to a gen­eral para­me­ter­ized algo­rithm, where the expo­nen­tial part of the com­plex­ity depends on the fam­ily of struc­tures. For each of the pre­vi­ously stud­ied fam­i­lies, our algo­rithm has the same com­plex­ity as the spe­cific algo­rithm that had been given before.”

    RNA structural-​​biology fold­ing bioin­for­mat­ics algo­rithms nudge-​​targets mod­el­ing

  • [1206.3403] Topo­log­i­cal Mea­sure Locat­ing the Effec­tive Crossover between Seg­re­ga­tion and Inte­gra­tion in a Mod­u­lar Network

    “Com­pu­ta­tional analy­sis of time-​​course data with an under­ly­ing causal struc­ture is needed in a vari­ety of domains, includ­ing neural spike trains, stock price move­ments, and gene expres­sion lev­els. How­ever, it can be chal­leng­ing to deter­mine from just the numer­i­cal time course data alone what is coor­di­nat­ing the vis­i­ble processes, to sep­a­rate the under­ly­ing prima facie causes into gen­uine and spu­ri­ous causes and to do so with a fea­si­ble com­pu­ta­tional com­plex­ity. For this pur­pose, we have been devel­op­ing a novel algo­rithm based on a frame­work that com­bines notions of causal­ity in phi­los­o­phy with algo­rith­mic approaches built on model check­ing and sta­tis­ti­cal tech­niques for mul­ti­ple hypothe­ses test­ing. The causal rela­tion­ships are described in terms of tem­po­ral logic for­mu­lae, refram­ing the infer­ence prob­lem in terms of model check­ing. The logic used, PCTL, allows descrip­tion of both the time between cause and effect and the prob­a­bil­ity of this rela­tion­ship being observed. We show that equipped with these causal for­mu­lae with their asso­ci­ated prob­a­bil­i­ties we may com­pute the aver­age impact a cause makes to its effect and then dis­cover sta­tis­ti­cally sig­nif­i­cant causes through the con­cepts of mul­ti­ple hypoth­e­sis test­ing (treat­ing each causal rela­tion­ship as a hypoth­e­sis), and false dis­cov­ery con­trol. By explor­ing a well-​​chosen fam­ily of poten­tially all sig­nif­i­cant hypothe­ses with rea­son­ably min­i­mal descrip­tion length, it is pos­si­ble to tame the algorithm’s com­pu­ta­tional com­plex­ity while explor­ing the nearly com­plete search-​​space of all prima facie causes. We have tested these ideas in a num­ber of domains and illus­trate them here with two examples.”

    time-​​series sta­tis­tics frame­work dynamical-​​systems to-​​read

  • [1206.5959] The Online Replace­ment Path Problem

    “We study a nat­ural online vari­ant of the replace­ment path prob­lem. The textit{replacement path prob­lem} asks to find for a given graph $G = (V,E)$, two des­ig­nated ver­tices $s,tin V$ and a short­est $s$-$t$ path $P$ in $G$, a textit{replacement path} $P_​e$ for every edge $e$ on the path $P$. The replace­ment path $P_​e$ is sim­ply a short­est $s$-$t$ path in the graph, which avoids the textit{failed} edge $e$. We adapt this prob­lem to deal with the nat­ural sce­nario, that the edge which failed is not known at the time of solu­tion imple­men­ta­tion. Instead, our prob­lem assumes that the iden­tity of the failed edge only becomes avail­able when the rout­ing mech­a­nism tries to cross the edge. This sit­u­a­tion is moti­vated by appli­ca­tions in dis­trib­uted net­works, where infor­ma­tion about recent changes in the net­work is only stored locally, and fault-​​tolerant opti­miza­tion, where an adver­sary tries to delay the dis­cov­ery of the mate­ri­al­ized sce­nario as much as pos­si­ble. Con­se­quently, we define the textit{online replace­ment path prob­lem}, which asks to find a nom­i­nal $s$-$t$ path $Q$ and detours $Q_​e$ for every edge on the path $Q$, such that the worst-​​case arrival time at the des­ti­na­tion is min­i­mized. Our main con­tri­bu­tion is a label set­ting algo­rithm, which solves the prob­lem in undi­rected graphs in time $O(m log n)$ and lin­ear space for all sources and a sin­gle des­ti­na­tion. We also present algo­rithms for exten­sions of the model to any bounded num­ber of failed edges.”

    operations-​​research plan­ning algo­rithms online-​​algorithms nudge-​​targets

  • [1206.6195] Par­rondo games with spa­tial depen­dence, II

    “…Again this sug­gests that the Par­rondo region (mu_​B is non­pos­i­tive and mu_[r,s] is pos­i­tive) has nonzero vol­ume in the limit. …”

    Parrondo-​​games game-​​theory counterintuitive-​​results sim­u­la­tion coop­er­a­tion

  • [1206.4648] Two-​​Manifold Prob­lems with Appli­ca­tions to Non­lin­ear Sys­tem Identification

    “Recently, there has been much inter­est in spec­tral approaches to learn­ing manifolds—so-called ker­nel eigen­map meth­ods. These meth­ods have had some suc­cesses, but their applic­a­bil­ity is lim­ited because they are not robust to noise. To address this lim­i­ta­tion, we look at two-​​manifold prob­lems, in which we simul­ta­ne­ously recon­struct two related man­i­folds, each rep­re­sent­ing a dif­fer­ent view of the same data. By solv­ing these inter­con­nected learn­ing prob­lems together, two-​​manifold algo­rithms are able to suc­ceed where a non-​​integrated approach would fail: each view allows us to sup­press noise in the other, reduc­ing bias. We pro­pose a class of algo­rithms for two-​​manifold prob­lems, based on spec­tral decom­po­si­tion of cross-​​covariance oper­a­tors in Hilbert space, and dis­cuss when two-​​manifold prob­lems are use­ful. Finally, we demon­strate that solv­ing a two-​​manifold prob­lem can aid in learn­ing a non­lin­ear dynam­i­cal sys­tem from lim­ited data.”

    sta­tis­tics inverse-​​problems system-​​identification algo­rithms nudge-​​targets bench­mark­ing

  • [1203.3367] Sto­chas­tic dif­fer­en­tial equa­tions for evo­lu­tion­ary dynam­ics with demo­graphic noise and mutations

    “We present a gen­eral frame­work to describe the evo­lu­tion­ary dynam­ics of an arbi­trary num­ber of types in finite pop­u­la­tions based on sto­chas­tic dif­fer­en­tial equa­tions (SDE). For large, but finite pop­u­la­tions this allows to include demo­graphic noise with­out requir­ing explicit sim­u­la­tions. Instead, the pop­u­la­tion size only rescales the ampli­tude of the noise. More­over, this frame­work admits the inclu­sion of muta­tions between dif­fer­ent types, pro­vided that muta­tion rates, $mu$, are not too small com­pared to the inverse pop­u­la­tion size 1/​N. This ensures that all types are almost always rep­re­sented in the pop­u­la­tion and that the occa­sional extinc­tion of one type does not result in an extended absence of that type. For $mu Nll1$ this lim­its the use of SDE’s, but in this case there are well estab­lished alter­na­tive approx­i­ma­tions based on time scale sep­a­ra­tion. We illus­trate our approach by a Rock-​​Scissors-​​Paper game with muta­tions, where we demon­strate excel­lent agree­ment with sim­u­la­tion based results for suf­fi­ciently large pop­u­la­tions. In the absence of muta­tions the excel­lent agree­ment extends to small pop­u­la­tion sizes.”

    finite-​​size-​​effects population-​​biology noise-​​in-​​design nudge-​​targets

  • [1206.5352] The Sub­word Com­plex­ity of k-​​Automatic Sequences is k-​​Synchronized

    “We show that the sub­word com­plex­ity func­tion p_​x (n), which counts the num­ber of dis­tinct fac­tors of length n of a k-​​automatic sequence x, is k-​​synchronized in the sense of Carpi. As an appli­ca­tion, we gen­er­al­ize recent results of Gold­stein. In con­trast, we show that func­tion which counts the num­ber of unbor­dered fac­tors of length n is not k-​​synchronized.”

    automata strings com­plex­ity nudge-​​targets

  • Con­vex hull algo­rithms — Wikipedia, the free encyclopedia

    “Com­put­ing the con­vex hull means that a non-​​ambiguous and effi­cient rep­re­sen­ta­tion of the required con­vex shape is con­structed. The com­plex­ity of the cor­re­spond­ing algo­rithms is usu­ally esti­mated in terms of n, the num­ber of input points, and h, the num­ber of points on the con­vex hull.”

    computational-​​geometry algo­rithms nudge-​​targets

  • [1205.6363] What Should Devel­op­ers Be Aware Of? An Empir­i­cal Study on the Direc­tives of API Documentation

    “Appli­ca­tion Pro­gram­ming Inter­faces (API) are exposed to devel­op­ers in order to reuse soft­ware libraries. API direc­tives are natural-​​language state­ments in API doc­u­men­ta­tion that make devel­op­ers aware of con­straints and guide­lines related to the usage of an API. This paper presents the design and the results of an empir­i­cal study on the direc­tives of API doc­u­men­ta­tion of object-​​oriented libraries. Its main con­tri­bu­tion is to pro­pose and exten­sively dis­cuss a tax­on­omy of 23 kinds of API directives.”

    digital-​​humanities doc­u­men­ta­tion text-​​mining software-​​development cultural-​​norms

  • Pub­li­ca­tions Avail­able Electronically

    God­fried T. Tou­s­saint, “The Erdos-​​Nagy the­o­rem and its ram­i­fi­ca­tions,” Proc. 11th Cana­dian Con­fer­ence on Com­pu­ta­tional Geom­e­try, Van­cou­ver, Canada, August 16–18 1999, pp. 9–12. Long ver­sion avail­able at: http://​www​.cs​.ubc​.ca/​c​o​n​f​e​r​e​n​c​e​s​/​C​CCG. Also: Tech­ni­cal Report No. SOCS-99.2, School of Com­puter Sci­ence, McGill Uni­ver­sity, June 18, 1999.

    nudge-​​targets geom­e­try genetic-​​programming-​​target low-​​hanging-​​fruit

  • Intro­duc­tion to Lam­ina Emer­gent Mech­a­nisms (LEMS) | Com­pli­ant Mechanisms

    “The fact that LEMs can be fab­ri­cated from pla­nar lay­ers influ­ences both what processes can be used for their man­u­fac­ture and what mate­ri­als may be used in their con­struc­tion. At the micro level, LEMS can be fab­ri­cated using single-​​layer MEMS fab­ri­ca­tion meth­ods and mate­ri­als, which offers sig­nif­i­cant cost and reli­a­bil­ity advan­tages. It also pro­vides oppor­tu­ni­ties for com­plex out-​​of-​​plane motion with only a sin­gle layer. At the macro level, man­u­fac­tur­ing processes used to make sta­tic struc­tures or com­po­nents for assem­bly can be used to cre­ate mech­a­nisms capa­ble of sophis­ti­cated motions and com­plex tasks. Example processes include stamp­ing, fine blank­ing, laser cut­ting, water jet cut­ting, plasma cut­ting, and wire elec­tri­cal dis­charge machin­ing (EDM). Some of these processes, such as stamp­ing, offer sig­nif­i­cant cost advan­tages for high-​​volume pro­duc­tion. Pla­nar fab­ri­ca­tion also allows the use of sheet goods to directly cre­ate mech­a­nisms. The use of low-​​cost, high-​​quality sheet goods has the poten­tial to dra­mat­i­cally reduce cost for high-​​volume pro­duc­tion. It also makes pos­si­ble the next char­ac­ter­is­tic: flat ini­tial state.”

    man­u­fac­tur­ing engineering-​​design fab­ri­ca­tion nudge-​​targets

Items of some interest:

Posted on by

These are my recent Pin​board​.in links:

  • Altaeros Ener­gies Releases Demo Video of Their Fly­ing Wind Tur­bine — Core77

    “What you saw there was a scaled pro­to­type, 35 feet in diam­e­ter. Dur­ing the test run it arrived on-​​site in a dock attached to a trailer, then deployed, acti­vated the tur­bine, and returned to the ground—all auto­mat­i­cally. At its high­est alti­tude of 350 feet, it suc­cess­fully got the tur­bine to gen­er­ate twice as much juice than it gets at tower height. We’d say Altaeros is one to watch.”

    wind-​​power pro­to­type engineering-​​design sus­tain­abil­ity energy

  • More on DRM and ebooks — Charlie’s Diary

    “There is a per­va­sive assump­tion that ebooks are dis­pos­able lit­er­a­ture. But to the vora­cious read­ers, this is not the case. Cur­rently it’s hard for many peo­ple to build up col­lec­tions of books due to space con­straints — nev­er­the­less I know many SF fans (of the kind who read 50–150 books a year) who have turned their homes into libraries. They will be the tip of an ice­berg once ebooks become main­stream; why dis­card an ebook when you can file it and come back to it in 10 years’ time and it takes up no space? For such peo­ple, fil­ing and tag­ging their col­lec­tions is a major issue. And so is porta­bil­ity. It’s true that if they own an iPad they can have an iBooks app full of books pur­chased from Apple, and a Kin­dle app full of books from Ama­zon, and a Nook app full of books from B&N. But those apps are, thanks to DRM, data silos — you can’t cross-​​check to see if you bought book 3 in a series from Apple and book 5 from Ama­zon with­out a lot of fid­dling around.”

    business-​​opportunity col­lect­ing nerds-​​as-​​camel-​​nose my-​​people vague-​​press

  • Avería – The Aver­age Font

    “I am not a type designer. This is the story of the cre­ation of a new font, Avería: the aver­age of all the fonts on my com­puter. The field of typog­ra­phy has long fas­ci­nated me, and I love play­ing with cre­ative pro­gram­ming ideas, so it was per­haps inevitable that the idea came to me one day of “gen­er­a­tive typog­ra­phy”. A Google on the sub­ject brought up lit­tle, and I put the idea to the back of my mind until it occurred to me that per­haps the process of aver­ag­ing, or inter­po­lat­ing, exist­ing fonts might bring up inter­est­ing results. Luck­ily at this point I didn’t do any more web search­ing – instead I grabbed my lap­top and came up with an ini­tial idea for find­ing what the aver­age of all my fonts might look like – by over­lay­ing each let­ter at low opac­ity. The results can be seen in the below image.”

    typog­ra­phy type-​​design type­face generative-​​art design graphic-​​design

  • Phillip Rhodes’ Weblog

    “In short, it’s time for a res­ur­rec­tion of the crypto-​​anarchist /​ techno-​​libertarian /​ cypher­punk move­ment and it’s asso­ci­ated val­ues, activ­i­ties and aes­thetic. Those of us who care about these issues can’t just lurk in the shad­ows and act like noth­ing is hap­pen­ing. It’s time to start telling peo­ple about public-​​key encryp­tion, host­ing key-​​signing par­ties, devel­op­ing new tech­nolo­gies for bypass­ing Inter­net cen­sor­ship, devel­op­ing tools for bypass­ing State and Cor­po­ra­tion con­trolled mes­sag­ing chan­nels, and tak­ing a stand for freedom.”

    cryp­tog­ra­phy nrrrrds cultural-​​assumptions cultural-​​dynamics diver­sity

  • No, physi­cians don’t under­stand screen­ing sta­tis­tics | The Inci­den­tal Economist

    “So basically,when it comes to sav­ing lives, docs are three times more likely to rec­om­mend a screen­ing test based on irrel­e­vant data than they are to rec­om­mend it based on rel­e­vant data. I’m brac­ing myself for the hate mail, but this is part of the rea­son why I’m skep­ti­cal that just pro­vid­ing docs with more evi­dence will change the way they prac­tice. Most docs just aren’t trained to under­stand this stuff.”

    medical-​​culture health­care sta­tis­tics probability-​​theory plan­ning

  • reveal.js


    slides pre­sen­ta­tion library javascript sim­ple

  • Fancy HTML5 Slides with knitr and pan­doc | Yihui Xie

    “Karthik Ram gave an Intro­duc­tion to R a cou­ple of weeks ago, and I strongly rec­om­mend you to take a look at his cool HTML5 slides. I started try­ing HTML5 slides last year, and now it is dif­fi­cult for me to go back to beamer, which I have used for a few years for my pre­se­n­a­tions. It is hor­ri­ble to see beamer slides every­where at aca­d­e­mic con­fer­ences (espe­cially the clas­sic blue themes).”

    slides pre­sen­ta­tion library javascript mark­down

  • An algo­rithm is just an algo­rithm | Gene Expres­sion | Dis­cover Magazine

    “Another illus­tra­tion that knowl­edge comes not through blind adher­ence to meth­ods, but human reflection.”

    algo­rithms sta­tis­tics sto­ry­telling i-​​need-​​the-​​name-​​for-​​this

  • Cap­tur­ing dealer descrip­tions in our online cat­a­log — Yale Law Library — Rare Books Blog

    “Attrac­tive and rare set of decrees con­cern­ing the func­tion­ing of the judi­ciary in the papal city of Bologna. These city statutes were pro­mul­gated by the Pope’s legate, Car­di­nal Benedetto Gius­tini­ani (1554−1621). Despite the issu­ing author­ity, the con­sti­tu­tions (a word indi­cat­ing leg­is­la­tion of the high­est level) are entirely non-​​religious in con­tent, relat­ing to civil law jus­tice in the city. They shed con­sid­er­able light into how courts worked in Bologna. Included are instruc­tions on cases involv­ing poor peo­ple; rules for notaries; the keep­ing of reg­is­ters; seizures of prop­erty; tak­ing of sus­pects; pay­ment of offi­cers; expert wit­nesses; and the gov­ern­ing of appeals. Pages 192–198 com­prise papal edicts on the salaries of Bolog­nese judges and notaries.” — Leo Cado­gan Rare Books (Dec. 2011)

    books cat­a­log nanohis­tory librar­i­ans meta­data

Items of some interest:

Posted on by

These are my recent Pin​board​.in links:

  • Jonathan Lethem’s ‘Neote­nous Aes­thetic” — Mis­ter Bit — Wired​.it

    ‘Dur­ing the brief, but very inter­est­ing Q&A ses­sion, Lethem argued that inter­net cul­ture brought the “closet into the open”, that is, it gave ephemera, triv­i­al­i­ties, and every­day activ­i­ties “A new kind of vis­i­bil­ity”. “Peo­ple have always been pro­duc­ing weird stuff and have always been engag­ing in arcane activ­i­ties,” Lethem remarked. “What is really new is the fact the now we can see it. We can see it all. We can quan­tify what we do — or not do — online.” Lethem men­tioned the uncanny abil­ity to track, in real time, “how many books I am not sell­ing on Ama­zon”. “Real­ity has acquired a new level of mea­sur­a­bil­ity”. “The activ­i­ties we per­form in our dig­i­tal age are not nec­es­sar­ily new. What is new is that. We. Can. See. Them. All.”.’

    one-​​measures-​​a-​​circle inter­per­me­ation access local­ism

  • Sex, Oil, and Video­tape | Mother Jones

    “Loom­ing over Saylor’s con­fronta­tion with Bolen­baugh was the EPA’s Sep­tem­ber 27 cleanup dead­line, and it appears that Enbridge and its con­trac­tors were feel­ing the pres­sure as it drew near. In early Sep­tem­ber, after the Michi­gan Mes­sen­ger pub­lished its exposé on the use of undoc­u­mented work­ers by Hall­mark Indus­trial, another group of work­ers employed by a dif­fer­ent Enbridge con­trac­tor came for­ward with detailed sto­ries of how they had been instructed to con­ceal oil at the same site. Work­ers would land on an island, they said, remove all veg­e­ta­tion, and then lay out absorbent pom-​​poms, all per EPA reg­u­la­tions. But once the top layer of oil was absorbed, they were instructed to rake dirt over the area to make it appear as though it had been dug out. One worker described his super­vi­sor show­ing him the process step-​​by-​​step, con­clud­ing with sprin­kling a thin layer of dirt on top. “He said, ‘There, now they can’t see it. It is clean,’” the worker told the Mes­sen­ger. Another worker described being told to cover pock­ets of oil with leaves and sticks. As a last step, such areas were cor­doned off with cau­tion tape.”

    oil­spill Kala­ma­zoo local whistle­blower

  • [1204.4200] Dis­crete Dynam­i­cal Genetic Pro­gram­ming in XCS

    “A num­ber of rep­re­sen­ta­tion schemes have been pre­sented for use within Learn­ing Clas­si­fier Sys­tems, rang­ing from binary encod­ings to neural net­works. This paper presents results from an inves­ti­ga­tion into using a dis­crete dynam­i­cal sys­tem rep­re­sen­ta­tion within the XCS Learn­ing Clas­si­fier Sys­tem. In par­tic­u­lar, asyn­chro­nous ran­dom Boolean net­works are used to rep­re­sent the tra­di­tional condition-​​action pro­duc­tion sys­tem rules. It is shown pos­si­ble to use self-​​adaptive, open-​​ended evo­lu­tion to design an ensem­ble of such dis­crete dynam­i­cal sys­tems within XCS to solve a num­ber of well-​​known test problems.”

    genetic-​​programming learning-​​classifier-​​systems representation-​​theory design-​​patterns boolean-​​networks nudge-​​targets nice

  • Why Is Darwin’s Tan­gled Bank Tan­gled? : 13.7: Cos­mos And Cul­ture : NPR

    Sad to hear him still phras­ing this sim­ple truth so obscurely: Not “Because, on the scale of mol­e­c­u­lar bind­ing site recog­ni­tion, say a few tens of angstroms in length, height and width and sev­eral other fea­tures such as polar­ity, van-​​der-​​Waal forces, and so on, there are far fewer effec­tively dif­fer­ent mol­e­c­u­lar shapes than there are kinds of mol­e­cules.“ … but “Because there are fewer sto­ries than there are facts.”

    oh-​​stu pragmatism-it-ain’t philosophy-​​of-​​science

  • Math Notes | Futil­ity Closet

    So for finite sequences of dig­its, which sequences are such that the most right-​​truncated sub­strings are prime? Which are such that the most right-​​repeating exten­sions are prime?

    nudge-​​targets number-​​theory indirect-​​link

  • Home — Scal­able and Mod­u­lar Archi­tec­ture for CSS

    “I’ve been ana­lyz­ing my process (and the process of those around me) and fig­ur­ing out how best to struc­ture code for projects on a larger scale. What I’ve found is a process that works equally well for sites small and large. Learn how to struc­ture your CSS to allow for flex­i­bil­ity and main­tain­abil­ity as your project and your team grows.”

    css tuto­r­ial best-​​practices graphic-​​design via-​​trek

  • [1204.3678] Crowd Mem­ory: Learn­ing in the Collective

    “Crowd algo­rithms often assume work­ers are inex­pe­ri­enced and thus fail to adapt as work­ers in the crowd learn a task. These assump­tions fun­da­men­tally limit the types of tasks that sys­tems based on such algo­rithms can han­dle. This paper explores how the crowd learns and remem­bers over time in the con­text of human com­pu­ta­tion, and how more real­is­tic assump­tions of worker expe­ri­ence may be used when design­ing new sys­tems. We first demon­strate that the crowd can recall infor­ma­tion over time and dis­cuss pos­si­ble impli­ca­tions of crowd mem­ory in the design of crowd algo­rithms. We then explore crowd learn­ing dur­ing a con­tin­u­ous con­trol task. Recent sys­tems are able to dis­guise dynamic groups of work­ers as crowd agents to sup­port con­tin­u­ous tasks, but have not yet con­sid­ered how such agents are able to learn over time. We show, using a real-​​time gam­ing set­ting, that crowd agents can learn over time, and ‘remem­ber’ by pass­ing strate­gies from one gen­er­a­tion of work­ers to the next, despite high turnover rates in the work­ers com­pris­ing them. We con­clude with a dis­cus­sion of future research direc­tions for crowd mem­ory and learning.”

    crowd­sourc­ing learn­ing agent-​​based collective-​​intelligence mem­ory nudge-​​targets

  • [0911.1582] Manip­u­lat­ing Tour­na­ments in Cup and Round Robin Competitions

    “In sports com­pe­ti­tions, teams can manip­u­late the result by, for instance, throw­ing games. We show that we can decide how to manip­u­late round robin and cup com­pe­ti­tions, two of the most pop­u­lar types of sport­ing com­pe­ti­tions in poly­no­mial time. In addi­tion, we show that find­ing the min­i­mal num­ber of games that need to be thrown to manip­u­late the result can also be deter­mined in poly­no­mial time. Finally, we show that there are sev­eral dif­fer­ent vari­a­tions of stan­dard cup com­pe­ti­tions where manip­u­la­tion remains polynomial.”

    algo­rithms eco­nom­ics game-​​theory nudge-​​targets

  • Intro­duc­ing the Jour­nal of Dig­i­tal Human­i­ties — ProfHacker — The Chron­i­cle of Higher Education

    “If the con­tents of the inau­gural issue—which range from an essay argu­ing that human­ists need to under­stand and inter­pret quan­ti­ta­tive data to a review of the Word­Seer text analy­sis tool—fall out­side your usual schol­arly domain, then cer­tainly the journal’s edi­to­r­ial and pub­lish­ing appa­ra­tus will piqué your interest. As Dan Cohen explained in a sep­a­rate blog post, the jour­nal oper­ates under the model of catch­ing the good—of find­ing sub­stan­tive and valu­able dig­i­tal human­i­ties work “in what­ever for­mat, and wher­ever, it exists.” Blogs, pod­casts, Twit­ter con­ver­sa­tions, slideshows, and so on, these are all venues in which sig­nif­i­cant and, though I hate to use such an ungainly word, impact­ful work is being done. The reg­u­lar and guest edi­tors “catch” this work, and then pro­vide lay­ers of eval­u­a­tion and review before it appears in JDH.”

    digital-​​humanities jour­nal to-​​read two-​​cultures-​​only-​​one-​​of-​​which-​​can-​​write

  • [1005.4159] The Com­plex­ity of Manip­u­lat­ing $k$-Approval Elections

    “An impor­tant prob­lem in com­pu­ta­tional social choice the­ory is the com­plex­ity of unde­sir­able behav­ior among agents, such as con­trol, manip­u­la­tion, and bribery in elec­tion sys­tems. These kinds of vot­ing strate­gies are often tempt­ing at the indi­vid­ual level but dis­as­trous for the agents as a whole. Cre­at­ing elec­tion sys­tems where the deter­mi­na­tion of such strate­gies is dif­fi­cult is thus an impor­tant goal. …”

    vot­ing game-​​theory design-​​patterns mechanism-​​design nudge-​​targets

  • [0903.1147] Tetravex is NP-​​complete

    “Tetravex is a widely played one per­son com­puter game in which you are given $n^2$ unit tiles, each edge of which is labelled with a num­ber. The objec­tive is to place each tile within a $n$ by $n$ square such that all neigh­bour­ing edges are labelled with an iden­ti­cal num­ber. Unfor­tu­nately, play­ing Tetravex is com­pu­ta­tion­ally hard. More pre­cisely, we prove that decid­ing if there is a tiling of the Tetravex board is NP-​​complete. Decid­ing where to place the tiles is there­fore NP-​​hard. This may help to explain why Tetravex is a good puz­zle. This result com­pli­ments a num­ber of sim­i­lar results for one per­son games involv­ing tiling. For exam­ple, NP-​​completeness results have been shown for: the offline ver­sion of Tetris, KPlumber (which involves rotat­ing tiles con­tain­ing draw­ings of pipes to make a con­nected net­work), and short­est slid­ing puz­zle prob­lems. It raises a num­ber of open ques­tions. For exam­ple, is the infi­nite ver­sion Turing-​​complete? How do we gen­er­ate Tetravex prob­lems which are truly puz­zling as ran­dom NP-​​complete prob­lems are often sur­pris­ing easy to solve? Can we observe phase tran­si­tion behav­iour? What about the com­plex­ity of the prob­lem when it is guar­an­teed to have an unique solu­tion? How do we gen­er­ate puz­zles with unique solutions?”

    mathematical-​​recreations computational-​​complexity algo­rithms nudge-​​targets

  • [1204.4286] Fair Allo­ca­tion With­out Trade

    “We con­sider the age-​​old prob­lem of allo­cat­ing items among dif­fer­ent agents in a way that is effi­cient and fair. Two papers, by Dolev et al. and Ghodsi et al., have recently stud­ied this prob­lem in the con­text of com­puter sys­tems. Both papers had sim­i­lar mod­els for agent pref­er­ences, but advo­cated dif­fer­ent notions of fair­ness. We for­mal­ize both fair­ness notions in eco­nomic terms, extend­ing them to apply to a larger fam­ily of util­i­ties. Not­ing that in set­tings with such util­i­ties effi­ciency is eas­ily achieved in mul­ti­ple ways, we study notions of fair­ness as cri­te­ria for choos­ing between dif­fer­ent effi­cient allo­ca­tions. Our tech­ni­cal results are algo­rithms for find­ing fair allo­ca­tions cor­re­spond­ing to two fair­ness notions: Regard­ing the notion sug­gested by Ghodsi et al., we present a polynomial-​​time algo­rithm that com­putes an allo­ca­tion for a gen­eral class of fair­ness notions, in which their notion is included. For the other, sug­gested by Dolev et al., we show that a com­pet­i­tive mar­ket equi­lib­rium achieves the desired notion of fair­ness, thereby obtain­ing a polynomial-​​time algo­rithm that com­putes such a fair allo­ca­tion and solv­ing the main open prob­lem raised by Dolev et al.”

    eco­nom­ics game-​​theory fair­ness algo­rithms phi­los­o­phy design-​​patterns

  • Why is Esti­mat­ing so Hard? | 8th Light

    “It turns out that we don’t know the pro­ce­dure. We haven’t got any clue to just how dif­fi­cult the pro­ce­dure is. We aren’t com­put­ers. We don’t fol­low pro­ce­dures. And so com­par­ing the com­plex­ity of the man­ual task, to the com­plex­ity of the pro­ce­dure is invalid. This is one of the rea­sons that esti­mates are so hard, and why we get them wrong so often. We look at a task that seems easy and esti­mate it on that basis, only to find that writ­ing down the pro­ce­dure is actu­ally quite intri­cate. We blow the esti­mate because we esti­mate the wrong thing.”

    esti­ma­tion agile-​​practices philosophy-​​of-​​engineering man­age­ment self-​​definition plan­ning

  • [1204.4374] Higher Order City Voronoi Diagrams

    “We inves­ti­gate higher-​​order Voronoi dia­grams in the city met­ric. This met­ric is induced by quick­est paths in the L1 met­ric in the pres­ence of an accel­er­at­ing trans­porta­tion net­work of axis-​​parallel line segments. …”

    computational-​​geometry algo­rithms voronoi-​​diagrams diver­sity network-​​theory nudge-​​targets

  • Topic mod­el­ing made just sim­ple enough. | The Stone and the Shell

    “Com­puter sci­en­tists make LDA seem com­pli­cated because they care about prov­ing that their algo­rithms work. And the proof is indeed brain-​​squashingly hard. But the prac­tice of topic mod­el­ing makes good sense on its own, with­out proof, and does not require you to spend even a sec­ond think­ing about “Dirich­let dis­tri­b­u­tions.” When the math is approached in a prac­ti­cal way, I think human­ists will find it easy, intu­itive, and empow­er­ing. This post focuses on LDA as short­hand for a broader fam­ily of “prob­a­bilis­tic” tech­niques. I’m going to ask how they work, what they’re for, and what their lim­its are.”

    text-​​processing clas­si­fi­ca­tion algo­rithms lovely two-​​cultures-​​only-​​one-​​of-​​which-​​can-​​write

  • Math­e­mati­cians are Giraffe Hunters by Barry Mazur | berfrois

    “No won­der life (i.e., the thing that my once 10-​​year old niece referred to as “the thing that isn’t fair”) comes to us as a fil­i­gree of ash sto­ries. Walk­ing down the street past a cou­ple in con­ver­sa­tion, an over­heard mor­pheme, a mere glance at a wrongly but­toned rain­coat, sparks a nar­ra­tive in our imag­i­na­tion. Ask any ques­tion begin­ning with “why?” and the answer will surely be a story, or it will be embed­ded in a story. Or, at the very least, it will offer a tempt­ing thread for some story that you your­self will hold onto, embell­ish even, as you try to absorb the answer. We inter­po­late between such frag­ments. This is, for many of us, sim­ply the way we think. What about the “why ques­tions” in sci­ence, in logic, in math­e­mat­ics? We should acknowl­edge how they are often “what ques­tions” or “how ques­tions” in dis­guise. Or how they slide down into such ques­tions, as the ever-​​elusive, ever-​​illusory quest for an X that actu­ally causes a Y dis­solves. Some of the more sat­is­fy­ing answers to sci­en­tific “why” ques­tions involves deft rephras­ing. “Why is the sky blue?” is replaced by the ques­tion “what is the func­tion that describes scat­ter­ing ampli­tude as depen­dent on wave-​​length”?”

    math­e­mat­ics philosophy-​​of-​​mathematics sto­ry­telling prag­ma­tism theory-​​and-​​practice-​​sitting-​​in-​​a-​​tree what-​​is-​​it-​​good-​​for-​​hunh

Items of some interest:

Posted on by

These are my recent Pin​board​.in links:

  • Wel­come to the Group Pat­tern Lan­guage Project | Group Works

    “This deck of 91 full-​​colour cards names what skilled facil­i­ta­tors and other par­tic­i­pants do to make things work.  The con­tent is more spe­cific than val­ues and less spe­cific than tips and tech­niques, cut­ting across exist­ing method­olo­gies with a designer’s eye to cap­ture the pat­terns that repeat.  The deck can be used to plan sess­sions, reflect on and debrief them, pro­vide guid­ance, and share respon­si­bil­ity for mak­ing the process go well.  It has the poten­tial to pro­vide a com­mon ref­er­ence point for prac­ti­tion­ers, and serve as a frame­work and learn­ing tool for those study­ing the field. ”

    via:bkerr col­lab­o­ra­tion design-​​patterns tools social-​​dynamics

  • [1202.0001] Vector-​​based model of elas­tic bonds for DEM sim­u­la­tion of solids

    “A new model for com­puter sim­u­la­tion of solids, com­posed of bonded par­ti­cles, is pro­posed. Vec­tors rigidly con­nected with par­ti­cles are used for descrip­tion of defor­ma­tion of a sin­gle bond. The expres­sion for poten­tial energy of the bond and cor­re­spond­ing expres­sions for forces and moments are pro­posed. For­mu­las, con­nect­ing para­me­ters of the model with lon­gi­tu­di­nal, shear, bend­ing and tor­sional stiff­nesses of the bond, are derived. It is shown that the model allows to describe any val­ues of the bond stiff­nesses exactly. Two dif­fer­ent cal­i­bra­tion pro­ce­dures depend­ing on bond length/​thickness ratio are pro­posed. It is shown that para­me­ters of model can be cho­sen so that under small defor­ma­tions the bond is equiv­a­lent to either Bernoulli-​​Euler or Tim­o­shenko rod or short cylin­der con­nect­ing par­ti­cles. Sim­ple expres­sions, con­nect­ing para­me­ters of V-​​model with geo­met­ri­cal and mechan­i­cal char­ac­ter­is­tics of the bond, are derived. Com­puter sim­u­la­tion of dynam­i­cal buck­ling of the straight dis­crete rod and dis­crete half-​​spherical shell is car­ried out.”

    mod­el­ing mechanical-​​systems materials-​​science computational-​​methods algo­rithms nudge-​​targets

  • [1202.0253] High-​​speed Flight in an Ergodic Forest

    “Inspired by birds fly­ing through clut­tered envi­ron­ments such as dense forests, this paper stud­ies the the­o­ret­i­cal foun­da­tions of a novel motion plan­ning prob­lem: high-​​speed nav­i­ga­tion through a randomly-​​generated obsta­cle field when only the sta­tis­tics of the obsta­cle gen­er­at­ing process are known a pri­ori. Resem­bling a pla­nar for­est envi­ron­ment, the obsta­cle gen­er­at­ing process is assumed to deter­mine the loca­tions and sizes of disk-​​shaped obsta­cles. When this process is ergodic, and under mild tech­ni­cal con­di­tions on the dynam­ics of the bird, it is shown that the exis­tence of an infi­nite collision-​​free tra­jec­tory through the for­est exhibits a phase tran­si­tion. On one hand, if the bird flies faster than a cer­tain crit­i­cal speed, then, with prob­a­bil­ity one, there is no infi­nite collision-​​free tra­jec­tory, i.e., the bird will even­tu­ally col­lide with some tree, almost surely, regard­less of the plan­ning algo­rithm gov­ern­ing the bird’s motion. On the other hand, if the bird flies slower than this crit­i­cal speed, then there exists at least one infi­nite collision-​​free tra­jec­tory, almost surely. Lower and upper bounds on the crit­i­cal speed are derived for the spe­cial case of a homo­ge­neous Pois­son for­est con­sid­er­ing a sim­ple model for the bird’s dynam­ics. For the same case, an equiv­a­lent per­co­la­tion model is pro­vided. Using this model, the phase dia­gram is approx­i­mated in Monte-​​Carlo sim­u­la­tions. This paper also estab­lishes novel con­nec­tions between robot motion plan­ning and sta­tis­ti­cal physics through ergodic the­ory and per­co­la­tion the­ory, which may be of inde­pen­dent interest.”

    robot­ics plan­ning algo­rithms nudge-​​targets

  • [1202.0077] An Inter­act­ing Par­ti­cle Model for Clus­ter­ing Euclid­ean Datasets

    “In this paper we pro­pose a method based on inter­act­ing par­ti­cle physics, devised for clus­ter­ing Euclid­ean datasets with­out ini­tial con­straints or con­di­tions. We model any dataset as an inter­act­ing par­ti­cle sys­tem, whose ele­ments cor­re­spond to par­ti­cles that inter­act through a sim­pli­fied ver­sion of Lennard-​​Jones poten­tials. In so doing, mutual attrac­tive inter­ac­tions allow to iden­tify groups of prox­i­mal par­ti­cles. The main out­come of this mod­el­ing task is an adja­cency matrix, taken as input by a com­mu­nity detec­tion algo­rithm aimed to iden­tify dif­fer­ent par­ti­tions. The under­ly­ing con­jec­ture is that, using a mul­tires­o­lu­tion analy­sis, the adopted model allows to find the right num­ber of clus­ters for any given dataset. Exper­i­men­tal results, per­formed in com­par­i­son with a clas­si­cal clus­ter­ing algo­rithm, con­firm this assumption.”

    clus­ter­ing data-​​analysis algo­rithms nudge-​​targets distributed-​​processing

  • [1201.6583] Empow­er­ment for Con­tin­u­ous Agent-​​Environment Systems

    “This paper devel­ops gen­er­al­iza­tions of empow­er­ment to con­tin­u­ous states. Empow­er­ment is a recently intro­duced information-​​theoretic quan­tity moti­vated by hypothe­ses about the effi­ciency of the sen­so­ri­mo­tor loop in bio­log­i­cal organ­isms, but also from con­sid­er­a­tions stem­ming from curiosity-​​driven learn­ing. Empowe­mer­ment mea­sures, for agent-​​environment sys­tems with sto­chas­tic tran­si­tions, how much influ­ence an agent has on its envi­ron­ment, but only that influ­ence that can be sensed by the agent sen­sors. It is an information-​​theoretic gen­er­al­iza­tion of joint con­trol­la­bil­ity (influ­ence on envi­ron­ment) and observ­abil­ity (mea­sure­ment by sen­sors) of the envi­ron­ment by the agent, both con­trol­la­bil­ity and observ­abil­ity being usu­ally defined in con­trol the­ory as the dimen­sion­al­ity of the control/​observation spaces.…”

    agent-​​based emergent-​​design robot­ics engineering-​​design machine-​​learning empow­er­ment nudge

  • [1201.6655] Learn­ing Per­for­mance of Pre­dic­tion Mar­kets with Kelly Bettors

    “In eval­u­at­ing pre­dic­tion mar­kets (and other crowd-​​prediction mech­a­nisms), inves­ti­ga­tors have repeat­edly observed a so-​​called “wis­dom of crowds” effect, which roughly says that the aver­age of par­tic­i­pants per­forms much bet­ter than the aver­age par­tic­i­pant. The mar­ket price—an aver­age or at least aggre­gate of traders’ beliefs—offers a bet­ter esti­mate than most any indi­vid­ual trader’s opin­ion. In this paper, we ask a stronger ques­tion: how does the mar­ket price com­pare to the best trader’s belief, not just the aver­age trader. We mea­sure the market’s worst-​​case log regret, a notion com­mon in machine learn­ing the­ory. To arrive at a mean­ing­ful answer, we need to assume some­thing about how traders behave. We sup­pose that every trader opti­mizes accord­ing to the Kelly cri­te­ria, a strat­egy that prov­ably max­i­mizes the com­pound growth of wealth over an (infi­nite) sequence of mar­ket inter­ac­tions. We show sev­eral consequences.…”

    pre­dic­tion performance-​​measure agent-​​based sim­u­la­tion nudge-​​targets wisdom-​​of-​​crowds

  • Curat­ing the kraken « Pub­lic Historian

    ‘This is why “curate” is still a word to con­jure by in our cul­ture.  It still promises trans­for­ma­tive power.’

    muse­ol­ogy prag­mat­ics nam­ing engineering-​​of-​​philosophy

  • [1201.5780] Full and Half Gilbert Tes­sel­la­tions with Rec­tan­gu­lar Cells

    “We inves­ti­gate the ray-​​length dis­tri­b­u­tions for two dif­fer­ent rec­tan­gu­lar ver­sions of Gilbert’s tes­sel­la­tion. In the full rec­tan­gu­lar ver­sion, lines extend either hor­i­zon­tally (with east– and west-​​growing rays) or ver­ti­cally (north– and south-​​growing rays) from seed points which form a Pois­son point process, each ray stop­ping when another ray is met. In the half rec­tan­gu­lar ver­sion, east and south grow­ing rays do not inter­act with west and north rays. For the half rec­tan­gu­lar tes­sel­la­tion we com­pute ana­lyt­i­cally, via recur­sion, a series expan­sion for the ray-​​length dis­tri­b­u­tion, whilst for the full rec­tan­gu­lar ver­sion we develop an accu­rate sim­u­la­tion tech­nique, based in part on the stopping-​​set the­ory of Zuyev, to accom­plish the same. We demon­strate the remark­able fact that plots of the two dis­tri­b­u­tions appear to be iden­ti­cal when the inten­sity of seeds in the half model is twice that in the full model. Our paper explores this coin­ci­dence mind­ful of the fact that, for one model, our results are from a sim­u­la­tion (with inher­ent sam­pling error).…”

    geom­e­try tiling algo­rithms generative-​​art sim­u­la­tion emer­gence interesting-​​problem

Items of some interest…

Posted on by

These are my recent Pin​board​.in links:

  • [1106.1804] A Crit­i­cal Assess­ment of Bench­mark Com­par­i­son in Planning

    “Recent trends in plan­ning research have led to empir­i­cal com­par­i­son becom­ing com­mon­place. The field has started to set­tle into a method­ol­ogy for such com­par­isons, which for obvi­ous prac­ti­cal rea­sons requires run­ning a sub­set of plan­ners on a sub­set of prob­lems. In this paper, we char­ac­ter­ize the method­ol­ogy and exam­ine eight implicit assump­tions about the prob­lems, plan­ners and met­rics used in many of these com­par­isons. The prob­lem assump­tions are: PR1) the per­for­mance of a gen­eral pur­pose plan­ner should not be penalized/​biased if exe­cuted on a sam­pling of prob­lems and domains, PR2) minor syn­tac­tic dif­fer­ences in rep­re­sen­ta­tion do not affect per­for­mance, and PR3) prob­lems should be solv­able by STRIPS capa­ble plan­ners unless they require ADL. The plan­ner assump­tions are: PL1) the lat­est ver­sion of a plan­ner is the best one to use, PL2) default para­me­ter set­tings approx­i­mate good per­for­mance, and PL3) time cut-​​offs do not unduly bias out­come. The met­rics assump­tions are: M1) per­for­mance degrades sim­i­larly for each plan­ner when run on degraded run­time envi­ron­ments (e.g., machine plat­form) and M2) the num­ber of plan steps dis­tin­guishes per­for­mance. We find that most of these assump­tions are not sup­ported empir­i­cally; in par­tic­u­lar, that plan­ners are affected dif­fer­ently by these assump­tions. We con­clude with a call to the com­mu­nity to devote research resources to improv­ing the state of the prac­tice and espe­cially to enhanc­ing the avail­able bench­mark problems.”

    plan­ning bench­mark­ing algo­rithms horse-​​races engineering-​​design operations-​​research nudge-​​targets

  • [1108.4361] The rela­tion­ship between acquain­tance­ship and coau­thor­ship in sci­en­tific col­lab­o­ra­tion networks

    “This arti­cle exam­ines the rela­tion­ship between acquain­tance­ship and coau­thor­ship pat­terns in a multi-​​disciplinary, multi-​​institutional, geo­graph­i­cally dis­trib­uted research cen­ter. Two social net­works are con­structed and com­pared: a net­work of coau­thor­ship, rep­re­sent­ing how researchers write arti­cles with one another, and a net­work of acquain­tance­ship, rep­re­sent­ing how those researchers know each other on a per­sonal level, based on their responses to an online sur­vey. Sta­tis­ti­cal analy­ses of the topol­ogy and com­mu­nity struc­ture of these net­works point to the impor­tance of small-​​scale, local, per­sonal net­works pred­i­cated upon acquain­tance­ship for accom­plish­ing col­lab­o­ra­tive work in sci­en­tific communities.”

    academic-​​culture network-​​theory cita­tion social-​​networks

  • [1108.4223] The set-​​theoretic multiverse

    “The mul­ti­verse view in set the­ory, intro­duced and argued for in this arti­cle, is the view that there are many dis­tinct con­cepts of set, each instan­ti­ated in a cor­re­spond­ing set-​​theoretic uni­verse. The uni­verse view, in con­trast, asserts that there is an absolute back­ground set con­cept, with a cor­re­spond­ing absolute set-​​theoretic uni­verse in which every set-​​theoretic ques­tion has a def­i­nite answer. The mul­ti­verse posi­tion, I argue, explains our expe­ri­ence with the enor­mous diver­sity of set-​​theoretic pos­si­bil­i­ties, a phe­nom­e­non that chal­lenges the uni­verse view. In par­tic­u­lar, I argue that the con­tin­uum hypoth­e­sis is set­tled on the mul­ti­verse view by our exten­sive knowl­edge about how it behaves in the mul­ti­verse, and as a result it can no longer be set­tled in the man­ner for­merly hoped for.”

    math­e­mat­ics mathematical-​​criticism looking-​​forward-​​to-​​understanding-​​this-​​someday pragmatism-it-ain’t

  • [1102.1934] The struc­ture of the Arts & Human­i­ties Cita­tion Index: A map­ping on the basis of aggre­gated cita­tions among 1,157 journals

    “Using the Arts & Human­i­ties Cita­tion Index (A&HCI) 2008, we apply map­ping tech­niques pre­vi­ously devel­oped for map­ping jour­nal struc­tures in the Sci­ence and Social Sci­ence Cita­tion Indices. Cita­tion rela­tions among the 110,718 records were aggre­gated at the level of 1,157 jour­nals spe­cific to the A&HCI, and the jour­nal struc­tures are ques­tioned on whether a cog­ni­tive struc­ture can be recon­structed and visu­al­ized. Both cosine-​​normalization (bot­tom up) and fac­tor analy­sis (top down) sug­gest a divi­sion into approx­i­mately twelve sub­sets. The rela­tions among these sub­sets are explored using var­i­ous visu­al­iza­tion tech­niques. How­ever, we were not able to retrieve this struc­ture using the ISI Sub­ject Cat­e­gories, includ­ing the 25 cat­e­gories which are spe­cific to the A&HCI. We dis­cuss options for val­i­da­tion such as against the cat­e­gories of the Human­i­ties Indi­ca­tors of the Amer­i­can Acad­emy of Arts and Sci­ences, the panel struc­ture of the Euro­pean Ref­er­ence Index for the Human­i­ties (ERIH), and com­pare our results with the cur­ricu­lum orga­ni­za­tion of the Human­i­ties Sec­tion of the Col­lege of Let­ters and Sci­ences of UCLA as an exam­ple of insti­tu­tional organization.”

    network-​​theory citation-​​networks human­i­ties academic-​​culture quantitative-​​humanities

  • [1108.4220] A Dynam­i­cal Sys­tems Approach for Sta­tic Eval­u­a­tion in Go

    “In the paper argu­ments are given why the con­cept of sta­tic eval­u­a­tion has the poten­tial to be a use­ful exten­sion to Monte Carlo tree search. A new con­cept of mod­el­ing sta­tic eval­u­a­tion through a dynam­i­cal sys­tem is intro­duced and strengths and weak­nesses are dis­cussed. The gen­eral suit­abil­ity of this approach is demonstrated.”

    representation-​​theory plan­ning monte-​​carlo-​​models nudge algo­rithms

  • [1105.5449] AntNet: Dis­trib­uted Stig­mer­getic Con­trol for Com­mu­ni­ca­tions Networks

    “…We com­pare our algo­rithm with six state-​​of-​​the-​​art rout­ing algo­rithms com­ing from the telecom­mu­ni­ca­tions and machine learn­ing fields. The algo­rithms’ per­for­mance is eval­u­ated over a set of real­is­tic test­beds. We run many exper­i­ments over real and arti­fi­cial IP data­gram net­works with increas­ing num­ber of nodes and under sev­eral par­a­dig­matic spa­tial and tem­po­ral traf­fic dis­tri­b­u­tions. Results are very encour­ag­ing. AntNet showed supe­rior per­for­mance under all the exper­i­men­tal con­di­tions with respect to its com­peti­tors. We ana­lyze the main char­ac­ter­is­tics of the algo­rithm and try to explain the rea­sons for its superiority.”

    ant-​​colony-​​optimization network-​​theory net­works con­trol algo­rithms nudge-​​targets rout­ing

  • Bozo Sapi­ens: Sacco and Vanzetti: Evidence

    “Wigmore’s tech­nique, like prob­a­bil­ity itself, is both wide-​​ranging and tediously painstak­ing; his book was pop­u­lar only among insom­niac judges. But now that com­put­ers can take on the numer­i­cal drudgery, it is prov­ing its worth in just such tan­gled cases as Sacco’s and Vanzetti’s. The legal schol­ars Joseph Kadane and David Schum have applied a sophis­ti­cated exten­sion of Wigmore’s method to the vast body of evi­dence from the case. Theirs is a remark­able achieve­ment; their charts retain all the orig­i­nal com­plex­i­ties: the facts with­held or per­verted, the hearsay, the lies told and dis­avowed on both sides, the charged polit­i­cal atmos­phere of eighty years ago. They never dis­count a fact, no mat­ter how far-​​fetched; they  sim­ply give it its due weight in their dynamic struc­ture. Their con­clu­sion?  Unjust though it is to sum­ma­rize a book in a sen­tence, the bal­ance of prob­a­bil­ity seems to favor the view expressed long ago by one of the defen­dants’ close com­pan­ions: “every­one in the Boston anar­chis­tic cir­cle knew that Sacco was guilty and that Vanzetti was inno­cent as far as the actual par­tic­i­pa­tion in the killing.” So, there it is: whichever side our polit­i­cal instincts favor, we are des­tined to be half wrong. Vanzetti’s last words were: “I wish to for­give some peo­ple for what they are now doing to me.”  If we were all will­ing to make the extra effort to work out the prob­a­bil­i­ties, per­haps we might not need for­give­ness so often.”

    probability-​​theory legal-​​studies computational-​​methods his­tory

  • Get­ting first sale wrong

    “I hate to imag­ine it, but this deci­sion raises some fright­en­ing pos­si­bil­i­ties and requires greater vig­i­lance on the part of librar­i­ans.  At the very least, libraries must demand infor­ma­tion from pub­lish­ers about where every item has been man­u­fac­tured. Obtain­ing such infor­ma­tion is no longer an option, since our legal uses of the things we buy now depends on know­ing this, and the place where the pub­lisher is located or where the sale took place is sim­ply not suf­fi­cient.  But what I really fear is that pub­lish­ers will begin to man­u­fac­ture more of their works over­seas and then try to demand a higher price – one that includes “pub­lic lend­ing rights” – from libraries. If libraries are in a dif­fi­cult posi­tion, stu­dents may be even worse off under the Sec­ond Circuit’s rul­ing.  Again, pub­lish­ers now have an incen­tive to man­u­fac­ture their text­books abroad and sell them to U.S. stu­dents.  Such stu­dents would no longer have the right to re-​​sell their text­books or to pur­chase used texts.  The defen­dant in the case, Supap Kirt­saeng, had made a lucra­tive busi­ness out of reselling text­books pur­chased in Asia.  He was per­haps an unsym­pa­thetic party, but what he was doing was not dif­fer­ent in kind from the resale of texts that is com­mon on all col­lege cam­puses.  This activ­ity makes higher edu­ca­tion a lit­tle more pos­si­ble for many.  Now pub­lish­ers have an easy way for to close down this sec­ondary mar­ket for text­books, about which they have com­plained for years.  In the process, the cost of edu­ca­tion for col­lege stu­dents would be pushed up even further.”

    copy­right insan­ity intellectual-​​property academic-​​culture librar­i­ans

  • [1106.6037] Black Hole Search with Finite Automata Scat­tered in a Syn­chro­nous Torus

    “We con­sider the prob­lem of locat­ing a black hole in syn­chro­nous anony­mous net­works using finite state agents. A black hole is a harm­ful node in the net­work that destroys any agent vis­it­ing that node with­out leav­ing any trace. The objec­tive is to locate the black hole with­out destroy­ing too many agents. This is dif­fi­cult to achieve when the agents are ini­tially scat­tered in the net­work and are unaware of the loca­tion of each other. Pre­vi­ous stud­ies for black hole search used more pow­er­ful mod­els where the agents had non-​​constant mem­ory, were labelled with dis­tinct iden­ti­fiers and could either write mes­sages on the nodes of the net­work or mark the edges of the net­work. In con­trast, we solve the prob­lem using a small team of finite-​​state agents each car­ry­ing a con­stant num­ber of iden­ti­cal tokens that could be placed on the nodes of the net­work. Thus, all resources used in our algo­rithms are inde­pen­dent of the net­work size. We restrict our atten­tion to ori­ented torus net­works and first show that no finite team of finite state agents can solve the prob­lem in such net­works, when the tokens are not mov­able. In case the agents are equipped with mov­able tokens, we deter­mine lower bounds on the num­ber of agents and tokens required for solv­ing the prob­lem in torus net­works of arbi­trary size. Fur­ther, we present a deter­min­is­tic solu­tion to the black hole search prob­lem for ori­ented torus net­works, using the min­i­mum num­ber of agents and tokens.”

    algo­rithms agent-​​based multi-​​agent-​​systems network-​​theory nudge-​​targets

  • [1106.1821] Col­lec­tive Intel­li­gence, Data Rout­ing and Braess’ Paradox

    “We con­sider the prob­lem of design­ing the the util­ity func­tions of the utility-​​maximizing agents in a multi-​​agent sys­tem so that they work syn­er­gis­ti­cally to max­i­mize a global util­ity. The par­tic­u­lar prob­lem domain we explore is the con­trol of net­work rout­ing by plac­ing agents on all the routers in the net­work. Con­ven­tional approaches to this task have the agents all use the Ideal Short­est Path rout­ing Algo­rithm (ISPA). We demon­strate that in many cases, due to the side-​​effects of one agent’s actions on another agent’s per­for­mance, hav­ing agents use ISPA’s is sub­op­ti­mal as far as global aggre­gate cost is con­cerned, even when they are only used to route infin­i­tes­i­mally small amounts of traf­fic. The util­ity func­tions of the indi­vid­ual agents are not “aligned” with the global util­ity, intu­itively speak­ing. As a par­tic­u­lar exam­ple of this we present an instance of Braess’ para­dox in which adding new links to a net­work whose agents all use the ISPA results in a decrease in over­all through­put. We also demon­strate that load-​​balancing, in which the agents’ deci­sions are col­lec­tively made to opti­mize the global cost incurred by all traf­fic cur­rently being routed, is sub­op­ti­mal as far as global cost aver­aged across time is con­cerned. This is also due to ‘side-​​effects’, in this case of cur­rent rout­ing deci­sion on future traf­fic. The math­e­mat­ics of Col­lec­tive Intel­li­gence (COIN) is con­cerned pre­cisely with the issue of avoid­ing such dele­te­ri­ous side-​​effects in multi-​​agent sys­tems, both over time and space. We present key con­cepts from that math­e­mat­ics and use them to derive an algo­rithm whose ideal ver­sion should have bet­ter per­for­mance than that of hav­ing all agents use the ISPA, even in the infin­i­tes­i­mal limit. We present exper­i­ments ver­i­fy­ing this, and also show­ing that a machine-​​learning-​​based ver­sion of this COIN algo­rithm in which costs are only impre­cisely esti­mated via empir­i­cal means (a ver­sion poten­tially applic­a­ble in the real world) also out­per­forms the ISPA, despite hav­ing access to less infor­ma­tion than does the ISPA. In par­tic­u­lar, this COIN algo­rithm almost always avoids Braess’ paradox.”

    collective-​​intelligence search-​​algorithms figure-​​ground-​​error plan­ning nudge

  • [1108.0404] Exploit­ing Agent and Type Inde­pen­dence in Col­lab­o­ra­tive Graph­i­cal Bayesian Games

    “Effi­cient col­lab­o­ra­tive deci­sion mak­ing is an impor­tant chal­lenge for mul­ti­a­gent sys­tems. Find­ing opti­mal joint actions is espe­cially chal­leng­ing when each agent has only imper­fect infor­ma­tion about the state of its envi­ron­ment. Such prob­lems can be mod­eled as col­lab­o­ra­tive Bayesian games in which each agent receives pri­vate infor­ma­tion in the form of its type. How­ever, rep­re­sent­ing and solv­ing such games requires space and com­pu­ta­tion time expo­nen­tial in the num­ber of agents. This arti­cle intro­duces col­lab­o­ra­tive graph­i­cal Bayesian games (CGBGs), which facil­i­tate more effi­cient col­lab­o­ra­tive deci­sion mak­ing by decom­pos­ing the global pay­off func­tion as the sum of local pay­off func­tions that depend on only a few agents. We pro­pose a frame­work for the effi­cient solu­tion of CGBGs based on the insight that they posses two dif­fer­ent types of inde­pen­dence, which we call agent inde­pen­dence and type inde­pen­dence. In par­tic­u­lar, we present a fac­tor graph rep­re­sen­ta­tion that cap­tures both forms of inde­pen­dence and thus enables effi­cient solu­tions. In addi­tion, we show how this rep­re­sen­ta­tion can pro­vide lever­age in sequen­tial tasks by using it to con­struct a novel method for decen­tral­ized par­tially observ­able Markov deci­sion processes. Exper­i­men­tal results in both ran­dom and bench­mark tasks demon­strate the improved scal­a­bil­ity of our meth­ods com­pared to sev­eral exist­ing alternatives.”

    col­lab­o­ra­tion agent-​​based complex-​​systems emergent-​​design nudge-​​targets

  • [1102.2837] Effi­cient Pro­mo­tion Strate­gies in Hier­ar­chi­cal Organizations

    “The Peter prin­ci­ple has been recently inves­ti­gated by means of an agent-​​based sim­u­la­tion and its valid­ity has been numer­i­cally cor­rob­o­rated. It has been con­firmed that, within cer­tain con­di­tions, it can really influ­ence in a neg­a­tive way the effi­ciency of a pyra­mi­dal orga­ni­za­tion adopt­ing mer­i­to­cratic pro­mo­tions. It was also found that, in order to bypass these effects, alter­na­tive pro­mo­tion strate­gies should be adopted, as for exam­ple a ran­dom selec­tion choice. In this paper, within the same line of research, we study pro­mo­tion strate­gies in a more real­is­tic hier­ar­chi­cal and mod­u­lar orga­ni­za­tion and we show the robust­ness of our pre­vi­ous results, extend­ing their valid­ity to a more gen­eral con­text. We dis­cuss also why the adop­tion of these strate­gies could be use­ful for real organizations.”

    organizational-​​behavior com­plex­ol­ogy complexological-​​amusements agent-​​based com­pe­tence